象棋和國際象棋的電腦程序是如何設計的？

01-04

RT，微博上看到李開復老師一段趣聞，所以就想問下，象棋和國際象棋真的可以處理各種情況嗎？有沒有可能設計出可以隨意打敗職業高手的象棋或者國際象棋程序？

國際象棋打敗人類10多年前就已經由深藍完成了，近年僅是個人電腦的國際象棋軟體的等級分就已經大幅度超過人類，已經沒有人類的世界冠軍笨到跟計算機挑戰自取其辱了。原先還經常的舉辦國際象棋人機對抗賽，但是幾年前開始，為了使人機對抗賽更為有懸念，比賽規則已經改變成計算機讓F線以外的一兵了——如果對國際象棋有較為深入一點的研究，就知道一個兵是多麼大的價值。

國際象棋軟體的結構分為：

1，人機界面：讓人類能直接以國際象棋語言和計算機對話；

2，引擎：計算局面得分權重，以一定的演算法得出分值，正數則白棋優勢，負數則黑棋優勢，分數越大（越小）則白棋（黑棋）越優。世界電腦國際象棋錦標賽（WCCC）每年都舉辦，引擎的計算能力是以摩爾定律的年為尺度的，而人類大腦的計算能力是以進化的百萬年為尺度的，差距只會越拉越大，何況之中還有程序員的努力將演算法優化的因素在內；

3，開局庫：集合數以百萬計的人類國際象棋比賽的開局，使得在有開局庫的前提下，計算機可以不必計算直接走出人類認為的開局譜招。國際象棋大師們都會記住相當多的開局，但是計算機會記住幾百萬盤棋局；

4，殘局庫：由超級電腦計算好剩餘棋子的所有局面，並存儲以備調用。當局面剩餘殘局庫中所存儲的局面時，不必計算，計算機直接可以知道結果。6子以內殘局庫已經算完，7子殘局庫也已經算出大半。

認識好多國際象棋的國手，自己也對國際象棋小有研究，共同認識是：

1，開局永遠拼不過計算機，除非脫離譜招拼計算；

2，計算永遠拼不過計算機，現在引擎的計算深度已經遠遠高於人類，而且——它永遠不犯錯。而偶爾犯錯卻是人類的天性，如果能均勢和計算機進入到殘局基本就算勝利。

3，殘局計算機相對弱勢，但是殘局庫卻在不斷完善，計算機不需要局面達到殘局庫，而只需要計算到殘局庫就可以立刻知道勝利的正確走法，就像你在和一個已經知道考試答案的人拼考分一樣。

即使對手的實力略遜於你，但是如果他永遠不會犯錯往往是最鬱悶的事情，何況無論哪方面，計算機在國際象棋方面的實力都要高於人類。

未來：引擎演算法會繼續完善；摩爾定律會使得計算機的能力更加強大；殘局庫會繼續計算7子，8子，9子；開局庫雖然是基於人類，但是只要有人走出招式，就會被計算機收錄以作備用；當殘局庫與開局庫對接的時候，甚至計算機取消引擎直接就可以知道怎麼走才是最優招法了。

從國際象棋來說吧，首先要知道的三個主角是：

1.加里·卡斯帕羅夫，俄羅斯人，國際象棋前世界冠軍，代表人類敗於深藍；

2.許峰雄，台灣人，計算機專家，深藍的主要開發者；

3.深藍，美國計算機，除了下棋什麼都不會。

http://en.wikipedia.org/wiki/Garry_Kasparov

http://zh.wikipedia.org/wiki/%E8%A8%B1%E5%B3%B0%E9%9B%84

http://en.wikipedia.org/wiki/Deep_Blue_(chess_computer)

另外推薦一本書：

《「深藍」揭秘》，許峰雄自己寫的，科學性和可讀性都相當值得推薦，答案的很多內容也是基於這本書的敘述，可惜現在不在手邊，只能憑記憶寫了。曾經在很長時間裡卡斯帕羅夫都是我偶像，讀了這本書以後感覺他的形象崩壞了好多，大概就和果粉讀喬布斯傳的效果差不多。

http://book.douban.com/subject/1491268/

關於三人當年的恩恩怨怨就不說了，直接正題。

當年的深藍是一台有自閉症的超級計算機，因為它的晶元也是為下棋而DIY出來的，因為這樣可以提高在這個特定領域的計算效率。現在由於硬體的飛速發展已近不需要軟硬兼修的弈棋計算機了，只需設計軟體就可以解決問題。

弈棋軟體的基本原理是決策樹和剪枝演算法，不同程序的區別也主要在於這些演算法的細節。之前看到一個答案說枚舉法，這是絕對不行的。在一盤棋中，每一步可能的走法大概有幾十上百種（當然大部分都是無厘頭的走法，正常人想都不會想），深藍的計算能力是每秒2億步，卡斯帕羅夫在長考中能考慮到14步之後的情形，請問如果僅用枚舉法深藍要算多久？數字太誇張就不算了吧。因此必須給決策樹剪枝，即合理地忽略掉一些不合理的可能性，有很多不同的剪枝演算法，如α-β剪枝等（下面的鏈接是演算法在黑白棋里的應用，更好理解一些），這些都是是計算機科學基礎知識的應用，有很多資料可以查閱，敘述的都比我詳細，就不多說了。總之不同的剪枝演算法影響的是計算的速度和深度。

http://www.soongsky.com/computer/alpha_beta.php

剪枝演算法都需要依據一個估值函數，估值函數就是從任意一個局面到一個有理數的映射，用於評價當前局面對雙方的優劣。估值函數需要考慮到場面上的很多變數，比如現存子力以及搭配、控制的空間、兵型、強格弱格等等問題，每一個變數都要分配不同的權重，最終相加起來得到函數值。程序的一大難點就在於變數的設置和權重的分配，這個問題是許峰雄無法解決的，但他的團隊里還有國際象棋高手，變數和權重就是由棋手憑經驗來設定。程序猿大概都有這感覺，最痛苦的事情不是編程而是調試，國際象棋程序的調試更加痛苦，比找程序的語法錯誤和邏輯錯誤都要困難。需要幕後的棋手們和程序一盤盤的對弈，然後棋手們要復盤分析程序哪一步走得不好，為什麼會選擇這一步。程序不會告訴你他為什麼這樣走，你只能查看運行日誌，了解計算機對決策樹中的各個關鍵局面的評分，看它錯誤的評估了哪些局面，從中歸納出不合理的變數權重或者沒有考慮到的變數或者需要細化的變數條件。更麻煩的是，不同棋手對於同一局面的評估還可能不一樣，因為他們各有自己的風格，比如棄兵獲得的局面優勢，保守的和激進的棋手就會有不同的評價。在傳統國際象棋的理論中，你只知道各個變數的優劣，但並沒有具體的數值，個人覺得如果它的研究價值足夠大的話弄一個所謂的「計算弈棋學」領域出來也不是不可能。總之估值函數影響的是計算的正確性。

綜上可知，剪枝演算法和估值函數就是弈棋程序的兩個核心內容，弈棋程序與其說是AI還不如說是程序猿和棋手的愛情啊不智慧結晶。

除此之外還有很多簡單粗暴的方法來增加性能，比如說開局庫和殘局庫。開局是可能性最多又最難評估的階段，好在我們幾百年的對弈經驗中已經總結出來了比較完善的開局庫，有了這個就不用費腦子想頭十幾步棋怎麼走了，除非對手首先非主流。殘局庫更加兇殘，只要局面滿足了一定條件，你就把它當成DFA（確定有限狀態自動機）來看吧，就是說該死的一定會死。

最後再說說人類怎麼面對這個怪物。當年華山論劍卡斯帕羅夫是6盤以2.5比3.5惜敗深藍，但假設總共下60盤棋（當然要有足夠的休息了），那我敢打包票卡斯帕羅夫會贏。面對深藍最好的辦法就是個兩個詞：次優，反推。

次優就是說，在自己也不確定的情況下，選次優的走法。因為在程序的計算中，想得最深的是如何應對你最有可能的走法，其他可能性的計算深度會少一些，那麼變數就會更大，當它想了那麼多結果你不照它想的走，那它很多局面就白算了。開局也一樣，選擇實例更少的開局，可以讓程序儘早脫離開局庫，開始獨立思考。

反推就只有卡斯帕羅夫這樣的大師能做到了，即通過大量的對抗，猜測它的估值函數的各個權重（這當然是保密的內容），從中找到設計者沒找到的不合理之處，藉此誘使程序進入自己想要的局面。人類可以針對機器改變自己的策略，而機器不會適應對手，這也是很多科幻電影的必殺技之一吧。

但是現在，由於計算機的速度一直在增長，即使剪枝演算法和估值函數完全不改變，它的水平也會變強，借用一句老話就是，人類已經擋不住深藍們了，因此也不會再有蛋疼的人機對弈比賽了。不過好在計算機的能力（應該是）永遠不可能枚舉出棋盤上的所有可能性，否則計算出了必勝的策略，我們就只能把國際象棋像Tic-Tac-Toe一樣扔進垃圾堆了。

中國象棋通用引擎協議(Universal Chinese Chess Protocol，簡稱UCCI)，是一種象棋界面和象棋引擎之間的基於文本的通訊協議。設立中國象棋通用引擎協議的目的有：

(1) 使一個「可視化象棋軟體」可以使用不同的「核心智能部件」，這些核心智能部件稱為「引擎」，凡是遵循UCCI的引擎，都可以被該可視化象棋軟體(也稱為「界面」)所調用；

(2) 針對所有遵循UCCI的引擎，都可以開發不同的界面，使其具有不同的功能。

這樣，「可視化象棋軟體」和「核心智能部件」實現了分離，使得一部分程序設計師能專註於前者(界面)的開發，而另一部分程序設計師能專註於後者(引擎)的開發，讓中國象棋軟體的設計工作系統化、分工化，提高軟體設計效率。

目前的象棋軟體水平已超越所有職業棋手水平。

首先是基本一些走法規則，每個子賦予權重值。。某些子在局面變化後權重變化。。例如馬和炮

然後就是庫的比拼。。普通一個軟體都算的十幾層。。。『

不過也有些時候強機庫坑挖過深反吧自己埋了的。。。100%勝不可能，壓倒性那是肯定的。人也不是不能贏你花個十年八載去遍歷測試他權重不走尋常路搞不好他就無法命中了。。那麼恭喜你少年你發現他的BUG了

隨意打敗職業高手的象棋或者國際象棋程序已經有許多了，之前深藍上用的可能算是第一例。

現在的國際象棋大師也不錯。

國際象棋的情況和中國象棋有點不同，因為愛好者已經在早期就把國際象棋的殘局庫和開局庫給電子化了。

就徐雄峰在他的《深藍揭秘》中的情況來說。

開局和殘局由開局庫和殘局庫來搞定了。

這是因為開局和殘局在幾百年前已經被研究的很透了，這部分沒什麼理由再由機器來干。對頂尖人類選手來說也是如此，所以從根本上來說這裡機器和人也拉不開差距。事實上，在殘局上來說，在大型人機對弈時操縱機器的通常有一個負責人懂一點棋，在殘局進行到一定程度時在必要的時候會主動認輸或提出和局以免浪費時間。

剩下的情況下，在各個局面中根據棋盤上各個棋子的擺放計算出當個局面的勢力方面的估值，每當要走一步時，搜索對應當前局面時、局面樹上各個路徑的情況來決定走哪部好。

《現代計算機圍棋基礎》

《C/C++中國象棋程序入門與提高》

還有一本比較早的，很薄的一本，質量很好，但是名字想不起來了

大概能找到的介紹人機博弈的中文書就這三本

http://www.xqbase.com

這個網站可以了解一些象棋編程的基礎知識，甚至還有程序代碼實例。

去象棋百科全書網學一下；

象棋這裡已經有程序了，和頂尖高手是不相上下的。目前中國象棋有比如象棋旋風，奇兵等軟體，都非常厲害了。職業象棋選手現在也用軟體來練習和拆棋。

當年卡斯帕羅夫和深藍對局有個非常不平等的前提沒有考慮：體力。深藍插上電就能無限制運行，而人腦會疲勞，會喪失注意力。一天一到兩步棋應該比較合理。

已有回答都根本沒回答問題：「象棋和國際象棋的電腦程序是如何設計的？」

推薦一本《象棋對策論》，黃少龍大師寫的，這樣你就知道象棋軟體的演算法。基於數學中的博弈論分支。

現在的中國象棋軟體的演算法都是在此基礎上進行發展和優化的。

中國象棋軟體的演算法也是基於國際象棋的演算法，基本類似，只是中國象棋策略略複雜點。

象棋資源 - 象棋百科全書

這個必須推薦！～