※ 引述《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設計應該真的沒有什麼關係。

alphago不是窮舉法吧不太懂為何玩家沒贏會無窮迴圈遊戲內部沒有結束無窮迴圈的判定嗎?像是圍棋的打結規則那樣

如果你是說遊戲內對loop的規則的話是玩家必須直接喊出要做的loop數量(取捷徑,當然這是實體牌的做法),而形成強制的無窮迴圈時若所有玩家都無法停止則和局,若有玩家有其他選擇能做的話,印象中好像是主動玩家(該

在一回合出現 消耗資源b產生資源a->消耗資源a產生資源b這樣就無限了吧

回合玩家)優先要把迴圈停下來(這個有點忘了現在問題是在電子版上要判定形成無窮迴圈會有問題吧MTG電子版的loop要全程自己按

痾……那就ai養好後再寫個if?XD

對AI不熟,但要判斷無窮迴圈這個好像也是個大問題?

我也不熟，不過可以想見最基本就窮舉殘局狀況手動寫if來判斷問題是如果不靠手動要AI自己判斷殘局，不知道該怎麼養可能首先會從重複行為下手吧

那看起來就是,如果是玩家要進行N次重複操作這個很好判斷,但遇到那種強制型的loop(先不考慮能不能中斷)判斷會有問題

可是判斷是否在無窮迴圈裡，一樣能達到判出和局的要求啊

問題就在無窮迴圈這件事本身不可能靠自身判斷出來

有可能會先窮舉列出但不給ai看，要ai自己判斷是不是然後根據判斷給分，慢慢養出(選出)接近窮舉（判斷100%正確）的ai

https://i.imgur.com/13kz15e.jpg比較經典的無法停止迴圈舉例就像是,在場上沒有其他可放逐目標的狀況下連拍三張這個,會導致2壓掉1,然後3壓

樓主就說判斷自己是否在無窮迴圈裡很簡單了，難的是預測

掉2讓1回來,1再壓掉3讓2回來壓掉1 (loop如果有其他目標可以選的狀況會被迫做其它選擇來中斷

圍棋也有循環劫啊 但現在看來不是問題

圍棋不太一樣的地方是，規則很明確定義結的狀況與應對，而且他只有一種狀況

我現在其實有點混亂，我想確認一下MTG的token有數量上限嗎? 圍棋不成問題應該是因為盤面大小固定，所以可以保證在有限步數內達到循環，但這篇論文似乎用了token來表示tape上的內容，而且似乎沒有假設上限，使得可能的狀態無限多

沒有上限

阿發夠不是窮舉喔，是算機率的

沒有上限

我文章應該沒說AlphaGo是窮舉吧...

推原po大神是說現在有閒情逸致做這種研究也是蠻厲害的…

推認真

這研究也不能說沒意義 如果結果是可以的話代表推翻了長久以來的理論

殘局要看多殘啊 只有動了一步也是殘局那當然是不存在這個演算法但如果倒數有限步 當然是找的到演算法的 人腦都可以算了

alphaGo就是靠隨機減少對窮舉的需求啊，這只是因為遊戲結構不同

圍棋才是公認最難的

深度學習其實比較像直覺 他不需要算出有沒有無窮 只評估勝率高的作法 後續就可以再用別的方式去模擬這些作法