Truth from Zero?
rjlipton.wordpress.com
Truth from Zero?
1–10 of 17 posts
Re: Truth from Zero?
#2". It announces an algorithm called AlphaZero that, given the rules of any two-player game of strategy and copious hardware, trains a deep neural network to play the game at skill levels approaching perfection."
I have a particular interest in having a computer play the game Magic: the Gathering at an expert level. In some ways, this seems like an ideal fit for AlphaZero - it's a two-player strategy game with a finite number of valid plays at each state, yet I'm still not sure how to deal with four key elements:
1. The game is random - it has a deck of cards that are shuffled.
2. The game has hidden information - cards in hand are hidden.
3. The cards can change the rules of the game itself. For example, a card could change the win conditions of the game. There are over 20,000 unique cards with more regularly being printed.
4. A major part of the game (perhaps the most important) is that each player chooses their own combination of sixty cards from the ever-increasing pool. This makes understanding the "metgame" extremely important - a "deck" that was good a week ago may be outclassed the following week as players react.
In addition, there are many decks that win with odd combinations of cards and often the only way to beat these decks is to know in advance how to stop the combo.
Any ideas on how best to approach this problem?
Right now I am working on building a very simple version of the game with both players playing the same three cards with no randomness. This will eventually feed a simple genetic algorithm to test different quantities of each of the three cards to find an optimal "build".
Re: Truth from Zero?
#3". It announces an algorithm called AlphaZero that, given the rules of any two-player game of strategy and copious hardware, trains a deep neural network to play the game at skill levels approaching perfection." I have a particular interest in having a computer play the game Magic: the Gathering at an expert level. In some ways, this seems like an ideal fit for AlphaZero - it's a two-player strategy game with a finit…
did you look at the already existing playing MTG AIs: https://www.slightlymagic.net/wiki/List_of_MTG_Engines
I thought about writing my own MTG engine for a while and I believe the key is in modeling the game state (and the valid/possible transitions/rules - which one could argue that are still part of the game state).
I believe exhaustively trying out all decks is not going to fly and deckbuilding should be centered around synergies + looking at what currently works (top decks).
I would personally settle on an AI bot that plays perfectly that I could feed decks to test.
Re: Truth from Zero?
#4". It announces an algorithm called AlphaZero that, given the rules of any two-player game of strategy and copious hardware, trains a deep neural network to play the game at skill levels approaching perfection." I have a particular interest in having a computer play the game Magic: the Gathering at an expert level. In some ways, this seems like an ideal fit for AlphaZero - it's a two-player strategy game with a finit…
In absolute generality, it's impossible. The game is Turing complete: 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 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.
Re: Truth from Zero?
#5". It announces an algorithm called AlphaZero that, given the rules of any two-player game of strategy and copious hardware, trains a deep neural network to play the game at skill levels approaching perfection." I have a particular interest in having a computer play the game Magic: the Gathering at an expert level. In some ways, this seems like an ideal fit for AlphaZero - it's a two-player strategy game with a finit…
did you look at the already existing playing MTG AIs: https://www.slightlymagic.net/wiki/List_of_MTG_Engines I thought about writing my own MTG engine for a while and I believe the key is in modeling the game state (and the valid/possible transitions/rules - which one could argue that are still part of the game state). I believe exhaustively trying out all decks is not going to fly and deckbuilding should be centered…
>did you look at the already existing playing MTG AIs: https://www.slightlymagic.net/wiki/List_of_MTG_Engines
Yes. I'm very likely going to use the guts of XMage to handle card text and encoding the game state and all legal actions. I'm deliberately trying to get a simpler version with only three cards working first so I can see if it's possible to "solve" (i.e. test every single possible action and response for every possible game and determine the optimal play each time) such a game.
A major issue is that determining what is in the opponents hand based on previous plays is pretty important in situations where such information cannot be brute forced and instead needs to rely on dependent probabilities.
>I believe exhaustively trying out all decks is not going to fly and deckbuilding should be centered around synergies + looking at what currently works (top decks).
I had decent success building a GA that could tweak the list for a simple burn deck by adding or removing single cards as a mutation. I only tested against a very simple opponent and all potential plays were hand-coded.
>I would personally settle on an AI bot that plays perfectly that I could feed decks to test.
The issue is that "plays perfectly" is an extremely tough bar (even against only one opposing deck). As a trivial example: Magic is full of "infinite" combos where a given loop can be completed an arbitrary amount of times. Knowing the "correct" point to stop the looping is extremely tough to code perfectly.
It's also possible to have, say, a trillion tokens on the board and it's legal to pick any one of them as a target - handling this kind of situation is also pretty hard to handle computationally.
Re: Truth from Zero?
#6". It announces an algorithm called AlphaZero that, given the rules of any two-player game of strategy and copious hardware, trains a deep neural network to play the game at skill levels approaching perfection." I have a particular interest in having a computer play the game Magic: the Gathering at an expert level. In some ways, this seems like an ideal fit for AlphaZero - it's a two-player strategy game with a finit…
In absolute generality, it's impossible. The game is Turing complete: 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.sc…
>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 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/scien... - note the date was yesterday :)
Re: Truth from Zero?
#7Earlier quoted context omitted.
did you look at the already existing playing MTG AIs: https://www.slightlymagic.net/wiki/List_of_MTG_Engines I thought about writing my own MTG engine for a while and I believe the key is in modeling the game state (and the valid/possible transitions/rules - which one could argue that are still part of the game state). I believe exhaustively trying out all decks is not going to fly and deckbuilding should be centered…
>did you look at the already existing playing MTG AIs: https://www.slightlymagic.net/wiki/List_of_MTG_Engines Yes. I'm very likely going to use the guts of XMage to handle card text and encoding the game state and all legal actions. I'm deliberately trying to get a simpler version with only three cards working first so I can see if it's possible to "solve" (i.e. test every single possible action and response for ever…
yeah. defining the problem as hard does not even begin to describe it.
I believe that an AI that plays perfectly while seeing everything (i.e. oppponent hand + both libraryies, so no hidden state) would still be an impressive accomplishment and could be used to fine tune the deck-building process.
Re: Truth from Zero?
#8". It announces an algorithm called AlphaZero that, given the rules of any two-player game of strategy and copious hardware, trains a deep neural network to play the game at skill levels approaching perfection." I have a particular interest in having a computer play the game Magic: the Gathering at an expert level. In some ways, this seems like an ideal fit for AlphaZero - it's a two-player strategy game with a finit…
Take a look at current research in poker-playing for something that is closer to your setting.
Re: Truth from Zero?
#9I like the idea of starting with simpler games to get a feel for how close AZ is to the minimax optimal strategy. For instance, just put chess or go on a smaller board. Part of DeepMind's claim is that their algorithm doesn't need tweaking when one changes the game, so this should be an easy experiment for them to run.
I wonder if there is any principled statistical way to test, given a set of players, how far the best of them is from optimal. Hmm....
Re: Truth from Zero?
#10". It announces an algorithm called AlphaZero that, given the rules of any two-player game of strategy and copious hardware, trains a deep neural network to play the game at skill levels approaching perfection." I have a particular interest in having a computer play the game Magic: the Gathering at an expert level. In some ways, this seems like an ideal fit for AlphaZero - it's a two-player strategy game with a finit…
In absolute generality, it's impossible. The game is Turing complete: 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.sc…
>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.