基于極小極大值搜索和Alpha Beta剪枝算法的五子棋智能博弈算法研究與實(shí)現(xiàn)

鄭健磊，匡芳君

(溫州商學(xué)院信息工程學(xué)院，浙江溫州 325035)

五子棋是一款經(jīng)典的兩人對弈的純策略型棋類游戲．相對于國際象棋、中國象棋、圍棋、日本將棋，五子棋簡單易學(xué)，但是精通五子棋并非易事．2016 年人工智能程序AlphaGo，擊敗人類圍棋冠軍李世石[1]，計(jì)算機(jī)在圍棋領(lǐng)域不可能戰(zhàn)勝人類的預(yù)言破滅．雖然AlphaGo 已經(jīng)宣布退出圍棋比賽，但是其留下來的寶貴算法和圍棋招數(shù)是計(jì)算機(jī)界的新突破，也給圍棋界帶來翻天覆地的變化．在五子棋領(lǐng)域，五子棋先后于1994 年[2]、2001 年[3]被計(jì)算機(jī)證明原始無禁手、原始有禁手規(guī)則下先手必勝，然而相比計(jì)算機(jī)象棋和圍棋，計(jì)算機(jī)五子棋的發(fā)展是緩慢的．很多五子棋專家相信目前的五子棋程序依舊無法超越最強(qiáng)的人類棋手．

五子棋博弈研究學(xué)者們都有其獨(dú)到見解，張明亮[4]通過各類棋型估值的研究，優(yōu)化了五子棋估值函數(shù)，解決了部分五子棋程序估值不完善的問題；毛麗民等[5]結(jié)合圖像采集和分析，研發(fā)可以進(jìn)行實(shí)物對弈的五子棋機(jī)器人；程宇等[6]通過對Alpha Beta 剪枝算法的改進(jìn)，優(yōu)化了著棋效率低下的問題；還有學(xué)者設(shè)計(jì)和實(shí)現(xiàn)了整套完整的五子棋人機(jī)博弈軟件[7-8]．但五子棋博弈系統(tǒng)仍然存在棋型定義模糊，說法不一和博弈水平不高等問題．因此，本文針對五子棋棋型的定義不準(zhǔn)確、棋型不充足，提出一套改進(jìn)的五子棋棋型模型和估值方法，對基本棋型和絕殺棋型分別進(jìn)行估值；針對Alpha Beta 剪枝算法存在效率低和博弈水平不高等問題，提出改進(jìn)智能博弈算法，利用多線程技術(shù)和淺層最優(yōu)算法優(yōu)化Alpha Beta 剪枝算法，以提升著棋速度和準(zhǔn)確率，通過局部搜索，加深程序的局部觀，使得系統(tǒng)著棋能力得到提升．

1 五子棋棋型與估值

五子棋棋型存在定義模糊，如對活二、眠三、死四定義的不完整或存在術(shù)語使用不當(dāng)[9]．而在大部分研究中，考慮的棋型較少，如對活三的定義不夠完整，對跳活三、跳四這樣的重要棋型未進(jìn)行定義或定義不完整[10]．本文對棋型進(jìn)行新的定義，特別是對一些特殊絕殺棋型進(jìn)行了直接定義，以降低搜索深度，即顛覆從前往后的計(jì)算方式，直接從后往前推算，可提供接近2 層的計(jì)算深度，而龐大的搜索樹需要提高1 層的搜索深度也是非常不容易的．

1.1 五子棋的基本棋型

在五子棋博弈中，活三和沖四是五子棋著棋過程最重要的棋型，活三兩頭均可進(jìn)攻，沖四具有絕對先手，連續(xù)的沖四和活三的進(jìn)攻是五子棋獲勝的關(guān)鍵技術(shù)．而活三的一些變體棋型，如有一邊空一格被對方棋子攔住，如圖1 的棋型g 所示．此外跳活三、跳四，也是十分重要的棋型．跳四和沖四一樣，具備絕對先手．

1.2 五子棋的絕殺棋型

如果不考慮對手的疏忽，那么活四或者成五一定是由多個(gè)棋型連續(xù)進(jìn)攻所形成．本文例舉了一方因無法防御而導(dǎo)致另一方必定出現(xiàn)活四或成五的棋型如圖1 所示，故著此類棋型是獲勝的關(guān)鍵所在．通過棋型可以判斷，此類棋型是由兩個(gè)或兩個(gè)以上的先手棋型組成．因此本文將先手棋型進(jìn)行計(jì)數(shù)，如果一方先手棋型的數(shù)量超過2 個(gè)，那么就給予一個(gè)相對非常高的分值，這些先手棋型包括：活三、跳活三、沖四、跳四．在著棋過程中發(fā)現(xiàn)，絕殺棋型有時(shí)也會存在被對手反勝或者化解的情況，一般是因?yàn)閷Ψ竭B續(xù)著絕對先手棋型（即沖四或跳四）導(dǎo)致的．而絕殺棋型中存在絕對先手的棋型，則不會存在此類情況，相對勝率會更高．

1.3 棋型的估值

通過對比不同估值的對局勝率，以及對棋型的分析，最終得出表1 所示估值方案．

表1 棋型估值Table 1 Chess Type Valuation

2 五子棋基礎(chǔ)算法分析

本研究的算法思想基于極小極大值算法和Alpha Beta 剪枝算法①Sato N, Ikeda K. Three types of forward pruning techniques to apply the alpha beta algorithm to turn-based strategy games [C]. 2016 IEEE Conference on Computational Intelligence and Games, Santorini, Greece, 2016: 20-23.，這兩種算法思想在棋類游戲中最為常用．

2.1 極小極大值算法效率分析

基于本文棋型的估值，使用極小極大值算法對局面進(jìn)行評估．極小極大值算法能夠模擬人的思維，找出局面范圍內(nèi)最優(yōu)的解．在對弈中，對局面進(jìn)行評估，估值越大表明對當(dāng)前棋手越有利，估分越小則表明越不利．對所有節(jié)點(diǎn)進(jìn)行計(jì)算局面評估，其所得最高分，即所達(dá)深度所能走出的最佳棋面，記錄第1 手著棋位置，即是當(dāng)前局面最佳著棋點(diǎn)．

如果不對極大極小值加以優(yōu)化，這樣的全盤遍歷的方法會搜索大量毫無意義的點(diǎn)，對代碼測試可以得出，在可以接受的時(shí)間內(nèi)，只能進(jìn)行兩層搜索，即黑白各一手棋，而專業(yè)棋手能對未來十幾步棋進(jìn)行預(yù)測．

2.2 Alpha Beta剪枝算法效率分析

AlphaBeta 剪枝算法在棋類博弈的應(yīng)用也不乏優(yōu)秀研究[6]．人類棋手在著棋的過程中不會去考慮對己方明顯不利的點(diǎn)和對對方明顯有利的點(diǎn)．AlphaBeta 剪枝算法就是不對那些雙方都不會考慮的點(diǎn)進(jìn)行剪枝，不進(jìn)行下一步的考慮，以此將搜索樹加以修剪．1975 年，Knuth 等[11]證明在搜索節(jié)點(diǎn)排列為理想的情況下，將節(jié)點(diǎn)分支數(shù)記為b，深度記為d，搜索的節(jié)點(diǎn)數(shù)n為：

當(dāng)d為偶數(shù)，

表2 AlphaBeta 剪枝算法效率分析Table 2 Efficiency Analysis of AlphaBeta Pruning Algorithm

Alpha Beta 剪枝算法高度依賴于節(jié)點(diǎn)的排列順序，如果每次總是找到最差的節(jié)點(diǎn)，那么相當(dāng)于剪枝永遠(yuǎn)不會發(fā)生，其效果相當(dāng)于沒有使用剪枝算法，即n=bd．Alpha Beta 剪枝算法效率分析如表2 所示．從表2 可知，雖然使用Alphabeta 剪枝對著棋能力有較大提升，但是其效率與理想排列狀態(tài)相差甚遠(yuǎn)．

3 五子棋博弈算法研究與效率改進(jìn)

通過對五子棋基礎(chǔ)算法的分析，算法所存在的問題已然暴露．在極小極大值算法暴力搜索的基礎(chǔ)上，使用AlphaBeta 剪枝算法進(jìn)行改進(jìn)，但其效率依舊低下，且只能對第四層進(jìn)行非常緩慢的搜索，因此，結(jié)合局部搜索、多線程技術(shù)和淺層最優(yōu)算法提出效率改進(jìn)方案．

3.1 局部搜索

在五子棋博弈過程中，沒有哪個(gè)人類棋手會對整個(gè)棋盤進(jìn)行計(jì)算，其思考過程往往是從中心向四周發(fā)散，并且五子棋著棋往往不會超出原有棋子兩格的位置，而未經(jīng)優(yōu)化的搜索算法會將任何一個(gè)空白的節(jié)點(diǎn)作為可能的落子點(diǎn)．

經(jīng)過文獻(xiàn)資料[6,8-9]和實(shí)戰(zhàn)分析，一般對于搜索區(qū)域限制的算法往往是計(jì)算具有最大橫坐標(biāo)的棋子(maxx)，具有最小橫坐標(biāo)的棋子(minx)，具有最大縱坐標(biāo)的棋子(maxy)，具有最小縱坐標(biāo)的棋子(miny)，得出一個(gè)區(qū)域?yàn)?maxx- minx+n)*(maxy- miny+n)，其中n表示偏移量，即可能的著棋點(diǎn)和原有棋子的最大距離[6]，但是這種計(jì)算方式并不高效．如果棋型呈現(xiàn)斜向狹長走勢，或者棋子距離較遠(yuǎn)且中間有大量空白的情況，依舊會存在大量的無效搜索．前者的情況并不少見，在五子棋博弈過程中，與任何已有棋子成不了直線的點(diǎn)也往往是不會成為落子區(qū)域，這樣就會出現(xiàn)如圖2 所示的區(qū)域化限制著棋點(diǎn)潛在的缺陷．對此，本文提出一種新思路，計(jì)算所需搜索節(jié)點(diǎn)的坐標(biāo)，即可精確確定搜索范圍．這樣記錄節(jié)點(diǎn)坐標(biāo)的計(jì)算方式雖然比記錄搜索范圍計(jì)算方式更加復(fù)雜，但其減少的時(shí)間依舊比其增加的時(shí)間更可觀．

圖2 區(qū)域化限制著棋點(diǎn)潛在的缺陷Fig 2 Potential Defects of the Chess Sub-point Restricted by Regionalization

使用局部搜索前后的節(jié)點(diǎn)量對比如表3 所示，局部搜索效果非常有效，第二層和第四層節(jié)點(diǎn)分別減少了96.59%和99.94%，且原本無法計(jì)算的第六層使用較長時(shí)間也可被成功計(jì)算．

表3 使用局部搜索前后的節(jié)點(diǎn)量對比Table 3 Comparison of Grid Point Variable before and after the Application of Local Search

3.2 多線程技術(shù)

使用局部搜索后，搜索速度有了質(zhì)的飛躍．但博弈過程中又出現(xiàn)了新問題，即在4 層和6 層搜索過程中CPU 的平均占用率只有35%左右．研究發(fā)現(xiàn)，這是因?yàn)檎麄€(gè)搜索的過程是單線程串行的，而現(xiàn)在的CPU 普遍采用了多核多線程設(shè)計(jì)，實(shí)驗(yàn)所用的筆記本電腦使用的是Intel i7 8550U處理器，使用了4 核8 線程的設(shè)計(jì)．多線程技術(shù)避免了因阻塞帶來的等待問題，能夠有效提高處理器的工作效率和資源利用率[12]．

本文采取了多線程技術(shù)來優(yōu)化CPU 的使用率，目前市面上多數(shù)消費(fèi)級CPU 采用的是2 核4線程，4 核4 線程，或者4 核8 線程的設(shè)計(jì)．因此，選擇了4 線程對搜索進(jìn)行優(yōu)化．

本文通過給每個(gè)線程分配不同的搜索區(qū)域，達(dá)到4 線程搜索，其偽代碼如下：

length=搜索數(shù)組的長度;

range 1[開始]=1; range 1[結(jié)束]=length / 4;

range 2[開始]=range 1[結(jié)束]+ 1; range 2[結(jié)束]=length / 2;

range 3[開始]=range 2[結(jié)束]+ 1; range 3[結(jié)束]=(range 2[結(jié)束]+1+length) / 2;

range 4[開始]=range 3[結(jié)束]+ 1; range 4[結(jié)束]=length;

通過將局部搜索時(shí)保存的節(jié)點(diǎn)數(shù)組4 等分，然后使用4 個(gè)線程分別對4 個(gè)節(jié)點(diǎn)數(shù)組分別進(jìn)行搜索．改進(jìn)后CPU 占用率從35%左右提升到了95%左右，而剩下的5%也已經(jīng)被其他任務(wù)占據(jù)，因此CPU 的使用率已經(jīng)達(dá)到了100%．

3.2.1 效率分析

CPU 效率得到明顯提升，本應(yīng)該計(jì)算速度也明顯提升．但是實(shí)驗(yàn)結(jié)果卻是令人意外的，使用多線程搜索之后，節(jié)點(diǎn)數(shù)幾乎是使用單線程的2-3倍．單位時(shí)間內(nèi)對節(jié)點(diǎn)的搜索速度提高到了原來的2 倍左右，如表4 所示，反而需要比單線程更長的時(shí)間．而且多線程的博弈過程發(fā)現(xiàn)，當(dāng)前局面存在沖四棋型時(shí)，個(gè)別線程的節(jié)點(diǎn)明顯增多．

表4 使用多線程技術(shù)前后的節(jié)點(diǎn)量與時(shí)間（取前10次平均值）對比Table 4 Comparison of Grid Point Variable and Time before and after the Application of Multi-threading Technology (Take the First 10Average Values)

3.2.2 多線程效率低下的原因分析

經(jīng)過多次博弈發(fā)現(xiàn)，多線程效率低下是因?yàn)樗膫€(gè)線程彼此獨(dú)立，個(gè)別線程所找到著棋點(diǎn)有時(shí)候往往是非常不好的，導(dǎo)致個(gè)別線程剪枝不易發(fā)生．最為顯著的是出現(xiàn)淺層絕殺的棋面，如對方著棋形成了沖四，那么只有一個(gè)線程可以找到攔截沖四繼續(xù)形成成五的點(diǎn)，而其他線程因?yàn)檫@個(gè)點(diǎn)不在它的搜索范圍內(nèi)，導(dǎo)致得到的永遠(yuǎn)是一個(gè)極差的局面分．

如果使用單線程，那么單棵的搜索樹將被分成4 棵彼此獨(dú)立的搜索樹，雖然4 線程的每棵小樹的節(jié)點(diǎn)比單線程的大樹要更少，但是4 棵樹的總和卻要更多．而多線程并不能帶來4 倍的速度提升，因?yàn)镃PU 負(fù)載升高后其每個(gè)線程所獲得的算力明顯低于單線程．

3.3 淺層最優(yōu)算法

Alpha Beta 剪枝算法嚴(yán)重依賴于節(jié)點(diǎn)的排列．如果程序總是先去搜索最壞的節(jié)點(diǎn)，那么Alpha Beta 截?cái)嗑筒粫l(fā)生，該算法最終會遍歷整個(gè)搜索樹．在搜索的過程中，節(jié)點(diǎn)的排列順序是完全無規(guī)律的，甚至沒有優(yōu)化的搜索往往是從邊緣往中心推進(jìn)，這樣得到的節(jié)點(diǎn)往往比隨機(jī)排列還要更差．顯然找到最優(yōu)排列是不可能的，因?yàn)檫@勢必要算出所有節(jié)點(diǎn)．但是可以通過著棋的特點(diǎn)，算法的特性，提前找到較為優(yōu)秀的解．

淺層搜索雖然不能找到深層的最優(yōu)解，但是其找到的解往往是較優(yōu)解．而且對于某些棋型，淺層的搜索結(jié)果和深層的結(jié)果是完全一樣的．比如下一著如果可以形成活四，那么不管搜索深度是多少，著活四棋型永遠(yuǎn)都是最優(yōu)解．通過這一特點(diǎn)，在原來的Alpha Beta 剪枝算法的搜索范圍的基礎(chǔ)上，先使用兩層搜索找到一個(gè)當(dāng)前局面的最優(yōu)解，再將這個(gè)解的節(jié)點(diǎn)替換為深層搜索的每一個(gè)線程的起始節(jié)點(diǎn)，那么深層搜索將從一個(gè)較為優(yōu)秀的節(jié)點(diǎn)開始搜索．淺層最優(yōu)搜索算法的偽代碼如下：

(x,y)=獲取深度為2 的最佳著棋點(diǎn);

線程1 計(jì)算范圍[0][0]=x; 線程1 計(jì)算范圍[0][1]=y;

線程2 計(jì)算范圍[0][0]=x; 線程2 計(jì)算范圍[0][1]=y;

線程3 計(jì)算范圍[0][0]=x; 線程3 計(jì)算范圍[0][1]=y;

線程4 計(jì)算范圍[0][0]=x; 線程4 計(jì)算范圍[0][1]=y;

這樣算法將四個(gè)線程都能聯(lián)系，尤其是在淺層絕殺的棋面下，讓四個(gè)線程都有機(jī)會找到絕殺點(diǎn)，大大提高了搜索效率，如表5 所示，使用了淺層最優(yōu)算法后的多線程搜索效率顯著提高．淺層最優(yōu)算法不僅解決某些線程因找不到攔截淺層絕殺的點(diǎn)而導(dǎo)致搜索速度極慢，還使得節(jié)點(diǎn)排列順序有一定提升，如表6 所示，單線程也比不使用淺層最優(yōu)算法的效率高．

表5 使用淺層最優(yōu)算法前后多線程的節(jié)點(diǎn)量與時(shí)間（取前10次平均值）對比Table 5 Comparison of the Amount of Nodes and Time of a Multiple Thread before and after the Application of Shallow Optimal Algorithm (Take the First 10Average Values)

表6 使用淺層最優(yōu)算法前后單線程的節(jié)點(diǎn)量與時(shí)間（取前10次平均值）對比Table 6 Comparison of the Amount of Nodes and Time of a Single Thread before and after the Application of Shallow Optimal Algorithm (Take the First 10Average Values)

使用了淺層最優(yōu)算法之后，無論單線程與多線程都有了效率的提升，使用淺層最優(yōu)算法后單線程與多線程的節(jié)點(diǎn)量與時(shí)間對比如表7 所示．

7 229 329 2 331 316 264 1 436 -38 38 48 55 889 593 77 904 424 -39 28 9 51 523 574 88 536 410-72 29 1099 954 1 055 174 941 821 -75 22平均值 70245.9 720.9 111 672.5 561.0-59 22 1 1 491 025 14 4602 111 35011 012 -42 24 6 2 1 946 012 17 664 3 549 182 18 797 -82 -6 3 787 581 7 271 1 603 237 6 791 -104 7 4 2 777 389 26 342 3 842 868 15 197 -38 42 5 7 529 166 74 4407 529 166 37 646 049 6 93 603 148 840879 98 675 655 432 788 -5 49 7 76 446 115 692 205 91 676 698 503 718 -2027 8 32 996 289 319 549 44 678 231 210746 -35 34 9 51 264 007 516 822 63 563 678 288 926 -24 44 1059 131 650601 98066 765 425 307 675 -13 49平均值 32 797 238.2 311 161.2 38 399 549.0183 329.6 -17 41

由表7 可知，在節(jié)點(diǎn)多的時(shí)候，多線程表現(xiàn)出的效率要優(yōu)于單線程，而在節(jié)點(diǎn)較少的時(shí)候，單線程效率更優(yōu)．由于深度為2 的時(shí)候，無論基于什么算法，都是瞬間完成的，因此不在考慮之內(nèi)．對于深度4 和深度6 而言，多線程的綜合速度要明顯優(yōu)于單線程，隨著棋面復(fù)雜度的增加，搜索深度加深，多線程的優(yōu)勢將更加明顯，因此多線程的表現(xiàn)是值得肯定的．

4 實(shí)驗(yàn)結(jié)果與分析

全文實(shí)驗(yàn)方式均采用了15×15 的標(biāo)準(zhǔn)五子棋棋盤，以前10步著棋為實(shí)驗(yàn)數(shù)據(jù)，并保持相同深度的著棋棋型一致，對所使用的各項(xiàng)技術(shù)進(jìn)行分析．通過使用五子棋基本棋型和絕殺棋型的兩種估值方式，對棋力帶來了明顯改善，尤其是對于淺層絕殺方面．對于極小極大值算法和Alpha Beta 剪枝算法效率不足的問題，提出了以下改進(jìn)方案：

（1）局部搜索意在優(yōu)化減少對理論上不會落子的區(qū)域進(jìn)行優(yōu)化，本文打破常見的計(jì)算著棋區(qū)域的方法，轉(zhuǎn)而使用了直接計(jì)算落子坐標(biāo)的方法，優(yōu)化了前者所存在的不足，其效率提升也十分明顯，帶來約99%的綜合效率提升，并使得6 層搜索成為了可能．

（2）對CPU 使用率過低的問題，采取了4 線程并行計(jì)算，但是其結(jié)果并不理想，因?yàn)锳lpha Beta 剪枝算法的特點(diǎn)，其效率反而有所下降．

（3）為了解決多線程計(jì)算存在的問題，提出了淺層最優(yōu)算法，此算法不僅提高了多線程效率，也提高了單線程效率，使用了淺層最優(yōu)算法之后，效率較低的多線程搜索有了較大的改善，相對于未使用此算法提升了約60%的綜合效率．

如圖3 是系統(tǒng)程序?qū)譁y試的結(jié)果，玩家持黑，電腦持白，電腦從第13 手進(jìn)行了連續(xù)的先手進(jìn)攻，最終于第27 手取勝．

5 結(jié) 語

本文針對五子棋棋型的定義不準(zhǔn)確，棋型不充足等問題，提出了一套改進(jìn)的五子棋棋型模型和估值方法．針對利用極小極大值搜索和Alpha Beta 剪枝算法對此棋型模型著棋時(shí)存在效率低和博弈水平不高的問題，提出改進(jìn)智能博弈算法，在可接受的時(shí)間內(nèi)，將搜索深度做到了6 層，實(shí)驗(yàn)結(jié)果表明，程序性能和效率相對較高，通過使用五子棋基本棋型和絕殺棋型的兩種估值方式，對棋力也有明顯改善，尤其是淺層絕殺方面有著很大優(yōu)勢．下一步工作將使用機(jī)器學(xué)習(xí)算法保存已下棋局，以使同樣錯(cuò)誤的著棋不再出現(xiàn)，同時(shí)在著棋時(shí)考慮對手存在計(jì)算漏洞，使程序具備更激進(jìn)棋風(fēng)．

圖3 電腦持白對弈過程Fig 3 The Process to Play Chess by Computer Holding White Chess