牛角棋博弈程序設(shè)計(jì)

《牛角棋博弈程序設(shè)計(jì)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、牛角棋博弈程序設(shè)計(jì)徐心和徐長(zhǎng)明東北大學(xué)機(jī)器博弈研究室2009.5東北大學(xué)機(jī)器博弈研究室民間棋類計(jì)算機(jī)博弈民間棋類的特點(diǎn)規(guī)則簡(jiǎn)單，很容易入門；不受專業(yè)知識(shí)限制；棋盤小，棋子少，復(fù)雜度不高；輸贏容易識(shí)別，局面容易判斷；完全信息，編程相對(duì)簡(jiǎn)單；人工智能的“果蠅”。麻雀雖小，五臟俱全從一個(gè)實(shí)例出發(fā)——牛角棋最簡(jiǎn)單的機(jī)器博弈項(xiàng)目——機(jī)器博弈入門課東北大學(xué)機(jī)器博弈研究室牛角棋牛角棋廣泛見(jiàn)于各地，別名較多，如憋死牛、憋死井、娃娃下山、娘子下山等。棋盤形狀及棋位數(shù)目也稍有差異。但是棋子、棋規(guī)都相同。東北大學(xué)機(jī)器博弈研究室牛角棋棋規(guī)紅子可上可下

2、，可左可右，一次一步，只能走向空位，不得重合與跳躍；藍(lán)子只上不下，可左可右，一次一步，只能走向空位，不得重合與跳躍；勝負(fù)判斷：憋死憋不死？東北大學(xué)機(jī)器博弈研究室紅先紅勝(7步)東北大學(xué)機(jī)器博弈研究室紅先藍(lán)勝(18步)為什么輸贏？需要不斷地摸索經(jīng)驗(yàn)，試驗(yàn)所有的局面。東北大學(xué)機(jī)器博弈研究室博弈思維過(guò)程展開(kāi)博弈樹(shù)紅方走棋紅方走棋藍(lán)方走棋紅方先手東北大學(xué)機(jī)器博弈研究室現(xiàn)在要考慮的就是計(jì)算機(jī)該如何實(shí)現(xiàn)這個(gè)博弈過(guò)程？如何存儲(chǔ)思維信息？棋盤、棋子、棋局、博弈樹(shù)如何判斷局面的勝負(fù)？如何展開(kāi)博弈樹(shù)？如何選擇當(dāng)前的著法？東北大學(xué)機(jī)器博弈研究室

3、如何存儲(chǔ)思維信息？編碼——數(shù)據(jù)結(jié)構(gòu)棋盤編碼（棋位編碼）棋子編碼初始局面的表示棋位向量：(100000023)棋子向量：(089)2034567891１２３東北大學(xué)機(jī)器博弈研究室棋局演化的形式化描述狀態(tài)變量棋子向量表示初始狀態(tài)狀態(tài)演化方程其中為棋子i第n+1步的著法（算子）著法規(guī)則：紅子可上可下，可左可右，一次一步，只能走向空位，不得重合與跳躍；藍(lán)子只上不下，可左可右，一次一步，只能走向空位，不得重合與跳躍；東北大學(xué)機(jī)器博弈研究室著法的形式化描述通過(guò)掃描棋盤，如果“落址”為空位，便是合法著法（算子）。2034567891東北大學(xué)

4、機(jī)器博弈研究室如何判斷局面的勝負(fù)？紅勝：“逃出”——藍(lán)勝：“憋死”——和棋——局面的無(wú)限次重復(fù)2034567891東北大學(xué)機(jī)器博弈研究室如何展開(kāi)博弈樹(shù)？紅方走棋紅方走棋藍(lán)方走棋紅方先手東北大學(xué)機(jī)器博弈研究室如何表示博弈樹(shù)？東北大學(xué)機(jī)器博弈研究室兩種不同的展開(kāi)方式廣度優(yōu)先東北大學(xué)機(jī)器博弈研究室兩種不同的展開(kāi)方式深度優(yōu)先東北大學(xué)機(jī)器博弈研究室廣度優(yōu)先的展開(kāi)與存儲(chǔ)東北大學(xué)機(jī)器博弈研究室深度優(yōu)先的展開(kāi)與存儲(chǔ)東北大學(xué)機(jī)器博弈研究室牛角棋搜索引擎程序設(shè)計(jì)深度優(yōu)先搜索選擇深度優(yōu)先搜索方法，可以在搜索過(guò)程中的任何時(shí)候僅僅生成（Makemov

5、e）整棵樹(shù)的一小部分，搜索過(guò)的部分被立即刪去（Unmakemove）。顯然，這個(gè)算法對(duì)內(nèi)存的要求極低，往往在內(nèi)存只有幾千字節(jié)的機(jī)器上也可以實(shí)現(xiàn)。并且同其他的選擇相比，速度上也并不遜色。東北大學(xué)機(jī)器博弈研究室如何選擇當(dāng)前的著法？在展開(kāi)的博弈樹(shù)中搜索——博弈搜索引擎基本原則：考慮到對(duì)手的存在我們想到的內(nèi)容，對(duì)手也一樣能想到對(duì)手會(huì)阻止我們達(dá)到目的而且，對(duì)手會(huì)想盡方法使其利益最大化如果是我方（紅方）走棋，那總要找到博弈樹(shù)中最好的棋局，而在考慮對(duì)方（藍(lán)方）走棋時(shí)，就要考慮最壞的局面，因?yàn)殡p方都是理智的博弈者，不應(yīng)該抱有任何僥幸的心理。如

6、果給每個(gè)棋局打分，那紅方可以稱得上是MAX方，藍(lán)方便是MIN方?；痉椒ǎ翰┺臉?shù)搜索（Max-Min,α-β,負(fù)極大值α-β）東北大學(xué)機(jī)器博弈研究室深度為3的博弈樹(shù)局面（取極大值）局面（取極小值）著法RootRootMovesLeavesPly=0Ply=1Ply=2Ply=3Depth=3Depth=2Depth=1Depth=0圖例：深度層數(shù)東北大學(xué)機(jī)器博弈研究室MAXMAXMIN1298765433213極大極小搜索找到最佳路徑與最佳著法東北大學(xué)機(jī)器博弈研究室MAXMAXMIN1298765433213從極大極小搜索到負(fù)

7、極大值搜索找到最佳路徑與最佳著法-3-2-1NegaMaxNegaMax東北大學(xué)機(jī)器博弈研究室MAXMAXMIN45682434α（Alpha）剪枝α=4找到最佳路徑與最佳著法α為最佳著法的下界東北大學(xué)機(jī)器博弈研究室β（Beta）剪枝174298MAXMINMIN77由此產(chǎn)生最佳路徑和最佳著法β為最佳著法的上界β=7東北大學(xué)機(jī)器博弈研究室負(fù)極大值形式的Alpha-beta搜索Alpha的含義：當(dāng)前方已經(jīng)存在某個(gè)著法，其估值至少為Alpha。Alpha為最佳著法的下界；Beta的含義：對(duì)手存在某個(gè)著法，令當(dāng)前方的著法的估值無(wú)論如

8、何也超不過(guò)Beta。Beta為最佳著法的上界；負(fù)極大值形式的Alpha-beta剪枝只有Beta剪枝。東北大學(xué)機(jī)器博弈研究室博弈樹(shù)搜索過(guò)程MoveGenerationMakeMoveMoveGenerationMakeMove10Evaluationdepth=01010Un