一字棋實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)?zāi)康模豪斫夂驼莆詹┺臉涞膯l(fā)式搜索過程學(xué)習(xí)極大極小搜索α–β剪枝能夠用選定的編程語言設(shè)計(jì)簡單的博弈游戲?qū)嶒?yàn)環(huán)境及工具硬件環(huán)境：網(wǎng)絡(luò)環(huán)境中的微型計(jì)算機(jī)軟件環(huán)境：Windows操作系統(tǒng)，VC++語言實(shí)驗(yàn)原理1.游戲規(guī)則“一字棋”游戲（又叫“三子棋”或“井字棋”），是一款十分經(jīng)典的益智小游戲?！熬制濉钡钠灞P很簡單，是一個(gè)3×3的格子，很像中國文字中的“井”字，所以得名“井字棋”?！熬制濉庇螒虻囊?guī)則與“五子棋”十分類似，“五子棋”的規(guī)則是一方首先五子連成一線就勝利；“井字棋”是一方首先三子連成一線就勝利。2.井字棋（英文名Tic-Tac-Toe）井字棋的出現(xiàn)年代估計(jì)已不可考，西方人認(rèn)為這是由古羅馬人發(fā)明的；但我們中國人認(rèn)為，既然咱們都發(fā)明了圍棋、五子棋，那發(fā)明個(gè)把井字棋自然是不在話下。3.極大極小分析法設(shè)有九個(gè)空格，由MAX，MIN二人對(duì)弈，輪到誰走棋誰就往空格上放一只自己的棋子，誰先使自己的棋子構(gòu)成“三子成一線”(同一行或列或?qū)蔷€全是某人的棋子)，誰就取得了勝利。用圓圈表示MAX，用叉號(hào)代表MIN。比如下圖中就是MAX取勝的棋局。估價(jià)函數(shù)設(shè)棋局為P，估價(jià)函數(shù)為e(P)。(1)若P對(duì)任何一方來說都不是獲勝的位置，則e(P)=e(那些仍為MAX空著的完全的行、列或?qū)蔷€的總數(shù))-e(那些仍為MIN空著的完全的行、列或?qū)蔷€的總數(shù))(2)若P是MAX必勝的棋局，則e(P)＝+∞（實(shí)際上賦了60）。(3)若P是B必勝的棋局，則e(P)＝-∞（實(shí)際上賦了-20）。比如P如下圖示,則e(P)=5-4=14.α–β剪枝算法上述的極小極大分析法，實(shí)際是先生成一棵博弈樹，然后再計(jì)算其倒推值，至使極小極大分析法效率較低。于是在極小極大分析法的基礎(chǔ)上提出了α-β剪枝技術(shù)。α-β剪枝技術(shù)的基本思想或算法是，邊生成博弈樹邊計(jì)算評(píng)估各節(jié)點(diǎn)的倒推值，并且根據(jù)評(píng)估出的倒推值范圍，及時(shí)停止擴(kuò)展那些已無必要再擴(kuò)展的子節(jié)點(diǎn)，即相當(dāng)于剪去了博弈樹上的一些分枝，從而節(jié)約了機(jī)器開銷，提高了搜索效率。具體的剪枝方法如下：(1)對(duì)于一個(gè)與節(jié)點(diǎn)MIN，若能估計(jì)出其倒推值的上確界β，并且這個(gè)β值不大于MIN的父節(jié)點(diǎn)(一定是或節(jié)點(diǎn))的估計(jì)倒推值的下確界α，即α≥β，則就不必再擴(kuò)展該MIN節(jié)點(diǎn)的其余子節(jié)點(diǎn)了(因?yàn)檫@些節(jié)點(diǎn)的估值對(duì)MIN父節(jié)點(diǎn)的倒推值已無任何影響了)。這一過程稱為α剪枝。(2)對(duì)于一個(gè)或節(jié)點(diǎn)MAX，若能估計(jì)出其倒推值的下確界α，并且這個(gè)α值不小于MAX的父節(jié)點(diǎn)(一定是與節(jié)點(diǎn))的估計(jì)倒推值的上確界β，即α≥β，則就不必再擴(kuò)展該MAX節(jié)點(diǎn)的其余子節(jié)點(diǎn)了(因?yàn)檫@些節(jié)點(diǎn)的估值對(duì)MAX父節(jié)點(diǎn)的倒推值已無任何影響了)。這一過程稱為β剪枝。從算法中看到：(1)MAX節(jié)點(diǎn)(包括起始節(jié)點(diǎn))的α值永不減少；(2)MIN節(jié)點(diǎn)(包括起始節(jié)點(diǎn))的β值永不增加。在搜索期間，α和β值的計(jì)算如下：(1)一個(gè)MAX節(jié)點(diǎn)的α值等于其后繼節(jié)點(diǎn)當(dāng)前最大的最終倒推值。(2)一個(gè)MIN節(jié)點(diǎn)的β值等于其后繼節(jié)點(diǎn)當(dāng)前最小的最終倒推值。5.輸贏判斷算法設(shè)計(jì)因?yàn)槊看螌?dǎo)致輸贏的只會(huì)是當(dāng)前放置的棋子,輸贏算法中只需從當(dāng)前點(diǎn)開始掃描判斷是否已經(jīng)形成三子。對(duì)于這個(gè)子的八個(gè)方向判斷是否已經(jīng)形成三子。如果有，則說明有一方勝利，如果沒有則繼續(xù)搜索，直到有一方勝利或者搜索完整個(gè)棋盤。數(shù)據(jù)結(jié)構(gòu)程序流程圖比賽結(jié)束，顯示結(jié)果比賽結(jié)束，顯示結(jié)果顯示棋盤用戶輸入搜索深度選擇玩家或者電腦先電腦先調(diào)用AlphaBata函數(shù)，計(jì)算下一步棋子位置比賽結(jié)束根據(jù)玩家鼠標(biāo)點(diǎn)擊位置下棋比賽結(jié)束YNNYYN主要成員函數(shù)Alpha-Beta剪枝算法//完成功能：根據(jù)輸入棋盤，搜索深度，及其他參數(shù)，給出一個(gè)相應(yīng)的最優(yōu)解，存入result中。//參數(shù)：board:待評(píng)估棋盤//Depth:搜索深度//turn:當(dāng)前是機(jī)器走(MAX結(jié)點(diǎn))還是玩家走(MIN結(jié)點(diǎn))//Alpha:alpha值，第一次調(diào)用默認(rèn)-100//Beta:beta值，第一次調(diào)用默認(rèn)+100//result:輸出結(jié)果//返回：若當(dāng)前點(diǎn)為MAX節(jié)點(diǎn)，則返回alpha值；//若當(dāng)前點(diǎn)為MIN節(jié)點(diǎn)，則返回beta值intCTic_MFCDlg::AlphaBeta(intBoard[],intDepth,intturn,intAlpha,intBeta,int*result)估值函數(shù)//完成功能：根據(jù)輸入棋盤，判斷當(dāng)前棋盤的估值，估價(jià)函數(shù)為課本P129所講：//若是MAX的必勝局，則e=+INFINITY，這里為+60//若是MIN的必勝局，則e=-INFINITY，這里為-20，這樣賦值的原因是機(jī)器若贏了，則不考慮其它因素。//其它情況，棋盤上能使CUMPUTER成三子一線的數(shù)目為e1//棋盤上能使PLAYER成三子一線的數(shù)目為e2，//e1-e2作為最終權(quán)值//參數(shù)：board:待評(píng)估棋盤//返回：評(píng)估結(jié)果intCTic_MFCDlg::evaluate(intboard[])鼠標(biāo)左鍵響應(yīng)//完成功能：鼠標(biāo)左鍵相應(yīng)，在點(diǎn)擊的那格放置玩家棋子，之后再相應(yīng)計(jì)算機(jī)走下一步voidCTic_MFCDlg::OnLButtonDown(UINTnFlags,CPointpoint)Draw系列函數(shù)//完成功能：根據(jù)Chess棋盤數(shù)組畫出棋盤voidCTic_MFCDlg::DrawBoard(CDC*pDC)//完成功能：在棋盤上畫一個(gè)O，電腦voidCTic_MFCDlg::DrawO(CDC*pDC,intPos)//完成功能：在棋盤上畫一個(gè)X，玩家voidCTic_MFCDlg::DrawX(CDC*pDC,intPos)電腦或玩家先開始//完成功能：計(jì)算機(jī)先走voidCTic_MFCDlg::OnStartCom()//完成功能：玩家先走voidCTic_MFCDlg::OnStartPly()判斷勝負(fù)//完成功能：根據(jù)輸入棋盤，判斷當(dāng)前棋盤的結(jié)果，COMPUTER勝？PLAYER勝？平局？//參數(shù)：board:待評(píng)估棋盤//返回：-1表示：尚未結(jié)束//0表示：平局//1表示：PLAYER勝//2表示：COMPUTER勝intCTic_MFCDlg::isWin(intcurPos)實(shí)驗(yàn)內(nèi)容基本功能簡介這里采用C++的MFC完成，總的界面如下，有以下功能：搜索樹深度的設(shè)置；機(jī)器先手或者玩家先手；游戲勝負(fù)或者平局判斷。并且經(jīng)測試，有較好的魯棒性，例如：1．鼠標(biāo)在游戲開始之前或者結(jié)束之后點(diǎn)擊棋盤不會(huì)有相應(yīng)，并會(huì)提示用戶先開始游戲；2．鼠標(biāo)點(diǎn)擊棋盤區(qū)域之外，不會(huì)有相應(yīng)3．搜索深度已經(jīng)設(shè)置區(qū)域4．同一棋盤格子點(diǎn)擊只響應(yīng)一次流程圖估價(jià)函數(shù)Alpha-Beta剪枝函數(shù)