一種新的計算機演算法可以近乎完美地玩最流行的撲克變體之一。其創造者表示，它實際上“不可能在公平遊戲中輸給任何對手”。
這超越了計算機程式擊敗頂尖人類玩家的成就，正如IBM的國際象棋程式“深藍”在1997年對陣當時的國際象棋世界冠軍加里·卡斯帕羅夫時所做的那樣。由計算機科學家邁克爾·鮑林及其在加拿大埃德蒙頓阿爾伯塔大學的同事，以及芬蘭軟體開發人員奧斯卡里·塔梅林設計的撲克程式，在所有意圖和目的上都表現得完美無缺。
這意味著這種特定的撲克變體，稱為單挑無限注德州撲克 (HULHE)，可以被認為是已被解決。該演算法在一篇發表於《科學》雜誌的論文中進行了描述。
支援科學新聞事業
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞事業 訂閱。透過購買訂閱，您正在幫助確保有關塑造我們當今世界的發現和思想的具有影響力的故事的未來。
作者們計算出的策略非常接近完美，“以至於對這個遊戲的進一步研究變得毫無意義”，位於加利福尼亞州門洛帕克的計算機撲克研究員埃裡克·傑克遜說。
“我認為，對於專家來說，如此龐大的一個遊戲這麼快就被解決，會讓他們感到驚訝，”傑克遜補充道。
之前已經有一些其他流行的遊戲被解決了。特別是，在2007年，來自阿爾伯塔大學同一計算機科學系的團隊——包括最新研究的合著者尼爾·伯奇——破解了跳棋，也稱為國際跳棋。
但撲克比跳棋更難解決。國際象棋和跳棋是完全資訊博弈的例子，在完全資訊博弈中，玩家完全瞭解所有過去的事件和遊戲中的當前情況。相比之下，在撲克中，玩家有一些事情不知道：最關鍵的是，其他玩家被髮了什麼牌。不完全資訊博弈類別對經濟學家和博弈論家尤其有趣，因為它包括實際問題，例如為拍賣和談判尋找最佳策略。
抱歉
在撲克中，主要的挑戰是處理遊戲中可能出現的無數種玩法。鮑林和他的同事們研究了最流行的形式之一，稱為德州撲克。只有兩名玩家時，遊戲變為單挑，當遊戲具有固定的下注大小和固定的加註次數時，它是一個“限注”遊戲。HULHE 可以達到 3.16 × 1017 個狀態，以及玩家必須做出決定的 3.19 × 1014 個可能點。
鮑林和他的同事們設計的演算法使其能夠從經驗中學習，達到冠軍級技能需要進行超過 1,500 場比賽。一開始，它隨機做出決定，但隨後它透過為每個決定附加一個“遺憾”值來更新自己，具體取決於它的表現有多差。
這個過程被稱為反事實遺憾最小化，已在自 2006 年以來舉辦的年度計算機撲克大賽中被廣泛採用。但鮑林和他的同事們透過允許演算法重新評估在早期訓練輪次中被認為較差的決策，從而改進了它。
另一個關鍵的創新是處理開發和使用該策略所需的大量資訊，這些資訊大約為 262 太位元組。如此大的資料量需要磁碟儲存，而磁碟儲存的訪問速度很慢。研究人員找到了一種資料壓縮方法，將資料量減少到更易於管理的 11 太位元組，並且僅將磁碟儲存的使用計算時間增加了 5%。
“我認為反事實遺憾演算法是主要的進步，”英國曼徹斯特大學的計算機科學家喬納森·夏皮羅說。“但他們還做了其他一些非常聰明的事情，使這個問題在計算上可行。”
虛張聲勢的遊戲
作為其發展策略的一部分，計算機學會在其遊戲中注入一定劑量的虛張聲勢。雖然虛張聲勢看起來像是遊戲中非常人性化的心理因素，但它實際上是博弈論的一部分——並且通常是計算機撲克的一部分。“虛張聲勢從遊戲的數學原理中自然而然地產生，”鮑林說，你可以計算出你應該多久虛張聲勢才能獲得最佳結果。
當然，沒有撲克演算法可以從數學上保證贏得每場比賽，因為該遊戲包含很大的機會成分，這取決於你拿到的牌。但鮑林和他的同事們已經證明，他們的演算法在長期來看總是會贏。
這個問題只是研究人員所說的“基本上已解決”，這意味著在理論上，計算機可能因技能而非機會而被擊敗的邊際極小。但在實踐中，這個邊際可以忽略不計。
鮑林說，這種方法可能在人們必須在資訊不完整的情況下做出決定的現實生活中很有用——例如，用於管理投資組合。該團隊現在正專注於將他們的方法應用於醫療決策，與糖尿病專家合作。
本文經許可轉載，首次發表於 2014 年 1 月 8 日的《自然》雜誌。 更多內容： 物理學家揭示德州撲克的秘密