基于模式匹配和靜態(tài)評估的計(jì)算機(jī)圍棋布局問題求解算法

余磊 陳涵

摘要：提出了一種基于模式匹配和靜態(tài)評估的計(jì)算機(jī)圍棋布局問題求解方法，包括候選棋步的產(chǎn)生、量化以及最佳棋步的確定等;并據(jù)此實(shí)現(xiàn)了一個圍棋布局問題求解程序BeginGame。通過測試，職業(yè)棋手評估BeginGame處理布局問題的水平約為業(yè)余1段，其棋力完全可以應(yīng)用于當(dāng)前的圍棋對弈軟件中，在計(jì)算機(jī)博弈、人工智能、游戲軟件的研究中具有實(shí)際應(yīng)用意義。

關(guān)鍵詞：模式匹配;靜態(tài)評估;布局問題;圍棋

中圖分類號：R318.08 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2018）12-0113-01

1 候選棋步的產(chǎn)生和量化

布局時的行棋目標(biāo)大致可以分為“占據(jù)空角”、“完成定式”、“掛角”、“拆邊”、“模樣”（包含“形成己方模樣”和“破壞對方模樣”）等5類。根據(jù)上述分類，BeginGame的數(shù)據(jù)庫相應(yīng)預(yù)設(shè)了一些由圍棋的棋理和棋形而來的模式。實(shí)驗(yàn)表明，在模式的幫助下，程序可以較為容易的尋找出布局階段的候選棋步。候選棋步越多，找尋到最佳棋步的概率也越大;但由于在實(shí)際對弈時思考時間有限，因此為了能夠準(zhǔn)確量化，候選棋步必須越少越好。根據(jù)大量的實(shí)戰(zhàn)經(jīng)驗(yàn)，BeginGame設(shè)定候選棋步的數(shù)量為10-20步。

1.1 占據(jù)空角棋步的產(chǎn)生和量化法則

圍棋中，占據(jù)空角的方法一般有：三·三、小目、星位、目外和高目（五·五，超高目等特殊的占據(jù)空角的方法由于使用較少，且后續(xù)變化不易掌握，因此將其舍去）。

由于占據(jù)空角的形式變化較少，因此我們采用模式匹配來進(jìn)行量化。在BeginGame中，占據(jù)空角的量化值如表1所示。

從表1可以看出，不論三·三、小目、星位、目外還是高目，每一種占據(jù)空角棋步的價(jià)值完全相等（都為20目），這表明占據(jù)空角的形式?jīng)]有優(yōu)劣，只是每種棋步的側(cè)重點(diǎn)不同（側(cè)重實(shí)空或外勢）。根據(jù)表1，我們能獲得占據(jù)空角棋步的對內(nèi)和對外影響值，這對于將來選擇偏重實(shí)空還是偏重外勢的棋步至關(guān)重要。

1.2 定式中棋步的產(chǎn)生和量化法則

古今中外的棋手，經(jīng)過多次對弈實(shí)踐，對于角上著子，逐漸形成的一些被公認(rèn)比較妥善的程式，被稱之為“定式”。定式是棋手們長期的實(shí)踐和理論上的歸納，一般是默認(rèn)的最佳并且雙方都能接受的走法。

為了給中盤戰(zhàn)斗留出盡可能多的思考時間，我們需要在布局階段盡可能快的做出決策;因此，在角部的戰(zhàn)斗中，我們通常選擇定式的著法。我們創(chuàng)建定式樹，采用搜索法來解決定式問題。通過搜索當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)，我們可以預(yù)知下一步能有多少種選擇。這些子節(jié)點(diǎn)的位置就是定式的候選棋步。我們將定式中棋步的順序輸入數(shù)據(jù)庫，并賦以相應(yīng)的量化值。因此，我們可以通過搜索定式樹中的節(jié)點(diǎn)來獲得量化值。

1.3 拆邊棋步的產(chǎn)生和量化法則

拆邊是指棋子由角向邊的展開過程。BeginGame中，我們采用模式匹配來產(chǎn)生候選棋步。模式匹配分為以下兩種：

（1）根據(jù)一些圍棋諺語（例如：“立二拆三”、“立三拆四”等等），獲得相應(yīng)模式;（2）圍棋中，如果一條邊上的兩個空角已經(jīng)被占據(jù)，那么這條邊上離兩個角上的子距離相等的點(diǎn)通常都是最佳棋步點(diǎn);再根據(jù)角部棋子的位置和顏色，確定最佳棋步點(diǎn)在三線還是四線。

量化拆邊棋步的過程主要遵循以下原則：

（1）計(jì)算拆邊棋步的對內(nèi)影響值;（2）計(jì)算拆邊棋步的對外影響值;（3）如果此棋步能削弱對方棋塊，計(jì)算削弱的價(jià)值;（4）計(jì)算對方占據(jù)此點(diǎn)的對內(nèi)影響值，對外影響值，和對我方棋塊的削弱值;（5）拆邊棋步的量化值為 。

1.4 模樣棋步的產(chǎn)生和量化法則

模樣分為形成己方模樣和破壞對方模樣，其中最主要的棋步是：“一間跳”、“二間跳”、“小飛”、“大飛”等等。形成己方模樣或破壞對方模樣的棋步往往出現(xiàn)在棋盤中央，關(guān)乎雙方此消彼長的重要一手通常在黑白棋陣之間的位置（圍棋術(shù)語中稱之為“急所”）。憑借上述圍棋規(guī)律，我們能通過運(yùn)用模式匹配的方法來找到候選棋步。

在量化模樣棋步時，我們同樣考慮棋步的對內(nèi)和對外影響值，量化方法與拆邊棋步的量化法則類似。模樣棋步的量化值。

2 最佳棋步的確定

根據(jù)圍棋本身的規(guī)律和實(shí)驗(yàn)經(jīng)驗(yàn)，BeginGame在實(shí)戰(zhàn)中優(yōu)先考慮占據(jù)空角候選棋步;其次考慮定式候選棋步;如果沒有占據(jù)空角候選棋步或定式候選棋步，則再比較拆邊候選棋步、模樣候選棋步的價(jià)值，從中選出價(jià)值最高的棋步作為最佳棋步。

3 結(jié)語

本文提出了一種基于模式匹配和靜態(tài)評估的計(jì)算機(jī)圍棋布局問題求解方法。根據(jù)棋局狀態(tài)和行棋目的，將候選棋步分為占據(jù)空角、定式、拆邊、模樣棋步等四部分;采用模式匹配的方法解決占據(jù)空角和定式問題，采用靜態(tài)評估算法解決拆邊和模樣問題。實(shí)驗(yàn)結(jié)果表明，BeginGame在布局問題的處理方面具備業(yè)余1段的水平，它已應(yīng)用于計(jì)算機(jī)圍棋程序CognitiveGo中，并取得了較好的實(shí)戰(zhàn)效果。

參考文獻(xiàn)

[1]周明明，高航，趙國安.UCT算法在計(jì)算機(jī)圍棋中的應(yīng)用與改進(jìn)[J].數(shù)據(jù)采集與處理，2012，27（S2）：330-335.

[2]陳磊.計(jì)算機(jī)圍棋領(lǐng)域概念網(wǎng)的設(shè)計(jì)與實(shí)現(xiàn)[D].北京郵電大學(xué)，2010（2）：1-4.

[3]王可佳，劉知青.通過圍棋博弈棋譜分析進(jìn)行棋手水平判定[J].中國科技論文在線，2009：1-12.

Algorithm for Solving Computer Go Layout Problem Based on

Pattern Matching and Static Evaluation

YU Lei， CHEN Han

（Key Laboratory of Nondestructive Testing Technology， Ministry of Education，

Nanchang Hangkong University， Nanchang Jiangxi 330063）

Abstract：A method for solving computer Go layout problems based on pattern matching and static evaluation is proposed， including the generation， quantification and determination of the best moves. The realization of a Go layout problem solving program BeginGame is realized. Through testing， the professional chess player evaluates the level of BeginGame's layout problem is about amateur 1 segment， and its chess power can be applied to the current game of chess game. It has practical application significance in the research of computer game， artificial intelligence and game software.

Key words：pattern matching;static evaluation;layout problem;Go