Tips for Forward Models
Always think carefully about copy() implementations
When implementing a game designed with a Forward Model the most important mindset to get into is that everything needs to be designed from the perspective of deep copies. When an agent is planning it will take a copy of the current state, apply several actions, possibly then save a ‘snapshot’ at a point to go revert back to, and then apply several more actions. It is critical that when a copy if taken of an Object (be it of a Game State, a Card, a TurnOrder, or anything else) there is absolutely no chance that changes to the copied Object can impact the original Object, or vice versa.
This is a very common source of often very subtle bugs in a game implementation. Avoiding opportunities for these bugs is helped by a style of programming that tends to the more ‘functional’. Make sure you copy the current state of everything in a class, and do not just re-use a reference unless you are absolutely certain that that thing is immutable. Any Components or helper objects you create for a game will usually also need to implement their own copy() methods so that the whole of a game state can be safely copied with no hanging references to the thing it was copied from.
Avoid Object References
If an Object is to be safely copied, then avoiding multiple direct references to other non-primitive Objects is vital. Consider the setup:
- Object A references Object B and Object C
- Object D references Object C
When calling A.copy(), we also need to copy B and C to avoid any changes to these affecting the original A. But when we copy Object D, if we also naively copy Object C, we now have two copies of this, and changing one will not affect other.
The standard approach is to be clear which Object ‘owns’ each other Object - as a default in TAG this is usually the extension of AbstractGameState. Any other Object that needs a reference should acquire this as needed from the owner.
A concrete example is shown below (this is especially an issue with Actions). Note how DrawCard does not refer to the Deck Objects that it draws from and to by reference, but using a Component ID. When it is copied these simple int fields can safely be copied independently of the main GameState, and when the Action is executed, the actual Deck objects are looked up on the owner.
public class DrawCard extends AbstractAction {
protected int deckFrom;
protected int deckTo;
protected int fromIndex;
protected int toIndex;
protected int cardId; // Component ID of the card moved, updated after the action is executed
protected boolean executed; // Indicates whether the action executed or not
/**
* This action moves one card (given by index in its origin deck) from a deck to another.
* @param deckFrom - origin deck from which card will be moved.
* @param deckTo - destination deck to which card will be moved.
* @param fromIndex - index in the origin deck where the card can be found.
* @param toIndex - index in the destination deck where the card should be placed.
*/
public DrawCard (int deckFrom, int deckTo, int fromIndex, int toIndex) {
this.deckFrom = deckFrom;
this.deckTo = deckTo;
this.fromIndex = fromIndex;
this.toIndex = toIndex;
}
...
@Override
public boolean execute(AbstractGameState gs) {
executed = true;
Deck<Card> from = (Deck<Card>) gs.getComponentById(deckFrom);
Deck<Card> to = (Deck<Card>) gs.getComponentById(deckTo);
Card card = from.pick(fromIndex);
if (card != null) {
cardId = card.getComponentID();
}
return card != null && to.add(card, toIndex);
}
@Override
public DrawCard copy() {
DrawCard copy = new DrawCard(deckFrom, deckTo, fromIndex, toIndex);
copy.cardId = cardId;
copy.executed = executed;
}
Seek Immutability
This is an exception to the point above. If an Object is immutable (i.e. once instantiated it cannot change state, and has no externally available methods that permit this) then we do not need to copy it, and copy() can simply return this.
As a further advantage, copying a state with lots of immutable components is very quick!
There is a downside to this however, and a reason that we do not go the whole functional hog and make GameState immutable. This is entirely plausible, but means that when we apply any AbstractAction that results in a change, we have to generate a whole new GameState as the successor state, leaving the old one unchanged. Generally speaking this is a bad idea as the performance hit of generating a new GameState is much larger than making a small change to internal mutable state (even if we are very careful to only recreate the parts that have changed). But, it is much less prone to accidental bugs, and this innate safety can make it worthwhile with some ingenuity to mitigate this performance hit.
As an illustration of this, have a look at the relative performance figures for the next() and copy() functions of various games on the Performance page. In general, the design objective in forward planning algorithms in TAG is to make the next() cheap, as this is called many more times that copy(). (But, there are of course always exceptions.)
We can extend this point to the DrawCard class above. This could easily be made properly immutable if we did not change the state on execution:
public class DrawCard extends AbstractAction {
protected final int deckFrom;
protected final int deckTo;
protected final int fromIndex;
protected final int toIndex;
...
@Override
public boolean execute(AbstractGameState gs) {
Deck<Card> from = (Deck<Card>) gs.getComponentById(deckFrom);
Deck<Card> to = (Deck<Card>) gs.getComponentById(deckTo);
Card card = from.pick(fromIndex);
return card != null && to.add(card, toIndex);
}
@Override
public AbstractAction copy() {
\\ all state is now immutable and final, so no need to create a new Object at all
return this;
}
The ForwardModelTester utility
Writing unit tests to check for safe copying can be tediously dull. And it’s well-nigh impossible to check every single thing that might have been miscopied, or only trigger after several future actions.
The ForwardModelTester is a utility in TAG that helps test many of these automatically, provided that you have implemented comprehensive hashcode() and equals() methods for the game state and all extended actions. (Comprehensive here means that every field in the game state is included in both functions, including appropriate deep iteration.)
If this is the case, then: 1) every time you copy a state, the hashcode before and after should be identical. 2) every time you apply next() to a copied state, its hashcode should change, but that of the state it is copied from should not (and vice versa)
The ForwardModelTester takes advantage of this, and runs a game using a specified agent. At every single action the two tests above will be checked, and an error thrown if they fail. Additionally, after taking, say, the 53rd action, the ForwardModelTester will also check that the hashcode of the state copies after the previius 52 actions has also not changed…this can help catch more subtle issues in deep copies where an action many steps in the future affects part of the state that was not sufficiently deeply copied.
Tests can then be added, like those below, that run a number of games. The default agent used is a random agent, but for best coverage also make sure you use an MCTS or other forward planning agent as in the second test below. This provides much better coverage and can surface bugs that are otherwise difficult to reproduce. If an error is thrown, then all you are told about is the difference in hashcodes. At this stage you will probably need to add some additional methods to your game to work our exactly where the problem is. (See the toString() methods of Dominion or Puerto Rico for some ideas here.)
Do not use ForwwardModelTester as a replacement of good unit tests. It is an additional integration testing supplement.
@Test
public void testPoker() {
new ForwardModelTester("game=Poker", "nGames=2", "nPlayers=3");
new ForwardModelTester("game=Poker", "nGames=2", "nPlayers=6");
}
@Test
public void testPoker() {
new ForwardModelTester("game=Poker", "nGames=2", "nPlayers=4", "agent=json\\players\\gameSpecific\\Poker\\Poker_3+P.json");
}
You can of course also use this approach to test specific parts of functionality that are especially tricksy, as in the unit test below:
@Test
public void placeMonkActionsGeneratedCorrectly() {
DiceMonasteryGameState state = (DiceMonasteryGameState) game.getGameState();
int startHash = state.hashCode();
DiceMonasteryGameState copy = (DiceMonasteryGameState) state.copy();
assertEquals(startHash, copy.hashCode());
List<AbstractAction> actions;
fm.next(state, new PlaceMonk(0, ActionArea.MEADOW));
actions = fm.computeAvailableActions(state);
int midHash = state.hashCode();
DiceMonasteryGameState midCopy = (DiceMonasteryGameState) state.copy();
assertEquals(midHash, midCopy.hashCode());
assertFalse(midHash == startHash);
fm.next(state, actions.get(0));
assertEquals(startHash, copy.hashCode());
assertFalse(startHash == state.hashCode());
assertEquals(midHash, midCopy.hashCode());
assertFalse(midHash == state.hashCode());
}