對弈類遊戲的人工智能設計（2）：性能優化

一、學習算法

分析:

評估函數的引入, 為遊戲AI提供了理論基礎。

1. G(s) = a1 * f1(s) + a2 * f2(s) + ... + an * fn(s)

複制代碼

但評估函數的標明并非簡單, 其面臨的問題如下:

1)評估因素的選擇, 如何挑選, 因素是否越多越好

2)對評估因素得分的歸一化處理

3)如何進行合理的權重系數配置設定

這些都是需要思考和優化的地方, 歸納而言就是特征(因素)選擇, 權重系數學習。

當然機器學習中的随機算法: 模拟退火/遺傳算法, 也是有效的方式, 而且其更簡單, 也更容易了解, 作者将在這邊重點闡釋。

遺傳算法:

遺傳算法(GA)是模拟自然界的進化過程而實作的。"物競天擇, 适者生成"是其永恒的定律。

首先讓我們來定義個體向量(染色體):

1. 評估函數各個特征的權重系數構成權重向量 (a1, a2, a3, ..., an), 視為個體向量

複制代碼

其必須滿足的限制如下:

• 權重向量中的系數和恒為1 (a1 + a2 + 。。。 + an = 1)
• 經變異/交叉操作後, 系數權重和不為1, 則歸一化過程統一為:

1. ai' = ai / ∑ ai (i = 0, 1, 2, ..., n)

複制代碼

來定義操作子:

• 複制: 下一代拷貝上一代的權重系數向量即可
• 變異: 随機標明某個權重系數ai, 其值設定為某個(0~1)的随機值, 再進行歸一化處理
• 交叉: 標明兩個個體向量, 按機率進行對位權重系數交換, 再進行歸一化處理。

适應度函數: 個體與其他個體的互相PK, 總得分即為其适應度值。

1)初始階段: 選擇N個随機值的向量個體

2)互相PK階段: N個向量互相PK, 擷取各自的适應度值

3)進化階段: 按适應度值排序, 引入淘汰率/變異率等, 進行複制/變異/交叉操作, 誕生新的N個個體

持續疊代2), 3)兩階段, 直到選取合适的個體。

該過程能達到我們的學習需求, 當然我們可以繼續做如下優化:

• 引入陪跑員機制: 依經驗挑選精英個體, 參加PK階段, 用于評估個體的适應度, 但不參與進化(複制, 變異, 交叉)過程。
• 按适應值機率進化: 防止群體中極少數适應度高的個體被複制和遺傳而達到局部最優解的情況。

複制/變異/交叉的比率, 以及群體數, 都會影響疊代次數和收斂效果。

小結:

使用遺傳算法進行參數學習後, 可以合理地配置設定權重系數, 那事先說好的特征挑選呢? 簡而言之, 通過篩選掉權重系數近似為0的特征即可, ^_^。

二、博弈樹優化

啟發搜尋:

博弈樹本質是極大極小的求解過程, 而alpha+beta剪枝則加速該求解過程。

讓我們來建構一個簡單的alpha+beta剪枝用例:

注: 紫色代表極大值求解, 綠色代表極小值求解。

通過人工演算和模拟, 整個博弈過程, 成功地減少了3個節點的計算量的, 效果一般。

這個過程, 我們是否有優化的餘地呢? 讓我們調整下, 節點S1和S2的搜尋順序。

與調整順序之前相比, 其alpha+beta剪枝的效果提升, 砍去了一個大分支, 減少了4個節點的計算量。

從這個例子中, 我們可以清晰的看到, 對于博弈樹而言, 其alpha+beta的剪枝效果, 和搜尋順序是有一定關系的。 簡單的總結: alpha+beta效果, 對搜素的順序敏感。

于是我們找到了一個優化方向: 手機遊戲賬号買号調整可行步的順序, 并優先搜尋預期高的分支。 該技巧命名為: 啟發搜尋。 常有人借助曆史值, killer步來構造啟發函數。

1. // 負極大值算法
2. int negamax(GameState S, int depth, int alpha, int beta) {
3.     // 遊戲是否結束 || 探索的遞歸深度是否到邊界
4.     if ( gameover(S) || depth == 0 ) {
5.         return evaluation(S);
6.     }
7.     // 依據預估(曆史, 經驗)對可行步, 進行排序
8.     sort (candidate list);
9.     // 周遊每一個候選步
10.     foreach ( move in candidate list ) {
11.         S' = makemove(S);
12.         value = -negamax(S', depth - 1, -beta, -alpha);
13.         unmakemove(S')
14.         if ( value > alpha ) {
15.             // alpha + beta剪枝點
16.             if ( value >= beta ) {
17.                 return beta;
18.             }
19.             alpha = value;
20.         }
21.     }
22.     return alpha;
23. }

複制代碼

此時的核心算法結構中: 添加了可行步排序過程(sort (candidate list))。

當然該過程是有一定代價的, 在alpha+beta剪枝效果提升和排序損耗需要均衡和折中。 一般采用計算簡單的預估函數即可。

讓我們回到黑白棋AI, 我們可以簡單標明, 預估函數等同于位置表, 即P(x, y) = Map(x, y)。 (Map 為 黑白棋棋面的位置重要度矩陣), 效果斐然。

置換表:

搞過ACM的人, 都知道DP求解的一種方式: 記憶化搜尋。 本質就是把中間狀态儲存, 減少重複搜尋的一種技巧。

置換表的核心思想基本一緻: 狀态儲存, 減少重複搜尋。

但置換表的難點不在于思想, 而在于狀态儲存。

具體可以分析如下:

1)遊戲局面S本身占用空間大, 而且需要儲存的狀态S集合多, 是以需要一個轉換函數F(S) => key, (key為不長二進制串, 或一個很大的整數)

2)轉換後的key, 一一對應了某個具體局面S (沖突率很低可忽略, 或不存在)

讓我們以黑白棋來做個例子, 局面轉換為矩陣(0: 空白, 1: 黑棋, 2:白棋), 扁平化為字元串, 在借助強有力的Hash函數來轉化。

這邊展示了具體的流程, 其效果的好壞, 取決于Hash函數的選擇。

簡單采用MD5算法, 其實是可行的, 不過比較消耗CPU。 Zobrist hashing算法也是備受推薦。

和記憶化搜尋相比, 置換表對應的局面是, 隻是中間的預測節點, 是以該狀态除了本身和遊戲局面相關, 還和目前的搜尋深度有關。

是以具體代碼可修正如下:

1. // 負極大值算法
2. int negamax(GameState S, int depth, int alpha, int beta) {
3.     // 判斷狀态已存在于置換表中, 且搜尋深度小于等于已知的, 則直接傳回
4.     if ( exists(TranspositionTable[S]) && TranspositionTable[S].depth >= depth ) {
5.         return TranspositionTable[S].value
6.     }
7.     // 遊戲是否結束 || 探索的遞歸深度是否到邊界
8.     if ( gameover(S) || depth == 0 ) {
9.         return evaluation(S);
10.     }
11.     // 周遊每一個候選步
12.     foreach ( move in candidate list ) {
13.         S' = makemove(S);
14.         value = -negamax(S', depth - 1, -beta, -alpha);
15.         // 儲存S'到置換表中, 當depth更深時.
16.         TranspositionTable[S'] <= (depth, value) If TranspositionTable[S'].depth < depth
17.         unmakemove(S')
18.         if ( value > alpha ) {
19.             // alpha + beta剪枝點
20.             if ( value >= beta ) {
21.                 return beta;
22.             }
23.             alpha = value;
24.         }
25.     }
26.     return alpha;
27. }

複制代碼

總結:

啟發搜尋和置換表, 兩者都是很好的思路, 前者通過調整搜尋順序來加速剪枝效果。 後者通過空間換時間。 總而言之, 這些都是博弈樹上很常見的優化手段。 當然在具體遊戲中, 需要權衡和評估。 下一篇講講出于遊戲性的考慮, 如何進行優化和政策選擇