五、權重計算

來自專欄 棋牌遊戲感悟

給定一組手牌，怎麼計算它的權重呢？我們可以把手牌切分成不同的牌型，一次出牌只能出一個牌型(Node)，手上有多少個Node就是手數。 我們可以對每種牌型，同一個牌型的每個面值，設置不同的權重。權重可以是正值，也可以是負值。

鬥地主以跑牌成功為勝利，手上多一張牌，就多一分負擔。 我們可以考慮以厭惡度來衡量每張牌型的權重。如果出完手上的牌，那麼手數為0，權重設為0；以此為基礎，面值越小，權重越低，每多一手數就再降低一定的權重。

牌型節點的權重

kOneHandPower: -150,kPowerUnit: -100,

kOneHandPower是每多一手數，就需要降低的權重，kPowerUnit是基礎厭惡值， 我們通過對不同的牌型，設置不同的bad度，最後得出牌型的權重:

self.getPower = function() { var Base = Landlord_AI.Base; var bad = 0.0; if (this.cardType == Base.kCardType_Rocket) { bad = ... } else { var top = (this.value + this.value + this.seralNum) / 2.0; bad = ... } var ret = Base.kOneHandPower + Base.kPowerUnit * bad; return ret;};

Node.getPower() 會返回每個節點的權重。對於某些大牌，權重為正，剩下的牌型，越厭惡的權重越小。

手牌權重

約定好每個節點牌型的權重後，手上的所有牌加在一起的權重也就可以計算出來啦。

假設手牌權重是p(cards)，cards里可以提取出n種不同的牌型，分別是 ， 每次提取出一種牌型後，剩下的手牌為，那麼，cards的權重可以計算為:

也就是說，每次提取的牌型權重，加上剩下的手牌權重，求最大值。還是拿 A, A, A, K, K, Q 舉例，它的權重，是下面所有權重里最大的那個，左邊的是每次提取的牌型，右邊的是剩下的手牌:

p{Q} + p{A, A, A, K, K}; p{K} + p{A, A, A, K, Q};p{A} + p{A, A, K, K, Q}, p{K, K} + p{A, A, A, Q}, p{A, A} + p{A, K, K, Q}, p{A, A, A, Q} + p{K, K},p{A, A, A, K} + p{K, Q},p{A, A, A, K, K} + p{Q},

計算耗時

根據這種演算法，C語言里，每次計算手牌的權重，17張手牌，耗時大概0.5秒，20張手牌，時間大概2~3秒，稍微有點卡頓。

一個可行的優化是，掃描手牌後，根據面值產生一個key，每次保留計算好的手牌，如果有相同key的手牌需要計算，就可以直接返回。

self.getMyPowerKey = function(obj) { var key = ""; obj.leastValue = 0; obj.maxCount = 0; for (var i = Base.kCard_Value3; i <= Base.kCard_ValueJoker2; ++i) { var num = this.cardsTable[0][i]; key += num; if (num > 0) { obj.leastValue = i; if (obj.maxCount < num) { obj.maxCount = num; } } } return key;};

與發牌的動畫效果同時，從1張手牌開始，每次加一張手牌，充分利用之前的計算結果，再計算加了一張牌的權重。這樣操作，C語言里，從19張到20張牌計算時，時間可以控制在1秒以內，卡頓不明顯。

但是，翻譯成javascript後，每次計算權重，17張牌時，幾乎在3秒左右，20張牌時，甚至是10秒，20秒(在我們的測試里，發現firefox和safari的js效率差不多，每次計算需要6秒左右，複雜一點時，10秒左右；反而號稱利用V8加速的chrome，時間更久，每次計算需要10秒多，複雜一點時，甚至可以到20秒。感覺很奇怪) ，上面的優化方式就不起作用了，有必要對手牌權重計算再優化，效率更高。

這個，在下一章詳細討論:-)

推薦閱讀：