MCTS AI Update

[BetaSteward]

After struggling with the MCTS AI for several weeks I have reached a point where I cannot make any further improvements without performing major surgery on the XMage game engine. The major hurdle is in pausing and resuming a simulated game at the point that a player needs to make a choice.

I have made some progress on reducing the amount of memory that a games consumes as well as reducing the processing overhead during a game. This allows more games to be simulated per second which helps the tree converge on the best play.

I feel that I should start merging some of the game improvements back into the master branch before it diverges too far. I can then concentrate on making the changes required to get player decisions into the tree.

If no one objects I will spend a few days merging and testing and then I will commit. I have been making use of the test project to ensure that nothing gets broken too badly.

There will be some small changes to the way that some functionality is handled but I will describe these changes a bit later.

Regards,

BetaSteward

[LevelX]

I'm glad to hear again from you and your XMage activities.

The mentioned improvements sound good.
Could you also solve some of the problems that let the Ai get passive often?

I'm curious what changes will come.

[jeffwadsworth]

Can't wait to see the new changes.

[BetaSteward]

Well, I've run into some more road blocks. By trying to merge all of my "improvements" in one commit I've introduced some nasty bugs that are affecting a few cards. I don't want to hack anything in just to make it work so I'm going to take a staged approach and reapply each of my changes, test and then commit them one by one. Hopefully a solution will present it self when I get to the breaking change.

For anyone that's interested I'll provide some background. My goal for the MCTS AI improvements was to dramatically increase the number of simulations per second without eating up huge chunks of memory. During my analysis I found that most of the time and memory was spent was on copying Cards. Since each simulation requires a copy of the game state I could really cut down on memory if I didn't need to include a copy of each Card. Plus I would eliminate the overhead of copying each Card and it's associated abilites, costs, effects, etc. To improve this I started with making Cards immutable.

A requirement for making Cards immutable was to move the ZoneChangeCounters to the game state object. Since Permanents created from Cards share the same UUID as the Card, the ZoneChangeCounters would be shared as well. My initial thought was that this wouldn't be a problem, but I was wrong. The current code relies on Permanents and Cards having separate ZoneChangeCounters. This resulted in targets and cards in exile zones not working properly. I found I was making way too many hacks to get it working properly.

Now that I have the problem in mind I can redo my "improvements" and hopefully tackle the ZoneChangeCounters problem at the same time.

[LevelX]

Well, I've run into some more road blocks. By trying to merge all of my "improvements" in one commit I've introduced some nasty bugs that are affecting a few cards. I don't want to hack anything in just to make it work so I'm going to take a staged approach and reapply each of my changes, test and then commit them one by one. Hopefully a solution will present it self when I get to the breaking change.

For anyone that's interested I'll provide some background. My goal for the MCTS AI improvements was to dramatically increase the number of simulations per second without eating up huge chunks of memory. During my analysis I found that most of the time and memory was spent was on copying Cards. Since each simulation requires a copy of the game state I could really cut down on memory if I didn't need to include a copy of each Card. Plus I would eliminate the overhead of copying each Card and it's associated abilites, costs, effects, etc. To improve this I started with making Cards immutable.

A requirement for making Cards immutable was to move the ZoneChangeCounters to the game state object. Since Permanents created from Cards share the same UUID as the Card, the ZoneChangeCounters would be shared as well. My initial thought was that this wouldn't be a problem, but I was wrong. The current code relies on Permanents and Cards having separate ZoneChangeCounters. This resulted in targets and cards in exile zones not working properly. I found I was making way too many hacks to get it working properly.

Now that I have the problem in mind I can redo my "improvements" and hopefully tackle the ZoneChangeCounters problem at the same time.

True, making the card object immutable sounds like a resonable task.
There are here and there workarounds/or not so optimal handlings that make use of changing the card object.

It's true, a permanent and the card the permanent is derived from have both a own zone chnage counter, but I guess they are counted up both the same way (at least they should).
I lately fixed that a permanent that leaves the battlefield did not increase the zone change counter of the card.

There is also that outstanding issue here: https://github.com/magefree/mage/issues/408
So we have to add to the state a list of objects where for every card the overwritable attributes are handled (e.g. ChangedCardAttributes). Maybe it's the easiest way to clear this list with every card reset and create it anew.
At least this contradicts a little bit to make the card object immutable.
Are you sure, it's the best way to go?

[emerald000]

There is also that outstanding issue here: https://github.com/magefree/mage/issues/408
So we have to add to the state a list of objects where for every card the overwritable attributes are handled (e.g. ChangedCardAttributes). Maybe it's the easiest way to clear this list with every card reset and create it anew.
At least this contradicts a little bit to make the card object immutable.
Are you sure, it's the best way to go?

I think the best way to handle that issue is actually to make cards immutable. All we need are the default characteristic of the cards and the list of current continuous effects.

[LevelX]

There is also that outstanding issue here: https://github.com/magefree/mage/issues/408
So we have to add to the state a list of objects where for every card the overwritable attributes are handled (e.g. ChangedCardAttributes). Maybe it's the easiest way to clear this list with every card reset and create it anew.
At least this contradicts a little bit to make the card object immutable.
Are you sure, it's the best way to go?

I think the best way to handle that issue is actually to make cards immutable. All we need are the default characteristic of the cards and the list of current continuous effects.

And of course a class/object that holds the current values of the changable attributes of a card, e.g. color.
Say a Painter's Servant was cast (chosen color was green). How do you know now, if a card in the graveyard it also green e.g. for a ability that can only target green cards in the graveyard?
You normal use something like:
game.getCard(cardId).getColor().isGreen()

So I guess this also would be best handled from the card object itself.

So maybe we need something like a cardBase that's immutable and a card frame class that also handles the variable attributes. And the GameState is holding a cardAttributes object that's used in the cardFrame to get the variable attributes.
And every card.reset() call, changes the variable attributes back to the values from the cardBase.

Or how would you design the classes for this purpose?

[BetaSteward]

Outside of a game a card is immutable but within a game certain properties can change: face-up/face-down, counters, color, etc.

In my efforts to make cards immutable I created an object called CardState which holds all state information for mutable properties of a Card. The object is held in a collection in GameState. For certain getters and setters on Card I overloaded them with a Game parameter which is used to lookup the CardState in the GameState object. Other setters have been moved to Permanent.

This should be coming in my next commit. I've also been creating a bunch of new test classes to make sure that I haven't broken anything or won't break anything with future changes.

[BetaSteward]

I just pushed my latest changes to the repo. In this update I moved all Watchers to Ability and moved Counters to the new CardState object. There is still more work to do to make Cards immutable.

There is an overloaded method of addAbility that includes a Watcher parameter. This is a convenience method that allows you to add both an ability and it's associated watcher at the same time.

I added some additional tests to check that nothing breaks but I wasn't able to add as many as I hoped. There is one test that is failing but I believe that it is due to an existing defect rather than one I introduced.

I will be away from home for the next week so I will not be able to work on xMage for a few days. Hopefully I haven't broken anything too badly

[mnapoleon]

Couple of issues with these set of changes now that I've had some time to figure out why I can't compile since grabbing them

1) GameState.getCardState make a call of the cardState map (HashMap) to putIfAbsent. This method was just added to HashMap in java 8 as far as I can tell. No big deal but probably should have been noted that Java 8 is now needed.

2) AbilitiesImpl has an @Override annotation on method containsClass but the Abilities interface doesn't have a method with this name.

Anyone else see seeing these issues?

[jeffwadsworth]

Yes, I see them. I needed to go to 1.8 anyway. But the second part needs some attention.

[LevelX]

2) AbilitiesImpl has an @Override annotation on method containsClass but the Abilities interface doesn't have a method with this name.

I missed to commit this interface change. I have done it now.

[fireshoes]

Getting this error when building now.

Failed to execute goal org.apache.maven.plugins:maven-compiler-plugin:3.2:compile (default-compile) on project mage: Compilation failure
mage/game/GameState.java:[786,22] cannot find symbol
symbol: method putIfAbsent(java.util.UUID,mage.game.CardState)
location: variable cardState of type java.util.Map<java.util.UUID,mage.game.CardState>
-> [Help 1]

[mnapoleon]

Getting this error when building now.

Failed to execute goal org.apache.maven.plugins:maven-compiler-plugin:3.2:compile (default-compile) on project mage: Compilation failure
mage/game/GameState.java:[786,22] cannot find symbol
symbol: method putIfAbsent(java.util.UUID,mage.game.CardState)
location: variable cardState of type java.util.Map<java.util.UUID,mage.game.CardState>
-> [Help 1]

This is the one that I think requires Java 1.8.

That method was on the ConcurrentHashMap in 1.7 but wasn't added to HashMap until 1.8. That cardState variable in the GameState class is initialized as a HashMap.
I haven't upgraded to 1.8 yet to see if the issue goes away.

[LevelX]

Yes with 1.8 the problem is gone.
But I changed it to be Java 1.7 compatible and committed the change.