Traversable Game State/Engine Code

[Myrd]

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.

You can probably just have a new class implement PlayerController and do the passing or whatever to make things work. I don't think this exists already.

By the way, I've landed an improvement to the simulation AI so that it actually tries to simulate the next combat each turn, which it uses to decide whether temp P/T boost effects change the score or not. (It can be smarter still... but for now this is better than before.)

By the way, here's an example of the kind of cool stuff this AI currently is able to figure out on its own: With Liliana and Ajani both in play, AI figured out (looking 3 moves deep) that it could use Liliana to search for a Siege Rhino* and put it on top of the library, then use Ajani to look at the top 4 cards of the library and choose one from among them (Seige Rhino*) and then play Seige Rhino for great results.

Of course, the above has a lot of caveats currently. For one, the AI currently cheats since there's no concept of "hidden information" - so it knew that using Ajani's ability without Lili wouldn't be as good due to having access to the information about its library. This can be fixed by keeping track of what's hidden to the AI - but ideally AI would also have some prediction - else AI would never using Ajani's top4 ability. But for now, there are bigger fish to fry.

*These choices were made by existing AI code, not using simulation. Possibly could be improved, but maybe good enough.

[Xitax]

By the way, here's an example of the kind of cool stuff this AI currently is able to figure out on its own: With Liliana and Ajani both in play, AI figured out (looking 3 moves deep) that it could use Liliana to search for a Siege Rhino* and put it on top of the library, then use Ajani to look at the top 4 cards of the library and choose one from among them (Seige Rhino*) and then play Seige Rhino for great results.

Of course, the above has a lot of caveats currently. For one, the AI currently cheats since there's no concept of "hidden information" - so it knew that using Ajani's ability without Lili wouldn't be as good due to having access to the information about its library. This can be fixed by keeping track of what's hidden to the AI - but ideally AI would also have some prediction - else AI would never using Ajani's top4 ability. But for now, there are bigger fish to fry.

In this case, I don't feel that it's cheating to know what's in your deck, provided it doesn't know the exact order. A human would do the same thing, I think.

[Marek14]

Contents of its deck should be known, and from that it can know what is left in library.

[Myrd]

Right. In this case, it knew Siege Rhino wasn't already in the top 4 cards - which was the part that was cheating. If it was, it wouldn't need to have bothered to use Liliana's ability first.

[excessum]

Right. In this case, it knew Siege Rhino wasn't already in the top 4 cards - which was the part that was cheating. If it was, it wouldn't need to have bothered to use Liliana's ability first.

I have a feeling that enforcing hidden information is going to be a major PITA for the simulation. Ideally, the simulated "game" should replace hidden cards (libraries, opponent hand/face-down) with mock/blank cards, replacing them when the state allows it like your Vampiric Tutor example or stuff like Thoughtseize, Courser of Kruphix. How and when to update this information is going to be messy though.

The current version with the simulated AI magically seeing all cards (due to going forward in time via simulation) is probably easier (albeit unfair) otherwise simulating cards with reveal-and-choose (Ancient Stirrings, Commune with Nature) will require messy probability computations based on the player's deck composition.

[Marek14]

Right. In this case, it knew Siege Rhino wasn't already in the top 4 cards - which was the part that was cheating. If it was, it wouldn't need to have bothered to use Liliana's ability first.

I have a feeling that enforcing hidden information is going to be a major PITA for the simulation. Ideally, the simulated "game" should replace hidden cards (libraries, opponent hand/face-down) with mock/blank cards, replacing them when the state allows it like your Vampiric Tutor example or stuff like Thoughtseize, Courser of Kruphix. How and when to update this information is going to be messy though.

The current version with the simulated AI magically seeing all cards (due to going forward in time via simulation) is probably easier (albeit unfair) otherwise simulating cards with reveal-and-choose (Ancient Stirrings, Commune with Nature) will require messy probability computations based on the player's deck composition.

My idea was to mix all unknown cards and redistribute them as starting point for Monte Carlo simulations; the only problem would be with cards that are unknown but not completely random, like something hidden by Windbrisk Heights. This would, for example, allow to evaluate a card draw spell based on specific cards left in the library with average value being calculated not by an algorithm, but by a stochastic process.

[excessum]

Do you mind refactoring out a portion of your GameSimulator class for a simpler base class? I am not familiar with inheritance in Java but I suppose I can always add this new class in the package and modify the required functions to "protected static".

Code: Select all

public class SpellAbilitySimulator{
    private GameCopier copier;
    private Player ai, opp;
   
    public SpellAbilitySimulator(final Game origGame, final Player aiPlayer) {
        copier = new GameCopier(origGame);
        ai = aiPlayer;
        opp = aiPlayer.getOpponent();
    }
   
    /**
     * Plays out a the chosen SpellAbility and returns the game state
     * @param origSa SpellAbility with choices (targets, X, etc.) already made
     * @return game state after given ability resolves
     */
    public Game playSpellAbility(final SpellAbility origSa) {
        Game game = copier.makeCopy();
        SpellAbility sa = findSaInSimGame(origSa);
        if (sa == Ability.PLAY_LAND_SURROGATE) {    //probably do not need this branch now
            ai.playLand(sa.getHostCard(), false);
        } else {
            ComputerUtil.handlePlayingSpellAbility(ai, sa, game);   //need to be careful of calls to PlayerControllerAi
        }
        resolveStack(game, opp);    //need to be careful of calls to PlayerControllerAi
        return game;
    }
}

[KrazyTheFox]

I've recently started work on this again and am fleshing out the basics I had before into a bigger proof-of-concept, going so far as to turn this into a playable (if lacking content) version of MtG. So far I have a game in which I can play lands, tap for mana, and go through turns/phases sequentially with an "AI" that always passes priority. I've discovered that this whole thing gets a hell of a lot more complicated when I have to account for the UI and what each player can do/see.

An example of this is paying mana costs. A player should be able to interact with the game state while paying costs without the other players receiving any information until the cost is paid and a spell is cast/ability is activated/etc.

With the current implementation, when a player taps a card, the information is broadcast to all players immediately. The game state needs to be decoupled here so players can progress a separate game state while paying costs that the other players are not listening to, then the changes in that state need to be applied to the real game once the cost is paid completely and the spell is cast/ability is activated/etc.

My current solution for this is to have a translation layer between the game itself and the UI. The UI would watch for changes and requests from the translation layer. The translation layer would present a set of "views" tied to an underlying game state, so that the state can be cloned/branched off and the UI won't have to re-register tons of listeners. Each player would have their own translation layer hooked into a game state. This only mitigates half of the problem, though, as I'll need a way to reconcile these intermediary objects with ones between potentially several game states at once.

My first idea is to give everything a numerical ID, then compare against the intermediary objects when switching game states. This seems a bit cumbersome and I'd like to find a better way to have UIs arbitrarily observe any number of game state clones/branches (it'll only ever observe one state at a time). Anyone have any ideas on how I can better swap out game states without having to register UI listeners again?

[KrazyTheFox]

I went back and read over the way Duels of the Planeswalkers handles their game state branching and I think it's way easier than doing what I was thinking of doing. Instead of cloning the game state and having each player listen to one at a time and switching between states, it's going to be much easier to have each player run their own game engine. They'd be synced whenever the player with priority needs them to be. This way, each player only sees what's in their local version of the game and when it's time for something to be visible to everyone, the rest of the games catch up. This will also make networked games basically built in already. In fact, I'll likely implement each state as a server/client early on.

Edit: Yeah, looks like networking from the get-go is going to be easiest.

[KrazyTheFox]

I had no idea I'd be opening such a huge can of worms when I took this up again. It's becoming quite clear that I need way more experience with threading. When I introduce a delay into everything it works fine, but take that away and there's race conditions everywhere. Woohoo! With the delay I now have the ability to decouple the game state to process AI (or payments) which will get signaled, properly rolled back, and synchronized when an event comes from another player. Once I sort out these pesky threading issues I'll be able to start posting demos of this in action.

[Agetian]

Sounds great so far, Krazy! Good luck with this effort! I'm sure that with time you'll be able to overcome the difficulties, can't wait to see some of this in action!

- Agetian

[KrazyTheFox]

Yesterday I nailed all the threading issues I could find. Today I've implemented some extremely basic casting of spells. I can now play lands, tap lands for mana, cast spells, and pay for spells. When a spell is cast it goes onto the stack and when all players have passed priority, the spell resolves. Paying for spells and AI simulations (currently just plays a land on its first turn) are decoupled from synchronization. When the payment is complete or the AI has performed their selected move, the game state difference is synchronized across all games. Undo/Redo, while possible, does not get synchronized yet. Any undos/redos must be performed while the game is decoupled from synchronization. I'll fix this one soon.

The costs are not enforced at the moment (I can pay for my Eager Cadet with green mana), nor is legality of casting spells. Fixing that is up next on my list, as is adding some basic card stats, like power and toughness. State-based actions will follow shortly and combat will likely happen after that.

The games are all networked through hard-coded, local sockets, but this would be very easy to inject real networking into. State synchronization uses an extremely small amount of data and should be playable on just about any internet connection in existence. It'll also allow the game to be streamed to files for saving/loading/playback without taking up much space.

Turns are handled as objects and each turn has its own list of steps/phases. The game maintains a list of future turns (generating a new one for the next player if the list is empty). Inserting steps/phases/turns is as simple as inserting a step/phase/turn into the appropriate list.

I'm hoping that within the next week or so I'll be able to post a playable demo of the Starter 2000 "set" in action (minus instants/sorceries, unless things go really well).

Edit: Have a .gif. (Yes, the AI is a dirty cheater.)

[Agetian]

That's really interesting, Krazy, congrats on your progress thus far! Can't wait to get my hands on the first playable demo and take a look at how things go!
A quick question: I noticed that you're using a specialized rudimentary UI for your current implementation (in the .gif) - is it going to be compatible with the Forge GUI in the end or will it be a completely "a thing in its own right" (new game logic + new UI)?

- Agetian

[KrazyTheFox]

That's really interesting, Krazy, congrats on your progress thus far! Can't wait to get my hands on the first playable demo and take a look at how things go!
A quick question: I noticed that you're using a specialized rudimentary UI for your current implementation (in the .gif) - is it going to be compatible with the Forge GUI in the end or will it be a completely "a thing in its own right" (new game logic + new UI)?

- Agetian

The UI I'm using is a quick thing I threw together with JavaFX. Answering your question isn't really a simple "yes" or "no", so I'll explain a little of how it works and go from there.

Currently, every value in the game that is relevant to the UI in some way is an ObservableValue, a basic Observable pattern implementation. Whenever a value gets changed, that value notifies its listeners. This completely decouples the UI from any game logic and allows the game to do whatever it needs to without concerning itself with making sure the UI is synchronized, especially when working with undos/redos. For example, when a card is tapped, the CardView is notified and sets its own orientation accordingly without having to update (or care about) any other values.

The UI also maintains a reference to human player controllers. The human player controller is a middle ground between the game and the UI and passes commands between the two, enforcing rules as need be (simple things like trying to play a land when you shouldn't be able to). In the case of the AI, it manages the AI's separated simulation thread and will interrupt it when appropriate (it still uses the same interface). I'll likely introduce these checks into the game object itself to ensure that a poorly coded controller can't break the game. Controllers can also be swapped out almost at will, allowing players to take over other players' turns with ease.

All of this should, in theory, be compatible with Forge's current UI, though I've made no attempts to keep it compatible thus far. It'll probably take some significant work to coerce it into using this system. Personally, I'd like to see a transition to JavaFX for the desktop game. It'd be much more hi-dpi friendly and future-proof and the ability to define UI layouts completely outside code would be a nice benefit, too. Besides, Forge 2.0 should probably come with a fresh coat of paint.

[Agetian]

Hehe, makes sense! Best of luck to you! I sincerely wish and hope that you succeed with all these amazing goals!

- Agetian