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

賀天琦

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

關(guān)鍵詞：圍棋；計算機；算法

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

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

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

二、計算機圍棋研究

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

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

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

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

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

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

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

參考文獻：

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

[2]曹文君.知識庫系統(tǒng)原理及其應(yīng)用[M].上海：復(fù)旦大學(xué)出版社，1995.endprint