牛角棋博弈程序分析與設計課件

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

1、牛角棋博弈程序分析與設計徐心和徐長明東北大學機器博弈研究室2009.5東北大學機器博弈研究室東北大學機器博弈研究室主要內(nèi)容民間棋類計算機博弈計算機該如何實現(xiàn)博弈過程的？—如何存儲思維信息？—如何判斷局面的勝負？—如何展開博弈樹？—如何選擇當前的著法？從極大極小搜索到負極大值Alpha-bete搜索計算機引擎程序的編寫（C）用C++編寫牛角棋程序算法優(yōu)化東北大學機器博弈研究室民間棋類計算機博弈民間棋類的特點規(guī)則簡單，很容易入門；不受專業(yè)知識限制；棋盤小，棋子少，復雜度不高；輸贏容易識別，局面容易判斷；完全信息，編程相對簡單；人工智能的“果蠅”。麻雀雖小，五臟俱

2、全從一個實例出發(fā)——牛角棋最簡單的機器博弈項目——機器博弈入門課東北大學機器博弈研究室牛角棋牛角棋廣泛見于各地，別名較多，如憋死牛、憋死井、娃娃下山、娘子下山等。棋盤形狀及棋位數(shù)目也稍有差異。但是棋子、棋規(guī)都相同。東北大學機器博弈研究室牛角棋棋規(guī)紅子可上可下，可左可右，一次一步，只能走向空位，不得重合與跳躍；藍子只上不下，可左可右，一次一步，只能走向空位，不得重合與跳躍；勝負判斷：憋死憋不死？東北大學機器博弈研究室紅先紅勝(7步)東北大學機器博弈研究室紅先藍勝(18步)為什么輸贏？需要不斷地摸索經(jīng)驗，試驗所有的局面。東北大學機器博弈研究室博弈思維過程展開博

3、弈樹紅方走棋紅方走棋藍方走棋紅方先手東北大學機器博弈研究室現(xiàn)在要考慮的就是計算機該如何實現(xiàn)這個博弈過程？如何存儲思維信息？棋盤、棋子、棋局、博弈樹如何判斷局面的勝負？如何展開博弈樹？如何選擇當前的著法？東北大學機器博弈研究室如何存儲思維信息？編碼——數(shù)據(jù)結(jié)構(gòu)棋盤編碼（棋位編碼）棋子編碼初始局面的表示棋位向量：(100000023)棋子向量：(089)2034567891１２３東北大學機器博弈研究室棋局演化的形式化描述狀態(tài)變量棋子向量表示初始狀態(tài)狀態(tài)演化方程其中為棋子i第n+1步的著法（算子）著法規(guī)則：紅子可上可下，可左可右，一次一步，只能走向空位，不得重合

4、與跳躍；藍子只上不下，可左可右，一次一步，只能走向空位，不得重合與跳躍；東北大學機器博弈研究室著法的形式化描述通過掃描棋盤，如果“落址”為空位，便是合法著法（算子）。2034567891東北大學機器博弈研究室如何判斷局面的勝負？紅勝：“逃出”——藍勝：“憋死”——和棋——局面的無限次重復2034567891東北大學機器博弈研究室如何展開博弈樹？紅方走棋紅方走棋藍方走棋紅方先手東北大學機器博弈研究室牛角棋搜索引擎程序設計深度優(yōu)先搜索選擇深度優(yōu)先搜索方法，可以在搜索過程中的任何時候僅僅生成（Makemove）整棵樹的一小部分，搜索過的部分被立即刪去（Unmak

5、emove）。顯然，這個算法對內(nèi)存的要求極低，往往在內(nèi)存只有幾千字節(jié)的機器上也可以實現(xiàn)。并且同其他的選擇相比，速度上也并不遜色。東北大學機器博弈研究室如何選擇當前的著法？在展開的博弈樹中搜索——博弈搜索引擎基本原則：考慮到對手的存在我們想到的內(nèi)容，對手也一樣能想到對手會阻止我們達到目的而且，對手會想盡方法使其利益最大化如果是我方（紅方）走棋，那總要找到博弈樹中最好的棋局，而在考慮對方（藍方）走棋時，就要考慮最壞的局面，因為雙方都是理智的博弈者，不應該抱有任何僥幸的心理。如果給每個棋局打分，那紅方可以稱得上是MAX方，藍方便是MIN方。基本方法：博弈樹搜索（M

6、ax-Min,α-β,負極大值α-β）東北大學機器博弈研究室深度為3的博弈樹局面（取極大值）局面（取極小值）著法RootRootMovesLeavesPly=0Ply=1Ply=2Ply=3Depth=3Depth=2Depth=1Depth=0圖例：深度層數(shù)東北大學機器博弈研究室負極大值形式的Alpha-beta搜索Alpha的含義：當前方已經(jīng)存在某個著法，其估值至少為Alpha。Alpha為最佳著法的下界；Beta的含義：對手存在某個著法，令當前方的著法的估值無論如何也超不過Beta。Beta為最佳著法的上界；負極大值形式的Alpha-beta剪枝只有B

7、eta剪枝。東北大學機器博弈研究室人機對弈信息流程棋局演化棋手界面引擎著法著法著法著法局面局面局面局面思考思考思考計算計算著法局面計算東北大學機器博弈研究室Human’sMove人機界面（CHI）界面更新，勝負判定搜索引擎（遞歸BEITA-剪枝）MoveGenerationMake/UnmakeMoveEvaluation數(shù)據(jù)結(jié)構(gòu)：棋子棋盤表示棋局序列，著法列表RootMove牛角棋軟件結(jié)構(gòu)軟件部分東北大學機器博弈研究室計算引擎程序的編寫首先需要解決的算法分析與設計然后考慮算法的實現(xiàn)與編程（編程語言，設計，編碼，調(diào)試）遵照軟件工程學的思想在程序設

8、計方法學上下功夫?qū)W習人工智能的先進理論與技術(shù)——這是