周洋，鄧?yán)?，謝煜

（武漢科技大學(xué)計(jì)算機(jī)學(xué)院，武漢 430065）

一種五子棋博弈算法的分析

周洋，鄧?yán)颍x煜

（武漢科技大學(xué)計(jì)算機(jī)學(xué)院，武漢 430065）

博弈是用來(lái)解決一組決策者之間沖突或合作問(wèn)題的數(shù)學(xué)方法。在實(shí)現(xiàn)玩家和電腦之間的五子棋對(duì)弈時(shí)，常常使用博弈方法來(lái)確定電腦的走法步驟。經(jīng)過(guò)對(duì)五子棋的一種博弈算法設(shè)計(jì)和實(shí)現(xiàn)的分析，總結(jié)出五子棋問(wèn)題求解的算法思路，并分析出算法的性能瓶頸及相應(yīng)的解決方案。

極大極小搜索算法；Alpha-beta剪枝；博弈；五子棋

0 引言

五子棋是一種深受大家喜愛(ài)的棋類游戲，其規(guī)則簡(jiǎn)單，變化多樣，為其增加了更多的趣味性。五子棋起源于中國(guó)古代棋類，而對(duì)其發(fā)展起重大作用的是日本。18世紀(jì)五子棋在日本流行起來(lái)，后來(lái)發(fā)現(xiàn)五子棋有執(zhí)黑先行必勝定律，為了讓其能更公平，在比賽中添加了許多禁手規(guī)則，而在業(yè)余人士的游戲中則一般不設(shè)置這些規(guī)則。五子棋發(fā)展至今禁手規(guī)則已逐漸削弱了執(zhí)黑先行的優(yōu)勢(shì)。在1997年計(jì)算機(jī)就下贏了當(dāng)時(shí)的國(guó)際象棋冠軍。而對(duì)五子棋一直以來(lái)都沒(méi)有發(fā)展出一種可以絕對(duì)取勝算法。原因就在于五子棋（15×15）的搜索空間比國(guó)際象棋（8×8）更大。想在有限的時(shí)間找出一種必勝的策略顯然是件非常困難的事。博弈是在一定條件下，遵守一定的規(guī)則，一個(gè)或幾個(gè)擁有絕對(duì)理性思維的人或團(tuán)隊(duì)，從各自允許選擇的行為或策略進(jìn)行選擇并加以實(shí)施，并從中各自取得相應(yīng)結(jié)果或收益的過(guò)程。博弈最終是要取得一種均衡解，即博弈的參與者對(duì)其收益達(dá)到一種較為滿意的程度。所以將博弈應(yīng)用于五子棋算法的研究可以有效地提高算法的效率。

五子棋的對(duì)弈雙方只能是黑子或者白子，而執(zhí)黑先行者一般都會(huì)選擇在棋盤中心，所以五子棋的開(kāi)局往往比較相似，常見(jiàn)的有26種開(kāi)局。如下：

圖1

而在這次將博弈的思想應(yīng)用于五子棋用到了極大極小的搜索算法和α-β剪枝算法。運(yùn)用這兩個(gè)算法和已經(jīng)確定的分?jǐn)?shù)表來(lái)產(chǎn)生出當(dāng)前節(jié)點(diǎn)的評(píng)估分值，計(jì)算機(jī)選擇一個(gè)對(duì)自己最有利的點(diǎn)落子。

1 主要算法

1.1 極大極小搜索算法

一般在一個(gè)五子棋對(duì)弈中如果采用暴力搜索得到最終結(jié)果，則會(huì)使搜索樹(shù)的深度非常大，盡管計(jì)算機(jī)的計(jì)算性能在不斷加快，但還是不能滿足需要，主要是因?yàn)楹臅r(shí)太長(zhǎng)。所以一般是規(guī)定一個(gè)搜索深度，然后在這個(gè)深度里進(jìn)行深度優(yōu)先搜索。而此處設(shè)計(jì)的極大極小搜索算法就是一個(gè)在有限深度上找出一個(gè)當(dāng)前搜索深度對(duì)自己最有利的節(jié)點(diǎn)，從而做出一個(gè)最優(yōu)的選擇。由此也可以看出搜索深度越深評(píng)估出的值更接近真實(shí)值。

舉個(gè)例子來(lái)說(shuō)明這個(gè)算法：假設(shè)：A和B對(duì)弈，當(dāng)前到A落子，此時(shí)我們會(huì)遍歷A的每一個(gè)落子點(diǎn)，而對(duì)于A的每一個(gè)具體的落子點(diǎn)，遍歷B的每一個(gè)落子點(diǎn)，然后再遍歷A的每一個(gè)落子點(diǎn)（如圖2），如此搜索下去，直到達(dá)到搜索深度。到此就遍歷了A的所有節(jié)點(diǎn)。

圖2

但是并沒(méi)有結(jié)束，我們得選出一個(gè)最有利的點(diǎn)落子，在剛剛的遍歷中我們已經(jīng)評(píng)估出每一個(gè)節(jié)點(diǎn)分?jǐn)?shù)值，如圖2所示。在搜索樹(shù)中，A落子的點(diǎn)為極大值點(diǎn)，B落子的點(diǎn)為極小值點(diǎn)。這是因?yàn)锳落子時(shí)肯定會(huì)選出對(duì)自己最有利的點(diǎn)下棋，而B(niǎo)會(huì)選擇一個(gè)當(dāng)前局面評(píng)分最小的點(diǎn)來(lái)落子。這樣做的目的就是為了在有限深度的搜索里找出最佳的走法。

1.2 Alpha-Beta剪枝

使用alpha-beta剪枝算法可以剪去一些不必要的分支，從而提高搜索效率，是一種優(yōu)化博弈樹(shù)的搜索算法。

圖3

將alpha-beta剪枝算法與極大極小搜索算法結(jié)合起來(lái)，可以有效改善決策搜索的性能。假設(shè)：A和B對(duì)弈，當(dāng)前已通過(guò)極大極小搜索算法遍歷出部分節(jié)點(diǎn)的值，假設(shè)如圖3所示，當(dāng)前對(duì)第二行第二個(gè)節(jié)點(diǎn)的深度搜索中出現(xiàn)了-2這個(gè)值，這就表明在其之后的節(jié)點(diǎn)中即使有比-2大的值，第二行第二個(gè)節(jié)點(diǎn)的值都不可能超過(guò)-2，由于第二行以一個(gè)節(jié)點(diǎn)的值已經(jīng)為7，故可將-2這個(gè)節(jié)點(diǎn)這條路剪去，從而有效的節(jié)約了計(jì)算機(jī)資源，提高效率。對(duì)于α-β剪枝算法來(lái)說(shuō)最主要的影響是排列順序，理想排列順序下的剪枝效率和最差情況下的剪枝效率相差極大。

圖4

2 性能分析

在這個(gè)五子棋游戲的設(shè)計(jì)中，除了以上兩個(gè)算法外最重要的就是評(píng)分表的設(shè)定，一個(gè)好的評(píng)分表對(duì)結(jié)果的影響也是顯而易見(jiàn)的，在這里由于很多人已經(jīng)做過(guò)相應(yīng)的研究，有很多比較好的評(píng)分表，所以這里可以借鑒那些經(jīng)過(guò)時(shí)間檢驗(yàn)過(guò)的評(píng)分表。不同搜索深度和搜索廣度對(duì)算法的效率影響較大，在這里以搜索深度為三（由于實(shí)際并不用遍歷所有節(jié)點(diǎn)，此處設(shè)置了搜索的廣度為七）和搜索深度為五的比較為例進(jìn)行算法的性能分析。理論上，深度為五和深度為三的算法的復(fù)雜度分別為O（n3）和O（n5），但是經(jīng)過(guò)alpha-beta剪枝，算法的執(zhí)行時(shí)間要遠(yuǎn)遠(yuǎn)低于這個(gè)值。我們分別實(shí)測(cè)了兩種不同深度下算法的執(zhí)行時(shí)間，每組分別重復(fù)執(zhí)行了五次，測(cè)試結(jié)果如表1和表2所示。

以上數(shù)據(jù)表明，depth=5的耗時(shí)大概為depth=3 的4到9倍，比理論上預(yù)估的倍數(shù)49要小很多，由此可以說(shuō)明alpha-beta剪枝算法有效縮小求解搜索空間的大小，大幅度降低計(jì)算復(fù)雜度，從而縮短了執(zhí)行時(shí)間。

3 結(jié)語(yǔ)

一個(gè)好的算法可以有效地提高計(jì)算效率，節(jié)約時(shí)間。將博弈的思想應(yīng)用于五子棋問(wèn)題的求解也正是出于此目的，由以上的分析可知五子棋博弈對(duì)搜索算法的效率有很高的要求。在算法中融入博弈的思想，力求在更快的時(shí)間里找出一個(gè)均衡解，本文證實(shí)這里使用的極大極小搜索算法與alpha-beta剪枝算法結(jié)合是一種高效的評(píng)估算法，由此可以更快地找出相對(duì)較好的解決方案。

表1 深度為3時(shí)五子棋每走一步的時(shí)間

表2 深度為5時(shí)五子棋每走一步的時(shí)間

[1]嚴(yán)蔚敏，吳偉民．?dāng)?shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M]．北京：清華大學(xué)出版社，2011.

[2]王曉東．計(jì)算機(jī)算法設(shè)計(jì)與分析（第4版）[M]．北京：電子工業(yè)出版社，2012.

[3]A.Levitin著.算法設(shè)計(jì)與分析基礎(chǔ)（第3版）[M]．潘彥譯．北京：清華大學(xué)出版社，2015.

[4]B.Eckel著.Java編程思想（第4版）[M]．陳昊鵬譯．北京：機(jī)械工業(yè)出版社，2007.

Analysis of a Game Playing Algorithm for Five-in-a-Row

ZHOU Yang，DENG Li，XIE Yu
（College of Computer Science and Technology,Wuhan University of Science and Technology,Wuhan 430065）

Game playing is a mathematical method to tackle conflict or cooperation between several decision-makers.Game playing is often used to find an optimal solution to five-in-a-low.By analyzing the design and implementation of a game playing algorithm for five-in-a-row, gives thorough design thoughts,finds performance bottleneck,and also presents according solution.

Max-Min Search;Alpha-Beta Pruning;Game Theory;Five-in-a-Row

1007-1423（2017）10-0008-03

10.3969/j.issn.1007-1423.2017.10.002

鄧?yán)颍?972-），女，湖北鐘祥人，博士，研究方向?yàn)樵朴?jì)算、分布式計(jì)算

2017-01-12

2017-03-28

周洋（1994-），男，湖北黃岡人，本科生

謝煜（1993-），男，湖北仙桃人，本科生