游研社
AI 認為萬智牌是世界上最複雜的遊戲
作者：跳跳 16小時前
全文約 1100 字，閱讀只需要 3 分鐘。
AI 們在遊戲領域也不是事事順心。
AI 們（準確來說是它們背後的開發者們）一直在想方設法破解人類們的遊戲。它們最大的勝利都是在完全信息——也就是對戰雙方都能知道所有信息——的棋類遊戲上，隨著演算法的演進，它們在更加複雜、信息不對稱的某些遊戲，比如《DOTA2》上，也取得了一定的成果。
但是就在最近，美國康奈爾大學的 AI 開發者們無奈地承認，他們沒法用 AI 算出萬智牌的最優解——在論文中他們寫道：「（遊戲的一系列結構）確定了萬智牌是目前已知計算最複雜的現實遊戲」。
萬智牌是一款歷史悠久的桌游。1993 年，理查德·加菲設計出這款世界上第一個真正意義上的 TCG，迄今已經近 30 年歷史了，這期間設計師們為這款遊戲推出了 20000 多張卡牌和近百種獨特的機制。
萬智牌這麼多年設計了大量機制各異的卡牌
康奈爾大學的AI開發者們發現，如此眾多的卡牌和機制讓這款遊戲的複雜度幾乎高於已知的任何遊戲。在萬智牌規則下的卡牌互動可以復原出一種通用的圖靈機 UTM（2，18）——代表著這款遊戲規則的複雜度已經達到了計算複雜度的上限。這與「AI 無法對圍棋進行窮舉」有不小的區別，對圍棋的無法窮舉只說明我們能提供給 AI 的時間和資源不夠，而複雜度達到上限說明從本質上來講，我們目前所知的演算法無法算出遊戲的最優解。
除了遊戲足夠複雜，AI 還面臨著遊戲中可能存在的各種邏輯陷阱：比如最簡單、也最具破壞力的回合內循環。萬智牌中有諸多可以達成「我的回合中可以做無限件事」的卡牌組合，比如經典的雙身惱人鬼可以讓玩家無限複製生物牌；比如莎妃旭日泰坦能夠實現「犧牲自己-復活」的無限循環。
分裂雙身與惱人鬼，很簡單就能達成無限複製循環
這些無限循環都是有意義的，萬智牌中沒有規則禁止玩家達成無限循環。在正常對戰中往往就是玩家口頭上說一句「我無限了你是不是該認輸了」，但是對於計算機而言，它們會真的一遍一遍計算這種無限。這倒並不會讓現代計算機 AI 崩潰，但是會極大改變其演算法，讓它們更加難以判斷潛在的勝負機率。
並不是萬智牌中的所有卡組都是這樣，遊戲中也有很多簡單易判斷機率的卡組。但是只分析簡單卡組恐怕很難說算是「攻克」了這款遊戲，往往世界級比賽中選手們使用的頂尖卡組都是比較複雜、也就是 AI 難以計算機率的。
研究人員目前的結論是：「萬智牌不符合計算機科學家在對遊戲建模時常做的假設」。不過他們也沒有打算就此放棄，既然現存的模型都不合適，那就新建一些模型——在論文結尾，他們指出，目前的圖靈機模型必然不足以分析所有遊戲，一個擁有基本水準的玩家就能做出勝過這些 AI 模型的分析，這些複雜度更高的遊戲可能更適合「超級圖靈」模型——他們希望關於萬智牌的研究能幫助後來者完善對於遊戲的 AI 分析模型。

那爐石呢？

爐石的話AI會無法理解為什麼對面又可以這樣

需要拜拜的遊戲

爐石打右手就好 沒難度阿嬤都會玩

如果有天deepmind派出阿發magic去打MTG一定很有趣

爐石的話，你要怎麼教AI面對幾乎不可能出現的牌？

對啊 怎麼沒有用AI玩爐石的新聞 難道也是訓練不起來?

從機器的角度，獲得隨機一張牌的複雜度靠盃高

隨機牌也是當下環境的牌，其實幾百張牌對AI是小case啦，像文中MTG這種無限才是比較麻煩的，因為有些無限是玩家會做但有些不會做，但AI卻無法分別，不過我覺得AI做個100次就可以視為無限了，再看是否有獲得大量資源來判斷是否會贏

AI:欸幹他作弊 作弊阿

遊戲王試過了嗎

AI卒於卡地

1993 30年

AI打爐石應該討不到太多好處 算多可能還是自己嚇自己每手都是最優姐還是會輸在右手

打一場是這樣 但打100場 打1000場 AI不可能算不出爐石有最佳解 因為玩家就已經在用最佳解了 加上爐石又不能對手回合做事情 也不能搞無限 純運氣的東西只要算出機率 除非你把把都神抽不然總有一天會輸 這跟AI玩德州樸克或21點一樣意思呀

alphastone: 對啊~你又可以了

不就是迴圈崩潰嗎？ 一直執行重複動作

玩家的最佳解不一定真的是最佳解 只是人類了解範圍內的最佳解 像圍棋已經也是認為有最佳解的解法 阿法狗還是下出人類無法理解的最佳解 AI說不定就是被智慧詛咒 考慮的太多反而無法下手

獲勝條件太多樣可能也是原因 如果AI只會計算不讓自己的血量低於0 那就很有可能被抽爆磨爆或是其他條件的組合技解決

麻煩在無限循環吧，碰到就卡死了

裁判主辦會作弊的遊戲當然難贏

這種含運氣成份的遊戲無法屌虐另一方吧

問題就是人類可以閱讀文字，非常容易理解各種規則，ai是靠大量嘗試去理解，一張卡的效果ai用幾億次可能都還不瞭解規則

AI只是無法理解規則外的勝利模式吧 像是無限loop會逼對面認輸 但是對於AI它不知道怎麼處理這種狀況

遊戲王ai可以ㄇ

等一下，這篇是講"MTG is Turing complete"那篇論文嗎是的話內容也錯太多了吧= =作者沒有一個是Cornell的，然後內容也跟AI沒啥關係阿..

另外就是文字理解 畢竟人類的語言對於電腦而言是非常不嚴謹的相同卡片效果的描述在人類不介入的狀況下AI可能做出人類無法接受的見解

圍棋也被說過 結果..

結果就是內文說的呀，概念完全不同

實體卡片上的效果說明跟電腦化後邏輯判斷有出入這連爐石裡都被笑稱為考古題了，30年份卡池就更不用說

這篇大概是抄esportstalk的，那裡也說是康奈爾大學，可能是看到網頁底下說arxiv是康奈爾的商標就誤會了

其實說穿了也只是訓練AI需要人力介入的部分過多 如果時間成本允許下仍然可以實現啦 這點跟過去靠窮舉破解棋類遊戲是一樣的狀況

遊戲王那滿滿的卡面文字和蓋牌的無法預期和發動時機才最難

爐石打頭薩腳本最佳解 打頭

cock magic

遊戲王我只記得ygopro的ai玩主流牌有夠無解==

可是MTG會一直出新牌啊 窮舉破解法趕得上嗎

MTG的EDH賽制扯到團戰更難算,所以常常在說來打EDH必須先把處理器規格上調(也總會被練上來)

先拔掉所有卡禁讓高端玩家打幾場比賽試試就知道了。棋類短時間就頻繁增減禁手或規則，不相信會好破解。魔法風雲會就是一張牌一種規則，規則效果可能部分重複，牌面有一點點不同就要整套重算，那維度大上棋類太多。

爐石沒有絕對的無限啊

遊戲王的ai是要很會說書嗎

別再貼來源不明的農場文了好嗎

遊戲王才是最難的吧

AI:為什麼對方可以自己編規則?

不是阿 爐石隨機性那麼高的遊戲 你才練一千場不可能知道每手的判斷是否正確好嗎隨機性影響的反饋太多了 可能要多加好幾個零的次數才有可能測出正確的反饋吧

爐石AI只會：你又可以了? 離譜至極