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

周洋，鄧莉，謝煜

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

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

周洋，鄧莉，謝煜

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

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

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

0 引言

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

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

圖1

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

1 主要算法

1.1 極大極小搜索算法

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

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

圖2

但是并沒有結(jié)束，我們得選出一個最有利的點落子，在剛剛的遍歷中我們已經(jīng)評估出每一個節(jié)點分數(shù)值，如圖2所示。在搜索樹中，A落子的點為極大值點，B落子的點為極小值點。這是因為A落子時肯定會選出對自己最有利的點下棋，而B會選擇一個當前局面評分最小的點來落子。這樣做的目的就是為了在有限深度的搜索里找出最佳的走法。

1.2 Alpha-Beta剪枝

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

圖3

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

圖4

2 性能分析

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

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

3 結(jié)語

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

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

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

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

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

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

[4]B.Eckel著.Java編程思想（第4版）[M]．陳昊鵬譯．北京：機械工業(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

鄧莉（1972-），女，湖北鐘祥人，博士，研究方向為云計算、分布式計算

2017-01-12

2017-03-28

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

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