Traversable Game State/Engine Code

[Myrd]

@ 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

I think it will let the AI play more cards (intelligently) than before - because it can now see complex interactions / effects that the current AI simply couldn't grasp. However, it still won't help with some other cards (e.g. Stain the Mind which exiles cards from opponents library) - since those require more information than just evaluating the board state.

[Agetian]

Thanks a lot for the information and good luck with the project!

- Agetian

[Max mtg]

The view objects are to make Forge playable over network. Instead of serialising the entire game state, the server serialises the relevant view classes and sends those over the network. This means that these classes should definitely not have a reference to any game objects (including the Game itself)... But maybe Dan can comment a bit further here, as he created the current version of the view objects.

Does the server ever serialize these objects? or does just anyone benefit from that system now?

(My idea of views was about client having special classes that act as "views" for objects that exist on server.)

[elcnesh]

Our current idea is serialisation, since the tracking of properties should allow us to do that quite efficiently.

[Hellfish]

@Myrd: Would it be possible/a good idea to make the simulation code available to the forge-game package, as it currently can't be due to creating a circular dependency? Having played around quite a bit with your new developments, I'm certain they could be useful for rules fidelity, specifically Equinox and continuous effects dependencies. Just as a thought for the future, I mean.

[Myrd]

@Myrd: Would it be possible/a good idea to make the simulation code available to the forge-game package, as it currently can't be due to creating a circular dependency? Having played around quite a bit with your new developments, I'm certain they could be useful for rules fidelity, specifically Equinox and continuous effects dependencies. Just as a thought for the future, I mean.

I think it could be OK to do. I suspect only some of the code can move - e.g. the code that copies game state and simulates a move can probably move. But the classes that depend on other parts in forge.ai (e.g. like code that re-uses AI utilities related to picking abilities for example) would likely have to stay in forge.ai. At the moment, though, I would prefer that this code stay together - as it will likely be undergoing a lot of change. Once things stabilize, we can think about moving parts of it out.

[Hellfish]

Absolutely. Like I said, just a thought for the future.

[Myrd]

There's still lots of work to be done, but I've now landed a change that allows enabling the new simulation-based AI from the UI of the game on desktop - with a somewhat hidden context menu when right clicking on the "AI" checkbox in the UI. Among other things, this allows you to have a simulated AI battle the original AI.

(In case you're wondering, from my quick testing, it looks like currently they perform about the same - while the new AI can make better decisions in many cases, it is still rough around the edges and can make stupid moves as well for a number of reasons.)

[excessum]

(In case you're wondering, from my quick testing, it looks like currently they perform about the same - while the new AI can make better decisions in many cases, it is still rough around the edges and can make stupid moves as well for a number of reasons.)

May I know which decks you were using to arrive at this conclusion? I was playing with Standard decks against the simulation AI and it is making terrible decisions. Here are some examples:
1) Sending burns to the face if no creatures are on board
2) Always using pump/protect spells (Gods Willing when opponent has nothing on board, Rakshasa Deathdealer even when not attack/blocking)
3) Wasting spells just to trigger Prowess (Seeker of the Way), even when not attack/blocking

It might be better if the simulation framework is applied to specific decisions like finding good targets for Bile Blight rather than running the entire AI off it. I am thinking of using small simulations to help the AI classify spells in order to simplify logic for stuff like pump/removal/burn/fight/etc. since the SpellAbilityApi system makes it hard to classify sub-abilities (Feat of Resistance) and multi-class abilities (Temur Sabertooth).

A small side note, it seems that playing multiple games with the simulated AI will slow the game down significantly with evaluation scores in the hundreds. Is some of the data not being cleaned up properly?

[Myrd]

(In case you're wondering, from my quick testing, it looks like currently they perform about the same - while the new AI can make better decisions in many cases, it is still rough around the edges and can make stupid moves as well for a number of reasons.)

May I know which decks you were using to arrive at this conclusion? I was playing with Standard decks against the simulation AI and it is making terrible decisions. Here are some examples:
1) Sending burns to the face if no creatures are on board
2) Always using pump/protect spells (Gods Willing when opponent has nothing on board, Rakshasa Deathdealer even when not attack/blocking)
3) Wasting spells just to trigger Prowess (Seeker of the Way), even when not attack/blocking

It might be better if the simulation framework is applied to specific decisions like finding good targets for Bile Blight rather than running the entire AI off it. I am thinking of using small simulations to help the AI classify spells in order to simplify logic for stuff like pump/removal/burn/fight/etc. since the SpellAbilityApi system makes it hard to classify sub-abilities (Feat of Resistance) and multi-class abilities (Temur Sabertooth).

A small side note, it seems that playing multiple games with the simulated AI will slow the game down significantly with evaluation scores in the hundreds. Is some of the data not being cleaned up properly?

There's still a lot of work to do - it's nowhere near ready to replace the current AI. I believe I was playing with standard decks and having AIs play against each other (simulated vs. not).

For example, right now it doesn't take into account combat plans when evaluating pumps and things like that, whereas clearly it should and there is infrastructure (i.e. via the Combat class) to make this happen. I've mostly been focusing on fixing bugs with game copying code lately so at least it can run without failing to simulate correctly due to not copying all of the game state. There's still lots to do on the AI smarts.

Anyway, feel free to experiment with the code and apply your ideas - that's the whole point of open source. Or feel free to fix some the things I've specifically identified above (e.g. simulating combat, better evaluating board state - e.g. to choose not to burn to the face, etc.)

[excessum]

I need a little help understanding the code...

simulateSpellAbility()
- ComputerUtil.handlePlayingSpellAbility(player, sa, game) simulates playing "sa" in "game"
- resolveStack() places the effect(s) that result from the above onto the stack
- loop with "recursionDepth" tries to play other abilities after this

Is the above correct? For a start, I only wish to simulate a single SpellAbility so I can skip the third step entirely. After simulating "sa", I would return the resultant "game" for analysis. Where exactly does the simulation decide how to play subsequently triggered abilities with choices (ie. casting Shock with Shu Yun, the Silent Tempest and Jeskai Ascendancy on board)?

EDIT: Figured out what "recursionDepth" is for, and it is a real resource hog for aggro decks with multiple possible plays in the mid-late game.

[Myrd]

I need a little help understanding the code...

simulateSpellAbility()
- ComputerUtil.handlePlayingSpellAbility(player, sa, game) simulates playing "sa" in "game"
- resolveStack() places the effect(s) that result from the above onto the stack
- loop with "recursionDepth" tries to play other abilities after this

Is the above correct? For a start, I only wish to simulate a single SpellAbility so I can skip the third step entirely. After simulating "sa", I would return the resultant "game" for analysis. Where exactly does the simulation decide how to play subsequently triggered abilities with choices (ie. casting Shock with Shu Yun, the Silent Tempest and Jeskai Ascendancy on board)?

EDIT: Figured out what "recursionDepth" is for, and it is a real resource hog for aggro decks with multiple possible plays in the mid-late game.

Right, recursionDepth is tracking how many moves ahead the AI looks. You can turn it back to just looking one move ahead (as I had it originally) by changing GameSimnulator.MAX_DEPTH constant.

Note that this will cause the AI to miss some move combinations where the sum of two moves is the best thing to do rather than any of the individual moves. Some examples include:
- Cracking a fetchland in order to be able to play e.g. a seige rhino that was previously not possible without it
- Casting two low-cost spells that together give a better benefit than one high cost spell for the same mana

With the recursion, the AI can find the above "automatically". However, I agree that in the current implementation, it can slow to a crawl if there's a lot of abilities available for AI to choose (especially targetted abilities). Right now it does all the possible simulation for the given depth in any order - so exponential complexity. The right way to fix this is to:
- Priority execution - i.e. choosing which recursion to go in first based on the score of the simulation of the first move
- Timing run time, so that the AI can "give up" and return the best move so far when the allocated time resolves
- Remembering best targets for abilities - so that targetted SAs don't explode on each recursion
- Pruning identical simulations - e.g. if two abilities A and B result in the same board state, then after simulating A->B, if you simulate B->A you should be able to determine that it's the same state and stop simulating that branch (i.e. stopping going down further) since you already have processed that state.

The above is just related to the recursion aspects of the code. Of course, there's many other things that need improvement - such as the things I mentioned earlier (e.g. simulating combat, scoring the game state) and other things - e.g. better deciding of spell timing (when it's better to hold a spell even if it would result in some benefit - e.g. saving a removal spell for when the opponent has something better than a 1/1).

[Myrd]

For a start, I only wish to simulate a single SpellAbility so I can skip the third step entirely. After simulating "sa", I would return the resultant "game" for analysis. Where exactly does the simulation decide how to play subsequently triggered abilities with choices (ie. casting Shock with Shu Yun, the Silent Tempest and Jeskai Ascendancy on board)?

This is another area that needs improvement. Right now, there's no special wiring into making choices for triggered abilities. So basically it just runs the existing AI code for making those decisions - and doesn't try to simulate different scenarios (e.g. to pay the mana to give something double strike or not via Shu Yun).

If you want to explore this part, it is a bit tricky. The way the current set up works in existing code is things to make decisions end up as calls on PlayerControllerAI - which returns the result. (I believe.) There's kind of two parts to it:
1. When this is happening in a simulated game, the PlayerControllerAI should defer to the simulation engine for making that decision. The simulation engine may actually want to enumerate possible answers and perhaps do multiple simulations. This can be done by re-running the same top-level simulation of the SA but then providing a different answer to the function that asks to make a decision.
2. When it actually comes down to making the play, in real game mode rather than simulated, the AI again needs to know how to make the best decision. Again, simulation engine could help here. Or if this is something it already previously simulated - perhaps that information could be saved and it could return the previous decision it found as best - but this gets tricky - since now you need to manage extra state and know when it's OK to apply it and when not to. The same problem exists for recursion - if I decide that A->B->C is the best chain, after playing A the AI currently has to simulate again to find that B->C is the way to go, despite it having figured it out earlier. Room for improvement here definitely.

[Myrd]

Note: I just submitted a small refactoring to the code to make it a little bit cleaner - the logic for whether recursion should be continued is now in SimulationController class - which is instantiated once per simulation.

In the future, this class can also have a timer to decide when to stop simulation altogether with a method like shouldContinueSimulation() that the other code would call on it, etc.

[excessum]

Thanks for the detailed replies!

I understand that simulating sequences allows new and possibly better decisions to appear, my concern is the cost, especially with recursion depths greater than two. Any response the opponent makes, however irrelevant (ie. Think Twice), will invalidate the previously (costly) sequence and start a new (costly) sequence.

The issue with carrying decisions to PlayerControllerAI is known (and annoying) and adding recursion adds to the hassle. I think I will stay off such effects for now to go for the low hanging fruit.

Is there any way to mock a PlayerController that only passes? I am looking to simulate a single creature attacking for multiple turns to capture effects like Goblin Rabblemaster and Master of the Feast where the benefit/cost is not apparent immediately.