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;
    }

Hashcode may be your friend

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.

One useful tool for this is us the hashcode() contract (and make very sure that you include all parts of an Object’s state in the hashcode). If these are correctly implemented, then when writing standard unit tests it is very easy to add in a test to exhaustively check the correct copying of a state using the pattern shown in the example below.

The idea is that: 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)

    @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());
    }

With this pattern, every unit test written to test some element of new functionality can be adapted to also be a unit test to check safe copying and check for future accidental copying errors.