人工智能實驗二-博弈樹井字棋-實驗報告

6/6人工智能實驗二博弈樹井字棋實驗報告姓名：舒吉克班級：545007學號：1000000000目錄一、 實驗環(huán)境 2二、 實驗目的 2三、 實驗內(nèi)容 2四、 實驗步驟 2（1） 博弈樹搜索算法 2（2） 估價函數(shù) 2（3） 數(shù)據(jù)結構 2五、 實驗結果 2實驗環(huán)境操作系統(tǒng)：WIN7編譯環(huán)境：Codeblocks13.12語言：C++實驗目的用博弈樹算法實現(xiàn)井字棋游戲。實驗內(nèi)容用博弈樹算法實現(xiàn)井字棋游戲。井字棋游戲是一種簡單的棋類游戲，在3*3的棋盤上，兩人輪流下子，誰的棋子先連成3顆一條直線，誰就贏了，可以橫著、豎著、斜著。博弈樹算法是用搜索來解決這類問題的算法，井字棋游戲步數(shù)較少，很容易用博弈樹算法實現(xiàn)AI。實驗步驟博弈樹搜索算法博弈樹搜索算法是搜索算法的一種，用深搜來遍歷所有的下子情況，利用一種叫做MIN-MAX的策略，就是對每種棋盤情況有一個估價函數(shù)，對A方有利就是正數(shù)，對B方有利就是負數(shù)。A方行動時，必然走使棋盤的估價函數(shù)最大的那一步，也就是MAX；而B方行動時，必然走使估價函數(shù)變得最小，也就是MIN的一步。博弈樹搜索時，會假設雙方都足夠聰明，每次都先試著走完所有的可能，然后讓當前行動人走對自己最有利的那一步。最后，得到AI當前所需走的這一步到底走哪步，讓AI走出這一步。估價函數(shù)估價函數(shù)是博弈樹算法重要的一部分。我設計的估價函數(shù)，是某一方已經(jīng)連三了（也就是已經(jīng)勝利了），就直接返回1000或-1000。若在某一行、某一列、某一斜線（一共有三行、三列、兩條斜線），每有兩個A方的棋和一個空格，則估價+50，每有一個A方的棋和兩個空格，則估價+10；B方的也類似。這樣，就能把雙方的勝負、優(yōu)劣勢情況用估價函數(shù)表示出來。數(shù)據(jù)結構沒有用太復雜的數(shù)據(jù)結構，用結構體中的3*3數(shù)組存儲棋盤，用vector來存儲某一情況電腦可以走的各種選擇，這樣電腦能在有多種估價函數(shù)相同的選擇的時候能隨機從中選一個。實驗結果測試的結果：程序無論先后手都根本不會輸，玩家有失誤的話它能贏。運行截圖：1.開始可以選擇先后手：2.我按了0，選擇了先手。電腦在對局途中都會說出我設定好的語句，來表明它用博弈樹算法得到的對局勢的分析。如我下在了中間的1,1位置，電腦用博弈樹算法，可以得知走四個角才不會輸，走其他的四個點必輸，所以如下圖進行了判斷，然后隨便選了一個角下棋。3.我第三手下載了左邊中間的1,0位置，電腦能判斷出它不堵我我就贏了（出了1,2之外的位置的估價數(shù)值都為1000，也就是玩家會獲勝，所以它只有走1,2，才能避免必輸?shù)那闆r）。4.我下錯了一步棋，電腦能通過博弈樹算法得知它走這一步他就贏了，然后他贏了。之后可以選擇重新開始或者退出。6.玩家選擇后手的話，AI會判斷出它先手走哪步其實都不是必贏，假設玩家足夠聰明（這也是博弈樹算法的一部分，會假設雙方足夠聰明，每步都走最好的位置），AI先手走哪個位置其實都是一樣的。7.玩家后手走一般要走中間，而我選擇下了一個無關的角，這是必輸?shù)淖叻?，?/p>