[2018年最新整理]實(shí)驗(yàn)二：利用α-β搜索過(guò)程的博弈樹(shù)搜索算法編寫(xiě)一字棋游戲

實(shí)驗(yàn)二：利用α-β搜索過(guò)程的博弈樹(shù)搜索算法編寫(xiě)一字棋游戲

一、實(shí)驗(yàn)?zāi)康呐c要求

(1)了解極大極小算法的原理和使用方法，并學(xué)會(huì)用α-β剪枝來(lái)提高算法的效率。

(2)使用C語(yǔ)言平臺(tái)，編寫(xiě)一個(gè)智能井字棋游戲。

(3)結(jié)合極大極小算法的使用方法和α-β剪枝，讓機(jī)器與人對(duì)弈時(shí)不但有智能的特征，而且計(jì)算的效率也比較高。

二、實(shí)驗(yàn)原理

一字棋游戲是一個(gè)流傳已久的傳統(tǒng)游戲。游戲由兩個(gè)人輪流來(lái)下，分別用“X”和“O”來(lái)代替自身的棋子。棋盤(pán)分9個(gè)格，雙方可以在輪到自己下的時(shí)候，可以用棋子占領(lǐng)其中一個(gè)空的格子。如果雙方中有一方的棋子可以連成一條直線，則這一方判勝，對(duì)方判負(fù)。當(dāng)所有的格子都被占領(lǐng)，但雙方都無(wú)法使棋子連成一條直線的話，則判和棋。

這是一個(gè)智能型的一字棋游戲，機(jī)器可以模擬人與用戶(hù)對(duì)弈。當(dāng)輪到機(jī)器來(lái)下的時(shí)候，機(jī)器會(huì)根據(jù)當(dāng)前棋局的形勢(shì)，利用極大極小算法算出一個(gè)評(píng)價(jià)值，判斷如何下才對(duì)自身最有利，同時(shí)也是對(duì)方來(lái)說(shuō)對(duì)不利的，然后下在評(píng)價(jià)值最高的地方。另外利用α-β剪枝，使機(jī)器在搜索評(píng)價(jià)值的時(shí)候不用擴(kuò)展不必要的結(jié)點(diǎn)，從而提高機(jī)器計(jì)算的效率。

在用戶(hù)界面方法，用一個(gè)3×3的井字格來(lái)顯示用戶(hù)與機(jī)器下的結(jié)果。當(dāng)要求用戶(hù)輸入數(shù)據(jù)的時(shí)候會(huì)有提示信息。用戶(hù)在下的過(guò)程中可以中途按下“0”退出。當(dāng)用戶(hù)與計(jì)算機(jī)分出了勝負(fù)后，機(jī)器會(huì)顯示出比賽的結(jié)果，并按任意鍵退出。如果用戶(hù)在下棋的過(guò)程中，輸入的是非法字符，機(jī)器不會(huì)做出反應(yīng)。

三、實(shí)驗(yàn)步驟和過(guò)程

1.α-β搜索過(guò)程　　在極小極大搜索方法中，由于要先生成指定深度以?xún)?nèi)的所有節(jié)點(diǎn)，其節(jié)點(diǎn)數(shù)將隨著搜索深度的增加承指數(shù)增長(zhǎng)。這極大地限制了極小極大搜索方法的使用。能否在搜索深度不變的情況下，利用已有的搜索信息減少生成的節(jié)點(diǎn)數(shù)呢？

MINIMAX過(guò)程是把搜索樹(shù)的生成和格局估值這兩個(gè)過(guò)程分開(kāi)來(lái)進(jìn)行，即先生成全部搜索樹(shù)，然后再進(jìn)行端節(jié)點(diǎn)靜態(tài)估值和倒推值計(jì)算，這顯然會(huì)導(dǎo)致低效率。如圖中，其中一個(gè)MIN節(jié)點(diǎn)要全部生成A、B、C、D四個(gè)節(jié)點(diǎn)，然后還要逐個(gè)計(jì)算其靜態(tài)估值，最后在求倒推值階段，才賦給這個(gè)MIN節(jié)點(diǎn)的倒推值－∞。其實(shí)，如果生成節(jié)點(diǎn)A后，馬上進(jìn)行靜態(tài)估值，得知f(A)＝－∞之后，就可以斷定再生成其余節(jié)點(diǎn)及進(jìn)行靜態(tài)計(jì)算是多余的，可以馬上對(duì)MIN節(jié)點(diǎn)賦倒推值－∞，而絲毫不會(huì)影響MAX的最好優(yōu)先走步的選擇。這是一種極端的情況，實(shí)際上把生成和倒推估值結(jié)合起來(lái)進(jìn)行，再根據(jù)一定的條件判定，有可能盡早修剪掉一些無(wú)用的分枝，同樣可獲得類(lèi)似的效果，這就是α-β過(guò)程的基本思想。α-β搜索過(guò)程一字棋的

圖一字棋第一階段α-β剪枝方法為了使生成和估值過(guò)程緊密結(jié)合，采用有界深度優(yōu)先策略進(jìn)行搜索，這樣當(dāng)生成達(dá)到規(guī)定深度的節(jié)點(diǎn)時(shí)，就立即計(jì)算其靜態(tài)估值函數(shù)，而一旦某個(gè)非端節(jié)點(diǎn)有條件確定其倒推值時(shí)就立即計(jì)算賦值。從圖中標(biāo)記的節(jié)點(diǎn)生成順序號(hào)(也表示節(jié)點(diǎn)編號(hào))看出，生成并計(jì)算完第6個(gè)節(jié)點(diǎn)后，第1個(gè)節(jié)點(diǎn)倒推值完全確定，可立即賦給倒推值－1。這時(shí)對(duì)初始節(jié)點(diǎn)來(lái)說(shuō)，雖然其他子節(jié)點(diǎn)尚未生成，但由于s屬極大值層，可以推斷其倒推值不會(huì)小于－1，我們稱(chēng)極大值層的這個(gè)下界值為α，即可以確定s的α＝－1。這說(shuō)明s實(shí)際的倒推值決不會(huì)比－1更小，還取決于其他后繼節(jié)點(diǎn)的倒推值，因此繼續(xù)生成搜索樹(shù)。當(dāng)?shù)?個(gè)節(jié)點(diǎn)生成出來(lái)并計(jì)算得靜態(tài)估值為－1后，就可以斷定第7個(gè)節(jié)點(diǎn)的倒推值不可能大于－1，我們稱(chēng)極小值層的這個(gè)上界值為β，即可確定節(jié)點(diǎn)７的β＝－1。有了極小值層的β值，很容易發(fā)現(xiàn)若α≥β時(shí)，節(jié)點(diǎn)7的其他子節(jié)點(diǎn)不必再生成，這不影響高一層極大值的選取，因s的極大值不可能比這個(gè)β值還小，再生成無(wú)疑是多余的，因此可以進(jìn)行剪枝。這樣一來(lái)，只要在搜索過(guò)程記住倒推值的上下界并進(jìn)行比較，就可以實(shí)現(xiàn)修剪操作，稱(chēng)這種操作為α剪枝。類(lèi)似的還有β剪枝，統(tǒng)稱(chēng)為α-β剪枝技術(shù)。在實(shí)際修剪過(guò)程中，α、β還可以隨時(shí)修正，但極大值層的倒推值下界α永不下降，實(shí)際的倒推值取其后繼節(jié)點(diǎn)最終確定的倒推值中最大的一個(gè)倒推值。而極小值層的倒推值上界β永不上升，其倒推值則取后繼節(jié)點(diǎn)最終確定的倒推值中最小的一個(gè)倒推值。在進(jìn)行α-β剪枝時(shí)，應(yīng)注意以下幾個(gè)問(wèn)題：　　(1)比較都是在極小節(jié)點(diǎn)和極大節(jié)點(diǎn)間進(jìn)行的，極大節(jié)點(diǎn)和極大節(jié)點(diǎn)的比較，或者極小節(jié)點(diǎn)和極小節(jié)點(diǎn)間的比較是無(wú)意義的。　　(2)在比較時(shí)注意是與"先輩層"節(jié)點(diǎn)比較，不只是與父輩節(jié)點(diǎn)比較。當(dāng)然，這里的"先輩層"節(jié)點(diǎn)，指的是那些已經(jīng)有了值的節(jié)點(diǎn)。　　(3)當(dāng)只有一個(gè)節(jié)點(diǎn)的"固定"以后，其值才能夠向其父節(jié)點(diǎn)傳遞。　　(4)α-β剪枝方法搜索得到的最佳走步與極小極大方法得到的結(jié)果是一致的，α-β剪枝并沒(méi)有因?yàn)樘岣咝?#xff0c;而降低得到最佳走步的可能性。　　(5)在實(shí)際搜索時(shí)，并不是先生成指定深度的搜索圖，再在搜索圖上進(jìn)行剪枝。如果這樣，就失去了α-β剪枝方法的意義。在實(shí)際程序?qū)崿F(xiàn)時(shí)，首先規(guī)定一個(gè)搜索深度，然

總結(jié)

以上是生活随笔為你收集整理的c语言编简单博弈小游戏,[2018年最新整理]实验二：利用α-β搜索过程的博弈树搜索算法编写一字棋游戏.doc...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。