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