鬥地主之用蟻群演算法整理牌型：幾個關鍵點的處理

牌型選擇和其它問題的差異性分析

蟻群演算法是由仿生螞蟻尋食發展而來，所以其很自然的就以尋找最短路徑的旅行家問題為研究對象。而旅行家問題有幾個特點：

- 每一步都是從當前所在城市的所有鄰接城市中挑選下一步的目標城市

- 演算法的判優指標（即解評分）是總距離最短

- 單步擇優的啟發性信息是兩鄰接城市之間的路徑長度

- 信息素就是本輪次最優解的路徑總長度/路徑中的城市數

對照我們的牌型選擇問題，就存在一定的差異了：

- 演算法的判優指標（即解評分）是各牌型累加調整後的剩餘牌手數，越小越好

- 單步擇優的啟發性信息是當前牌點可組成的牌手的牌力估計（概率不能為負數，所以是剩餘牌手數的一個變換，一般只要能大致反映不同選擇的價值即可）

- 信息素是每輪次最優解評分/解的牌手數

我們在上一講中談到了我們在構思如何解決問題時，首先要完成在想像世界中的問題轉換。所以我提出了用剩餘牌手數這個自造的概念來衡量各牌手的價值。而更宏觀的，我們也要對牌型選擇問題進行轉換，通過上面的對比，我們可以看出牌型選擇問題和旅行家問題是截然不同的（即解的構造方式完全不同），那我們該用什麼樣的模型來構思牌型選擇問題的解決方案呢？！

為了在遇到問題時我們能快速的構思出有效的解決方案，我們需要廣泛的學習，以積累自己的見聞。這樣當遇到新問題時，就能找到比較接近的參考問題，然後參照參考問題的解決辦法來擬定自己的解決辦法。如果大家對一些經典的計算機演算法求解問題有所了解，那麼就會看出來，我們的牌型選擇問題其實比較類似多重背包問題。在有了這個觀察之後，我們可以翻開書，看看如何用蟻群演算法來解決多重背包問題的，這樣來構思我們的實現就會少走很多的彎路，大幅提高了自己解決問題的效率

這裡的加權概率需要同時結合啟發性知識和全局信息素。其中，啟發性知識指出了優化方向，而全局信息素則保留了對之前探索質量的記憶，這兩者的結合就是之前討論過的蟻群演算法的威力所在！

這些不同我們需要高度關註：我們需要深入思考這是否會影響到蟻群演算法的執行，並驗證這些差異的影響。這是由於任何演算法都有其應用前提和假設，我們需要理解並滿足這些前提和假設，而差異點正是檢驗是否滿足的關鍵點。

牌手的可滿足性檢查

隨著一個個牌手的挑出，後繼牌手的選擇空間越來越小。因此，為了避免固定順序挑選牌手導致解質量太差，我們在每一次挑選牌點時，都應是從現有牌點中隨機挑選。而這又和尋找最短路徑的從特定的起點一步步找到特定終點是截然不同的。

初始牌型的確定

蟻群演算法本意是先生成一個螞蟻，讓它在一無所知的情況下爬出一個初始結構，然後用這個初始結構的評分來生成初始信息素數據。但通過前面的講解，我們可以看出蟻群演算法其實是圍繞著局部優勝解探索出局部最優解，因此對於很多問題，初始解會影響蟻群演算法求解的效率和質量，所以一般都是特別的精心構造一個高質量的初始解，以試圖提高解決NP難問題的效率。

但我最後採用了一種簡單粗暴的方式來生成初始牌型，即按牌力大小提取出初始牌型：

- 先提取所有的炸彈

- 再提取對大鬼、對小鬼、單張大小鬼

- 再提取大的飛機帶翅膀、大的飛機、大的連對

- 再提取大的順子

- 最後，按飛機帶翅膀、飛機、連對、順子、拂綠、三張、對、單張的順序將牌全部提完

我採取這種方式的原因很簡單：對於某些問題，初始解決定了演算法的效率和成本，但牌型選擇不是這樣的問題。

請想一下，為什麼呢？！

所以，我們沒必要花費太多的心思來精心生成初始螞蟻以求得一個高質量的初始解，按上述方式快速生成一個簡單的初始解即可。

局部更新

前面討論過，蟻群演算法本質並不是算出最優解，而是高效的搜索出最優解，所以我們需要擴大螞蟻的搜索空間。但隨著演算法的一輪輪迭代，當優勢結構慢慢呈現時，由於信息素的頻繁釋放，會造成優勢結構的吸引力比較大，這可能會限制螞蟻對其它潛在最優解的探索。針對這種情況，改進的蟻群演算法引入了局部更新技術：即在選擇了一個牌手後，立刻對本次選擇做一個小的蒸發，以降低該選擇的信息素濃度，這就增加了其它螞蟻做出其它選擇的可能性。

但由於局部更新會導致每隻螞蟻每步選擇後都修改全局信息素的數據，這就是我們前面說過的，局部更新技術會對蟻群演算法的分布式執行造成嚴重干擾。如果大家考慮分布式的蟻群演算法，就需要去掉該技術。而針對搜索空間快速收窄的問題，可以結合爬山法來擴大搜索空間。

信息素蒸發

由於蟻群演算法每輪次有一個信息素的蒸發動作，這個蒸發的目的是如果不是最優的選擇，則在某次嘗試後就會逐漸喪失吸引力，被再次選中的可能性會越來越小。但由於我們的評分是剩餘牌手數，而剩餘牌手數可能會是負數，那麼負數的蒸發反而會導致信息素的值越來越大了，而且負數也會干擾加權概率的計算。所以為了避免評分出現負數，我們在計算完剩餘牌手數後，對其統一增加了100以進行結構評分的正向糾正。

結構罰分

上一講也說過，如果把對大鬼拆為兩個單張的大鬼，會提升牌型的評分，所以我們會發現，螞蟻受提高牌型質量的鼓勵，導致提取出的牌型非常瑣碎。因此，目前在計算牌型評分的時候，我還加入了一個針對牌手數量的懲罰性加分，但又使得牌型非常偏向簡潔，似乎有過份懲罰的傾向，本來以為應當需要根據大量數據的分析來確定一個合理的懲罰係數。但是在這個調整過程中，突然發現，似乎只要調整結構懲罰係數，我們就能得到從偏向威力最大化到偏向簡潔的不同情況下的一系列牌型，這倒是豐富了我們的牌型選擇空間。

本來我們靜態確定了一個最優的牌型，在後面打牌的過程中，隨時可能需要根據牌面進行牌手的重新組合、分拆。如，最優牌型可能以炸彈、三張為主，但對家判明這一點後，始終利用單張過橋，那我們就必須不停的拆牌。但這帶來了一個問題：如何判斷該不該拆牌、該拆哪手牌、剩下的牌又該如何重新組合呢？筆者花了很長的時間都找不到一個合適的方法來處理這個問題:(

但現在我們有了通過動態調整結構罰分係數可以得出一系列牌型的能力，就有個了意外之喜：我們只要先生成一系列各種各樣的牌型，然後根據對家出牌確定各牌型中如何應牌最有利即可。這就略去了處理拆牌、組合的煩惱:)

這個問題再次說明，數字世界和現實世界有著本質的區別，我們在想像世界中的問題變換至關重要！

綜上，目前的牌型評分的計算公式為：

牌型評分 = 各類型牌的累計剩餘牌手數（經過了牌力過剩處理） + 牌手數 × 結構懲罰係數（可動態指定） + 結構糾偏值（100，這個取值只要大於最大可能的剩餘牌手數33就可以了）

====================================================================================================

關注我的公眾號及時獲取推送的最新文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！