Computational Games, part 2

Let’s see about coding up the “1, 2, … 10” game so the computer can arrive at the same conclusion we did: that player 1 is going to win the game.

Read Computational Games, Part 1 for the background material.

Each node in the tree is represented with:

  • The player number (1 or 2)
  • The number of tokens remaining in the pile
  • Pointers to the child nodes

(By the way, the content of this blog is aimed at university/college freshman and sophomores. The code is straightforward with not a lot of fancy syntax until it’s needed.)

Let’s define a Java class to represent a OneTwoTen node. We’ll also provide a convenient constructor for setting the attribute values and a toString for displaying them.

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

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

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

Here’s how to define a few nodes:

OneTwoTen n1 = new OneTwoTen(1, 0);    // The initial state
OneTwoTen n2 = new OneTwoTen(2, 10);   // One of the leaf nodes
OneTwoTen n3 = new OneTwoTen(1, 6);    // A mid-game node

(I use BlueJ for a lot of my coding. Its Code Pad feature lets me simply type in statements like the ones above. With BlueJ, I can quickly test code without laboriously defining a main method. If you’re not using BlueJ, you’ll need to put the statements into a main.)

We can inspect the nodes, again in the CodePad:

> n1.player
1 (int)
> n1.pile
0 (int)
> n2.player
2 (int)
> n2.pile
10 (int)
> n1.toString()
“(1, 0)” (String)
> n3.toString()
“(1, 6)” (String)

Next, define a method called spawn that creates a node’s children. For a node where the pile is 10, there’s nothing to do. If the pile is 9, only one child is created. In all other cases, both children are spawned.

The otherPlayer method is a helper. It simply returns the number of the other player.

public void spawn()
{
    if (pile == 10) return;   // Nothing to do for the leaves
    else if (pile == 9)
    {
        // Only one child here
        add1 = new OneTwoTen(otherPlayer(), pile + 1);
    }
    else
    {
        add1 = new OneTwoTen(otherPlayer(), pile + 1);
        add2 = new OneTwoTen(otherPlayer(), pile + 2);
    }
}

public int otherPlayer()
{
    if (player == 1) return 2;
    else return 1;
}

Try it out:

> OneTwoTen n1 = new OneTwoTen(1, 0);
> n1.spawn();
> n1.add1.toString()
“(2, 1)” (String)
> n1.add2.toString()
“(2, 2)” (String)

Looks good! To build the whole tree, we’ll spawn a node’s children, then call buildTree on each of the children, telling each one to build their own trees.

public void buildTree()
{
    spawn();
    if (add1 != null) add1.buildTree();
    if (add2 != null) add2.buildTree();
}

Did it work? Let’s see…

> OneTwoTen n1 = new OneTwoTen(1, 0);
> n1.buildTree();
> n1.add1.add1.toString()
“(1, 2)” (String)
> n1.add1.add2.toString()
“(1, 3)” (String)
> n1.add1.add1.add1.toString()
“(2, 3)” (String)
> n1.add1.add1.add2.toString()
“(2, 4)” (String)

Sure looks like it! It would be nice to see the whole tree, though. The next method below prints the tree, but it’s sideways. You’ll need to turn your head 90 degrees to the left to see it.

The first printTree method takes an integer argument that tells it how far to indent the node. It calls printTree on the take2 node (so it appears on the right side of the sideways tree), then prints itself, then calls printTree on the take1 node. This is called an in-order traversal.

The second no-argument method just calls the first one with an indent of 0.

public void printTree(int indent)
{        
    if (add2 != null) add2.printTree(indent + 1);

    for (int i = 0; i < indent; i++) System.out.print("   ");
    System.out.println(toString());

    if (add1 != null) add1.printTree(indent + 1);
}

public void printTree()
{
    printTree(0);
}

I’ll leave it to you to call printTree after building the tree and seeing the fruits of your (well, my) labor.

In the next post, I’ll show you how to assign the win-loss label to each node.

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