Re: [閒聊] 魔法風雲會可能是AI眼中最複雜的遊戲

看板C_Chat作者aaaaajack (丁丁是個人才)時間5年前 (2019/05/12 13:40)推噓19(19推 0噓 45→)

留言64則, 16人參與討論串2/2 (看更多)

※ 引述《jerry78424 (青松碧濤)》之銘言： : 游研社 : AI 認為萬智牌是世界上最複雜的遊戲 : 作者：跳跳 16小時前 : 全文約 1100 字，閱讀只需要 3 分鐘。 : AI 們在遊戲領域也不是事事順心。 : AI 們（準確來說是它們背後的開發者們）一直在想方設法破解人類們的遊戲。它們最大的勝利都是在完全信息——也就是對戰雙方都能知道所有信息——的棋類遊戲上，隨著演算法的演進，它們在更加複雜、信息不對稱的某些遊戲，比如《DOTA2》上，也取得了一定的成果。 : 但是就在最近，美國康奈爾大學的 AI 開發者們無奈地承認，他們沒法用 AI 算出萬智牌的最優解——在論文中他們寫道：「（遊戲的一系列結構）確定了萬智牌是目前已知計算最複雜的現實遊戲」。 : 萬智牌是一款歷史悠久的桌游。1993 年，理查德·加菲設計出這款世界上第一個真正意義上的 TCG，迄今已經近 30 年歷史了，這期間設計師們為這款遊戲推出了 20000 多張卡牌和近百種獨特的機制。 : 萬智牌這麼多年設計了大量機制各異的卡牌 : 康奈爾大學的AI開發者們發現，如此眾多的卡牌和機制讓這款遊戲的複雜度幾乎高於已知的任何遊戲。在萬智牌規則下的卡牌互動可以復原出一種通用的圖靈機 UTM（2，18）——代表著這款遊戲規則的複雜度已經達到了計算複雜度的上限。這與「AI 無法對圍棋進行窮舉」有不小的區別，對圍棋的無法窮舉只說明我們能提供給 AI 的時間和資源不夠，而複雜度達到上限說明從本質上來講，我們目前所知的演算法無法算出遊戲的最優解。 : 除了遊戲足夠複雜，AI 還面臨著遊戲中可能存在的各種邏輯陷阱：比如最簡單、也最具破壞力的回合內循環。萬智牌中有諸多可以達成「我的回合中可以做無限件事」的卡牌組合，比如經典的雙身惱人鬼可以讓玩家無限複製生物牌；比如莎妃旭日泰坦能夠實現「犧牲自己-復活」的無限循環。 : 分裂雙身與惱人鬼，很簡單就能達成無限複製循環 : 這些無限循環都是有意義的，萬智牌中沒有規則禁止玩家達成無限循環。在正常對戰中往往就是玩家口頭上說一句「我無限了你是不是該認輸了」，但是對於計算機而言，它們會真的一遍一遍計算這種無限。這倒並不會讓現代計算機 AI 崩潰，但是會極大改變其演算法，讓它們更加難以判斷潛在的勝負機率。 : 並不是萬智牌中的所有卡組都是這樣，遊戲中也有很多簡單易判斷機率的卡組。但是只分析簡單卡組恐怕很難說算是「攻克」了這款遊戲，往往世界級比賽中選手們使用的頂尖卡組都是比較複雜、也就是 AI 難以計算機率的。 : 研究人員目前的結論是：「萬智牌不符合計算機科學家在對遊戲建模時常做的假設」。不過他們也沒有打算就此放棄，既然現存的模型都不合適，那就新建一些模型——在論文結尾，他們指出，目前的圖靈機模型必然不足以分析所有遊戲，一個擁有基本水準的玩家就能做出勝過這些 AI 模型的分析，這些複雜度更高的遊戲可能更適合「超級圖靈」模型——他們希望關於萬智牌的研究能幫助後來者完善對於遊戲的 AI 分析模型。又是一篇胡扯的農場文章... 原論文在這裡 https://arxiv.org/abs/1904.09828 首先作者並不是康乃爾大學的，並不是文章在arXiv上就代表作者是康乃爾大學的。再來作者也不是「AI開發者」，也沒有「無奈的承認無法算出MTG最佳解」，他們的目的就是證明MTG是個難到電腦算不出來的遊戲，怎麼會無奈呢 XD 首先承認一下我沒打過MTG，所以我也沒有詳細的看完這篇文章，不過根據我的理解這篇論文並不能得出「AI幾乎不可能打敗人類玩家」的結論。首先我們看看這篇文章具體的結論: 「給定一個殘局，算出誰能贏下這場遊戲」的演算法並不存在。但這代表人類寫不出魔風的AI嗎？AlphaGo也沒有算出誰100%會贏啊，但它打敗了所有的職業棋士。所以「找不出最佳解」跟「無法打敗人類玩家」其實沒有什麼直接關係... 當然這篇論文某種程度上證明了魔法風雲會非常非常難，因為即使像圍棋這麼難的遊戲，只要擁有足夠的時間，電腦還是能夠窮舉出所有的可能性，並且得出誰會贏的結論。 (地球會不會先毀滅先不談 XD) 但這篇文章說明了我們無法用圖靈機(電腦的理論模型)對魔風做同樣的事情接下來談一下這篇文章具體是怎麼證明的。學資工的同學可能會在離散數學課聽到所謂的「停機問題」，也就是「判斷一支程式會不會停」，而一個著名的結論是圖靈機算不出這個問題的答案。這篇文章的邏輯是「如果我有個算MTG殘局的演算法，我就可以拿它來算出停機問題的答案」，這顯然不可能，所以我們想要的演算法不可能存在。 (也就是所謂的reduction) 而具體的做法是，假設我們想要算程式A能不能停下來，我們根據A設定出一個殘局，在這個殘局下兩個玩家能做的事情完全固定(透過一張叫Wild Evocation的卡達成)，並且這個唯一的選擇會對應程式的一步 (準確來說是四個回合對應UTM的一步...) 也就是說，盤面狀態對應了程式的內部狀態(可以想成是記憶體+指令位置)，而玩家的行動對盤面的改變會恰好對應程式的一步對其內部狀態的改變。因此跑這個殘局其實等同於「模擬程式的進行」。如果程式本身會停，那相應的殘局最後會停下來並且使得先手玩家勝利；如果程式本身不會停，那相應的殘局也不會停，根據規則無窮迴圈和局。因此如果我們能設計一個演算法算出任何殘局的結果，那麼這個演算法也能用來判斷任何程式會不會停，與事實矛盾。基本上就是這樣，有興趣的再麻煩自己看論文吧 XD 總之這只是一個理論上的結果，首先打贏對手並不需要最優解，再來我們在現實中可能也不會達到這麼麻煩的殘局，所以這跟魔風的AI設計應該真的沒有什麼關係。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 67.241.78.93 ※ 文章網址: https://www.ptt.cc/bbs/C_Chat/M.1557639642.A.A0E.html ※ 編輯: aaaaajack (67.241.78.93), 05/12/2019 13:43:36

推