In this lab, we'll build up the tree. Doing this involves first deciding how we will represent the tree. Then, we'll need to write a method that allows us to generate all the possible moves from a given game board. Lastly, we'll need to be able to evaluate which move we should make given a game position by searching down the tree and deciding which direction makes the most sense.
Lab 7B: Building Trees, Evaluating Boards
My Solution
My solution currently plays Tic Tac Toe very poorly. I think something is wrong with my implementation.
That said, these are the methods I had in mine:
Pasted, so you can see:
TreeNode
|
buildTree(int Bx,
int Bo, int PLAYER) |
boolean
|
checkFinalWin(int Bx,
int Bo, int player) |
boolean
|
checkWin(int Bx,
int Bo, int player) |
TreeNode
|
chooseNextPlay(TreeNode root,
int PLAYER) |
boolean
|
eitherWin(int Bx,
int Bo) |
boolean
|
isGameOver(int Bx,
int Bo) |
boolean
|
isValidPlay(int loc,
int Bx, int Bo) |
int
|
minimax(TreeNode root,
int PLAYER, int depth) |
void
|
play() |
ArrayList<BoardPair>
|
possibleMoves(int Bx,
int Bo, int PLAYER) |
void
|
printString() |
void
|
setLocation(int loc,
int player) |
java.lang.String
|
toString() |
java.lang.String
|
toString(int Bx,
int Bo)
|
There are a few things to note:
[ 1 ] I converted most methods to take BOARD_X and BOARD_O as arguments. I no longer rely on the fields of the same name. For example, the method isValidPlay(int loc) just calls
[ 2 ] I have two data structures that I use: BoardPairs and TreeNodes.
[ 3 ] Some of these methods are very simple, and are either one line long, or just a few calls to other methods. For example, eitherWin() just calls checkWin() once for each player.
What follows are the implementations of the data structures used, and then descriptions of the methods that I've written to implement Tic Tac Toe, the implementations to which you can explore on your own.
Data Structures
I've defined two structures for implementing my solution. I intentionally chose to build an entire tree of game boards and then evaluate their value. This is not strictly necessary for playing TTT, but it gives us some experience building and traversing trees.
My TreeNode class looks like this:
|
import java.util.*; public class TreeNode { private BoardPair value; private ArrayList<TreeNode> children;
public TreeNode() { value = new BoardPair(0, 0); children = new ArrayList<TreeNode>(); }
public TreeNode(int x, int o) { value = new BoardPair(x, o); children = new ArrayList<TreeNode>(); }
public BoardPair getValue() { return value; }
public ArrayList<TreeNode> getChildren() { return children; }
public void addChild(int x, int o) { children.add(new TreeNode(x, o)); }
public void addChild(TreeNode tn) { children.add(tn); } } |
Note that I created an additional structure for managing my game boards. Specifically, the pair of integers for the X and O positions. It might have been overkill to use BoardPairs for this, but I didn't want to ever get an X,O pair mixed up or lost. Creating a class seemed like the best way to keep things together.
|
public class BoardPair { private int[] p;
public BoardPair(int x, int o) { p = new int[2]; p[0] = x; p[1] = o; }
public int getX() { return p[0]; } public int getO() { return p[1]; } } |
The BoardPair is simple, as you would expect.
What remains...
I then needed to write a few methods:
First, I needed a game loop. I will provide my game loop to you upon request.
Second, I needed a method that would generate a game tree from a starting board position. To do that, I needed to be able to generate all the possible moves from a given board.
I called the first method buildTree:
TreeNode
|
buildTree(int Bx,
int Bo, int PLAYER) |
This method consumes the BOARD_X and BOARD_O positions and the current player, and returns a TreeNode that represents the complete set of all possible plays from that point forward.
My buildTree method makes use of possibleMove:
ArrayList<BoardPair>
|
possibleMoves(int Bx,
int Bo, int PLAYER) |
It takes a board position (X, O) and a current player, and it returns the list of possible moves from that position.
My game loop makes use of chooseNextPlay:
TreeNode
|
chooseNextPlay(TreeNode root,
int PLAYER)
|
This method takes a node, looks at all of its children, and decides which of children represents the best next move. It uses minimax to do this.
int
|
minimax(TreeNode root,
int PLAYER, int depth)
|
You can research minimax either in the text or online. You should be able to implement it from pseudocode; given a node, it recursively searches for the best possible play by looking down the tree until it finds a win, and percolates that result back up.
These methods make up the bulk of my TTT implementation. None of the methods are particularly long. buildTree roughly follows are recursive template, possibleMoves is a simple loop to generate possible moves into a list, chooseNextPlay runs minimax on each of a list of possible moves, and minimax walks down the tree.
Any methods I have not accounted for here are very small helpers that do what they say. For example, isGameOver checks to see if the board is full. (It doesn't actually check for a win—it really should be called isBoardFull.)
Additional Input
I think you could probably use a bit more detail, but that's what I'm going to give you for the moment.
There is no penalty for requesting a copy of my game loop.
Ask questions as you need to. Good luck.
