五子棋ai如何判斷活三
五子棋ai如何判斷活三
五子棋中什么是活三?五子棋ai如何判斷活三?下面學(xué)習(xí)啦小編給你介紹五子棋ai如何判斷活三，歡迎閱讀。
五子棋中什么是活三?
活三：若對(duì)方不進(jìn)行必要防守，本方下一手可取得活四的基本子力形式(包括連活三和跳活三)：①連活三：在一條橫線、豎線或斜線上緊緊相連的同色三子，兩端均有空交叉點(diǎn)，且至少有一端有兩個(gè)或以上的空交叉點(diǎn)(對(duì)于黑方則還需左右相鄰的兩個(gè)交叉點(diǎn)在此三形成的同時(shí)至少有一個(gè)不為禁點(diǎn)，且從兩端向外數(shù)至少在各兩個(gè)交叉點(diǎn)上均無黑子)所構(gòu)成的基本子力形式②跳活三：中間間隔一子的活三 ，且兩端均有空交叉點(diǎn)(對(duì)于黑方則還需在此三形成的同時(shí)中間的空交叉點(diǎn)不為禁點(diǎn)，且從兩端向外數(shù)至少在各兩個(gè)交叉點(diǎn)上均無黑子)所構(gòu)成的基本子力形式。特別的，1、3、5式的中間空出兩個(gè)子的三不叫跳活三，而只能稱為跳三。
五子棋ai如何判斷活三?
第一步，了解禁手規(guī)則
做一個(gè)五子棋的程序，自然對(duì)五子棋需要有足夠的了解，現(xiàn)在默認(rèn)大家現(xiàn)在和我研究五子棋之前了解是一樣多的。以這個(gè)為基礎(chǔ)，介紹多數(shù)人不大熟悉的方面。五子棋的規(guī)則實(shí)際上有兩種：有禁手和無禁手。由于無禁手的規(guī)則比較簡(jiǎn)單，因此被更多人所接受。其實(shí)，對(duì)于專業(yè)下五子棋的人來說，有禁手才是規(guī)則。所以，這里先對(duì)“有禁手”進(jìn)行一下簡(jiǎn)單介紹：
五子棋中“先手必勝”已經(jīng)得到了論證，類似“花月定式”和“浦月定式”，很多先手必勝下法雖然需要大量的記憶，但高手確能做到必勝。所以五子棋的規(guī)則進(jìn)行了優(yōu)化，得到了 “有禁手”五子棋。五子棋中，黑棋必然先行。因此“有禁手”五子棋競(jìng)技中對(duì)黑棋有以下“禁手”限制:“三三禁”:黑棋下子位置同時(shí)形成兩個(gè)以上的三;“四四禁”:黑棋下子位置同時(shí)形成兩個(gè)以上的四;“長(zhǎng)連禁”:六子以上的黑棋連成一線。黑棋如下出“禁手“則馬上輸?shù)羝寰?。不過如果“連五”與“禁手”同時(shí)出現(xiàn)這時(shí)“禁手”是無效的。所以對(duì)于黑棋只有沖四活三(后面會(huì)有解釋)是無解局面。反觀白棋則多了一種獲勝方式，那就是逼迫黑棋必定要下在禁點(diǎn)。
為了迎合所有玩家，五子棋自然需要做出兩個(gè)版本，或者是可以進(jìn)行禁手上的控制。
第二步，實(shí)現(xiàn)游戲界面
這里，我制作了一個(gè)簡(jiǎn)單的界面，但是，對(duì)于人機(jī)對(duì)弈來說，絕對(duì)夠用。和很多網(wǎng)上的精美界面相比，我的界面也許略顯粗糙，但，開發(fā)速度較高，僅用了不到半天時(shí)間。下面我們簡(jiǎn)單看下界面的做法。
界面我采用了WPF，表現(xiàn)層和邏輯層完全分開，前臺(tái)基本可以通過拖拽完成布局，這里就不做過多介紹。根據(jù)界面截圖簡(jiǎn)單介紹
1處實(shí)際上市兩個(gè)漸變Label的拼接，2、3是兩個(gè)label，4、5實(shí)際上是兩個(gè)Button，但是沒有做事件響應(yīng)。通過按鈕6、7、8、9 的控制，修改label和Button的Content屬性。也許有人會(huì)奇怪，為什么Button會(huì)絲毫看出不出有Button的影子，這里戰(zhàn)友whrxiao寫過一個(gè)Style如下
這里我們把這個(gè)Style稱為Style1。界面邏輯上，將是否開始、是否禁手和是否電腦先行作為兩個(gè)全局變量的布爾型值，通過設(shè)置和判斷bool型值進(jìn)行邏輯上的控制。中間的棋盤是個(gè)canvas，一個(gè)15*15的Grid放滿Button并將每個(gè)Button應(yīng)用Style1開始時(shí)候透明度設(shè)為0，也就是根本看不到，在下棋的時(shí)候改變Button的背景和透明度，實(shí)現(xiàn)落子的效果，因?yàn)镚rid的位置關(guān)系，所以可看起來好像是下在橫豎的交線處。
第三步，進(jìn)行輸贏判斷：
因?yàn)橐?guī)則不同，“無禁手”和“有禁手”的輸贏判斷自然不同。先看無禁手：這個(gè)比較簡(jiǎn)單，遍歷每個(gè)位置，然后從這個(gè)位置開始，分別判斷它的四個(gè)方向：即橫、豎、左上到右下、左下到右上。每個(gè)方向從中間點(diǎn)開始，往兩邊數(shù)連子數(shù)，然后將兩個(gè)方向的連字?jǐn)?shù)加和再加一(中間的棋子)。如果得到大于等于5，那么就說明下子方贏棋。
對(duì)于有禁手的五子棋，輸贏判斷還需要判斷禁手，禁手的判定較為復(fù)雜。將待判斷點(diǎn)放入黑棋子。然后搜索待判斷點(diǎn)周邊棋盤;還原棋盤;利用搜索結(jié)果依次對(duì)各方向進(jìn)行分析，判斷黑棋放入后所產(chǎn)生的棋型是否形成長(zhǎng)連或形成某種四連或三連的的棋型。若形成長(zhǎng)連，判定為禁手，返回長(zhǎng)連禁手標(biāo)識(shí)。若形成某種四連或三連的棋型，該棋型統(tǒng)計(jì)數(shù)加1，再對(duì)下一個(gè)方向進(jìn)行判斷，直到各個(gè)方向分析結(jié)束。若四連棋型或三連棋型的統(tǒng)計(jì)數(shù)大于1，則返回為禁手。其余情況返回非禁手。
第四步：構(gòu)造棋型估分
“有禁手”規(guī)則比較復(fù)雜，涉及到比較多下棋方面的技巧，而且對(duì)算法的思路沒有絲毫影響，所以下面我們主要考慮無禁手規(guī)則下的AI設(shè)計(jì)。若設(shè)計(jì)好無禁手AI，只需要讓AI執(zhí)黑時(shí)堅(jiān)決不下到禁手點(diǎn)，就可以很快構(gòu)造有禁手的AI。雖然這種方式?jīng)]有利用有禁手規(guī)則下的技巧，但這些技巧只需要修改下面所講到的估分函數(shù)即可。
我們可以將五子棋的連珠可以分為以下幾種：
成5：即構(gòu)成五子連珠
活4：即構(gòu)成兩邊均不被攔截的四子連珠。
死4：一邊被攔截的四子連珠
活3：兩邊均不被攔截的三字連珠
死3：一邊被攔截的三字連珠
活2：兩邊均不被攔截的二子連珠
死2：一邊被攔截的二子連珠
單子：四周無相連棋子
根據(jù)五子棋的技巧，可以將五子棋的棋型用連珠進(jìn)行分類，分類過后我們按照威力給每種棋型打分。因?yàn)槲遄悠逡淮沃宦湟蛔?，因此很容易理解，雙活三和三活三的威力是一樣的，類似情況不多做解釋。程序中，我以100分為滿分，對(duì)棋型進(jìn)行了以下打分：
成5, 100分
活4、雙死4、死4活3， 90分
雙活3， 80分
死3活3， 70分
死4， 60分
活3， 50分
雙活2， 40分
死3， 30分
活2， 20分
死2， 10分
單子 0分
有了估分方法，就有了五子棋AI的基礎(chǔ)，接下來就是一些博弈的方法了。
第五步：得到位置估分AI
單純應(yīng)用棋譜以及對(duì)五子棋當(dāng)前局勢(shì)的分析，對(duì)每步進(jìn)行估分，程序中做如下工作：將每個(gè)位置進(jìn)行分析，假設(shè)AI落子在該位置，用以上打分規(guī)則為AI打分,并將得到的分?jǐn)?shù)加一。然后，假設(shè)玩家落子在該點(diǎn)，為玩家打分，然后將所有的分值匯總。取最高分作為這個(gè)位置的估分，接下來就是取分?jǐn)?shù)最高的位置下棋了。“位置估分”，下棋的時(shí)候，既可以考慮到自己攻擊對(duì)手，又能考慮到對(duì)對(duì)手的防御，可以說，很多時(shí)候可以頂上考慮兩步的AI。作實(shí)驗(yàn)，從網(wǎng)上下載了一個(gè)用博弈做的AI，和“位置估分”對(duì)下，結(jié)果是一勝一負(fù)。誰先子，誰贏得勝利。而且一步估分毫無疑問是最快的，即使遍歷所有位置，也能很快的做出決策。
第六步：應(yīng)用博弈樹，提高AI智能
做五子棋的博弈，自然會(huì)用到博弈樹，這里我說下自己的思路。在對(duì)弈中,根據(jù)下一步由誰來走,AI對(duì)任何一個(gè)局面根據(jù)前面估分方法給出一個(gè)分?jǐn)?shù),我們把這個(gè)估分方法匯總成一個(gè)評(píng)估函數(shù)，并返回分值。據(jù)此來選擇下一步的走法。由于人和AI是輪流落子，可以將人的估分也算入，并將前面加負(fù)號(hào)。那么，估值越大表明對(duì)AI越有利，估分越小則表明對(duì)AI越不利。那么每次AI選擇都是從它可能的走法樹的某層節(jié)點(diǎn)，返回評(píng)估值中最大點(diǎn)。而用戶總是從走法樹的某層節(jié)點(diǎn)中選擇最小點(diǎn)，從而形成一棵極大極小搜索樹，然后根據(jù)深度優(yōu)先搜索，可以最后得到固定搜索深度下的一個(gè)最好的走法。我做了下試驗(yàn)，單純應(yīng)用博弈樹，可以在100ms之內(nèi)讓AI考慮完整的兩步，由于組合爆炸，當(dāng)需要考慮三步的時(shí)候，就需要6s左右，4步就需要1分鐘。拿兩步來和一步估分作比較，雖然比較慢，但是確實(shí)有了一定智能。
第七步：考慮層數(shù)，提高AI智能
上面的設(shè)計(jì)對(duì)于返回值是統(tǒng)一處理的,但是，層數(shù)是個(gè)很重要的信息.因?yàn)橄缕鍟r(shí)如果能2步獲勝,不應(yīng)選擇4步獲勝。對(duì)于輸?shù)钠逍蛯訑?shù)就更重要,AI必須盡可能拖延輸?shù)臅r(shí)間，就有更大的可能讓AI化險(xiǎn)為夷。這樣，可以通過設(shè)置一個(gè)dep值。深度約淺，dep越大，用dep和得到的得分相乘，得到搜索節(jié)點(diǎn)的得分，再進(jìn)行以上算法，進(jìn)一步提高AI的智能。
第八步：應(yīng)用α-β剪枝，提高AI速度
在搜索博弈樹的過程中，實(shí)際上搜索有很多點(diǎn)是多余的，例如下圖
圖中，方形框節(jié)點(diǎn)是該AI走,圓形框節(jié)點(diǎn)是該人走.比如C節(jié)點(diǎn),它需要從E和F當(dāng)中選取最大的值。目前已經(jīng)得出E為2,當(dāng)搜索F節(jié)點(diǎn)時(shí),因?yàn)镕是人走的節(jié)點(diǎn)，那么F需要從K L M中選取最小的，因?yàn)镵已經(jīng)是1，也就是說F<=1，那么L，M就不需要搜索，因此就發(fā)生了α剪枝。然后看A節(jié)點(diǎn)，該人走了，需要從C和D中選取最小值，因?yàn)镃節(jié)點(diǎn)是2，而G是7，那么D至少是7。因此，D的其他節(jié)點(diǎn)不必再考慮，就發(fā)生如上圖所示的β剪枝?？偨Y(jié)上面規(guī)律，我們可以得到剪枝方法如下：
當(dāng)前為AI下棋節(jié)點(diǎn)：
α剪枝：如果當(dāng)前節(jié)點(diǎn)的值不比父節(jié)點(diǎn)的前兄弟節(jié)點(diǎn)的大值大,則舍棄此節(jié)點(diǎn)。
β剪枝：如果當(dāng)前節(jié)點(diǎn)子節(jié)點(diǎn)的值不比當(dāng)前節(jié)點(diǎn)的前兄弟節(jié)點(diǎn)中的最小值小,則舍棄該子節(jié)點(diǎn)和該子節(jié)點(diǎn)的所有后兄弟節(jié)點(diǎn)。
當(dāng)前為用戶下棋節(jié)點(diǎn)：
α剪枝：如果當(dāng)前節(jié)點(diǎn)的某子節(jié)點(diǎn)的值不比當(dāng)前節(jié)點(diǎn)的前兄弟節(jié)點(diǎn)中的最大值大,則舍棄該子節(jié)點(diǎn)和該子節(jié)點(diǎn)的所有后兄弟節(jié)點(diǎn)。
β剪枝：如果當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)的值不比當(dāng)前的父節(jié)點(diǎn)的前兄弟節(jié)點(diǎn)中的最小值小則舍棄此節(jié)點(diǎn)。
經(jīng)過α-β剪枝，可以極大的減少搜索的數(shù)量，很多時(shí)候，能把幾十億的搜索數(shù)量，縮小到幾億，那么，就可以把搜索深度增1。
第九步：應(yīng)用下棋范圍，提高AI速度
當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)的數(shù)量和排列順序?qū)τ谒阉鞯乃俣绕鹬陵P(guān)重要的影響。根據(jù)五子棋的特點(diǎn),可以產(chǎn)生一個(gè)棋面搜索范圍。記錄當(dāng)前棋面所有棋子的最左最右最上最下點(diǎn)構(gòu)成的矩形,我們認(rèn)為下一步棋的位置不會(huì)脫離這個(gè)框3步以上。這樣在棋子較少的時(shí)候，搜索節(jié)點(diǎn)的數(shù)量大大減少?？梢詫I的速度提高一倍左右。
第十步：利用棋型得分，提高AI速度
因?yàn)槊糠N下法都對(duì)應(yīng)一種得分，所以，可以每次只考慮當(dāng)前得分前十的節(jié)點(diǎn)進(jìn)行下一步搜索，大大減少了搜索范圍，可以進(jìn)一步增加搜索的深度。
第十一步：利用置換表，提高AI速度
我們一般用遞歸的方法實(shí)現(xiàn)博弈樹，但是，遞歸的效率是低的，而且很明顯，有很多重復(fù)搜索的節(jié)點(diǎn)，所以，我們可以用一個(gè)表，記錄下所有搜索過節(jié)點(diǎn)的情況，然后只要遇到搜索到的節(jié)點(diǎn)，就可以直接得到結(jié)果。置于這個(gè)“表”是什么，就是一個(gè)置換表，利用Zobrist算法，進(jìn)行Hash處理，使在表中查找的時(shí)間大大縮短，這樣AI的速度又能提高一個(gè)數(shù)量級(jí)。
第十二步：利用多線程，提高AI速度
我們其實(shí)可以利用多核技術(shù)，利用多個(gè)線程，讓算法實(shí)現(xiàn)并行計(jì)算，提高AI的速度。我們?cè)诘谝粚佑靡粋€(gè)線程分配器把第二層的候選節(jié)點(diǎn)分配給多個(gè)線程,每個(gè)線程包含著從第二層一個(gè)候選節(jié)點(diǎn)開始的搜索,然后等所有線程結(jié)束后,將所有線程的結(jié)果進(jìn)行匯總,選出最大值。并行的程序，可以將速度提高一倍左右。
第十三步：利用隨機(jī)化算法，讓確定方法不能必勝
由于AI算法的固定性，所以一擔(dān)玩家一次獲勝，按照相同的走法，必然會(huì)再次獲勝。但除了必殺招或者必防招,一個(gè)局面很多時(shí)候沒有絕對(duì)最好的走法。而是有一些都不錯(cuò)的走法,那么可以把這些評(píng)分差不多走法匯集起來,然后隨機(jī)選擇它們中的一種走法,避免AI的走法的固定.這樣最簡(jiǎn)單的方法避免固定方法AI必輸。
第十四步：讓AI自學(xué)習(xí)，不再同一個(gè)地方犯錯(cuò)
上面的算法還沒有自學(xué)習(xí)的能力,這樣AI在下棋時(shí)還可能會(huì)重蹈覆轍。因此在每盤棋結(jié)束時(shí),如果AI輸，則進(jìn)行大于搜索深度的步數(shù)回退?？梢园训箶?shù)為搜索深度數(shù)目的局面定為目標(biāo)局面，從倒數(shù)深度加一步局面進(jìn)行預(yù)測(cè),找到不會(huì)導(dǎo)出必?cái)∧繕?biāo)局面的局面。然后記錄下這個(gè)局面和前面的局面，并據(jù)此修改評(píng)分函數(shù)。這樣AI就不會(huì)犯曾經(jīng)犯過的錯(cuò)誤，達(dá)到自學(xué)習(xí)的效果。
做到以上十四步，一個(gè)擁有強(qiáng)大AI的五子棋游戲即可誕生!