基于牛角棋的博弈電路系統(tǒng)設(shè)計(jì)

preTable是三維的預(yù)置表，其中的兩個(gè)高維度分別代表了2個(gè)條件：
(1)棋子的顏色是什么；
(2)棋子處在什么位置上。
在明確上述兩個(gè)條件的具體值之后，就可以獲得全部可行著法的列表。由于預(yù)置表是頻繁訪問的數(shù)據(jù)，所以，預(yù)置表占用的空間不應(yīng)太大，而且執(zhí)行時(shí)應(yīng)以能夠載入內(nèi)存為宜，所以針對(duì)具體棋類還須因地制宜地采用一些技巧。
1．3 搜索控制
在解決機(jī)器博弈問題中，搜索是機(jī)器博弈的核心，他控制著系統(tǒng)各個(gè)模塊的調(diào)用，他效率的高低直接影響搜索的速度，是決定整個(gè)博弈系統(tǒng)棋力高低的首要因素。
首先，他調(diào)用招法生成模塊，對(duì)當(dāng)前局面產(chǎn)生所有可能的招法并將產(chǎn)生的招法保存到招法列表中。然后，判斷當(dāng)前局面是否有獲勝方，如果有獲勝方返回當(dāng)前局面的估值；否則再判斷是否是葉子節(jié)點(diǎn)，如果是葉子節(jié)點(diǎn)，調(diào)用估值模塊對(duì)當(dāng)前局面進(jìn)行估值并將其返回；如果不是葉子節(jié)點(diǎn)則按照當(dāng)前招法走一步棋并且調(diào)用自身將剛生成的節(jié)點(diǎn)展開，此過程一直持續(xù)下去直到分出勝負(fù)或者搜索到葉子節(jié)點(diǎn)。接著，按照走法將當(dāng)前局面撤銷，退到?jīng)]有走棋時(shí)的局面。然后判斷是否需要剪枝。以上過程反復(fù)執(zhí)行，將龐大的博弈樹一層一層展開以搜索最佳招法，并將其輸出。
在NiosⅡ系統(tǒng)中，使用遞歸調(diào)用的方式來實(shí)現(xiàn)搜索算法，使用負(fù)極大值算法(Negamax algorithm)，并且采用固定深度的深度優(yōu)先搜索，同時(shí)配合α-β剪枝技術(shù)來搜索最佳招法。
1．4 局面評(píng)估
對(duì)葉子結(jié)點(diǎn)所對(duì)應(yīng)的局面打分是估值函數(shù)的職責(zé)，通過對(duì)局面的量化值來表示局面的好壞，而博弈樹的其他節(jié)點(diǎn)的值則通過算法從葉子節(jié)點(diǎn)返回得到。函數(shù)的輸入是待評(píng)估的函數(shù)，輸出是一個(gè)數(shù)值。
博弈樹的葉子結(jié)點(diǎn)是需要調(diào)用估值函數(shù)加以估值的結(jié)點(diǎn)。而博弈樹的中間結(jié)點(diǎn)和根節(jié)點(diǎn)的分值，均可利用極大極小原理從葉子節(jié)點(diǎn)的取值倒推出來。除了殘局階段，搜索樹中的大部分葉子結(jié)點(diǎn)，都是未分勝負(fù)的結(jié)點(diǎn)，需要估值函數(shù)對(duì)該局面做出評(píng)價(jià)，并以數(shù)值的形式反映優(yōu)劣程度。一般地，將所有特征的取值的加權(quán)和作為估值函數(shù)值。局面p的估值函數(shù)V(p)，一般形式如下：

式中：fi表示特征；wi表示權(quán)值。
需要注意到是，對(duì)于負(fù)極大值算法中葉子節(jié)點(diǎn)的估值必須對(duì)那一方走棋敏感，評(píng)估模塊設(shè)置使能信號(hào)，在搜索狀態(tài)機(jī)發(fā)出評(píng)估使能信號(hào)后，評(píng)估模塊立即對(duì)當(dāng)前局面進(jìn)行評(píng)估并在一定的延時(shí)后返回局面的評(píng)估值。如果評(píng)估使能信號(hào)無效，評(píng)估模塊的輸出保持在高阻態(tài)，不對(duì)局面進(jìn)行評(píng)估。