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

賀天琦

摘 要：隨著科技的發展，人工智能的開發很受追捧，博弈已經成為人工智能研究的重點目標。他們是相互促進的關系，因為人工智能的發展在很大程度上依靠博弈的發展。雖然棋類博弈的結果令人滿意，但是在圍棋領域卻依舊不理想，沒有較大的突破。因此，近年來才有眾多的人力和物力投入到計算機圍棋研究上。

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

觀察人工智能并不長但起起落落的發展史可以發現，凡是人工智能技術的躍升，都是在棋類運動上與人類較量，進而通過機器完勝人類來證明人工智能的發展程度。但是圍棋技術的發展卻面臨了很多難題。雖然現在的科技很發達，但是通過分析可以看出，現有的圍棋程序還有待提高。對于計算機來說，在圍棋方面，比較難以處理的是其中的模糊概念，因為這些是很難用算法設計的。圍棋本身就是考驗人智力與思維的一種博弈方式，也是因為如此，開發計算機圍棋程序不僅是為了滿足人類的娛樂需求，也是在考驗設計者的思維是否活躍。所以，設計開發計算機圍棋是很有意義的一項工程。

一、計算機圍棋中的算法種類

目前的國內外市場對于圍棋的研究主要有三種方法，分別是基礎算法、搜索算法以及學習算法，每類算法里面包含的小型算法都是很多的。筆者著重研究的是搜索算法，所以簡單地介紹一下搜索算法中小的算法種類。搜索算法中包括minmax算法、negmax算法、mtdf算法等，因為搜索算法是與人競技的一種圍棋程序，需要有完整的計算和精確的時間對峙。當然，在搜索算法中，不免會包含數學形態學、遺傳算法、模糊學習法等算法來完善這道程序。

二、計算機圍棋研究

這是一個不斷追求超越的年代，不僅經濟在發展，科技也在不斷地進步。因此，對于圍棋搜索算法方面的研究也沒有滯后，有很多的創新點。

第一，不斷地提出新的思維模式，而且在不斷地完善完棋手的思維，計算機的程序在不停地探討新的思維空間。在一盤圍棋的棋局中，應該先對整盤棋局進行評估分析，經過仔細推敲來判斷出棋局的死活。當然對于棋局死活的判斷并非簡單的事情，而且對于有些棋局也不一定能夠判斷出死活。雖然如此，這種思想和入手的方式是不可缺少的，從而在棋手對決時，就給棋手造成困難，讓其在完勝的情況下由程序判斷出的時間指數。

第二，在程序的設計中，經常會有出其不意的設計。在死活搜索中，它是通過這種搜索方式，通過直接的算法方式直接地面向目標，在棋局進行過程中，計算這顆旗子是救還是舍。但是實驗發現，這種搜索方式有不足之處，就是浪費時間，不能直接地、快速地傳遞出正確的指令和判斷。這也就需要在程序中不斷改進，從而達到人性化運用，提高它的利用價值。

第三，在上面的介紹中，我們可以看到，搜索算法中還涉及數學形態學，引用了數學中的函數和計算。在程序設計算法的過程中，運用數學的函數型模式來有效計算每個旗子出現在某一位置的概率，以及棋子在落下后出現在哪一范圍內的比例比較大，這是與人類棋手對決的關鍵一項，是不可缺少的。通過直觀的函數圖像反應，然后做出正確的判斷，再根據數字明確地計算在對方落子后下一步該如何走，才能置對方于死地或者吃掉對方的棋子。由此可以看出，在計算機圍棋設計中，程序師對圍棋程序的設計考慮得很周到，這也是在不斷的嘗試和改進中的發光點。

第四，在數字算法的不斷發掘之后，又出現了復合目標搜索算法。這種算法貴在復合的方式。這種算法主要運用簡單的基本函數，通過單一的目標，對當時棋局的形式建立二維的向量，從而分析和決定棋子的下一步走向。這種算法簡單，其可用率也是比較大的。

第五，在不斷的開發和設計中，圍棋程序搜索算法的設計師也沒有讓我們失望，陸續地設計出了pemis模擬庫與定式庫學習算法。這種算法是一種對稱的棋局方式，能夠在棋局中建立黑白的不同模式，可進行旋轉和移動等，而且在使用的過程中所占的空間較小，對于圍棋程序來說是一個很好的算法設計，在有利的情況下又不浪費所占的空間。

總之，在計算機圍棋研究的過程中，不同的算法得出來的效果是不同的，在不斷地探究搜索算法和完善算法時，就會發現，棋類博弈中的圍棋的研究領域是很大的，而且具有很高的研究價值，促進了人類設計思維的創新。

參考文獻：

[1]姜啟源.數學模型[M].北京：高等教育出版社，1987.

[2]曹文君.知識庫系統原理及其應用[M].上海：復旦大學出版社，1995.endprint