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

看板C_Chat作者 (青松碧濤)時間5年前 (2019/05/12 11:19), 編輯推噓32(32推 0噓 45→)
留言77則, 42人參與, 5年前最新討論串1/2 (看更多)
游研社 AI 認為萬智牌是世界上最複雜的遊戲 作者：跳跳 16小時前 全文約 1100 字，閱讀只需要 3 分鐘。 AI 們在遊戲領域也不是事事順心。 AI 們（準確來說是它們背後的開發者們）一直在想方設法破解人類們的遊戲。它們最大的勝利都是在完全信息——也就是對戰雙方都能知道所有信息——的棋類遊戲上，隨著演算法的演進，它們在更加複雜、信息不對稱的某些遊戲，比如《DOTA2》上，也取得了一定的成果。 但是就在最近，美國康奈爾大學的 AI 開發者們無奈地承認，他們沒法用 AI 算出萬智牌的最優解——在論文中他們寫道：「（遊戲的一系列結構）確定了萬智牌是目前已知計算最複雜的現實遊戲」。 萬智牌是一款歷史悠久的桌游。1993 年，理查德·加菲設計出這款世界上第一個真正意義上的 TCG，迄今已經近 30 年歷史了，這期間設計師們為這款遊戲推出了 20000 多張卡牌和近百種獨特的機制。 萬智牌這麼多年設計了大量機制各異的卡牌 康奈爾大學的AI開發者們發現，如此眾多的卡牌和機制讓這款遊戲的複雜度幾乎高於已知的任何遊戲。在萬智牌規則下的卡牌互動可以復原出一種通用的圖靈機 UTM（2，18）——代表著這款遊戲規則的複雜度已經達到了計算複雜度的上限。這與「AI 無法對圍棋進行窮舉」有不小的區別，對圍棋的無法窮舉只說明我們能提供給 AI 的時間和資源不夠，而複雜度達到上限說明從本質上來講，我們目前所知的演算法無法算出遊戲的最優解。 除了遊戲足夠複雜，AI 還面臨著遊戲中可能存在的各種邏輯陷阱：比如最簡單、也最具破壞力的回合內循環。萬智牌中有諸多可以達成「我的回合中可以做無限件事」的卡牌組合，比如經典的雙身惱人鬼可以讓玩家無限複製生物牌；比如莎妃旭日泰坦能夠實現「犧牲自己-復活」的無限循環。 分裂雙身與惱人鬼，很簡單就能達成無限複製循環 這些無限循環都是有意義的，萬智牌中沒有規則禁止玩家達成無限循環。在正常對戰中往往就是玩家口頭上說一句「我無限了你是不是該認輸了」，但是對於計算機而言，它們會真的一遍一遍計算這種無限。這倒並不會讓現代計算機 AI 崩潰，但是會極大改變其演算法，讓它們更加難以判斷潛在的勝負機率。 並不是萬智牌中的所有卡組都是這樣，遊戲中也有很多簡單易判斷機率的卡組。但是只分析簡單卡組恐怕很難說算是「攻克」了這款遊戲，往往世界級比賽中選手們使用的頂尖卡組都是比較複雜、也就是 AI 難以計算機率的。 研究人員目前的結論是：「萬智牌不符合計算機科學家在對遊戲建模時常做的假設」。不過他們也沒有打算就此放棄，既然現存的模型都不合適，那就新建一些模型——在論文結尾，他們指出，目前的圖靈機模型必然不足以分析所有遊戲，一個擁有基本水準的玩家就能做出勝過這些 AI 模型的分析，這些複雜度更高的遊戲可能更適合「超級圖靈」模型——他們希望關於萬智牌的研究能幫助後來者完善對於遊戲的 AI 分析模型。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.193.111 ※ 文章網址: https://www.ptt.cc/bbs/C_Chat/M.1557631176.A.48A.html
推
05/12 11:21, 5年前 , 1F
那爐石呢？
05/12 11:21, 1F
→
05/12 11:21, 5年前 , 2F
爐石的話AI會無法理解為什麼對面又可以這樣
05/12 11:21, 2F
推
05/12 11:22, 5年前 , 3F
需要拜拜的遊戲
05/12 11:22, 3F
推
05/12 11:22, 5年前 , 4F
爐石打右手就好 沒難度阿嬤都會玩
05/12 11:22, 4F
推
05/12 11:22, 5年前 , 5F
如果有天deepmind派出阿發magic去打MTG一定很有趣
05/12 11:22, 5F
推
05/12 11:23, 5年前 , 6F
爐石的話，你要怎麼教AI面對幾乎不可能出現的牌？
05/12 11:23, 6F
推
05/12 11:23, 5年前 , 7F
對啊 怎麼沒有用AI玩爐石的新聞 難道也是訓練不起來?
05/12 11:23, 7F
→
05/12 11:24, 5年前 , 8F
從機器的角度，獲得隨機一張牌的複雜度靠盃高
05/12 11:24, 8F
推
05/12 11:26, 5年前 , 9F
隨機牌也是當下環境的牌，其實幾百張牌對AI是小case啦，像文
05/12 11:26, 9F
→
05/12 11:27, 5年前 , 10F
中MTG這種無限才是比較麻煩的，因為有些無限是玩家會做但有
05/12 11:27, 10F
→
05/12 11:27, 5年前 , 11F
些不會做，但AI卻無法分別，不過我覺得AI做個100次就可以視
05/12 11:27, 11F
→
05/12 11:28, 5年前 , 12F
為無限了，再看是否有獲得大量資源來判斷是否會贏
05/12 11:28, 12F
推
05/12 11:28, 5年前 , 13F
AI:欸幹他作弊 作弊阿
05/12 11:28, 13F
推
05/12 11:34, 5年前 , 14F
遊戲王試過了嗎
05/12 11:34, 14F
推
05/12 11:34, 5年前 , 15F
AI卒於卡地
05/12 11:34, 15F
→
05/12 11:36, 5年前 , 16F
1993 30年
05/12 11:36, 16F
推
05/12 11:37, 5年前 , 17F
AI打爐石應該討不到太多好處 算多可能還是自己嚇自己
05/12 11:37, 17F
→
05/12 11:37, 5年前 , 18F
每手都是最優姐還是會輸在右手
05/12 11:37, 18F
推
05/12 11:39, 5年前 , 19F
打一場是這樣 但打100場 打1000場 AI不可能算不出爐石有
05/12 11:39, 19F
→
05/12 11:39, 5年前 , 20F
最佳解 因為玩家就已經在用最佳解了 加上爐石又不能對手
05/12 11:39, 20F
→
05/12 11:40, 5年前 , 21F
回合做事情 也不能搞無限 純運氣的東西只要算出機率 除
05/12 11:40, 21F
→
05/12 11:40, 5年前 , 22F
非你把把都神抽不然總有一天會輸 這跟AI玩德州樸克或21
05/12 11:40, 22F
→
05/12 11:41, 5年前 , 23F
點一樣意思呀
05/12 11:41, 23F
推
05/12 11:43, 5年前 , 24F
alphastone: 對啊~你又可以了
05/12 11:43, 24F
→
05/12 11:44, 5年前 , 25F
不就是迴圈崩潰嗎？ 一直執行重複動作
05/12 11:44, 25F
推
05/12 11:46, 5年前 , 26F
玩家的最佳解不一定真的是最佳解 只是人類了解範圍內的最
05/12 11:46, 26F
→
05/12 11:46, 5年前 , 27F
佳解 像圍棋已經也是認為有最佳解的解法 阿法狗還是下出
05/12 11:46, 27F
→
05/12 11:46, 5年前 , 28F
人類無法理解的最佳解 AI說不定就是被智慧詛咒 考慮的太
05/12 11:46, 28F
→
05/12 11:46, 5年前 , 29F
多反而無法下手
05/12 11:46, 29F
推
05/12 11:47, 5年前 , 30F
獲勝條件太多樣可能也是原因 如果AI只會計算不讓自己的
05/12 11:47, 30F
→
05/12 11:47, 5年前 , 31F
血量低於0 那就很有可能被抽爆磨爆或是其他條件的組合
05/12 11:47, 31F
→
05/12 11:47, 5年前 , 32F
技解決
05/12 11:47, 32F
推
05/12 11:48, 5年前 , 33F
麻煩在無限循環吧，碰到就卡死了
05/12 11:48, 33F
→
05/12 11:49, 5年前 , 34F
裁判主辦會作弊的遊戲當然難贏
05/12 11:49, 34F
推
05/12 11:50, 5年前 , 35F
這種含運氣成份的遊戲無法屌虐另一方吧
05/12 11:50, 35F
推
05/12 11:53, 5年前 , 36F
問題就是人類可以閱讀文字，非常容易理解各種規則，ai是
05/12 11:53, 36F
→
05/12 11:53, 5年前 , 37F
靠大量嘗試去理解，一張卡的效果ai用幾億次可能都還不瞭
05/12 11:53, 37F
→
05/12 11:53, 5年前 , 38F
解規則
05/12 11:53, 38F
推
05/12 12:02, 5年前 , 39F
AI只是無法理解規則外的勝利模式吧 像是無限loop會逼對面認
05/12 12:02, 39F
→
05/12 12:02, 5年前 , 40F
輸 但是對於AI它不知道怎麼處理這種狀況
05/12 12:02, 40F
推
05/12 12:04, 5年前 , 41F
遊戲王ai可以ㄇ
05/12 12:04, 41F
→
05/12 12:04, 5年前 , 42F
等一下，這篇是講"MTG is Turing complete"那篇論文嗎
05/12 12:04, 42F
→
05/12 12:04, 5年前 , 43F
是的話內容也錯太多了吧= =
05/12 12:04, 43F
→
05/12 12:06, 5年前 , 44F
作者沒有一個是Cornell的，然後內容也跟AI沒啥關係阿..
05/12 12:06, 44F
推
05/12 12:07, 5年前 , 45F
另外就是文字理解 畢竟人類的語言對於電腦而言是非常不嚴
05/12 12:07, 45F
→
05/12 12:07, 5年前 , 46F
謹的相同卡片效果的描述在人類不介入的狀況下AI可能做出人
05/12 12:07, 46F
→
05/12 12:07, 5年前 , 47F
類無法接受的見解
05/12 12:07, 47F
→
05/12 12:13, 5年前 , 48F
圍棋也被說過 結果..
05/12 12:13, 48F
推
05/12 12:19, 5年前 , 49F
結果就是內文說的呀，概念完全不同
05/12 12:19, 49F
→
05/12 12:22, 5年前 , 50F
實體卡片上的效果說明跟電腦化後邏輯判斷有出入
05/12 12:22, 50F
→
05/12 12:23, 5年前 , 51F
這連爐石裡都被笑稱為考古題了，30年份卡池就更不用說
05/12 12:23, 51F
→
05/12 12:26, 5年前 , 52F
這篇大概是抄esportstalk的，那裡也說是康奈爾大學，
05/12 12:26, 52F
→
05/12 12:26, 5年前 , 53F
可能是看到網頁底下說arxiv是康奈爾的商標就誤會了
05/12 12:26, 53F
推
05/12 12:27, 5年前 , 54F
其實說穿了也只是訓練AI需要人力介入的部分過多 如果時間
05/12 12:27, 54F
→
05/12 12:27, 5年前 , 55F
成本允許下仍然可以實現啦 這點跟過去靠窮舉破解棋類遊戲是
05/12 12:27, 55F
→
05/12 12:27, 5年前 , 56F
一樣的狀況
05/12 12:27, 56F
推
05/12 12:30, 5年前 , 57F
遊戲王那滿滿的卡面文字和蓋牌的無法預期和發動時機才最難
05/12 12:30, 57F
→
05/12 12:36, 5年前 , 58F
爐石打頭薩腳本最佳解 打頭
05/12 12:36, 58F
推
05/12 12:36, 5年前 , 59F
cock magic
05/12 12:36, 59F
→
05/12 12:37, 5年前 , 60F
遊戲王我只記得ygopro的ai玩主流牌有夠無解==
05/12 12:37, 60F
→
05/12 12:44, 5年前 , 61F
可是MTG會一直出新牌啊 窮舉破解法趕得上嗎
05/12 12:44, 61F
推
05/12 12:54, 5年前 , 62F
MTG的EDH賽制扯到團戰更難算,所以常常在說來打EDH必
05/12 12:54, 62F
→
05/12 12:54, 5年前 , 63F
須先把處理器規格上調(也總會被練上來)
05/12 12:54, 63F
推
05/12 13:09, 5年前 , 64F
先拔掉所有卡禁讓高端玩家打幾場比賽試試就知道了。
05/12 13:09, 64F
→
05/12 13:13, 5年前 , 65F
棋類短時間就頻繁增減禁手或規則，不相信會好破解。
05/12 13:13, 65F
→
05/12 13:15, 5年前 , 66F
魔法風雲會就是一張牌一種規則，規則效果可能部分重複，
05/12 13:15, 66F
→
05/12 13:16, 5年前 , 67F
牌面有一點點不同就要整套重算，那維度大上棋類太多。
05/12 13:16, 67F
推
05/12 13:34, 5年前 , 68F
爐石沒有絕對的無限啊
05/12 13:34, 68F
推
05/12 14:33, 5年前 , 69F
遊戲王的ai是要很會說書嗎
05/12 14:33, 69F
→
05/12 14:38, 5年前 , 70F
別再貼來源不明的農場文了好嗎
05/12 14:38, 70F
→
05/12 15:04, 5年前 , 71F
遊戲王才是最難的吧
05/12 15:04, 71F
推
05/12 15:50, 5年前 , 72F
AI:為什麼對方可以自己編規則?
05/12 15:50, 72F
推
05/12 16:07, 5年前 , 73F
不是阿 爐石隨機性那麼高的遊戲 你才練一千場不可能知
05/12 16:07, 73F
→
05/12 16:07, 5年前 , 74F
道每手的判斷是否正確好嗎
05/12 16:07, 74F
→
05/12 16:08, 5年前 , 75F
隨機性影響的反饋太多了 可能要多加好幾個零的次數才有
05/12 16:08, 75F
→
05/12 16:08, 5年前 , 76F
可能測出正確的反饋吧
05/12 16:08, 76F
推
05/12 16:09, 5年前 , 77F
爐石AI只會：你又可以了? 離譜至極
05/12 16:09, 77F
‣ 更多 jerry78424 的文章
文章代碼(AID): #1Srv38IA (C_Chat)
‣ 更多 jerry78424 的文章
文章代碼(AID): #1Srv38IA (C_Chat)