Myrd wrote:There will still be a lot of work to make this truly work - for example, the function to evaluate and score a game state probably needs to be very sophisticated - right now I just have dumb multipliers for things like P/T, life totals, some effects - but in reality we probably need to not evaluate things in isolation - for example a creature that the opponent can't block (e.g. due to not having flyers, or it being unblockable or shadow or whatever) is probably worth a whole lot more than one that can be blocked. But maybe not worth as much if the opponent has more creatures and you're at low life and you need blockers rather than a shadow creature, etc.
I gotta say this is a fantastic project. It opens up tons of new possibilities, especially around AI.
Machine learning could provide a very good approach to finding the game state evaluation function. That problem is effectively - given a set of observable parameters about the game state, predict the probability of winning. Machine learning is especially good at this problem given a good training data set. The nice thing about Magic is that the outcome (win/loss) is concrete and available for every game. You just need to collect the event playback logs from a large number of games to train from. (e.g. a "help make forge better by automatically uploading logs" option). Of course even collecting this type of data depends on the refactoring work being done.
For those unfamiliar, here is a quick summary of how the procedure could work:
1) Collect game logs
2) Define a set of observable "features" which define the game state (creature power/toughness, # of creatures, creatures with evasion, life total, etc. - these are all the things that would be an input to an evaluation function)
3) Define a relationship between the "features". Generally you want to start simple with a linear relationship with associated weights - e.g. w1 * f1 + w2 *f2 + ... + wn * fn. (however, as you want to improve it can get more complex - polynomial, exponential, or combinations)
4) Pass the data collected in step 1 (reserving ~10%) though a learning algorithm (e.g. logistic regression) to learn the weights.
5) Evaluate how good the function predict winning by passing the reserved 10% through the function with the parameters learned in #4.
6) Once satisfied with the results, you now have a game state evaluation algorithm.
The nicest thing about the approach is that you could use the existing scoring implementation for steps 2-4 and still evaluate the results against real data. That gives a baseline to objectively evaluate any improvements. However, it all hinges on collecting game logs with action state information.
This is an area I'm very interested in and can help once there is data.
-jim
PS> This approach can also be extended (with effort) to be much more sophisticated - taking into account hidden information and the aggregate outcomes of several potential game states. It could also be used to predict which branches you should traverse further in min/max and which variables are most useful to randomize in monte carlo. (To do that, you would run 100,000+ games with a large number of min/max branches to end state and then feed that back in as training data).