[發明專利]一種圍棋人機對弈軟件中圍棋落子點的選擇方法

無效

• 申請號: 200910071894.2
• 申請日: 2009-04-27
• 公開（公告）號: CN101571892A
• 公開（公告）日: 2009-11-04
• 發明（設計）人: 姚斯宇
• 申請（專利權）人: 姚斯宇
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 哈爾濱市松花江專利商標事務所
• 代理人: 張宏威

技術領域

本發明涉及一種圍棋人機對弈技術，具體涉及到計算機和人類對弈來下圍棋的系統中，計算機選擇落子點的方法。

背景技術

隨著人類幾十年來的不斷努力，計算機已經在眾多棋類中擊敗人類頂尖高手，但由于圍棋本身復雜度極高，變化無窮，戰術運用極其靈活，而且下棋多靠模式識別的特點，使得圍棋變成了計算機科學的“阿喀琉斯之踵”。

圍棋是一種源于中國的智力游戲，先介紹一下圍棋的基礎知識：

棋子的氣，是指：一個棋子在棋盤上，與它直線緊鄰的空點是這個棋子的“氣”。棋子直線緊鄰的點上，如果有同色棋子存在，則它們便相互連接成一個不可分割的整體。它們的氣也應一并計算。棋子直線緊鄰的點上，如果有異色棋子存在，這口氣就不復存在。

提子，是指如一塊棋所有的氣均被對方占據，便呈無氣狀態，將被提掉，稱為“提子”。若下子后，雙方棋子都呈無氣狀態，應只提取對方無氣之子。

禁著點，是指棋盤上的任何一子，如某方下子后，該子立即呈無氣狀態，同時又不能提取對方棋子，這個點叫做“禁著點”，禁止落子。

禁止全局同型，是指禁止該局棋曾出現的局面再次出現。

終局勝負判斷，是指在終局時，根據中國規則，先將死子撿掉，再把目和子數加起來，看看是否達到個子(黑棋應贏的目數)或個子(白棋應贏的目數)，并決定勝負。

圍棋為什么這么難呢？圍棋是棋類中最復雜的一項(參見文獻：施遙《人工智能在圍棋程序中的應用》復旦大學附屬中學)，圍棋獨特的復雜性即：

1.圍棋的模糊性：棋型過多致使計算機無法識別出準確招法；

2.圍棋的反復性：僅圍棋中存在提子和打劫這兩種極其復雜的情況，人類都無法很準確地指出正著所在，在計算機程序上的實現則更為復雜而繁瑣；

3.圍棋的靈活性：圍棋中存在大量高深的棋理和靈活戰術，計算機無法“理解的。而且圍棋中戰略的目的性沒有其他棋類明顯，很難對每個子的價值進行評估。

人類圍棋高手下棋時的“感覺”也是目前計算機無法“領會”的。

基于上述三種獨特的復雜性，圍棋中很多著手無法被抽象成機械化的算法。現有的圍棋人機對弈軟件只能采用近似的數學方法或模擬方法，致使圍棋人機對弈軟件上的算法無法發揮出在其他棋類人機對弈軟件上的效果。

現有的人機對弈軟件的棋力最高水平不過是業余2段，常用的有以下四個圍棋人機對弈軟件：

1、法國的Sylvain?Gelly等編制的Mogo，是第一個使用UCT為基礎的電腦程式，它的落子特性為：沒有布局，但是擅長近距離接觸戰，也擅長收官，但是該程序的暈著過多，經常漫天落子，不走棋理，棋感差。

2、日本的Hiroshi編制的Aya，是亞洲最強的人機對弈軟件，其功能較全，但定式下法混亂，落子速度慢。

3、中國的陳志行編制的手談，在90年代一直占據著圍棋人機對弈軟件世界第一的位置。它采用了大量圍棋知識作為模式庫，但戰斗力差，算路不深。后添加搜索算法，而效果不明顯，一旦局面復雜，軟件棋力將大幅下降。

4、美國的開源軟件GNUGo的軟件引擎已經發展二十年，經過無數開源軟件開發者的不懈努力和創新，目前該軟件的實力不俗，棋風正派、大氣，落子穩定，但是其落子經常脫離主戰場，對全局的把握能力較差。它對世界計算機圍棋領域的貢獻永不會被人們所遺忘。

蒙特卡羅算法(以下簡稱MC算法)自06年開始被各個軟件所使用，它使軟件的戰斗力達到了一個新的高度。但MC算法基于概率論，存在很大的不確定性，而圍棋是錙銖必較的，純基于MC算法的程序雖然可以大量模擬對局，但是程序會漫天落子，毫無章法(文中稱為MC缺陷)，后來Mogo雖然加入了一定的圍棋知識和棋理來輔助落子(參見文獻Sylvain?Gelly《Introducinghuman?expertise?and?diversity?in?Monte-Carlo?Tree-search》EWRL?2008和谷蓉，劉學民，朱仲濤，周杰《一種圍棋定式的機器學習方法》清華大學自動系北京100084)，很多情況下，程序仍然欠缺棋感。不過，就算缺陷十分明顯，Mogo仍然是世界上最擅長復雜局面戰斗的程序。

蒙特卡羅的不穩定性是不可避免的，但它有一個可以避免的缺陷，即MC缺陷，這個缺陷會讓程序經常走出送子型打吃的走法，尤其是在隨機模擬數量大的程序中，程序一旦模擬到打吃等情況，對方脫先，已方下一手再提子會嚴重影響到MC算法的結果，這會使所有打吃的子節點的分值大大增加，而在實際對弈中，打吃常常是送子的表現，是程序應該避免的。