Shortly after publication, Alex Churchill, one of the authors of the paper, responded to Kotaku in an email with some further clarifications on the group’s findings.
"What we’ve proven is that the operation of "finding the best move in a game of Magic," in the worst case, cannot be computed," he said. "There are certain circumstances, even though they’re very contrived, where it’s proven that no algorithm can find whether there exists a winning move. In fact, since we eliminate all player choice, we’ve proved something slightly stronger: that it’s impossible in the general case for an algorithm to look at a board state and see whether it’s possible for the game to end at all."
He went on:
"This is what computer scientists care about when they talk about the complexity of an algorithm. The algorithm might be easy to solve in almost all cases, but we’ve shown that the worst case is as hard as it can be."
"This has very little implication for playing the game in practice, but it does have takeaways for potential AI designers. Probably anyone who was going to write an AI for Magic would not have made the AI choose its next move by trying to exhaustively compute all possible consequences of the current board state - that’d be crazy. They’d do it using heuristics, rules of thumb that give a best guess about how to play. Our paper just proves that the exhaustive computation approach is definitely not the way to go because it’s actually impossible (in some cases)."
Il semble que le seul but de l'étude était de dire qu'il y a des cas où on ne sait pas dire qui va gagner ou pas, et si la partie va finir ou pas. Ils ont fait leur test en format legacy, mais rien qu'en standard, qui possède pourtant beaucoup moins de cartes, il y a le deck Wilderness Reclamation où tu peux faire une boucle infinie grâce à l'infâme Nexus of Fate. Cette boucle te permettra de gagner sous certaines conditions, et dans les autres tu peux te retrouver à jouer un nombre de tours infinis. En tournoi papier il y aura sans doute un avertissement pour "slow play" (équivalent des pénalités pour non combativité dans les arts martiaux), mais certains noobs ne maîtrisant pas le deck le jouent sur Magic Arena (où il n'y a pas de pénalités, juste un timer qui se recharge) et se retrouvent donc à attendre que leur adversaire concèdent la partie d'ennui. La riposte trouvée a été de scripter l'intéraction et de juste dérouler le script et partir faire autre chose quand on est face à ce type d'adversaire.
[^] # Re: Vraiment surprenant ?
Posté par liberforce (site web personnel, Mastodon) . En réponse au journal Magic: the Gathering, le problème de l'arrêt, et une inférence un peu rapide. Évalué à 4.
À vrai dire, les articles de vulgarisation semblent s'être embalés, cf la mise à jour en fin de l'article de kotaku:
https://kotaku.com/magic-the-gathering-is-so-complex-it-could-stump-a-com-1834623872
Il semble que le seul but de l'étude était de dire qu'il y a des cas où on ne sait pas dire qui va gagner ou pas, et si la partie va finir ou pas. Ils ont fait leur test en format legacy, mais rien qu'en standard, qui possède pourtant beaucoup moins de cartes, il y a le deck Wilderness Reclamation où tu peux faire une boucle infinie grâce à l'infâme Nexus of Fate. Cette boucle te permettra de gagner sous certaines conditions, et dans les autres tu peux te retrouver à jouer un nombre de tours infinis. En tournoi papier il y aura sans doute un avertissement pour "slow play" (équivalent des pénalités pour non combativité dans les arts martiaux), mais certains noobs ne maîtrisant pas le deck le jouent sur Magic Arena (où il n'y a pas de pénalités, juste un timer qui se recharge) et se retrouvent donc à attendre que leur adversaire concèdent la partie d'ennui. La riposte trouvée a été de scripter l'intéraction et de juste dérouler le script et partir faire autre chose quand on est face à ce type d'adversaire.
D'autres decks comme le deck Eggs sont notoirement connus pour être très longs et incertains dans leur manière de partir en combo (combo off), car tu ne sais pas si tu vas converger et réussir à gagner ou pas.