12年前的作品──《美綠中國象棋》制作過程及算法簡介
2010-03-16 21:43
Milo Yip
閱讀(21442)
評論(57)
編輯
收藏
舉報
這個遊戲是大學大學二年級時(1998年)修人工智能課程的功課 。這個遊戲的「棋力」并不高，主要是因為沒有花時間在調整的工作上。比較滿意的部分是使用 OpenGL 做的使用者介面。本文将簡單介紹制作本遊戲的過程及當中用到的算法。你可以先下載下傳(1049KiB)試試，但現時已找不到源碼了，将來找到的話再分享。
制作過程
約在接到這項功課前的一個月，剛開始自學 OpenGL，是以便考慮利用 OpenGL 做使用者接口。
以前寫程式都是會先寫使用者接口，用來顯示程式的一些資料，之後再寫算法，遊遊戲也不例外。我利用Photoshop 及 Illustrator 繪制棋子及棋盤，再嘗試寫程式 (Visual C++ 6.0) 以立體方式顯示它們。由于太想試一試 OpenGL 的能力，在制作初期已加上了棋盤反射的效果。
之後便建構程式的重要資料結構，為每種棋子設定可行走法，有些棋子是頗麻煩的，例如炮除了可四方向移動外，還能隔子吃棋。做好了這些規則，便加入使用者介面的輸入部分，可以進行人對人的遊戲。
至于人工智能部分，首先寫最簡單的搜尋演算法──極大極小搜尋 (Minimax search) 。最初使用的評估函數(Evaluation function)隻是雙方餘下棋子的數目的差，那麼電腦會避免自己的棋子被吃，又會盡量去吃對方的棋子，可謂已有一點「智能」了。 然後着手改良搜尋方法，使搜尋的速度提高。與此同時，參考了吳身潤先生的作品，去編寫評估函數。之後更加入了二千個棋譜走法 (book moves)。
接着得到各方好友的幫助，替它進行測試，以改善評估函數。我同時制作其餘的使用者接口部分，包括左上方的選單、右方的按鈕及棋局資料顯示。
整個制作過程曆時兩個月，幸好在功課期限前的一個星期是假期，能通宵達旦去完成。
算法簡介
這裡簡介這遊戲中用到的人工智能相關的算法。
遊戲樹
如同大部份中國象棋程式，這遊戲也是從遊戲樹(Game Tree)中找出最好的走法(Move)。
在遊戲樹中，每個節點代表遊戲的一個狀态(State)，而每條邊是一個合法的走法。因為象棋是雙方輪交替下棋(紅 -> 黑 -> 紅 -> ...)，是以樹中每對相鄰的層階都是雙方各自可走的走法。下圖(來源)顯示了打井遊戲的部份遊戲樹。
在打井遊戲中，由于最多是 9 步，它的遊戲樹深度為 9，每一步之後，合法的走法變少了一個。是以，這個遊戲樹的總節點數目為 1 + 9 + 9 * 8 + 9 * 8 * 7 + ... = 986410。假設有了這個遊戲樹，我們隻要從樹中找出目前狀态的節點，再往下搜尋到任何一個獲勝的葉節點(我方勝利終局)，從目前節點走到該葉節點就是「必勝之道」，是以隻要按「必勝之道」的第一步去走就會勝利了。事實上，寫一個不會輸的打井遊戲搜尋 AI 隻需要十數行代碼左右。
最小最大搜尋
不過，中國象棋的遊戲樹是非常大的(雖然比圍棋小)，不可把整個樹儲存或搜尋至葉節點(終局除外)。是以，隻能搜到某個深度，并在該深度的節點進行啟發評估 (Heuristic Evaluation)，這估值反映了該節點棋局對我方的優勢。
由于在我方下棋的層數，我們會在每個節點選擇子節點中最大評估值，作為本節點的評估值；在對方的層數，我們會假設他選擇最小啟評估值的節點；這就是最小最大搜尋(Minimax Search)的原理。
為了簡化程式，不用按層數選擇用 min 或 max，Minimax 通常在實作的時候會采用 Negamax 方式。其原理就是每層都是取下一層結果的負值的最大值。
所有 Minimax 搜尋都可以做到安全的上下界剪枝，稱為 Alpha-Beta 剪枝 (Alpha-Beta Pruning)，這裡不詳述了。
以下是這遊戲中用到的方式:
AlphaBeta(alpha, beta, depth) {
if (depth == 0)
return Quiescence(alpha, beta);
succ = generate all move from current board
sort succ by estimate function
for each node n in succ {
makeMove(n);
x = -AlphaBeta(alpha, beta, depth - 1);
takeBack();
if (x > alpha) {
if (x >= beta)
return beta;
alpha = x;
// update principal variation here
}
}
if (no legal move)
return -10000 + ply;
return alpha;
}
平靜搜尋
當搜尋到最大深度的時候，有機會在下一步會産生很大的評估值變化(例如被吃子)。平靜搜尋(Quiescence Search)就是在最大深度的時候繼續搜尋，直至局勢變得穩定。
疊代深化
在Alpha-Beta 剪枝中，如果能盡快縮小上下界，将會減少搜尋的節點數目。這就産生了疊代深化(Iterative Deepening) 的優化方法。相對于直接搜尋深度為N的樹，先搜尋深度為i，并用其結果來優化深度為 i + 1 的搜尋。
所謂結果，是指在Alpha-Beta 剪枝發生時去記錄Principal Variation，并利用這個來排序下疊代裡産生的走法。
遊戲樹中會有很多相同的節點。為免重覆計算節點，這遊戲也使用了Transposition Table技術。
走法産生
在搜尋中，産生合法走法占很大的時間。是以，遊戲狀态的表示方式和走法産生是非常重要的。而産生的走法也用在使用者接口上:
因為沒有源代碼，我記憶中，這遊戲同時采用了"棋子->位置"及"位置->棋子"兩個數組去表達棋盤的狀态。例如車的移動要向四個方向産生走法，就可以用"位置->棋子"的數組去檢查某位置是否有其他棋子。
在開局時，會首先尋找開局庫有沒有記錄，這時候會用到一個更緊湊的棋盤表達方法。
評估方式
一個象棋的「智能」就在于其評估棋局的能力，上面提到的各種搜尋優化隻是用來加速搜尋(但在同等時限裡增加搜尋的節點也能增加「棋力」)。評估方法花費的時間也大大影響整體速度，是以必須平衡評估函數的能力及花費時間。
這個遊戲采用的靜态評估分數為(在結合其他評估時, 把這值乘以系數 10):
- 士 6
- 象 6
- 馬 13
- 車 52
- 炮 22
- 兵 2
如前文提及，隻是按棋盤餘下的棋子，按這個分數來計算評估值，已可以有不少的「棋力」。這麼簡單的評估已令到計算機懂得「将軍抽車」，我這個象棋門外漢會輸給深度4的搜尋。
我按照 [1]，加入了單獨棋子位置的分數，及一些全局分析的分數，例如:
- 車遲開步 -13
- 車在馬後 -8
- 炮在馬後 +8
- 馬路被封 -4
要獲得更好的評估方式，可以靠人的經驗、分析專業棋譜、人工智能自動學習等等方法。
回顧感想
這個程式是我比較喜歡的作品，從外表(使用者接口)到内函(人工智能)都頗滿意。而在開發過程中也真正地學會了課堂和課本的知識。
在開發這個遊戲中，我也學習了象棋的一些規則，例如勝利條件不是吃了對方的将軍，而是對手沒步可走。但平手的規則并沒有完成。
沒想到十二年後，這個程式依然可以在Windows 7上運作自如(NT/2000/XP/Vista也沒問題)，這要贊一下微軟。外表上，大概是用了比較簡單而獨特一點的設計，包括渲染和GUI等也不會感到很落後。不過，當年應該沒有使用系統時鐘，使現在棋子移動得太快，這算是一個缺憾吧。
在進入社會工作以後，我很少有機會自己一個人寫程式，程式設計的熱情也不如當天。但我會繼續在家裡程式設計，希望能回複一點當日的熱血。
參考
- [1] 吳身潤, 人工智慧程式設計：象棋, 旗标出版股份有限公司, 1996.
- [2] George F. Luger, William A. Stubblefield, Artificial Intelligence: Structures and Strategies for Complex Problem Solving 2nd Edition, The Benjamin/Cummings Publishing Co. Inc., 1992.
- 分類 人工智能