本文轉(zhuǎn)載至知乎ID:Charles(白露未晞)知乎個(gè)人專欄
下載W3Cschool手機(jī)App,0基礎(chǔ)隨時(shí)隨地學(xué)編程>>戳此了解
導(dǎo)語(yǔ)
本文轉(zhuǎn)載至知乎ID:Charles(白露未晞)知乎個(gè)人專欄
下載W3Cschool手機(jī)App,0基礎(chǔ)隨時(shí)隨地學(xué)編程>>戳此了解
閑來(lái)無(wú)事寫了個(gè)比較愚蠢的AI五子棋。
T_T當(dāng)然你好好和它下,它還是比較機(jī)智的。
讓我們愉快地開始吧~~~
相關(guān)文件
網(wǎng)盤下載鏈接: https://pan.baidu.com/s/1DV09ZdyNMoZF2KoKQ4GH_A
密碼: ujrh
開發(fā)工具
Python版本:3.6.4
相關(guān)模塊:
graphics模塊。
環(huán)境搭建
安裝Python并添加到環(huán)境變量即可。
注:
graphics模塊在相關(guān)文件中已經(jīng)提供,就是一個(gè)py文件,直接放在當(dāng)前路徑或者放到python安裝文件夾下的site-packages文件夾內(nèi)均可。
原理簡(jiǎn)介
對(duì)于五子棋這樣的博弈類AI,很自然的想法就是讓計(jì)算機(jī)把當(dāng)前所有可能的情況都嘗試一遍,找到最優(yōu)的落子點(diǎn)。這里有兩個(gè)問(wèn)題:
(1)如何把所有可能的情況都嘗試一遍;
(2)如何定量判斷某落子點(diǎn)的優(yōu)劣。
對(duì)于第一個(gè)問(wèn)題,其實(shí)就是所謂的博弈樹搜索,對(duì)于第二個(gè)問(wèn)題,其實(shí)就是所謂的選擇評(píng)估函數(shù)。評(píng)估函數(shù)的選取直接決定了AI算法的優(yōu)劣,其形式也千變?nèi)f化。可以說(shuō),每個(gè)評(píng)估函數(shù)就是一個(gè)選手,對(duì)不同的棋型每個(gè)選手自然有不同的看法和應(yīng)對(duì)措施,當(dāng)然他們的棋力也就因此各不相同了。
但博弈樹搜索就比較固定了,其核心思想無(wú)非是讓計(jì)算機(jī)考慮當(dāng)前局勢(shì)下之后N步所有可能的情況,其中奇數(shù)步(因?yàn)楝F(xiàn)在輪到AI下)要讓AI方的得分最大,偶數(shù)步要讓AI方的得分最小(因?yàn)閷?duì)手也就是人類,也可以選擇最優(yōu)策略)。
當(dāng)然這樣的搜索其計(jì)算量是極大的,這時(shí)候就需要剪枝來(lái)減少計(jì)算量。例如下圖:
其中A代表AI方,P代表人類方。AI方搜索最大值,人類方搜索最小值。因此Layer3的A1向下搜索的最終結(jié)果為4,Layer3的A2向下搜索,先搜索Layer4的P3,獲得的分值為6,考慮到Layer2的P1向下搜索時(shí)取Layer3的A1和A2中的較小值,而Layer3的A2搜索完Layer4的P3時(shí),其值就已經(jīng)必大于Layer3的A1了,就沒有搜索下去的必要了,因此Layer3到Layer4的路徑3就可以剪掉了。
上述搜索策略其實(shí)質(zhì)就是:
minimax算法+alpha-beta剪枝算法。
了解了上述原理之后,就可以自己寫代碼實(shí)現(xiàn)了。當(dāng)然實(shí)際實(shí)現(xiàn)過(guò)程中,我做了一些簡(jiǎn)化,但萬(wàn)變不離其宗,其核心思想都是一樣的。
具體實(shí)現(xiàn)過(guò)程詳見相關(guān)文件中的源代碼。
使用演示
在cmd窗口運(yùn)行GobangAI.py文件即可。
下面的視頻是我和AI的一局對(duì)弈,我執(zhí)黑先行,所以贏的比較輕松T_T。畢竟五子棋先手者優(yōu)勢(shì)巨大,或者說(shuō)在某些情況/規(guī)則下是必勝的。至于原因,在相關(guān)文件中提供了兩篇論文,感興趣的可以看看。
更多
之后有時(shí)間的話會(huì)研究一下基于深度學(xué)習(xí)的AI五子棋算法,目前這個(gè)版本還是比較low的,當(dāng)然你好好和它下的話,它還是可以走出一些精妙的步子的。
T_T沒有仔細(xì)測(cè)試,如果有什么bug可以留言反饋給我,我會(huì)進(jìn)行修復(fù)。