中國象棋“深藍(lán)”含苞待放

1、“深藍(lán) ” 含苞待放野生的魚從接觸計算機(jī)時起，我就有一個夢想，自己設(shè)計出一個頂級的中國象棋或圍棋人機(jī)對弈系統(tǒng)，達(dá)到甚至打敗特級大師、專業(yè)九段的水平。那時由于無知者無畏，不知深淺。現(xiàn)如今已在此道潛心修行了二十多載，驀然回首，夢想未果，悵然若失。今放眼環(huán)視，悲喜交加，個中情愫，現(xiàn)一并道來，以慰平生，以饗棋朋博友。你可能會問我，早過不惑之年了，此種情結(jié)為何經(jīng)久不散呢？我想主要有一下三個原因吧。一則它確實(shí)能滿足我作為超級棋迷的實(shí)際需要；二來想發(fā)揮自己軟件工程專業(yè)所長找些成就感；再者也是為我國棋類事業(yè)盡微薄之力吧。當(dāng)前三大棋國際象棋，中國象棋，圍棋人機(jī)對弈算法中以國際象棋最強(qiáng)，中國象棋次之，圍棋最弱。造

2、成此格局的主要原因很多，如普及程度，科技水 平及科研經(jīng)費(fèi)，復(fù)雜度不同等。以復(fù)雜度為例，具體如下表： 表 幾種棋類的空間復(fù)雜度及樹的復(fù)雜度對比 ( 表中的數(shù)字為搜索的復(fù)雜度的自然對數(shù)值 )棋類棋盤大小 空間復(fù)雜度樹的復(fù)雜度 TOC o 1-5 h z 國際象棋8 X850123中國象棋10 X 952150圍棋19 X 19172400可以看出，中國象棋的狀態(tài)空間復(fù)雜度和博弈復(fù)雜度都比國際象棋要高，圍棋就更高，顯然這是對中國學(xué)者提出的嚴(yán)峻挑戰(zhàn)。所幸的是，經(jīng)過半個世紀(jì)的發(fā)展，及計算機(jī)界大師積極的參與，國際象棋的人機(jī)對弈已經(jīng)得相當(dāng)成熟。早在上世紀(jì)， 及時代的奠基人美國的香農(nóng)(1950)與被稱為計算機(jī)

3、科學(xué)之父、 人工智能之父的圖靈(1953)提出了對象棋博弈編程的方案，成為機(jī)器博弈的創(chuàng)始人。系統(tǒng)的博弈論的研究是從國際象棋開始的，被稱為 計算機(jī)之父”和之父”的馮諾依曼通過對兩人零和一類博弈游戲的分析，提出了極大極小值定理，這也是博弈論產(chǎn)生的第一個里程碑。國際象棋是影響最大研究時間最長投入研究精力最多的博弈項目，成為計算機(jī)博弈發(fā)展的主線。具體的國際象棋的編程可以通過優(yōu)秀的評估函數(shù)和修剪搜索樹解決， 國際象棋軟件的協(xié)議UCI(Universal Chess Interface 即通用象棋接口 )就一直在發(fā)展和完善，并已逐步成為國際象棋程序設(shè)計的標(biāo)準(zhǔn)，在此基礎(chǔ)上的國際象棋程序自動對弈比賽也在大規(guī)模

4、地開展， 1997 年 IBM 公司的超級計算機(jī)深藍(lán)戰(zhàn)勝了國際象棋世界冠軍卡斯帕羅夫 ，成為人工智能領(lǐng)域的一個里程碑。我想，對于我們中國象棋，兩者的相似度又很高，我們完全可以借鑒其經(jīng)驗，通過適當(dāng)?shù)母脑焐踔涟l(fā)展，早就我們自己的中國象棋“深藍(lán)” 。近年來，我們欣喜的看到，我們的中國象棋人機(jī)博弈的發(fā)展非常迅速，如作者趙明陽設(shè)計的象棋奇兵， 在家用普通PC 上達(dá)到了中國象棋業(yè)余高手水平， 在高性能計算機(jī)上達(dá)到了中國象棋特級大師水平。軟件特征：棋盤表示基于 Bitboard ；規(guī)則判斷；后臺思考；置換表；迭代深化；開局庫；歷史表；空著裁剪；學(xué)習(xí)文件；PVS 搜索算法； LBR 裁剪算法。榮獲第十屆奧林匹

5、克中國象棋電腦軟件大賽冠軍， 2006 年 8 月 “浪潮杯 ”首屆中國象棋人機(jī)大賽中一勝一和中國象棋特級大師卜風(fēng)波。另外東北大學(xué)開發(fā)的棋天大圣，榮獲2006 年和 2007 年的世界冠軍，其研發(fā)小組深入研究了中國象棋計算機(jī)博弈的特點(diǎn)，研究了中國象棋計算機(jī)博弈狀態(tài)空間表示、搜索算法、數(shù)據(jù)結(jié)構(gòu)、審局函數(shù)、開局庫、殘局庫等關(guān)鍵技術(shù)，建立了數(shù)字化的象棋博弈模型，開發(fā)出了可以達(dá)到人類特級大師水平的中國象棋博弈軟件 “棋天大圣 ” 。有力開展了計算機(jī)博弈的普及活動，實(shí)實(shí)在在地推動了中國計算機(jī)博弈的發(fā)展進(jìn)程等。盡管中國象棋計算機(jī)博弈已經(jīng)取得了很好的成績，但是畢竟離戰(zhàn)勝世界冠軍還有一定的差距，同國際象棋相比

6、也遜色不少，中國象棋有它自己獨(dú)特的特點(diǎn)，如大的棋盤，不同的子力和走法規(guī)則等，要做的工作還有很多，我認(rèn)為主要應(yīng)在以下方面做好研究：棋盤的表示不象國際象棋剛好用 6 位位圖表示，還沒有統(tǒng)一高效的方法；局面采用 64 位 HASH 函數(shù)表示，高效唯一； 開局庫的高效檢索優(yōu)化；尤其是核心算法博弈樹的a -B剪枝優(yōu)化，引進(jìn)最新的遺傳變異算法，BP神經(jīng)網(wǎng)絡(luò)技術(shù)，自適應(yīng)學(xué)習(xí)方法等，尤其是后者；評價函數(shù)需要快速科學(xué)精準(zhǔn)；殘局庫的完備性等。令人欣慰的是，以上方面國內(nèi)有許多業(yè)內(nèi)人士已在開展了研究，其中也有不少碩士博士加盟，如大連交通大學(xué)的鹿榮碩士，提出了一種新的混合博弈樹的搜索算法， 其基本搜索算法如： PVS

7、搜索、 靜寂搜索等； 高級搜索算法為 1) 歷史啟發(fā)；2)殺手啟發(fā)；3) 迭代深化； 4)迭代深化，它能夠根據(jù)搜索所需要的時間選擇搜索深度； 5) 改進(jìn)的置換表等。同時也設(shè)計了一種新的評估函數(shù)在中國象棋開局庫中的應(yīng)用，結(jié)合了利用共軛梯度求解二次最優(yōu)的方法，盡可能的保證系統(tǒng)在開局階段便處于優(yōu)勢，并使開局庫具有一定的自學(xué)習(xí)能力，提高了博弈水平。哈爾濱工程大學(xué)的碩士王一非的具有自學(xué)習(xí)功能的計算機(jī)象棋博弈系統(tǒng)的研究與實(shí)現(xiàn)工學(xué)碩士學(xué)位論文，其中主要運(yùn)用神經(jīng)網(wǎng)絡(luò)結(jié)合時間差分算法的方法來代替?zhèn)鹘y(tǒng)的線性估值函數(shù),利用強(qiáng)化學(xué)習(xí)的方法，使象棋程序具有自學(xué)習(xí)的功能 ,使計算機(jī)在對弈的過程中不斷地學(xué)習(xí)。 這是一種非常有意義的嘗試 。我認(rèn)為這也是以后人工智能研究的方向，也是攻克圍棋博弈算法的