[Improvement] Lazily cloned CardCollection/Cards to improve AI performance

[doctorpangloss]

I'm seeking a way to improve the AI performance without doing huge rewrites like e.g. Brimstone, which explicitly address game state cloning to improve performance.

By profiling I see that about half an alphaBeta's time is spent cloning the game context. 99% of the game context clone time is spent cloning the two players, and 50% of cloning each player is spent on cloning the player's deck.

To clone cards faster, we'd want to "intern" cards. But cards are entities, and entities are assumed to be mutable, so you can't just go and use an interning utility like the one in Guava.

Abilities which mutate every card in the deck are rare. So my expectation is that handling this one special case could significantly improve the performance of the AI.

Can cards be aware of when they're mutated, and clone only then? Can the references to the clones be updated when that clone occurs? You can imagine a pretty cockamamie system with WeakReferences that uses an interned card on reads and creates a newly interned mutated clone on writes. It could just be a feature of CardCollection (List<Card> should always have mutable clones of cards).

Are there any thoughts about how to achieve this? Does there exist a library that facilitates something similar? The payoff would be pretty substantial: a full GameStateValue sim would go just about 20% faster.

Better performance could attract more experimenters to metastone and improve the code base overall. I'm looking forward to contributing this improvement with some help about how to better consider the existing architecture of the engine.

[webadict]

Well, here's the thing: Cards AREN'T mutated until they're drawn. In fact, any Card mutation effect that affects Cards in the deck is explicitly set to only happen when drawn (As this is how Hearthstone implements this... MOSTLY. There are technically cases where this doesn't happen... But those are considered bugs, so we'll avoid them.)

This means that Decks should only contain unmutated Cards... But it IS possible they contain Jade Golem cards, which are stored within the GameContext. But that should ALSO be an unmutated Card.

So, there's your answer: Cards are explicitly unmutated if they're contained in the deck. We could replace the deck with a List of Strings and have no effect on the game.

[demilich1]

So this is really interesting to me. What if we really did that, i.e. replacing the Deck collection with List of card ids? Surely cloning would be much fast that way, also the simulator would use less RAM.

[webadict]

Well... Actually, I'm going to change my answer, as I forgot about two recent additions: Prince Malchezaar, and Patches the Pirate. It's ALMOST doable. The only key cards that remain a factor are those with deckTriggers attached to them, BUT those could be added without the Cards existing themselves (Or possibly in some sort of extra deck space to keep them alive and kicking) or something to that effect.

Technically, if Patches didn't exist, it would be much easier. But, the existence of Patches makes everything awful, really.

[webadict]

Hmm... The more I think about it, the less I like that. Starting the game with a bunch of strings would work, but every additional cards sort of throws the whole thing off. Fringe cases include:

• Malorne, who shuffles his base card into the deck instead of dying. That means if his deathrattle triggers twice, he should only shuffle himself in once, then reshuffle himself in again.
• Weasel tunneler, who shuffles his base card into the opponent's deck instead of dying. This goes back to the original owner if activated twice.
• Madam Goya, who can double battlecry a minion to be summoned from within the deck, but then reshuffles the minion afterward.

So, in order to do this, the cards would still need a unique ID attached to them, especially since triggers need a host, and all that jazz... But it might be possible to have a difference between a Hand Card and a Deck Card.

[demilich1]

Mmmh, really hard to assess if this approach would be worth it. What if the next expansion introduces a card which REALLY interacts with the deck?

But what about the graveyard? As far as I know there are very few cards which interact with the graveyard. Perhaps this would be a good candidate for List of Strings?

Apart from that, maybe the original approach of @doctorpangloss is more promising. However, it might be a mess to implement. Do you know by any chance how Brimstone achieves the really cheap clones of GameState?

[webadict]

As far as I know, no card interacts with the Graveyard... However, the real issue is that the Graveyard is currently a list of Entities, which means that moving to a list of Strings creates confusion when needing to tell if minion_murloc_tinyfin was a minion that died and needs to be resurrected, or if minion_murloc_tinyfin was the card that was discarded.

Now, would Cards necessarily need to exist in the Graveyard? Maybe not. But, they certainly might not need the cloning that's going on with it.

[doctorpangloss]

@demilich1 from reading around, I see that Brimstone says:

This is the default mode. Brimstone uses a proxy class to represent each entity and only copies the proxies when cloning. The base entities maintain a reference count of how many games are using them. When an entity in the cloned game is changed, that entity alone is deep copied with a new reference count of 1, and the original entity has its reference count decremented.

Sounds like interning. But in their code, a Card is not an Entity (targetable) at all. They haven't implemented any abilities that modify cards in the hand / in the deck anyway.

In my opinion, it seems like most of their performance boost comes from not copying decks, because they have no abilities that mutate decks. So after closer inspection, I can conclude that there isn't necessarily much to learn from their implementation.

Specifically, while it sounds like they've implemented interning, they've done it using proxies, which is no good. If you have to iterate through an entire collection and create an new instance for each element, you've saved memory with the proxy but no time. And our goal is to save time.

Furthermore, it looks like they do not use struct (i.e., valuetypes, or easy-to-copy representations in C# of objects) as a performance boost. How would that work?

If in Java we could just copy a contiguous memory region start-to-end representing all the contents of the game state, cloning would be fast. Copy-on-write, which Brimstone claims to have implemented, is supposed to enable contiguous easy copies and mutability: if you mutate the game state, you allocate a large region of memory to accommodate the modification and write a whole, modified copy to that new region. Brimstone's implementation of copy-on-write doesn't really enable this performance benefit though. To do it in metastone, you'd need to make e.g. a byte array that "backs" the entire game state (the two player objects, tigger manager, environment, turn number, turn state and ID factory ID) and use sun.misc.Unsafe for fast copies. Very cumbersome... But it would be super fast!

[demilich1]

I also already thought about the 'represent the game state as a byte array' direction. It would be a lot of work. The main question for me is just: Is it really THAT much faster? Because I don't really know how the .clone() method in Java works; it is clearly some kind of low-level magic. For example you can see some performance results here: https://vyazelenko.com/2013/10/29/copy-object-in-java-performance-comparison/ where calling .clone() is much faster than calling a hand-crafted copy constructor. I agree that copying a single continuous byte array will probably still be much faster, but what about the runtime performance? Each time the game state changes the byte array would need to be updated, which could be very expensive. There would be nice side-effects though, we could easily persist the game state on disc or even share it across a network connection.