IExtendedSequence Action chains

IExtendedSequence Action chains

The IExtendedSequence interface supports linked extended actions, potentially across multiple players. This is useful in two related use-cases:

  1. Move Groups

    This is where we have to make what is formally a single ‘action’, but one which makes sense to break up into a set of distinct decisions to avoid combinatorial explosions. An example in Dominion is where we have to discard 3 cards out of 6. This gives a total of 20 possible actions (6C3); but might be more tractable to consider as three distinct decisions - the first card to discard (out of 6), then the second (out of 5), and then the third (out of 4). This formally gives 120 options over the three decisions, but can be very helpful where there is clearly one best card to discard, which will focus MCTS rapidly on this as the first action. An example in Catan might be first deciding to what to build (Development Card, Settlement, or Road if you have cards for any of them), and then secondly deciding where to build it.

    (The ‘Move Group’ comes originally (I think) from Saito et a. 2007 in Go, and the idea of first deciding whether to play a) in the corners, b) adjacent to the last piece played, c) one of the other possible board positions; and then secondly deciding which exact space to play on from the reduced options.)

  2. Extended Actions

    In Dominion we can have chains of decisions that cascade from each other. For example if I play a ‘Militia’, each other player decides first whether to defend themselves with a Reaction card (which may in turn enable a whole set of further decision), or else discards down to a hand of three cards (their decision as to which to discard). This circulates round the table before I continue with my turn.

    This sort of thing is perfectly trackable within ForwardModel and TurnOrder directly (as, for example, Exploding Kittens does with a Nope action that cancels the last action card played), but when one has 15 different cards (and many more to come in expansions) that have some chain of actions in this way, it makes better design sense to try and encapsulate all this logic and tracking in one place - otherwise ForwardModel (or TurnOrder, or GameState) becomes very bloated.

If an Action extends IExtendedSequence, then it can temporarily take control of who takes the next action (from TurnOrder), and what actions are available to them (from ForwardModel). Once the sequence of actions is complete, then it passes control back. See below for a detailed example for how to implement this.

The implementation has the following components:

a) Stack in GameState to track the chain of interrupts and reactions (exactly like that used in ExplodingKittens):

Stack<IExtendedSequence> actionsInProgress = new Stack<>();

b) In ForwardModel, if an action is in progress, then we delegate to that to provide the set of available actions.

protected List<AbstractAction> _computeAvailableActions(AbstractGameState state) {

    if (state.isActionInProgress()) {
    	return state.actionsInProgress.peek().followOnActions(state);
    }
    ...

c) Similarly in TurnOrder, we delegate to this to determine the current player:

public int getCurrentPlayer(AbstractGameState state) {
    if (state.isActionInProgress()) {
        return state.actionsInProgress.peek().getCurrentPlayer(state);
    }
    return super.getCurrentPlayer(state);
}

d) In ForwardModel we update the stack to keep it informed of changes to the state whenever we apply the forward model.

protected void _next(AbstractGameState currentState, AbstractAction action) {

	if (!state.actionsInProgress.isEmpty()) {
    	// we just register the action with the currently active action
    	state.actionsInProgress.peek().registerActionTaken(state, action);
	}

	action.execute(state);  // existing code

	// we may be in an extended action, so update that
	if (!state.actionsInProgress.isEmpty()) {
    	// we just register the action taken with the currently active action
    	// and then remove anything which is now complete
    	while (!state.actionsInProgress.isEmpty() && state.actionsInProgress.peek().executionComplete(state)) {
        	state.actionsInProgress.pop();
    	}
    }
    
    ...
}

e) That then leaves the interface to be implemented by the AbstractAction:

/**
 * An Action (usually) that entails a sequence of linked actions/decisions. This takes temporary control of deciding
 * which player is currently making a decision (the currentPlayer) from TurnOrder, and of what actions they have
 * available from ForwardModel.
 *
 * ForwardModel will register all actions taken and the current state just before execution of each action in next().
 *
 * IExtendedSequence is then responsible for tracking all local state necessary for its set of actions, and marking
 * itself as complete. (ForwardModel will then detect this, and remove it from the Stack of open actions.)
 */
public interface IExtendedSequence {

    /**
     * Forward Model delegates to this from computeAvailableActions() if this Extended Sequence is currently active.
     *
     * @param state The current game state
     * @return the list of possible actions for the currentPlayer
     */
    List<AbstractAction> followOnActions(DominionGameState state);

    /**
     * TurnOrder delegates to this from getCurrentPlayer() if this Extended Sequence is currently active.
     *
     * @param state The current game state
     * @return The player Id whose move it is
     */
    int getCurrentPlayer(DominionGameState state);

    /**
     * This is called by ForwardModel whenever an action is about to be taken. It enables the IExtendedSequence
     * to maintain local state in whichever way is most suitable.
     *
     * After this call, the state of IExtendedSequence should be correct ahead of the next decision to be made.
     * In some cases there is no need to implement anything in this method - if for example you can tell if all
     * actions are complete from the state directly, then that can be implemented purely in executionComplete()
     *
     *
     * @param state The current game state
     * @param action The action about to be taken (so the game state has not yet been updated with it)
     */
    void registerActionTaken(DominionGameState state, AbstractAction action);

    /**
     * Return true if this extended sequence has now completed and there is nothing left to do.
     *
     * @param state The current game state
     * @return True if all decisions are now complete
     */
    boolean executionComplete(DominionGameState state);

    /**
     * Usual copy() standards apply.
     * NO REFERENCES TO COMPONENTS TO BE KEPT, PRIMITIVE TYPES ONLY.
     *
     * @return
     */
    IExtendedSequence copy();
}

An example is shown below.

On execution, the implementing action should call AbstractGameState.setActionInProgress(this) as well as any other immediate effects (in this example there are none). This example of an Artisan card requires a player to make two linked decisions - first which card to gain into their hand, and then which card from their hand to put onto their Deck.

public class Artisan extends DominionAction implements IExtendedSequence {
    public Artisan(int playerId) {
        super(CardType.ARTISAN, playerId);
    }

    public final int MAX_COST_OF_GAINED_CARD = 5;

    public boolean gainedCard;
    public boolean putCardOnDeck;

    @Override
    boolean _execute(DominionGameState state) {
        state.setActionInProgress(this);
        return true;
    }

    @Override
    public List<AbstractAction> followOnActions(DominionGameState state) {
        if (!gainedCard) {
            return state.cardsToBuy().stream()
                    .filter(c -> c.cost <= MAX_COST_OF_GAINED_CARD)
                    .map(c -> new GainCard(c, player, DeckType.HAND))
                    .collect(toList());
        } else {
            return state.getDeck(DeckType.HAND, player).stream()
                    .map(c -> new MoveCard(c.cardType(), player, DeckType.HAND, player, DeckType.DRAW, false))
                    .distinct()
                    .collect(toList());
        }
    }

    @Override
    public int getCurrentPlayer(DominionGameState state) {
        return player;
    }

    @Override
    public void registerActionTaken(DominionGameState state, AbstractAction action) {
        if (action instanceof GainCard && ((GainCard) action).buyingPlayer == player)
            gainedCard = true;
        if (action instanceof MoveCard && ((MoveCard) action).playerFrom == player)
            putCardOnDeck = true;
    }

    @Override
    public boolean executionComplete(DominionGameState state) {
        return gainedCard && putCardOnDeck;
    }

    @Override
    public Artisan copy() {
        Artisan retValue = new Artisan(player);
        retValue.putCardOnDeck = putCardOnDeck;
        retValue.gainedCard = gainedCard;
        return retValue;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Artisan) {
            Artisan other = (Artisan) obj;
            return other.gainedCard == gainedCard && other.putCardOnDeck == putCardOnDeck && other.player == player;
        }
        return false;
    }

    @Override
    public int hashCode() {
        return Objects.hash(gainedCard, putCardOnDeck, player, CardType.ARTISAN);
    }
}