4 ms·
In absolute generality, it's impossible. The game is Turing complete: https://www.toothycat.net/~hologram/Turing/ https://www.toothycat.net/~hologram/Turing/ O
by yorwba 9y ago
In absolute generality, it's impossible. The game is Turing complete: https://www.toothycat.net/~hologram/Turing/ https://www.toothycat.net/~hologram/Turing/
Of course you may still be able to find a strategy that works well against humans, but that would still be a cutting-edge research task.
Hidden information is a big problem, the classic benchmark for that is poker. The latest breakthrough I'm aware of was for heads-up limit Texas hold'em http://science.sciencemag.org/content/347/6218/145 http://science.sciencemag.org/content/347/6218/145 That may be a difficult game, but it has vastly fewer possible states. The same approach as used in the paper would almost certainly not scale for MTG.
Dealing with cards that can arbitrarily change the rules of the game would require human-level AI almost by definition, unless you want to manually translate them into code, in which case the system would be unable to deal with new cards.
Now that I have told all about how the problems you identified are much too difficult, I want to add that that shouldn't discourage you from just playing around. Starting with a minimal test case is how poker research took off, so you're definitely on the right track.
- alasdair_ 9y ago>Hidden information is a big problem, the classic benchmark for that is poker. The latest breakthrough I'm aware of was for heads-up limit Texas hold'em http://science.sciencemag.org/content/347/6218/145 http://science.sciencemag.org/content/347/6218/145 That may be a difficult game, but it has vastly fewer possible states. The same approach as used in the paper would almost certainly not scale for MTG. I'm a big AI poker fan (and a big fan in general). The current state of the art is now a bot that can consistently beat the very best heads-up no limit (i.e. there are a very large number of possible legal bets) players in real money games. http://science.sciencemag.org/content/early/2017/12/15/science.aao1733.full http://science.sciencemag.org/content/early/2017/12/15/scien... - note the date was yesterday :)
- marcoperaza 9y agoHow do online poker sites deal with this? No one would want to play if they were constantly getting rinsed by bots.
- alasdair_ 9y agoMost people don't play heads-up no limit, they play 9-10 person games which are tougher for AI to beat currently. Eventually though, online poker will be full of bots.
- lern_too_spel 9y agoIf you can put your bots in more seats at the table, they can share information and collude in their betting strategy. No amount of smartness in a single player's strategy is going to beat cheating.
- marcoperaza 9y ago>Dealing with cards that can arbitrarily change the rules of the game would require human-level AI almost by definition, unless you want to manually translate them into code, in which case the system would be unable to deal with new cards. That's not unreasonable at all. No one is expecting you to solve general purpose AI by having the cards interpreted with NLP. And translating the cards' behavior to code is not some insurmountable task. Wizards of the Coast has presumably already done that for the online version of the game.