淺談計算機圍棋中的搜索算法

袁溪

摘要：圍棋講究的是下棋者之間的博弈，這種博弈人工智能的開發也成為相關人員研究開發的的重點課題。可以說，發展人工智能，和棋類博弈有著密不可分的關系，研究發現，大部分棋類博弈人工智能的結果是不錯的， 但是圍棋的成效和突破卻不太有明顯，本文主要對計算機圍棋中的搜索算法進行了簡要分析，希望對計算機圍棋研究有所幫助。

關鍵詞：計算機圍棋；搜索算法

隨著高科技和人工智能的快速發展，但凡人工智能技術的有所突破，都是在棋類運動人工智能的研究上有所突破，通俗說，就是人類與機器人在棋類博弈之間的較量，如果機器人戰勝了人類的棋藝，那么就說明人工智能的發展進了一步。縱觀在眾多的棋類運動中，圍棋技術的發展一直不盡如人意，困難重重。從現階段圍棋程序中，研究人員發現還有很多可以提高的空間。

一、計算機圍棋的概念

在計算機圍棋運行的過程中，有四方面最主要的內容，分別是全盤評價、戰略評價、著法選擇以及搜索策略。一個優秀的全盤評價器的編寫程序難度是非常高的，目前就算是程序寫出來，但要是將其運行起來其速度還是相對較為緩慢的。所以要想在此條件下對著法選擇器進行編寫，并達到人讓人們滿意的程度還是既重要又有一定難度的。通常情況下，人類在博弈時，一般不會只算眼前的一步，相反則是會進行全面的思考，以便為下一步棋子的落腳奠定基礎，所以當我們與計算機進行博弈的過程中，計算機中的程序就會對對戰做出相應的判斷，并依據棋子的走向來計算出以下幾十步的走法，而在休戰時，也需要利用著法選擇器，從戰略大局的角度，將下一步的有利落腳點預測出來。但計算機計算出的評價結果時高時低，并不是太可靠，這時，就需要程序從不同的評價結果之間選擇一個可靠的結果。在對棋子的落法進行選擇時，需要依據相應的選擇程序從宏觀角度全方位的進行計算和預測，以保障棋子著法正確，但有時候，其選擇就會與全盤器計算的落子點大致相同，此時就需要計算機來針對其戰略目標進行思考。也就是說對于計算機圍棋，其首要任務就是要明確戰略方向，其次是棋子落腳點的選擇，最后需要搜索全盤。并依據搜索結果來對其著法進行評價，選擇出最為恰當和價值最高的落腳點。

二、計算機圍棋的搜索算法

在計算機圍棋發展的過程中，其在計算方面一共所涉及到了以下幾種方法：基礎、搜索以及學習算法等。其中不同的算法內也涵蓋了諸多小比例算法。以下主要以搜索算法為例來予以探討。

在博弈樹上，我們能夠清楚的了解到在其選擇結點若為最大值時必定實在max的方向，而最小值也通常在min方向，也就說明兩者之間是相互交換的，也是很典范的雙人對戰過程。完成這個過程的算法有很多，比如minmax算法、negmax算法、mtdf算法、alphabeta算法、failsoft算法等，這些都屬于搜索算法中的小算法， 這幾年，又出現了抽象證據搜索、證據數搜索，分解搜索等等。不管哪種算法，都是與人競技的一種圍棋程序，搜索算法也不例外，運行時，一定要有完整的計算和精確的時間對峙。同時，決定計算機圍棋搜索算法的快慢因素主要有：狀態表示、候選走法產生、確定目標狀態、確定相對優勢狀態的靜態評估函數等，因此，在使用搜索算法的同時，還需各種類的學科來完善程序，比如包含數學形態學、遺傳算法、模糊學習法等算法。

我們對經典的搜索算法的性能，通過模擬數據進行了比較，可以了解到，博弈樹不論是在最大結點數、最大分支數方面還是在最大深度、結點值方面其數量都是相對較大的。我們對每次搜索后記錄實際搜索結點數和搜索時間（毫秒）的結果進行經典搜索算法的性能進行對比，如表所示：

從比較中可以發現，alphabeta算法和failsofta雖然所用的時間不一樣，但剪枝效率最好，所用時間不同主要是因為它們的內在邏輯結構不一樣。Negascout算法由于子結點的排序完全沒有規律，是隨機的，所以剪枝效率就稍微差了些。而minmax算法和negamax算法對所有的結點都搜索了一次，而mtdf算法因為沒有采用置換表，所以造成了大量重復的搜索。

三、計算機圍棋搜索算法的發展創新

計算機圍棋搜索算法必須要緊跟時代步伐，不斷創新。

一方面要創新計算機程序的思維模式， 探討新的思維空間。例如，輸贏搜索時，可采用直接算法來對走向目標進行確定，在棋局開始時，來對棋子的價值進行分析，明確棋子舍得。以往的搜索方式大多不能又快又準的進行判斷，給出正確的指令。這就需要在程序的設計中要有常人想不到的設計，提高它的利用價值。

另一方面， 程序師對圍棋程序設計的方方面面都要考慮到。比如，在程序設計算法的過程中， 機器人與人類棋手對決的關鍵步驟，是依據走向來對棋子每一位置落點概率進行計算，并對其落點范圍加以計算，然后通過函數圖像， 做出正確的判斷。

參考文獻：

[1]張玉琪.基于靜態評估的計算機圍棋UCT算法改進研究[D].導師：熊邦書；余磊.南昌航空大學，2015.

[2]岳鵬.計算機圍棋中的算法研究[D].導師：邱玉輝.西南大學，2015.