Saturday, November 28, 2009

Creating a state tree

I'm back at min-max for a short question: How do you search the possible sequences of moves in a game?

well, there are two ways: one is, you copy the game state to try different plays. this guarantees you that you don't accidetially manipulate the game, even though you only wanted to test some moves for the computer. it has two downsides: one, you have to take some preparations so that your game state is copyable. magic is a complicated game, and it's easy to forget things. two, it takes up space. while this sounds not too much a problem nowadays, java by default starts with 32MB of memory. I did a test, and that didn't even fit the full game tree of the way easier game of quarto, which I presented earlier.

the second way is to enable undo. you work with the original game, make moves and undo them after running the evaluation function. memory is not the problem here, but the first one stays. an undo function is very complicated to implement, because magic has so many facettes.

I think that the second aproach is the better one. While it may take more work, you will want an undo function at some point, and in addition it implicitly allows some cool stuff: given the initial game state (the order of libraries), you can duplicate a game by applying the same actions to that state. this allows for storing a game state as a file, replaying awesome matches, and easily implement gaming over the network by simply transmitting an action.

1 comment:

nantuko84 said...

now once table was changes, I send the whole table to the client that is not effecient. but once I implement some small package-of-updated-permanents, it will reduce the traffic and make undo action possible.
I even already have an example of it in MagicWars, now tapping lands for mana is the only table action that goes separate. So once you tapped permananent for mane, SM_TABLE_CHANGED_TAPPED instead of big SM_TABLE_CHANGED will be sent.

that means that here I can create undo action that will simply untap.
need to think over it