五子棋AI算法的改進(jìn)方法講解

1、五子棋AI算法的改進(jìn)方法講解又是本人一份人工智能作業(yè)首先道歉，從Word貼到Livewrter，好多格式?jīng)]了，也沒(méi)做代碼高亮大家湊活著看想做個(gè)好的人機(jī)對(duì)弈的五子棋，可以說(shuō)需要考慮的問(wèn)題還是很多的，我們將制作擁有強(qiáng)大AI五子棋的過(guò)程分為十四步，讓我來(lái)步步介紹。第一步，了解禁手規(guī)則做一個(gè)五子棋的程序，自然對(duì)五子棋需要有足夠的了解，現(xiàn)在默認(rèn)大家現(xiàn)在和我研究五子棋之前了解是一樣多的。以這個(gè)為基礎(chǔ)，介紹多數(shù)人不大熟悉的方面。五子棋的規(guī)則實(shí)際上有兩種：有禁手和無(wú)禁手。由于無(wú)禁手的規(guī)則比較簡(jiǎn)單，因此被更多人所接受。其實(shí)，對(duì)于專(zhuān)業(yè)下五子棋的人來(lái)說(shuō)，有禁手才是規(guī)則。所以，這里先對(duì)“有禁手”進(jìn)行一下簡(jiǎn)單介紹：五子

2、棋中“先手必勝”已經(jīng)得到了論證，類(lèi)似“花月定式”和“浦月定式”，很多先手必勝下法雖然需要大量的記憶，但高手確能做到必勝。所以五子棋的規(guī)則進(jìn)行了優(yōu)化，得到了“有禁手”五子棋。五子棋中，黑棋必然先行。因此“有禁手”五子棋競(jìng)技中對(duì)黑棋有以下“禁手”限制:“三三禁”:黑棋下子位置同時(shí)形成兩個(gè)以上的三；“四四禁”:黑棋下子位置同時(shí)形成兩個(gè)以上的四；“長(zhǎng)連禁”:六子以上的黑棋連成一線(xiàn)。黑棋如下出“禁手“則馬上輸?shù)羝寰帧２贿^(guò)如果“連五”與“禁手”同時(shí)出現(xiàn)這時(shí)“禁手”是無(wú)效的。所以對(duì)于黑棋只有沖四活三（后面會(huì)有解釋?zhuān)┦菬o(wú)解局面。反觀(guān)白棋則多了一種獲勝方式，那就是逼迫黑棋必定要下在禁點(diǎn)。為了迎合所有玩家，五子棋

3、自然需要做出兩個(gè)版本，或者是可以進(jìn)行禁手上的控制。第二步，實(shí)現(xiàn)游戲界面這里，我制作了一個(gè)簡(jiǎn)單的界面，但是，對(duì)于人機(jī)對(duì)弈來(lái)說(shuō)，絕對(duì)夠用。和很多網(wǎng)上的精美界面相比，我的界面也許略顯粗糙，但，開(kāi)發(fā)速度較高，僅用了不到半天時(shí)間。下面我們簡(jiǎn)單看下界面的做法。界面我采用了WPF，表現(xiàn)層和邏輯層完全分開(kāi)，前臺(tái)基本可以通過(guò)拖拽完成布局，這里就不做過(guò)多介紹。根據(jù)界面截圖簡(jiǎn)單介紹1處實(shí)際上市兩個(gè)漸變Label的拼接，2、3是兩個(gè)label，4、5實(shí)際上是兩個(gè)Button，但是沒(méi)有做事件響應(yīng)。通過(guò)按鈕6、7、8、9 的控制，修改label和Button的Content 屬性。也許有人會(huì)奇怪，為什么Button會(huì)絲毫

4、看出不出有Button的影子，這里戰(zhàn)友whrxiao寫(xiě)過(guò)一個(gè)Style如下這里我們把這個(gè)Style稱(chēng)為Style1。界面邏輯上，將是否開(kāi)始、是否禁手和是否電腦先行作為兩個(gè)全局變量的布爾型值，通過(guò)設(shè)置和判斷bool型值進(jìn)行邏輯上的控制。中間的棋盤(pán)是個(gè)canvas，一個(gè)15*15的Grid放滿(mǎn)Button并將每個(gè)Button應(yīng)用Style1開(kāi)始時(shí)候透明度設(shè)為0，也就是根本看不到，在下棋的時(shí)候改變Button的背景和透明度，實(shí)現(xiàn)落子的效果，因?yàn)镚rid的位置關(guān)系，所以可看起來(lái)好像是下在橫豎的交線(xiàn)處。第三步，進(jìn)行輸贏(yíng)判斷：因?yàn)橐?guī)則不同，“無(wú)禁手”和“有禁手”的輸贏(yíng)判斷自然不同。先看無(wú)禁手：這個(gè)比較簡(jiǎn)單

5、，遍歷每個(gè)位置，然后從這個(gè)位置開(kāi)始，分別判斷它的四個(gè)方向：即橫、豎、左上到右下、左下到右上。每個(gè)方向從中間點(diǎn)開(kāi)始，往兩邊數(shù)連子數(shù)，然后將兩個(gè)方向的連字?jǐn)?shù)加和再加一（中間的棋子）。如果得到大于等于5，那么就說(shuō)明下子方贏(yíng)棋。對(duì)于有禁手的五子棋，輸贏(yíng)判斷還需要判斷禁手，禁手的判定較為復(fù)雜。將待判斷點(diǎn)放入黑棋子。然后搜索待判斷點(diǎn)周邊棋盤(pán)；還原棋盤(pá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é)束。若四連棋型或三連棋型的

6、統(tǒng)計(jì)數(shù)大于，則返回為禁手。其余情況返回非禁手。第四步：構(gòu)造棋型估分“有禁手”規(guī)則比較復(fù)雜，涉及到比較多下棋方面的技巧，而且對(duì)算法的思路沒(méi)有絲毫影響，所以下面我們主要考慮無(wú)禁手規(guī)則下的AI設(shè)計(jì)。若設(shè)計(jì)好無(wú)禁手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：一邊被攔截的二子連珠單

7、子：四周無(wú)相連棋子根據(jù)五子棋的技巧，可以將五子棋的棋型用連珠進(jìn)行分類(lèi)，分類(lèi)過(guò)后我們按照威力給每種棋型打分。因?yàn)槲遄悠逡淮沃宦湟蛔?，因此很容易理解，雙活三和三活三的威力是一樣的，類(lèi)似情況不多做解釋。程序中，我以100分為滿(mǎn)分，對(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ǔ)，接下來(lái)就是一些博弈的方法了。第五步：得到位置估分AI單純應(yīng)用棋譜以及對(duì)五子棋當(dāng)前局勢(shì)的分析，對(duì)每步進(jìn)行估分，程序中做如下工作：將每個(gè)位置進(jìn)行分析，假設(shè)AI落子

8、在該位置，用以上打分規(guī)則為AI打分,并將得到的分?jǐn)?shù)加一。然后，假設(shè)玩家落子在該點(diǎn)，為玩家打分，然后將所有的分值匯總。取最高分作為這個(gè)位置的估分，接下來(lái)就是取分?jǐn)?shù)最高的位置下棋了?！拔恢霉婪帧?，下棋的時(shí)候，既可以考慮到自己攻擊對(duì)手，又能考慮到對(duì)對(duì)手的防御，可以說(shuō)，很多時(shí)候可以頂上考慮兩步的AI。作實(shí)驗(yàn)，從網(wǎng)上下載了一個(gè)用博弈做的AI，和“位置估分”對(duì)下，結(jié)果是一勝一負(fù)。誰(shuí)先子，誰(shuí)贏(yíng)得勝利。而且一步估分毫無(wú)疑問(wèn)是最快的，即使遍歷所有位置，也能很快的做出決策。第六步：應(yīng)用博弈樹(shù)，提高AI智能做五子棋的博弈，自然會(huì)用到博弈樹(shù)，這里我說(shuō)下自己的思路。在對(duì)弈中,根據(jù)下一步由誰(shuí)來(lái)走,AI對(duì)任何一個(gè)局面根據(jù)前

9、面估分方法給出一個(gè)分?jǐn)?shù),我們把這個(gè)估分方法匯總成一個(gè)評(píng)估函數(shù)，并返回分值。據(jù)此來(lái)選擇下一步的走法。由于人和AI是輪流落子，可以將人的估分也算入，并將前面加負(fù)號(hào)。那么，估值越大表明對(duì)AI越有利，估分越小則表明對(duì)AI 越不利。那么每次AI選擇都是從它可能的走法樹(shù)的某層節(jié)點(diǎn)，返回評(píng)估值中最大點(diǎn)。而用戶(hù)總是從走法樹(shù)的某層節(jié)點(diǎn)中選擇最小點(diǎn)，從而形成一棵極大極小搜索樹(shù)，然后根據(jù)深度優(yōu)先搜索，可以最后得到固定搜索深度下的一個(gè)最好的走法。我做了下試驗(yàn)，單純應(yīng)用博弈樹(shù)，可以在100ms之內(nèi)讓AI考慮完整的兩步，由于組合爆炸，當(dāng)需要考慮三步的時(shí)候，就需要6s左右，4步就需要1分鐘。拿兩步來(lái)和一步估分作比較，雖然比

10、較慢，但是確實(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)為夷。這樣，可以通過(guò)設(shè)置一個(gè)dep值。深度約淺，dep越大，用dep和得到的得分相乘，得到搜索節(jié)點(diǎn)的得分，再進(jìn)行以上算法，進(jìn)一步提高AI的智能。第八步：應(yīng)用-剪枝，提高AI速度在搜索博弈樹(shù)的過(guò)程中，實(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)

11、時(shí),因?yàn)镕是人走的節(jié)點(diǎn)，那么F需要從K L M中選取最小的，因?yàn)镵已經(jīng)是1，也就是說(shuō)F當(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)前為用戶(hù)下棋節(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)過(guò)-剪枝，可以極大的減少搜索的數(shù)量，很多時(shí)候，能把幾十億的搜索數(shù)量，縮小到幾億，那么，就可以把搜索深

12、度增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)博弈樹(shù)，但是，遞歸的效率是低的，而且很明顯，有很多重復(fù)

13、搜索的節(jié)點(diǎn)，所以，我們可以用一個(gè)表，記錄下所有搜索過(guò)節(jié)點(diǎn)的情況，然后只要遇到搜索到的節(jié)點(diǎn)，就可以直接得到結(jié)果。置于這個(gè)“表”是什么，就是一個(gè)置換表，利用Zobrist算法，進(jìn)行Hash處理，使在表中查找的時(shí)間大大縮短，這樣AI的速度又能提高一個(gè)數(shù)量級(jí)。第十二步：利用多線(xiàn)程，提高AI速度我們其實(shí)可以利用多核技術(shù)，利用多個(gè)線(xiàn)程，讓算法實(shí)現(xiàn)并行計(jì)算，提高AI的速度。我們?cè)诘谝粚佑靡粋€(gè)線(xiàn)程分配器把第二層的候選節(jié)點(diǎn)分配給多個(gè)線(xiàn)程,每個(gè)線(xiàn)程包含著從第二層一個(gè)候選節(jié)點(diǎn)開(kāi)始的搜索,然后等所有線(xiàn)程結(jié)束后,將所有線(xiàn)程的結(jié)果進(jìn)行匯總,選出最大值。并行的程序，可以將速度提高一倍左右。第十三步：利用隨機(jī)化算法，讓確定方

14、法不能必勝由于A(yíng)I算法的固定性，所以一擔(dān)玩家一次獲勝，按照相同的走法，必然會(huì)再次獲勝。但除了必殺招或者必防招,一個(gè)局面很多時(shí)候沒(méi)有絕對(duì)最好的走法。而是有一些都不錯(cuò)的走法,那么可以把這些評(píng)分差不多走法匯集起來(lái),然后隨機(jī)選擇它們中的一種走法,避免AI的走法的固定.這樣最簡(jiǎn)單的方法避免固定方法AI必輸。第十四步：讓AI自學(xué)習(xí)，不再同一個(gè)地方犯錯(cuò)上面的算法還沒(méi)有自學(xué)習(xí)的能力,這樣AI在下棋時(shí)還可能會(huì)重蹈覆轍。因此在每盤(pán)棋結(jié)束時(shí),如果AI輸，則進(jìn)行大于搜索深度的步數(shù)回退。可以把倒數(shù)為搜索深度數(shù)目的局面定為目標(biāo)局面，從倒數(shù)深度加一步局面進(jìn)行預(yù)測(cè),找到不會(huì)導(dǎo)出必?cái)∧繕?biāo)局面的局面。然后記錄下這個(gè)局面和前面的局

15、面，并據(jù)此修改評(píng)分函數(shù)。這樣AI就不會(huì)犯曾經(jīng)犯過(guò)的錯(cuò)誤，達(dá)到自學(xué)習(xí)的效果。做到以上十四步，一個(gè)擁有強(qiáng)大AI的五子棋游戲即可誕生！五子棋算法可簡(jiǎn)可繁,要看你對(duì)自己五子棋程序智能的要求, 人機(jī)對(duì)戰(zhàn)的意思就是人和電腦下,也就是說(shuō)電腦會(huì)思考如何下棋.其實(shí)這才是五子棋程序的核心.如果只實(shí)現(xiàn)人與人對(duì)戰(zhàn)的話(huà),是一件很簡(jiǎn)單的事情,無(wú)非就是繪制棋盤(pán),然后繪制下棋的效果,再寫(xiě)個(gè)下棋合法性判斷,勝負(fù)判斷.大概就搞定了.所以核心其實(shí)是人機(jī)對(duì)戰(zhàn)的電腦那部分人工智能.這東西吧,可以研究的很多,不過(guò)主要的幾個(gè)設(shè)計(jì)要點(diǎn)就是搜索算法和估值算法,這兩個(gè)是最主要的,還有提高電腦思考銷(xiāo)率的方法就有多cpu的計(jì)算機(jī)多線(xiàn)程思考的設(shè)計(jì).通

16、過(guò)一些手段讓電腦變得更像人類(lèi)棋手的,例如利用一些遺傳算法之類(lèi)的讓電腦具有學(xué)習(xí)能力,可以在失敗中吸取教訓(xùn),開(kāi)局庫(kù),歷史啟發(fā)之類(lèi)的一大堆.但是總而言之,這一系列算法的設(shè)計(jì)沒(méi)有一個(gè)標(biāo)準(zhǔn),只要能讓你的電腦下棋下的更聰明,更快那就是好算法.國(guó)內(nèi)有一個(gè)叫王曉春的寫(xiě)過(guò)一本叫五子棋的核心算法五子棋是一種受大眾廣泛喜愛(ài)的游戲，其規(guī)則簡(jiǎn)單，變化多端，非常富有趣味性和消遣性。這里設(shè)計(jì)和實(shí)現(xiàn)了一個(gè)人機(jī)對(duì)下的五子棋程序，采用了博弈樹(shù)的方法，應(yīng)用了剪枝和最大最小樹(shù)原理進(jìn)行搜索發(fā)現(xiàn)最好的下子位置。介紹五子棋程序的數(shù)據(jù)結(jié)構(gòu)、評(píng)分規(guī)則、勝負(fù)判斷方法和搜索算法過(guò)程。一、相關(guān)的數(shù)據(jù)結(jié)構(gòu)關(guān)于盤(pán)面情況的表示，以鏈表形式表示當(dāng)前盤(pán)面的情

17、況，目的是可以允許用戶(hù)進(jìn)行悔棋、回退等操作。CList StepList;其中Step結(jié)構(gòu)的表示為：struct Stepint m; /m,n表示兩個(gè)坐標(biāo)值int n;char side; /side表示下子方;以數(shù)組形式保存當(dāng)前盤(pán)面的情況，目的是為了在顯示當(dāng)前盤(pán)面情況時(shí)使用：char FiveAreaFIVE_MAX_LINEFIVE_MAX_LINE;其中FIVE_MAX_LINE表示盤(pán)面最大的行數(shù)。同時(shí)由于需要在遞歸搜索的過(guò)程中考慮時(shí)間和空間有效性，只找出就當(dāng)前情況來(lái)說(shuō)相對(duì)比較好的幾個(gè)盤(pán)面，而不是對(duì)所有的可下子的位置都進(jìn)行搜索，這里用變量CountList來(lái)表示當(dāng)前搜索中可以選擇的所有

18、新的盤(pán)面情況對(duì)象的集合：CList CountList;其中類(lèi)CBoardSituiton為:class CBoardSituationCList StepList; /每一步的列表char FiveAreaFIVE_MAX_LINEFIVE_MAX_LINE;struct Step machineStep; /機(jī)器所下的那一步double value; /該種盤(pán)面狀態(tài)所得到的分?jǐn)?shù)二、評(píng)分規(guī)則對(duì)于下子的重要性評(píng)分，需要從六個(gè)位置來(lái)考慮當(dāng)前棋局的情況，分別為：-,|,/,/,實(shí)際上需要考慮在這六個(gè)位置上某一方所形成的子的布局的情況，對(duì)于在還沒(méi)有子的地方落子以后的當(dāng)前局面的評(píng)分，主要是為了說(shuō)明在這

19、個(gè)地方下子的重要性程度，設(shè)定了一個(gè)簡(jiǎn)單的規(guī)則來(lái)表示當(dāng)前棋面對(duì)機(jī)器方的分?jǐn)?shù)?；镜囊?guī)則如下：判斷是否能成5, 如果是機(jī)器方的話(huà)給予100000分，如果是人方的話(huà)給予100000 分；判斷是否能成活4或者是雙死4或者是死4活3，如果是機(jī)器方的話(huà)給予10000分，如果是人方的話(huà)給予10000分；判斷是否已成雙活3，如果是機(jī)器方的話(huà)給予5000分，如果是人方的話(huà)給予5000 分；判斷是否成死3活3，如果是機(jī)器方的話(huà)給予1000分，如果是人方的話(huà)給予1000 分；判斷是否能成死4，如果是機(jī)器方的話(huà)給予500分，如果是人方的話(huà)給予500分；判斷是否能成單活3，如果是機(jī)器方的話(huà)給予200分，如果是人方的話(huà)給

20、予200分；判斷是否已成雙活2，如果是機(jī)器方的話(huà)給予100分，如果是人方的話(huà)給予100分；判斷是否能成死3，如果是機(jī)器方的話(huà)給予50分，如果是人方的話(huà)給予50分；判斷是否能成雙活2，如果是機(jī)器方的話(huà)給予10分，如果是人方的話(huà)給予10分；判斷是否能成活2，如果是機(jī)器方的話(huà)給予5分，如果是人方的話(huà)給予5分；判斷是否能成死2，如果是機(jī)器方的話(huà)給予3分，如果是人方的話(huà)給予3分。實(shí)際上對(duì)當(dāng)前的局面按照上面的規(guī)則的順序進(jìn)行比較，如果滿(mǎn)足某一條規(guī)則的話(huà)，就給該局面打分并保存，然后退出規(guī)則的匹配。注意這里的規(guī)則是根據(jù)一般的下棋規(guī)律的一個(gè)總結(jié)，在實(shí)際運(yùn)行的時(shí)候，用戶(hù)可以添加規(guī)則和對(duì)評(píng)分機(jī)制加以修正。三、勝負(fù)判斷

21、實(shí)際上，是根據(jù)當(dāng)前最后一個(gè)落子的情況來(lái)判斷勝負(fù)的。實(shí)際上需要從四個(gè)位置判斷，以該子為出發(fā)點(diǎn)的水平，豎直和兩條分別為45度角和135度角的線(xiàn)，目的是看在這四個(gè)方向是否最后落子的一方構(gòu)成連續(xù)五個(gè)的棋子，如果是的話(huà)，就表示該盤(pán)棋局已經(jīng)分出勝負(fù)。具體見(jiàn)下面的圖示：四、搜索算法實(shí)現(xiàn)描述注意下面的核心的算法中的變量currentBoardSituation，表示當(dāng)前機(jī)器最新的盤(pán)面情況, CountList表示第一層子節(jié)點(diǎn)可以選擇的較好的盤(pán)面的集合。核心的算法如下：void MainDealFunction()value=MAXINT; /對(duì)初始根節(jié)點(diǎn)的value賦值CalSeveralGoodPlace(

22、currentBoardSituation,CountList);/該函數(shù)是根據(jù)當(dāng)前的盤(pán)面情況來(lái)比較得到比較好的可以考慮的幾個(gè)盤(pán)面的情況，可以根據(jù)實(shí)際的得分情況選取分?jǐn)?shù)比較高的幾個(gè)盤(pán)面，也就是說(shuō)在第一層節(jié)點(diǎn)選擇的時(shí)候采用貪婪算法，直接找出相對(duì)分?jǐn)?shù)比較高的幾個(gè)形成第一層節(jié)點(diǎn)，目的是為了提高搜索速度和防止堆棧溢出。pos=CountList.GetHeadPosition();CBoardSituationpBoard;for(i=0;ivalue=Search(pBoard,min,value,0);Value=Select(value,pBoardvalue,max);/取value和pBoardvalue中大的賦給根節(jié)點(diǎn)for(i=0;ivalue)/找出那一個(gè)得到最高分的盤(pán)面currentBoardSituation=pBoard;PlayerMode=min; /當(dāng)前下子方改為人Break;其中對(duì)于Search函數(shù)的表示如下：實(shí)際上核心的算法是一個(gè)剪枝過(guò)程，其中在這個(gè)搜索過(guò)程中相關(guān)的四個(gè)參數(shù)為：（1）當(dāng)前棋局情況；（