It is currently 19 Jul 2019, 10:49
   
Text Size

Traversable Game State/Engine Code

Post MTG Forge Related Programming Questions Here

Moderators: timmermac, friarsol, Blacksmith, KrazyTheFox, Agetian, CCGHQ Admins

Re: Traversable Game State/Engine Code

Postby KrazyTheFox » 11 Sep 2014, 00:27

Today's bit of programming involved started working out which classes should have which responsibilities and more of how the whole thing fits together, starting with Phases. I've always thought it odd that the PhaseHandler class has the main game loop instead of, well, Game. I'm considering switching the game loop over to Game where it makes more sense and can be tied in closer to the event and action queues, then having PhaseHandler handle only the phases—beginning, ending, and switching them. This is subject to further change as I dig around more.

As far as actual implementation goes, I've ensured that passing priority works as intended. I can now pass on phases and turns will rollover in priority for eternity, since none of the stuff that ends the game is implemented. I'm starting to pull the phase change actions into event and action classes instead so that steps/phases can be undone and redone.
User avatar
KrazyTheFox
Programmer
 
Posts: 725
Joined: 18 Mar 2014, 23:51
Has thanked: 66 times
Been thanked: 226 times

Re: Traversable Game State/Engine Code

Postby excessum » 12 Sep 2014, 00:32

Just a random question off my mind: In order to implement the "game-state" as you describe, won't you have to refactor the entire engine and player controller codebase to support the concept of a player "action"? For example a single combat with multiple creatures on both sides will involve
1) choice of combatants
2) assignment of attackers (if planeswalker(s) are present)
3) assignment of damage
*) insert the possible activated and triggered abilities all over the place...
and repeat for the defender. I don't think there is a common interface presently to represent the above player choices as a sequence of interchangeable "actions".
excessum
 
Posts: 177
Joined: 21 Oct 2013, 02:30
Has thanked: 0 time
Been thanked: 19 times

Re: Traversable Game State/Engine Code

Postby KrazyTheFox » 12 Sep 2014, 01:23

excessum wrote:Just a random question off my mind: In order to implement the "game-state" as you describe, won't you have to refactor the entire engine and player controller codebase to support the concept of a player "action"? For example a single combat with multiple creatures on both sides will involve
1) choice of combatants
2) assignment of attackers (if planeswalker(s) are present)
3) assignment of damage
*) insert the possible activated and triggered abilities all over the place...
and repeat for the defender. I don't think there is a common interface presently to represent the above player choices as a sequence of interchangeable "actions".
This does involve rewriting the entire rules engine, yes (which is why it's probably several months away at the very least). For something like blockers, a declared blocker would be a BlockerDeclaredEvent and that event would submit GameActions to the Game that would set the game state appropriately. The GUI itself works fine with all of this.
User avatar
KrazyTheFox
Programmer
 
Posts: 725
Joined: 18 Mar 2014, 23:51
Has thanked: 66 times
Been thanked: 226 times

Re: Traversable Game State/Engine Code

Postby excessum » 12 Sep 2014, 03:46

KrazyTheFox wrote:This does involve rewriting the entire rules engine, yes (which is why it's probably several months away at the very least). For something like blockers, a declared blocker would be a BlockerDeclaredEvent and that event would submit GameActions to the Game that would set the game state appropriately. The GUI itself works fine with all of this.
Hmm I was thinking about how to contribute to or even start this gargantuan effort...

I am only familiar with the AI code so relating to that, a simple AI decision to use/play an effect/spell is SpellAbilityAi.canPlayAi() with the selected targets embedded somewhere within that. For the desired list of decision representation, the above has to be broken into individual choices for each of the possible decision branches (ie. Hero's Downfall only requires targets while Hour of Need is going to be a nightmare).

The AI combat logic with AiBlock/AttackController implements lists of Cards and makes comparisons between the attacker and blocker lists so it might be easier to start with that. Unfortunately, the logic for abilities and spells is still required for this to work properly. It might be possible to just consider end-states (ie. after pumps and ability activates) from the currently available PumpAiBase and save the SpellAbilityAi for later though.
excessum
 
Posts: 177
Joined: 21 Oct 2013, 02:30
Has thanked: 0 time
Been thanked: 19 times

Re: Traversable Game State/Engine Code

Postby Agetian » 12 Sep 2014, 03:49

@ KrazyFox: This is indeed a really big undertaking, and I wholeheartedly support your desire in giving it a shot! Better AI and networking support (which are largely the possibilities that open up once what you're planning is done) were talked about for years but no one has been able to complete the foundation for it yet. :( Best of luck to you in this hard and long work, I respect your decision to see this through and I believe that you can see this project through and I'm sure that it will help make Forge considerably better in several aspects!

A more technical question because your project involves a large amount of work that will likely take many months: would you like to consider setting up a branch for your project on our SVN? I mean, the code base is rather dynamic. You'll basically be rewriting huge portions of the game to make this all work, and probably the most frustrating thing that can happen is if some other drastic code base change breaks your newly written code halfway (or more) through. If you set up a branch you'll be able to slowly merge portions of trunk with your code where and when necessary to ensure that everything still works smoothly; at the same time, other devs will be able to see what you're doing by switching over to your branch and possibly they'll have some ideas or contributions that will prove worthy and, if anything, can possibly speed up the development process? Please let me know what you think.

- Agetian
Agetian
Programmer
 
Posts: 3341
Joined: 14 Mar 2011, 05:58
Has thanked: 641 times
Been thanked: 495 times

Re: Traversable Game State/Engine Code

Postby elcnesh » 12 Sep 2014, 09:15

I fully support the idea of this undertaking, and would gladly contribute to it :) However,it might be a good idea to wait just a bit until my branch has merged back into trunk, which (considering the current status) should be before the next beta release. It features a number of changes to the code, and I think it'd be horrible to have these two huge refactoring branches in parallel.
elcnesh
 
Posts: 290
Joined: 16 May 2014, 15:11
Location: Netherlands
Has thanked: 34 times
Been thanked: 92 times

Re: Traversable Game State/Engine Code

Postby KrazyTheFox » 12 Sep 2014, 20:44

Agetian wrote:@ KrazyFox: This is indeed a really big undertaking, and I wholeheartedly support your desire in giving it a shot! Better AI and networking support (which are largely the possibilities that open up once what you're planning is done) were talked about for years but no one has been able to complete the foundation for it yet. :( Best of luck to you in this hard and long work, I respect your decision to see this through and I believe that you can see this project through and I'm sure that it will help make Forge considerably better in several aspects!

A more technical question because your project involves a large amount of work that will likely take many months: would you like to consider setting up a branch for your project on our SVN? I mean, the code base is rather dynamic. You'll basically be rewriting huge portions of the game to make this all work, and probably the most frustrating thing that can happen is if some other drastic code base change breaks your newly written code halfway (or more) through. If you set up a branch you'll be able to slowly merge portions of trunk with your code where and when necessary to ensure that everything still works smoothly; at the same time, other devs will be able to see what you're doing by switching over to your branch and possibly they'll have some ideas or contributions that will prove worthy and, if anything, can possibly speed up the development process? Please let me know what you think.

- Agetian
Once I have the main parts written I'll definitely make a branch for this. Right now since there's so many things woven do closely together I'm starting over with empty files that would completely break everything if I were copy them into the current code base. That would pretty much defeat the point of branching. Hopefully this step won't take too long. I can expand on what's preventing things when I get home as typing on phone is slow for such a large amount of text and work almost over the day.

elcnesh wrote:I fully support the idea of this undertaking, and would gladly contribute to it :) However,it might be a good idea to wait just a bit until my branch has merged back into trunk, which (considering the current status) should be before the next beta release. It features a number of changes to the code, and I think it'd be horrible to have these two huge refactoring branches in parallel.
Most of the stuff I'm doing right now isn't dependent on any existing forge code, so no worries there! I'll look at the new UI stuff when I'm ready to start adding interaction back in and since I'm not on the main branch (or any branch) right now there's nothing break.
User avatar
KrazyTheFox
Programmer
 
Posts: 725
Joined: 18 Mar 2014, 23:51
Has thanked: 66 times
Been thanked: 226 times

Re: Traversable Game State/Engine Code

Postby Marek14 » 14 Sep 2014, 09:19

You could use the Monte Carlo method with this, basically:

1. At each step of AI, build a list of actions AI can take.

2. Make a number of simulations for each action. At the beginning of each simulation, randomize unknown cards. This means to take all "invisible" cards for every player and randomly re-assign them, so if opponent has hand of 7 cards, 40 cards remaining in library and 3 face-down creatures, the simulation will build his hand, library and morphs randomly from cards he plays but the AI cannot see at the moment. If the AI used some effect to see his hand, then those cards are known and will be locked to be the same.
This is mainly to prevent cheating (if AI can get a very good card by using a random "draw a card" effect, it would otherwise "know" that it's a very good idea to use the effect). It also allows to implicitly solve some problems like "how likely it is that opponent has a counterspell?". The only problem is that simple randomization algorithm might have some problem with morphs (which are restricted to cards with morph keyword) or with cards like Summoner's Egg where the face-down card in exile can theoretically be anything, but it will be usually a card from restricted set.

3. After randomizing, the AI takes the action which is being evaluated, and then the basic Forge AI is used to run the simulation, making decisions for all players.

4. When the simulation stops, the game state is evaluated. All game states resulting from one action are then averaged. Since default Forge AI is very fast, it might be even possible to let the game run until the end and just evaluate how many simulations were won by AI.

5. In the end, AI will, in the "real game", take action with highest score.

This approach has some advantages. For example, it allows AI to play around threats correctly since the randomization will tell it roughly the right chance that a threat is among the invisible cards. It selects strategies that are good in general, and not just with a specific configuration of invisible cards that's supposed to be unknown. It should also allow AI to use "corner" plays that are only advantageous in certain rare situations like casting Lightning Bolt on yourself to boost your Death's Shadow if such play can lead to a quick win. There are no branching trees (there can be, but they are not necessary), increasing speed.
Finally, it would allow AI to use any card in the game (though the cards it's not able to use well at the moment wouldn't be used well in simulations, so playing with them or against them would still be weaker).
Marek14
Tester
 
Posts: 2647
Joined: 07 Jun 2008, 07:54
Has thanked: 0 time
Been thanked: 262 times

Re: Traversable Game State/Engine Code

Postby mastroego » 14 Sep 2014, 12:33

This is very fascinating.
Human intelligence is not that different after all: evaluate options, guesstimate the results.
OK, actual intelligence requires a perfected feedback-adjustments loop, but for the sake of the game, this could be HUGE :)

Wish I was a skilled programmer to help...
mastroego
 
Posts: 231
Joined: 22 Sep 2013, 14:04
Has thanked: 28 times
Been thanked: 16 times

Re: Traversable Game State/Engine Code

Postby silly freak » 16 Sep 2014, 23:00

Only reading the initial post (it's 1 AM over here), this sounds great. I have done something similar, maybe you can use some of my concepts, or even code: http://laterna--magica.blogspot.co.at/2 ... chive.html Basically, I look at games as if they were git repositories. The actions done by players are the commits; the changes made to objects are the deltas between two commits; a history of the game can be viewed as a branch. And the whole thing can be replicated as often as needed, without a central or privileged repo (e.g. give the AI module its own game engine to play with - and multiplayer of course).

I will read up on this thread tomorrow!
___

where's the "trust me, that will work!" switch for the compiler?
Laterna Magica - blog, forum, project, 2010/09/06 release!
silly freak
DEVELOPER
 
Posts: 598
Joined: 26 Mar 2009, 07:18
Location: Vienna, Austria
Has thanked: 93 times
Been thanked: 25 times

Re: Traversable Game State/Engine Code

Postby KrazyTheFox » 16 Sep 2014, 23:14

silly freak wrote:Only reading the initial post (it's 1 AM over here), this sounds great. I have done something similar, maybe you can use some of my concepts, or even code: http://laterna--magica.blogspot.co.at/2 ... chive.html Basically, I look at games as if they were git repositories. The actions done by players are the commits; the changes made to objects are the deltas between two commits; a history of the game can be viewed as a branch. And the whole thing can be replicated as often as needed, without a central or privileged repo (e.g. give the AI module its own game engine to play with - and multiplayer of course).

I will read up on this thread tomorrow!
Yeah, that's pretty much exactly what I'm doing. :P
User avatar
KrazyTheFox
Programmer
 
Posts: 725
Joined: 18 Mar 2014, 23:51
Has thanked: 66 times
Been thanked: 226 times

Re: Traversable Game State/Engine Code

Postby Agetian » 17 Sep 2014, 17:07

I think this is a priority thread that is hopefully going to only increase its relevance as the project is developed further and further. Maybe it's worth making this thread sticky so it doesn't get lost among other posts and so that it's visible enough for everybody to discuss?

- Agetian
Last edited by Agetian on 17 Sep 2014, 17:51, edited 1 time in total.
Agetian
Programmer
 
Posts: 3341
Joined: 14 Mar 2011, 05:58
Has thanked: 641 times
Been thanked: 495 times

Re: Traversable Game State/Engine Code

Postby silly freak » 17 Sep 2014, 17:31

So you're trying to come up with a concept separate of Forge before trying to integrate it. I think this is a good idea. After all, the concept is applicable to any turn based game/general purpose engine. It's gonna be hard to integrate this into an existing code base as large as Forge - you have my respect for trying!
Two things I couldn't read out of this thread, but you probably thought of them already: be sure to use identifiers that are applicable across engines. For example, if two engines execute "put a ... creature token onto the battlefield", both engines need the same ID for this token. I think the easiest way for this is to make ID generation predictable. Second, make sure that the game logic, like triggers, is separate from the undo/redo logic (and everything else). You don't want an ETB trigger to go off when a destroy effect is undone, but you do want the card to reappear on the battlefield in the GUI.
If you can use concepts or code from my project, please do, it's open source. I doubt you can just reuse it for Forge, as it pulls in a few dependencies (AspectJ, Protobuf, Polybuf).

Good luck!
___

where's the "trust me, that will work!" switch for the compiler?
Laterna Magica - blog, forum, project, 2010/09/06 release!
silly freak
DEVELOPER
 
Posts: 598
Joined: 26 Mar 2009, 07:18
Location: Vienna, Austria
Has thanked: 93 times
Been thanked: 25 times

Re: Traversable Game State/Engine Code

Postby KrazyTheFox » 17 Sep 2014, 17:42

silly freak wrote:So you're trying to come up with a concept separate of Forge before trying to integrate it. I think this is a good idea. After all, the concept is applicable to any turn based game/general purpose engine. It's gonna be hard to integrate this into an existing code base as large as Forge - you have my respect for trying!
Two things I couldn't read out of this thread, but you probably thought of them already: be sure to use identifiers that are applicable across engines. For example, if two engines execute "put a ... creature token onto the battlefield", both engines need the same ID for this token. I think the easiest way for this is to make ID generation predictable. Second, make sure that the game logic, like triggers, is separate from the undo/redo logic (and everything else). You don't want an ETB trigger to go off when a destroy effect is undone, but you do want the card to reappear on the battlefield in the GUI.
If you can use concepts or code from my project, please do, it's open source. I doubt you can just reuse it for Forge, as it pulls in a few dependencies (AspectJ, Protobuf, Polybuf).

Good luck!
For the token IDs and such, the entire game will be 100% deterministic when I'm done. As long as events are executed in the same order and as long as the random generator is seeded the same in all games, every little thing will be identical. This is a wonderful little side effect of the way I'm building this that will also make pinpointing bugs easy. Need to reproduce something? Share the game log!

Triggers work in much the same way as everything else. When you undo something, whatever the trigger added to the game will be undone as well. Then, should you redo something, the trigger will fire again in the exact same way it did before it was undone. A token entering the battlefield after a kill spell is undone won't trigger anything since triggers won't be checked at all.

So in fact, the triggers will be very closely tied in to the undoing and redoing of game states, just not quite in the way you're thinking. Check out the triggers topic newly posted in this forum for an idea of how this will function. I'm at work and don't have time to write it again.

As you can probably tell, great care is being put into making sure everything is well and truly capable of being undone and redone completely and as many times as desired.
User avatar
KrazyTheFox
Programmer
 
Posts: 725
Joined: 18 Mar 2014, 23:51
Has thanked: 66 times
Been thanked: 226 times

Re: Traversable Game State/Engine Code

Postby silly freak » 18 Sep 2014, 07:48

KrazyTheFox wrote:For the token IDs and such, the entire game will be 100% deterministic when I'm done. As long as events are executed in the same order and as long as the random generator is seeded the same in all games, every little thing will be identical. This is a wonderful little side effect of the way I'm building this that will also make pinpointing bugs easy. Need to reproduce something? Share the game log!

Triggers work in much the same way as everything else. When you undo something, whatever the trigger added to the game will be undone as well. Then, should you redo something, the trigger will fire again in the exact same way it did before it was undone. A token entering the battlefield after a kill spell is undone won't trigger anything since triggers won't be checked at all.

So in fact, the triggers will be very closely tied in to the undoing and redoing of game states, just not quite in the way you're thinking. Check out the triggers topic newly posted in this forum for an idea of how this will function. I'm at work and don't have time to write it again.

As you can probably tell, great care is being put into making sure everything is well and truly capable of being undone and redone completely and as many times as desired.
Cool! Yeah, it's great how many things suddenly become possible when the game logic is organized into GameEvents - undo, network play, spectators, game recording, AI...

Speaking of network, how are you serializing GameEvents? Are you including the GameActions, or are you re-running the GameActions on the other side? Do you identify game states as well, or only events, i.e., will two engines be aware whether they are in the same state or not at a given moment?
___

where's the "trust me, that will work!" switch for the compiler?
Laterna Magica - blog, forum, project, 2010/09/06 release!
silly freak
DEVELOPER
 
Posts: 598
Joined: 26 Mar 2009, 07:18
Location: Vienna, Austria
Has thanked: 93 times
Been thanked: 25 times

PreviousNext

Return to Developer's Corner

Who is online

Users browsing this forum: No registered users and 6 guests


Who is online

In total there are 6 users online :: 0 registered, 0 hidden and 6 guests (based on users active over the past 10 minutes)
Most users ever online was 287 on 31 Mar 2019, 04:11

Users browsing this forum: No registered users and 6 guests

Login Form