We can use the General Tree Data Structure in several ways. One of them is to create game trees. In this post, you will learn how to print some levels of the game tree for the popular game Tic-tac-toe.
Tic-Tac-Toe
The Tic-tac-toe game consists of a 3×3 board. One player places X’s on the board and the other one place O’s.
The first player that manages to place three symbols on the same row, column, or diagonal wins.
Game Tree
A game tree is a general tree that represents all the possibilities that two players have in a certain game.
We use this structure to model games that have only two players and are zero-sum games. In other words, for one player to win, the other must lose.
One of those types of games is the popular Tic-tac-toe.
See below an example of part of the game tree for the tic-tac-toe game.
From the picture above, we can see that it is a general tree structure. Each node of the tree has several children (or subtrees). Not all of them have the same number.
Let’s see a Java implementation that will allow create one and two levels of this tree and print the boards to the console.
Code example
Here we will use the General Tree implementation explained in this post.
First, we must create a class to represent a Player, a Position and a Board.
public enum Player
{
X,
O
}
public class Position
{
public int x;
public int y;
public int score;
public Position(int x, int y)
{
this.x = x;
this.y = y;
score = 0;
}
public Position(int x, int y, int score)
{
this.x = x;
this.y = y;
this.score = score;
}
public override string ToString()
{
return "(" + this.x.ToString() + "," + this.y.ToString() + ") , score: " + score;
}
}
public class Board : ICloneable
{
public object Clone()
{
Board t = new Board();
if (this.player1)
t.player1 = true;
else
t.player1 = false;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
t.matrix[i, j] = this.matrix[i, j];
}
}
return t;
}
public Position LastMove() { return lastMove; }
private Position lastMove;
private char[,] matrix;
private Boolean player1;
public Board()
{
player1 = true;
matrix = new Char[3, 3];
InitBoard();
}
public List<Position> AvailablePositions()
{
List<Position> result = new List<Position>();
Position p;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (matrix[i, j] == '_')
{
p = new Position(i, j);
result.Add(p);
}
}
}
return result;
}
public void Undo(Position position)
{
matrix[position.x, position.y] = '_';
player1 = !player1; //Exchange the player
}
private void InitBoard()
{
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
matrix[i, j] = '_';
}
}
vacio = true;
}
public void Play(int x, int y)
{
vacio = false;
lastMove = new Position(x, y);
if (player1)
{
matrix[x, y] = 'X';
}
else
{
matrix[x, y] = 'O';
}
player1 = !player1;
}
public void Play(Position p)
{
this.Play(p.x, p.y);
}
public override string ToString()
{
String result = "";
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
result = result + matrix[i, j] + " ";
}
result = result + "\n";
}
return result;
}
public string ToString(String space)
{
String result = space;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
result = result + matrix[i, j] + " ";
}
result = result + "\n" + space;
}
return result + "\n";
}
bool empty;
public bool Empty()
{
return this.empty;
}
public void PlayInRandomPosition()
{
Random r = new Random();
Position p = new Position(r.Next(0, 3), r.Next(0, 3));
Play(p);
}
}
Now, we can implement a method that will create one level of the game tree.
private static void AddLevelTo(ITree<Board> tree)
{
Board board = tree.Root();
List<Position> positions = board.AvailablePositions();
foreach (Position position in positions)
{
//Console.WriteLine("Playing in position: " + position);
board.Play(position);
//Add the new board to the tree.
//this will be the first level of the tree
tree.addSubTree(new GeneralTree<Board>((Board)board.Clone()));
//We have to undo the last position to play in the other
//available positions
board.Undo(position);
}
}
To test this implementation, we can create a utility method that prints the tree to the console, in a way that we can see the tree structure.
public static void PrintTreeToConsole(ITree<Board> tree, String space)
{
Console.WriteLine(tree.Root().ToString(space));
if (tree.numberSubTrees() > 0)
{
Console.WriteLine();
String moreSpace = space + " ";
ITree<Board> subtree;
for (int i = 0; i < tree.numberSubTrees(); i++)
{
subtree = tree.getSubTree(i);
PrintTreeToConsole(subtree, moreSpace);
}
}
}
Now, we can implement the method Main in a console app that prints a two-level game tree. Find the code below.
static void Main(string[] args)
{
GeneralTree<Board> gameTree;
Board root = new Board();
gameTree = new GeneralTree<Board>(root);
//create two levels tree
AddLevelTo(gameTree);
foreach (ITree<Board> tree in gameTree.getSubTrees())
{
AddLevelTo(tree);
}
PrintTreeToConsole(gameTree, "");
}
After executing the previous code, you will get a result like the picture below.
Summary
As you can see, the General Tree data structure is important to model situations that have a hierarchical structure.
In the case of the game tree for tic-tac-toe, the hierarchical structure can be seen as follows:
- The first node is the empty board.
- The first level of the hierarchy represents each possible play for the first player.
- The second level of the board, represents all possibilities for the second player, depending on what was the move of the first player in the previous level.
H@ppy coding!
Related posts: