基于牛角棋的博弈電路系統設計
1.2.2 招法的形式化描述
用


式中qn+1為第n+1時(shí)刻的招法。
由于紅子走子方向不受限制,可上可下,可橫走,只能走向空位,不得跳躍。所以紅方棋子可以表述為:

藍方的棋子走棋方向受到限制,只能上不能下,可以橫走,只能走向空位,不得跳躍。故藍方的兩枚棋子可以描述為:

1.2.3 預置表招法生成
預置表可看作一個(gè)可快速檢索到滿(mǎn)足某些簡(jiǎn)單條件的、預先生成的招法列表的知識庫。
對照圖2棋盤(pán)的編碼方式,參照牛角棋的規則,一種預置招法表的設計方案如圖3所示。本文引用地址:http://dyxdggzs.com/article/175910.htm
preTable是三維的預置表,其中的兩個(gè)高維度分別代表了2個(gè)條件:
(1)棋子的顏色是什么;
(2)棋子處在什么位置上。
在明確上述兩個(gè)條件的具體值之后,就可以獲得全部可行著(zhù)法的列表。由于預置表是頻繁訪(fǎng)問(wèn)的數據,所以,預置表占用的空間不應太大,而且執行時(shí)應以能夠載入內存為宜,所以針對具體棋類(lèi)還須因地制宜地采用一些技巧。
1.3 搜索控制
在解決機器博弈問(wèn)題中,搜索是機器博弈的核心,他控制著(zhù)系統各個(gè)模塊的調用,他效率的高低直接影響搜索的速度,是決定整個(gè)博弈系統棋力高低的首要因素。
首先,他調用招法生成模塊,對當前局面產(chǎn)生所有可能的招法并將產(chǎn)生的招法保存到招法列表中。然后,判斷當前局面是否有獲勝方,如果有獲勝方返回當前局面的估值;否則再判斷是否是葉子節點(diǎn),如果是葉子節點(diǎn),調用估值模塊對當前局面進(jìn)行估值并將其返回;如果不是葉子節點(diǎn)則按照當前招法走一步棋并且調用自身將剛生成的節點(diǎn)展開(kāi),此過(guò)程一直持續下去直到分出勝負或者搜索到葉子節點(diǎn)。接著(zhù),按照走法將當前局面撤銷(xiāo),退到?jīng)]有走棋時(shí)的局面。然后判斷是否需要剪枝。以上過(guò)程反復執行,將龐大的博弈樹(shù)一層一層展開(kāi)以搜索最佳招法,并將其輸出。
在NiosⅡ系統中,使用遞歸調用的方式來(lái)實(shí)現搜索算法,使用負極大值算法(Negamax algorithm),并且采用固定深度的深度優(yōu)先搜索,同時(shí)配合α-β剪枝技術(shù)來(lái)搜索最佳招法。
1.4 局面評估
對葉子結點(diǎn)所對應的局面打分是估值函數的職責,通過(guò)對局面的量化值來(lái)表示局面的好壞,而博弈樹(shù)的其他節點(diǎn)的值則通過(guò)算法從葉子節點(diǎn)返回得到。函數的輸入是待評估的函數,輸出是一個(gè)數值。
博弈樹(shù)的葉子結點(diǎn)是需要調用估值函數加以估值的結點(diǎn)。而博弈樹(shù)的中間結點(diǎn)和根節點(diǎn)的分值,均可利用極大極小原理從葉子節點(diǎn)的取值倒推出來(lái)。除了殘局階段,搜索樹(shù)中的大部分葉子結點(diǎn),都是未分勝負的結點(diǎn),需要估值函數對該局面做出評價(jià),并以數值的形式反映優(yōu)劣程度。一般地,將所有特征的取值的加權和作為估值函數值。局面p的估值函數V(p),一般形式如下:
式中:fi表示特征;wi表示權值。
需要注意到是,對于負極大值算法中葉子節點(diǎn)的估值必須對那一方走棋敏感,評估模塊設置使能信號,在搜索狀態(tài)機發(fā)出評估使能信號后,評估模塊立即對當前局面進(jìn)行評估并在一定的延時(shí)后返回局面的評估值。如果評估使能信號無(wú)效,評估模塊的輸出保持在高阻態(tài),不對局面進(jìn)行評估。
評論