Computational Games, part 3

If you’ve been following along, you should have a working Java program that builds the entire game tree for the “1, 2, … 10” two-player game. We are now going to add some code to compute each node’s win/loss status.

(This is the third part of a series on computational games. Read part 1 and part 2 before tackling the code here.)

Start by refactoring the class to add a winLoss attribute. Its values will be W (win), L (loss), or ? (don’t know yet). Also modify the constructor and toString methods accordingly. The changes are highlighted in green.

public class OneTwoTen
{
    int player;
    int pile;
    OneTwoTen add1;
    OneTwoTen add2;
    char winLoss;

    public OneTwoTen(int player, int pile)
    {
        this.player = player;
        this.pile = pile;
        this.add1 = null;
        this.add2 = null;
        this.winLoss = '?';
    }

    public String toString()
    {
        return "(" + player + ", " + pile + ", " + winLoss + ")";
    }

All the other methods remain as they are.  Don’t you love nicely modularized code that “just works” when you make changes?

We can’t know whether a particular node is a win or a loss until we know what its children are. So we’ll do this from the bottom up as described in part 1 of this series.

The leaves are handled specially: they are automatically losses. (By the way, this is only true for games where the goal is to be first to finish. In other games, such as “Even or Odd,” the goal is to have an even number of tokens regardless of who took the last one. Therefore, the leaves are not strictly losses.)

For all other nodes, we call doWinLoss on the children, then figure out if there are any losses among them. If there are, we are a win. Otherwise, a loss.

public void doWinLoss()
{
    if (add1 == null && add2 == null) winLoss = 'L';
    else
    {
        if (add1 != null) add1.doWinLoss();
        if (add2 != null) add2.doWinLoss();

        if ( ((add1 != null) && (add1.winLoss == 'L'))  ||
             ((add2 != null) && (add2.winLoss == 'L')) )
             winLoss = 'W';
        else
             winLoss = 'L';
    }
}

That’s all there is to it! Run it like this:

OneTwoTen root = new OneTwoTen(1,0);
root.buildTree();
root.doWinLoss();
root.printTree();

You should see that the root (1,0) node is labeled with a W to indicate it is a winning position — the first player is guaranteed a way to win. All other nodes will be labeled according to the rules discussed in part 1.

Want to try this on your own? Modify the program to implement the Even or Odd game. Here are the rules:

  • Start with 15 tokens in the pile. Each player maintains their own piles, initially with zero tokens in them.
  • At each turn, a player can take one, two, or three tokens from the central pile and adds them to their pile.
  • The game is over when the central pile is empty.
  • The winner is the player with an even number in their pile, regardless of who took the last tokens or who has more.

Some key points to consider when writing the program:

  • Each node will have three children because you can take 1, 2, or 3.
  • The win/loss status of the leaves depend on who has an even number and are therefore not automatically losses.
  • The in-order traversal of the tree won’t be pretty. You might be better off with a pre-order traversal: display the node first, then call printTree on each of the children.

When you’re done, you’ll be able to answer the central questions: will the first player win or lose the game? What moves should each player make?

In later posts, we’ll tackle some harder problems:

  • “Loopy” games, in which a move may take you back to a state you’ve already seen. Checkers is a well-known example of a loopy game — once a piece is kinged, it can move back and forth on the board.
  • You may have noticed a lot of duplication among the nodes. A total of 232 states are in the tree, but there are only twenty-one distinct states. How can we avoid computing and storing the duplicates? This will help us deal with games that have a lot of states.

Along the way, you’ll learn some more advanced data structures, such as HashMaps, and Java techniques for using them effectively.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s