六、權重的優化

05-10

前文說過，計算權重時，javascript代碼耗時過多，有必要進行優化。

還是拿A, A, A, K, K, Q舉例，之前計算權重時，是計算以下所有組合的最大值:

1. p{Q} + p{A, A, A, K, K}; 2. p{K} + p{A, A, A, K, Q};3. p{A} + p{A, A, K, K, Q}, 4. p{K, K} + p{A, A, A, Q}, 5. p{A, A} + p{A, K, K, Q}, 6. p{A, A, A, Q} + p{K, K},7. p{A, A, A, K} + p{K, Q},8. p{A, A, A, K, K} + p{Q},

由於前後是對稱的，幾乎所有牌型組合都計算了多次，比如，先提取Q的1和最後提取Q的8，其實是完全一樣的。假設一張手牌可以分成1, 2, 3, 4, 5種牌型，上面計算時，計算了這5種牌型的所有排列，以下組合都會被計算到：

1, 2, 3, 4, 5,1, 2, 3, 5, 4,1, 2, 4, 3, 5,....5, 4, 3, 2, 1

但其實呢，提取牌型的先後不影響整體手牌的權重，我們完全可以定一個提取順序，規定每次提取時，先提取由最大面值的牌所組成的所有牌型，這樣，5種牌型組合只會計算5, 4, 3, 2, 1這一次；把中間計算狀態的可能性從 $P_{N}^{M}$ 變成 $Oleft( N + M ight)$ ，由於手牌的權重有緩衝，時間複雜度和空間複雜度也大大減少。像A, A, A, K, K, Q，計算手牌權重時，可能性就減少為:

1. p{A} + p{A, A, K, K, Q}, 2. p{A, A} + p{A, K, K, Q}, 3. p{A, A, A, Q} + p{K, K},4. p{A, A, A, K} + p{K, Q},5. p{A, A, A, K, K} + p{Q},

這樣計算手牌的權重，1）可以避免前後的重複計算，2）可以盡量讓手牌的緩衝得到利用，3）避免中間面值無意義的提取。

與之前相比，假設手牌權重是p(cards)，cards里最大面值的牌為v，可以提取出包含v的n種不同的牌型，分別是 $node^{1} node^{2} node^{3} ...node^{n}$ ，每次提取出一種牌型後，剩下的手牌為 $cards^{1} cards^{2} cards^{3} ... cards^{n}$ ，那麼，cards的權重可以計算為:

$p(cards) = max(node^{i} + p(cards^{i}))$

。與未優化的權重計算相比，node的數目大大減少；優化後，C語言版本的權重計算只有幾十毫秒，javascript版本的權重計算，最多(20張手牌)也只有一兩百毫秒，已經不再是AI的演算法瓶頸，可以供後續階段使用。