資源描述：
《研討班_牛角棋》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
1、牛角棋博弈程序分析與設計徐心和徐長明東北大學信息科學與工程學院2009-01-24東北大學機器博弈研究室民間棋類計算機博弈最簡單的機器博弈項目——機器博弈入門課麻雀雖小，五臟俱全從一個實例出發(fā)——牛角棋東北大學機器博弈研究室民間棋類的特點規(guī)則簡單，很容易入門；不受專業(yè)知識限制；棋盤小，棋子少，復雜度不高；輸贏容易識別，局面容易判斷；完全信息，編程相對簡單；人工智能的“果蠅”。東北大學機器博弈研究室牛角棋牛角棋廣泛見于各地，別名較多，如憋死牛、憋死井、娃娃下山、娘子下山等。棋盤形狀及棋位數(shù)目也稍有差異。但是棋子、棋規(guī)都相同。東北大學機器博弈研究室牛角棋棋規(guī)紅子可
2、上可下，可左可右，一次一步，只能走向空位，不得重合與跳躍；藍子只上不下，可左可右，一次一步，只能走向空位，不得重合與跳躍；勝負判斷：憋死憋不死？東北大學機器博弈研究室紅先紅勝(7步)東北大學機器博弈研究室紅先藍勝(18步)為什么輸贏？需要不斷地摸索經驗，試驗所有的局面。東北大學機器博弈研究室博弈思維過程展開博弈樹紅方走棋紅方走棋藍方走棋紅方先手東北大學機器博弈研究室計算機是如何實現(xiàn)博弈過程的？計算機如何進行博弈思維？如何編寫機器博弈程序？東北大學機器博弈研究室計算機如何進行博弈思維？如何存儲思維信息？棋盤、棋子、棋局、博弈樹如何判斷局面的勝負？如何展開博弈樹？
3、如何選擇當前的著法？如何編寫程序？如何總結博弈的規(guī)律？東北大學機器博弈研究室如何存儲思維信息？編碼——數(shù)據(jù)結構棋盤編碼（棋位編碼）棋子編碼初始局面的表示棋位向量：(100000023)棋子向量：(089)2034567891１２３東北大學機器博弈研究室棋局演化的形式化描述狀態(tài)變量棋子向量表示初始狀態(tài)狀態(tài)演化方程其中為棋子i第n+1步的著法（算子）著法規(guī)則：紅子可上可下，可左可右，一次一步，只能走向空位，不得重合與跳躍；藍子只上不下，可左可右，一次一步，只能走向空位，不得重合與跳躍；東北大學機器博弈研究室著法的形式化描述通過掃描棋盤，如果“落址”為空位，便是合法
4、著法（算子）。2034567891東北大學機器博弈研究室如何判斷局面的勝負？紅勝：“逃出”——藍勝：“憋死”——和棋——局面的無限次重復2034567891東北大學機器博弈研究室如何展開博弈樹？紅方走棋紅方走棋藍方走棋紅方先手東北大學機器博弈研究室如何表示博弈樹？東北大學機器博弈研究室兩種不同的展開方式廣度優(yōu)先東北大學機器博弈研究室兩種不同的展開方式深度優(yōu)先東北大學機器博弈研究室廣度優(yōu)先的展開與存儲東北大學機器博弈研究室深度優(yōu)先的展開與存儲東北大學機器博弈研究室如何選擇當前的著法？在展開的博弈樹中搜索——博弈搜索引擎如果紅方走棋，他總要找到博弈樹中最好的棋局，
5、而在考慮對方（藍方）走棋時，就要考慮最壞的局面，因為雙方都是理智的博弈者，不應該抱有任何僥幸的心理。如果給每個棋局打分，那紅方可以稱得上是MAX方，藍方便是MIN方。東北大學機器博弈研究室深度為3的博弈樹局面（取極大值）局面（取極小值）著法RootRootMovesLeavesPly=0Ply=1Ply=2Ply=3Depth=3Depth=2Depth=1Depth=0圖例：深度層數(shù)東北大學機器博弈研究室MAXMAXMIN1298765433213極大極小搜索找到最佳路徑與最佳著法東北大學機器博弈研究室MAXMAXMIN1298765433213從極大極小搜
6、索到負極大值搜索CurrentbestPVandbestmove-3-2-1NegaMaxNegaMax東北大學機器博弈研究室MAXMAXMIN45682434Alpha剪枝α=4找到最佳路徑與最佳著法東北大學機器博弈研究室β-剪枝（1）174298MAXMINMIN77由此產生最佳路徑和最佳著法β=7東北大學機器博弈研究室β-剪枝（2）835791MAXMINMIN8426由此產生最佳路徑和最佳著法448β=4東北大學機器博弈研究室負極大值形式的Alpha-beta搜索Alpha的含義：當前方已經存在某個著法，其估值至少為alpha；Beta的含義：對手存在
7、著某個著法，令當前方的著法的估值無論如何也超不過beta。負極大值形式的alpha-beta剪枝只有beta剪枝。東北大學機器博弈研究室（alpha，beta）窗口A1A2A3An…（alpha，beta）Value=-Search()If(Value<=alpha)A1A2A3An…（alpha，beta）Value=-Search()負極大值條件下的（alpha，beta）窗口東北大學機器博弈研究室A1A2A3An…returnvalueIf(Value>=beta)A1A2A3An…（alpha，beta）Value=-Search()An（alpha，
8、beta）窗口東北大學機器博弈研究室博
