中國象棋AI實現?

12-30

和我弟下中國象棋，老是輸給他，想到李開復老師在CMU設計演算法贏了真人，所以打算用C++編寫一套AI演算法，然後用人機博弈贏他。上網查了了解到alpha-beta剪枝等一些實現方法，只是我對編寫這個方面的東西完全沒有經驗，所以想找知乎上的前輩請教一下，指指路。
我個人現在是大一數學系在讀，對編程感興趣，自學C++ing，《c++ primer》還在讀，也參加學校ACM培訓。雖然編程能力和NOI上來的大牛比還是有很大差距，但我正花時間下去追趕，個人計劃大二前能把這個象棋的AI比較好的實現出來，然後約我弟人機博弈。
//我想的機器就是用我手上這台筆記本（CPU I7u/ram 8G），當然，如果演算法不夠好的話，我也可以去租一台計算機來用（這個待定）。

鑒於題主是初學者，我就不推薦什麼開源項目讓你自己去讀代碼了，因為我覺得理論學習更重要。主要說一下學習路線吧。

先讀一下《Artificial Intelligence A Modern Approach》第5章 Adversarial Search，知道一下對抗搜索的原理（其實就是Min-Max Search），非常簡單，但後面的優化演算法都是基於這個的。之後再看Alpha-Beta pruning，先理解演算法直到可以在紙上自己畫出某個example 的裁剪過程就可以了。之後建議先寫個五子棋程序，這個東西難度適中，既可以練練怎麼實現Alpha-Beta pruning，又不必糾纏太多規則上的細節。一方面幫你熟悉了怎麼解決書本上沒有提到的技術細節，比如標準的Alpha-Beta pruning 函數是返回Value 的，但你要得到下一步棋怎麼走需要它返回一個Action，對於新手這個可能沒那麼容易想到。另一方面也幫你思考一下如何優化程序和下一步改進程序的重點，比如書上提到的Cutting Off 和Evaluation Function（其實五子棋和象棋最大的不同就是這個Evaluation Function）。

然後，隨著你探索更聰明的AI 的過程你就會發現其實Alpha-Beta pruning 的效率非常差。上學期我做了個課程作業就是用Common Lisp 實現了一個Web 版的五子棋：fiigii/gomoku-CommonLisp · GitHub 我在測試的時候發現，Alpha-Beta pruning 在搜索狀態空間時差不多每100個狀態才能減除5至8個狀態，再加上我用Common Lisp，每一步棋總要卡個幾秒鐘，實在不能忍受……然後有了實現能力你就可以去學習更高級的裁剪演算法了，比如Principal variation search。或者《Artificial Intelligence A Modern Approach》第五章後面也提到了一些改進策略比如history heuristic、order of choice 等等，夠你研究一下了。

除此之外還有一個很好的資料是《Paradigms of Artificial Intelligence Programming》的第18章帶你親手實現一個黑白棋程序，不過也是用Common Lisp 的。

做完這些之後，我相信你只要再看看象棋規則以及具體的Evaluation策略，不看別人的代碼自己徒手實現一個就是很輕鬆的事了。

P.S. 鑒於你還在看《C++ Primer》我建議你在學習過程中再學點數據結構，起碼STL里的常用容器的應用場景得瞭然於胸，要不然書上的偽代碼怎麼翻譯成程序都是個問題……

象棋巫師用的ai（引擎）是開源的，可以參考一下。中國象棋ai已經有很多現成的基礎理論了，當然，也可以造輪子

和其他各種棋類AI一樣，就是搜索演算法+評估函數，只是中國象棋比國際象棋規則複雜，每一局的move可能性比國際象棋要多得多，造成1.搜索深度受限，2.局勢評估異常艱難。

基本上中國象棋的搜索演算法和國際象棋搜索演算法差異不大，各種優化方法如alpha-beta剪枝，蒙特卡羅什麼的是非常成熟的。而評估函數就和國際象棋差異很大，把中國象棋棋局的局勢量化有太多參數要考慮，簡直令人髮指。

這兩塊演算法寫出能跑的不難，寫出能PK過自己的AI也不難，但要真的要寫好是個巨大的坑，要量化自己演算法的好壞就是和開源演算法進行對弈，在相同開銷下比勝率，或者勝率相同比開銷。

時隔一年，希望我的回答對題主（或者後來人）有幫助。

首先推薦一個博客：博弈與演算法實現

然後推薦一個網站：計算機博弈 - 象棋百科全書

要寫一個AI？很簡單。

1.熟悉一門編程語言。（這個比較寬泛）

2.掌握基本演算法/數據結構的概念和用法。

3.閱讀「一個博客」。這時候你大概明白用什麼演算法實現/優化搜索部分了。但這遠遠不夠，這只是AI的「思維邏輯」。

4.閱讀「一個網站」。這時候你大概明白，怎麼構建AI的「知識」。

5.做一個簡單的Demo（你下不過的那種）。如果你不是天才，在這個過程中會遇到種種問題，而導致這些問題的根本原因就是你壓根沒理解「一個網站」和「一個博客」在說啥。所以你需要看很多遍。

6.你發現，因為你對象棋的理解很有限，所以你的估值做得一團糟。你開始研究象棋。

7.你可以在象棋上碾壓你弟了，但你對你的半成品AI耿耿於懷。

8.你繼續研究AI。

9.你變成了一個程序員。

10.你弟找到了女朋友。

11.你越來越胖，寫了一個AI當女朋友。

（逃

乾貨：

http://chessprogramming.wikispaces.com

http://www.aiexp.info

私貨：

我的五子棋AI Chis

https://github.com/ChisBread/Chis

完成度尚可，正在逐步完善。

開源協議是MPL 2.0，在遵守協議的前提下可任意使用。

I helped you to Google it, and find [this page](chessprogramming), might be helpful to you.

去年年底剛寫過一個，課程作業，所以AI的實現比較naive，你可以參考下。

IntelligentChineseChessSystem/src/alogrithm at master · geeeeeeeeek/IntelligentChineseChessSystem · GitHub

主要思路就是模仿人對棋局態勢的判斷，利用計算機速度快的優勢迭代多層，確定一個最優的著棋方案。

相對來說搜索比較容易實現了，模擬一下博弈樹，極小極大搜索 + 剪枝，其實一個DFS就完成了。每一步有那麼多子可以走，每一個子有那麼多步可以走，如果要思考很多層，那博弈樹就太大了。你說的alpha-beta剪枝就是為了跳出一些不必要的枝節，這樣就可以多搜幾層。

其實象棋AI的瓶頸在於估價函數的實現，現在通行的做法包含固定子力值、棋子位置值、棋子靈活度值、威脅與保護值、動態調整值（我的AI只包含了前兩部分）。這些函數需要通過遺傳演算法等更高級的演算法學習得到，以及函數之間的係數也是很重要的。

不過速度和經驗又是成反比的，如果估價太複雜也會影響到演算法的效率。

至於how-to，請使用Google搜索，中英論文都一大堆。

你可以先寫一些簡單的，比如tic tac toe，知道基本思路

然後稍難一些的五子棋（重估值），黑白棋（重優化）

然後就可以上象棋了

假設你已經會寫Minimax和alpha-beta剪枝。。然後可以看Monte Carlo tree search。

更高級的方法就是機器學習了。。Tom Mitchell的Machine Learning一書第一章就講了個訓練下棋AI的例子。機工有這書的翻譯版，題主可以找來看。

推薦學習路線：

一、了解象棋AI的整體框架和基本原理

建議通過象棋百科全書網站的計算機博弈部分學習。也可以到國外介紹國際象棋AI技術的網站學習。

二、了解頂尖水平棋軟的思想方法

棋軟"縱馬奔流"在2003年獲得奧林匹克電腦象棋比賽冠軍，其開發者塗志堅的論文《電腦象棋的設計與實現》介紹了軟體使用的技術。

棋軟"ELP"在1990、2011、2012年都獲得了奧林匹克電腦象棋比賽冠軍，其開發者許舜欽團隊的英文論文《Computer Chinese Chess》介紹了ELP和象棋世家兩款軟體使用的技術。

棋軟"棋天大聖"在2006年獲得浪潮杯首屆中國計算機博弈錦標賽冠軍，其開發者王驕的論文《中國象棋計算機博弈關鍵技術分析》介紹了大量AI技術，但並沒有對"棋天大聖"使用了什麼技術做太多的介紹。

當然，如果你的目的是快速實現一個很厲害的棋軟，你可以通過修改頂尖的開源國際象棋軟體來實現。

我自己的開源象棋ai項目，基於非遞歸的alpha beta剪枝演算法，使用了歷史搜索記錄緩存表。

http://git.oschina.net/quancs/ChineseChess

請參考我在這裡的回答：

用Python寫一個中國象棋AI？ - 知乎用戶的回答

希望對你會有所幫助，也可私信與我交流。

我在大學期間用android java寫過一個象棋機器人，地址是：MKeng象棋機器人，我當時在多普達上測試通過，智力還行雖然我現在覺得很爛（還有優化空間，殘局庫還存在一些bug，以及我自學幾天android寫的程序，所以幾乎沒有優化）。我個人比較推薦象棋巫師 - 象棋百科全書，演算法是開源的，有C++等版本。