Traversable Game State/Engine Code

[Myrd]

Got it.

So then it means that any code that looks up a GameEntity from its GameEntityView (via those caches) should be code that would be running on the server in that model. So, for example, UI code shouldn't be doing this, correct? i.e. in such a model the client would only have CardViews and a GameView, but not a Game, right?

And so it's still OK to hang the caches off of the Game object, since if there is a Game, then you're the server, so you're allowed to look up the GameEntity from the GameEntityView - but for some other code that should only be running on the client, they shouldn't have access to either a Game or the GameEntity objects.

[elcnesh]

Completely correct good luck!

[drdev]

Myrd, please include forge-gui-mobile in your workspace. You're latest changes introduced compilation errors with the mobile app.

EDIT: Just committed fixes for those errors, but please be sure in the future to test the mobile app against changes you're making.

[Myrd]

Sorry, will do. Thanks for fixing the errors.

[Myrd]

Just an update on my experimentation (in my local copy).

I hacked up the game's AI to be able to simulate the results of playing a SpellAbility and to evaluate the resulting game state. Then, the AI decides the best SA to use based on the highest scoring game state.

Right now it's nowhere near production quality and I had to hack some things to make this work that need to be done in a proper way (for example, I haven't gotten rid of the global Card cache yet - but just hacked around it by backing up and restoring the Card cache when I switch to using the simulated Game vs. the real one - whereas the correct solution is to make the Card not global and tied to the Game).

Additionally, right now I just simulate 1 move deep (but including resolving the triggers as a result of that move and of the triggers, etc).

Still needs a lot of work before this can be a real thing, but I'm already seeing promising results - for example with my field containing a Serra Ascendant and a Soul's Attendant and me being at 29 life, the AI is able to figure out that playing a creature will cause the Serra Ascendant to become a 6/6 flyer instead of a 1/1 and decides it's better not to play the creature!

There's still lots to do, so my plan is to polish the prototype a bit more and refactor the underlying code to not need the hacks I currently have in place and when hacks are no longer needed for it, I can land it "off by default" at which point others can help with it.

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.

[friarsol]

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.

Are you reusing the functions that we have that already do these type of multipliers or did you make your own? I believe the AI already has similar sounding rankings for when it's trying to decide if it should destroy something with a Doom Blade (or similar).

[Myrd]

Currently using my own - but I'm not married to them. I'll take a look at the existing ones.

[Marek14]

How do you handle the hidden information? Do you randomize it so the algorithm wouldn't give AI information it should not possess?

[Golob]

As a thing for the future, if the parameters were 'easily' modifiable one could think of running a genetic algorithm to find somewhat suboptimal weights for evaluation function components. But thats an even further thing to be done

[Myrd]

How do you handle the hidden information? Do you randomize it so the algorithm wouldn't give AI information it should not possess?

Right now, I don't handle hidden information. The AI just simulates what would happen. So if he's simulating playing Sidisi, he'll know whether he'll get a 2/2 zombie - even if he's not supposed to know what the top 3 cards of his library are.

Obviously, this is cheating and we'll want it to not do this. But I'm not yet at the stage where this is the biggest problem to worry about. Ideally, I think AI should use a probabilistic estimate of expected outcomes and interpolate between the scores of their resulting game states.

As a thing for the future, if the parameters were 'easily' modifiable one could think of running a genetic algorithm to find somewhat suboptimal weights for evaluation function components. But thats an even further thing to be done

I've though of this too - but I think as I said, my belief is that weights of the different attributes in isolation, however much we can tweak them - via a genetic algorithm or not, won't be as good as an algorithm that doesn't look at them in isolation - but rather in comparison to other things (e.g. what's my life total - do I need a blocker now to not die next turn, etc).

Of course, in the most optimal world, one could think we don't need to score the game state at all - we'll simply simulate and play the game tree out and see which moves result in us winning most likely. But I don't think it's realistic to assume we'd be able to do that - there's just too many decision points in magic, so simulating till "game over" through all the branches will take forever - so we'll only be able to look only _so_ deep.

[Marek14]

How do you handle the hidden information? Do you randomize it so the algorithm wouldn't give AI information it should not possess?

Right now, I don't handle hidden information. The AI just simulates what would happen. So if he's simulating playing Sidisi, he'll know whether he'll get a 2/2 zombie - even if he's not supposed to know what the top 3 cards of his library are.

Obviously, this is cheating and we'll want it to not do this. But I'm not yet at the stage where this is the biggest problem to worry about. Ideally, I think AI should use a probabilistic estimate of expected outcomes and interpolate between the scores of their resulting game states.

I always suggested a Monte Carlo approach here -- a function that will randomize all hidden information but keep hidden cards the AI knows about, like top three cards of its library if it used Sensei's Divining Top etc. Then you could create a hundred or so "possible realities" and run a high-speed simulation with default Forge AI (which is dumb, but fast) several turns ahead for each one of them. This would get roughly the same result as a probabilistic estimate without actually requiring any probabilistic calculations. It should be fast. The randomizing function is obviously the trickiest thing because of morph; unknown face-down cards should be determined first since these are the only unknown cards that cannot be, even theoretically, arbitrary.

Another problem is with cards like Clone Shell, where the unknown card can theoretically be anything, but in practice it's more likely to be a creature, though there is not many such cards.

[jje4th]

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).

[Myrd]

Okay, I've landed the changes to finally get rid of the global Card cache (now it hangs off the game). It was a rather large-ish change, so let me know if you see any problems as a result of it - though I've tried to be careful.

Next will be polishing up my game simulation code a bit and fixing a couple of issues with it before landing it (off by default).

[Myrd]

I've committed an initial prototype of the code that makes the AI simulate each SpellAbility before choosing which one to play. It currently only looks one move deep and not any further ahead (and thus can be dumber than current AI that sometimes will try to hold spells back for second main phase, etc).

It's off by default, but you could enable it by setting USE_SIMULATION to true in forge.ai.simulation.SpellAbilityPicker. Warning: It currently prints a lot of debugging output.

Also, while it works most of the time, there are still many issues. A lot of them are in the underlying infrastructure (e.g. making a copy of the game state or UI still triggering from the copy of the Game that's being simulated).

Anyway, having said all that - feel free to try it out!

Post feedback or even hack on it, if you'd like - e.g. fix bugs that you see with it - or make other improvements (there's a number of TODOs and also the game state scoring function can be made much smarter as well). It will take a lot of work to make this really "production quality" - so help is welcome!

[Agetian]

@ Myrd: This is a very interesting project! Thanks a lot for seeing it through to the initial alpha release! It will be great to see how it develops, I think it has a lot of potential to improve the AI in Forge! I'll take some time to look through the code soon, will see if I can contribute in any way. I have a question: does this simulation-based approach to the AI have potential to broaden the array of cards potentially playable by the AI (once e.g. the state evaluation function is improved), or is it bound by the same limitations in what cards are AI-playable as the default AI?

- Agetian