#α-β剪枝實現(xiàn)的一字棋實驗評測報告

1、人工智能大作業(yè) 極大極小算法和- 剪枝實現(xiàn)一字棋學(xué)院：班級：姓名：學(xué)號：輔導(dǎo)老師：日期： 目錄一、實驗?zāi)康?3二、實驗環(huán)境 3三、實驗原理 3游戲規(guī)則 3極小極大分析法 3- 剪枝算法 4輸贏判斷算法設(shè)計 5四、數(shù)據(jù)結(jié)構(gòu) 5程序流程 5主要成員函數(shù) 5估值函數(shù) 5Alpha-Beta 剪枝算法 6判斷勝負 6鼠標左鍵響應(yīng) 6Draw 系列函數(shù) 6COMPUTER or PLAYER 先走 7五、實驗內(nèi)容 7基本功能簡介 7流程圖 .85.2.1 估價函數(shù) 8Alpha-Beta 剪枝 9六、實驗小結(jié) 10七、實驗源代碼 10、實驗?zāi)康?1 學(xué)習(xí)極大極小搜索及 - 剪枝(2 利用學(xué)到的算法實現(xiàn)一

2、字棋。二、實驗環(huán)境(1 硬件環(huán)境：網(wǎng)絡(luò)環(huán)境中的微型計算機。(2 軟件環(huán)境： Windows 操作系統(tǒng)， Microsoft Visual C+ 語言。三、實驗原理游戲規(guī)則一字棋游戲又叫三子棋 或井字棋)，是一款十分經(jīng)典的益智小游戲。 井字棋 的棋盤很簡單，是一個33的格子，很像中國文字中的 井字，所以得名 井字棋 。井字棋 游戲的規(guī)則與 五子棋 十 分類似， 五子棋 的規(guī)則是一方首先五子連成一線就勝利；井字棋 是一方首先三子連成一線就勝利。井字棋 ，誰就取得了勝利。用圓圈表示 MAX ，用叉號代表 MIN 。 比如左圖中就是 MAX 取勝的棋局。 估價函數(shù)定義如下： 設(shè)棋局為 P，估價函數(shù)為

3、e(P。(1 若 P 對任何一方來說都不是獲勝的位置，則e(P=e(那些仍為MAX空著的完全的行、列或?qū)蔷€的總數(shù) -e(那些仍為 MIN 空著的完全的行、列或?qū)蔷€的總數(shù) 2 / 9（2 若 P 是 MAX 必勝的棋局，則 e（P + 若 P 是 B 必勝的棋局，則 e（P - =5-4=1剪枝技術(shù)的基本思想或算法是，邊生成博弈樹邊計算評估各節(jié)點的倒推值，并且根據(jù)評估 出的倒推值范圍，及時停止擴展那些已無必要再擴展的子節(jié)點，即相當于剪去了博弈樹上 的一些分枝，從而節(jié)約了機器開銷，提高了搜索效率。具體的剪枝方法如下：（1 對于一個與節(jié)點 MIN ，若能估計出其倒推值的上確界 ，并且這個 值不大

4、于 MIN 的父節(jié)點 （一定是或節(jié)點 的估計倒推值的下確界，即 ，則就不必再擴展該 MIN節(jié)點的其余子節(jié)點了 （因為這些節(jié)點的估值對MIN父節(jié)點的倒推值已無任何影響了 。這一過程稱為 剪枝。（2 對于一個或節(jié)點 MAX ，若能估計出其倒推值的下確界 ，并且這個 值不小于 MAX 的父節(jié)點 （一定是與節(jié)點 的估計倒推值的上確界 ，即 ，則就不必再擴展該 MAX 節(jié)點的其余子節(jié)點了 （因為這些節(jié)點的估值對 MAX 父節(jié)點的倒推值已無任何影響 了 。這一過程稱為 剪枝。從算法中看到：（1 MAX 節(jié)點（包括起始節(jié)點 的 值永不減少；（2 MIN 節(jié)點（包括起始節(jié)點 的 值永不增加。在搜索期間， 和

5、值的計算如下：（1 一個 MAX 節(jié)點的 值等于其后繼節(jié)點當前最大的最終倒推值。（2 一個 MIN 節(jié)點的 值等于其后繼節(jié)點當前最小的最終倒推值。輸贏判斷算法設(shè)計因為每次導(dǎo)致輸贏的只會是當前放置的棋子 , 輸贏算法中只需從當前點開始掃描判斷是 否已經(jīng)形成三子。對于這個子的八個方向判斷是否已經(jīng)形成三子。如果有，則說明有一方 勝利，如果沒有則繼續(xù)搜索，直到有一方勝利或者搜索完整個棋盤。四、數(shù)據(jù)結(jié)構(gòu)程序流程主要成員函數(shù)估值函數(shù)估價函數(shù)： int CTic_MFCDlg:evaluate(int board 完成功能：根據(jù)輸入棋盤，判斷當前棋盤的估值，估價函數(shù)為前面所講：若是 MAX 的必勝局，則 e

6、 = +INFINITY ，這里為 +60 若是 MIN 的必勝局，則 e = -INFINITY ，這里為 - 20，這樣賦值的原因是機器若贏了，則不考慮其它因素。其它情況，棋盤上能使 CUMPUTER 成三子一線的數(shù)目為 e1 棋盤上能使 PLAYER 成三子一線的數(shù)目為 e2， e1-e2 作為最終權(quán)值參數(shù)： board: 待評估棋盤 返回： 評估結(jié)果Alpha-Beta 剪枝算法AlphaBeta 剪枝主函數(shù)：int CTic_MFCDlg:AlphaBeta(int Board, int Depth, int turn, int Alpha, int Beta, int *resul

7、t 完成功能：根據(jù)輸入棋盤，搜索深度，及其他參數(shù)，給出一個相應(yīng)的最優(yōu)解，存入 result中。 參數(shù)：board :待評估棋盤Depth :搜索深度turn :當前是機器走 (MAX 結(jié)點 還是玩家走 (MIN 結(jié)點 Alpha :alpha 值，第一次調(diào)用默認 -100Beta :beta 值，第一次調(diào)用默認 +100 result : 輸出結(jié)果返回：若當前點為 MAX 節(jié)點，則返回 alpha 值； 若當前點為 MIN 節(jié)點，則返回 beta 值判斷勝負int CTic_MFCDlg:isWin(int curPos 完成功能：根據(jù)輸入棋盤，判斷當前棋盤的結(jié)果， COMPUTER 勝？ P

8、LAYER 勝？平局？參數(shù)：board:待評估棋盤返回：-1 表示：尚未結(jié)束0 表示：平局1 表示： PLAYER 勝2 表示： COMPUTER 勝鼠標左鍵響應(yīng)void CTic_MFCDlg:OnLButtonDown(UINT nFlags, CPoint point 完成功能：鼠標左鍵相應(yīng)，在點擊的那格放置玩家棋子，之后再相應(yīng)計算機走下一步Draw 系列函數(shù)void CTic_MFCDlg:DrawBoard(CDC *pDC 完成功能：根據(jù) Chess 棋盤數(shù)組 畫出棋盤void CTic_MFCDlg:DrawO(CDC *pDC, int Pos 完成功能：在棋盤上畫一個 O，電

9、腦void CTic_MFCDlg:DrawX(CDC *pDC, int Pos 完成功能：在棋盤上畫一個X ，玩家COMPUTER or PLAYER先 走void CTic_MFCDlg:OnStartCom( 完成功能：計算機先走 void CTic_MFCDlg:OnStartPly( 完成功能：玩家先走五、實驗內(nèi)容5.1 基本功能簡介本實驗的界面采用 C+ 的 MFC 完成，總的界面如下，有以下功能：搜索樹深度的設(shè)置；機器先走或者玩家先走；游戲勝負或者平局判斷。4鼠標在游戲開始之前或者結(jié)束之后點擊棋盤不會有相應(yīng)，并會提示用戶先開始游戲5鼠標點擊棋盤區(qū)域之外，不會有相應(yīng)6搜索深度已經(jīng)設(shè)置區(qū)域7同一棋盤格子點擊只響應(yīng)一次這里需要說明的是，搜索深度 并非越深越好，局限于估值函數(shù)是 根據(jù)能夠成三子一線的數(shù)目決定的 ，所以搜索到最后一層，如果有人 勝，則出現(xiàn) ，如果沒人勝，則 三子一線數(shù)目為 0，所以毫無意義。如果搜索深度取 到4 或者以上，會發(fā)現(xiàn)電腦會走出一些 很 笨的棋，就是這個原因。經(jīng)測試發(fā)現(xiàn)，搜索深度為 2時效果最好，這也是我為什么默認值取2 的原因。5.2 流程圖 .5