One of the General Tree Data Structure example of application 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.
Table of Contents
- Tic-Tac-Toe
- Game Tree (It is also a General Tree)
- General Tree Data Structure example in Java
- Summary
Tic-Tac-Toe
The Tic-tac-toe game consists of a 3×3 board. One player place 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 (It is also a General 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 is a zero-sum game. In other words, for one player to win, the other must lose.
One of such 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.
General Tree Data Structure example in Java
Here we will use the General Tree implementation explained in this post.
First, we have to 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;
}
@Override
public String toString() {
return "(" + this.x + "," + this.y + ") , score: " + score;
}
}
public class Board {
public Player GetPlayer() {
if (player1Turn) return Player.X;
return Player.O;
}
public Position LastPlay() {
return lastPlay;
}
private Position lastPlay;
private char[][] matrix;
private Boolean player1Turn;
public Board() {
player1Turn = true;
matrix = new char[3][3];
InitBoard();
}
// Set a specific value on the board
public void set(int x, int y, char value){
matrix[x][y] = value;
}
public List<Position> AvailablePositions() {
List<Position> result = new ArrayList<>();
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 UndoPlay(Position position) {
matrix[position.x][position.y] = '_';
player1Turn = !player1Turn; //exchange the player turn
}
private void InitBoard() {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
matrix[i][j] = '_';
}
}
empty = true;
}
private void Play(int x, int y) {
empty = false;
lastPlay = new Position(x, y);
if (player1Turn) {
matrix[x][y] = 'X';
}
else {//The turn of the player O
matrix[x][y] = 'O';
}
player1Turn = !player1Turn;
}
public void Play(Position p) {
this.Play(p.x, p.y);
}
public 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";
}
boolean empty;
public boolean HumanWins() {
return player1Turn && WiningSituation(Player.O);
}
public boolean ComputerWins() {
return !player1Turn && WiningSituation(Player.X);
}
public boolean gameOver() {
return AvailablePositions().size() == 0 || WiningSituation(Player.O) || WiningSituation(Player.X);
}
private boolean WiningSituation(Player player) {
int count = 0;
char charToCheck = 'O';
if (player == Player.X)
charToCheck = 'X';
//columns
for (int x = 0; x < 3; x++) {
count = 0;
for (int y = 0; y < 3; y++)
if (matrix[x][y] == charToCheck)
count++;
if (count == 3)
return true;
}
//rows
for (int x = 0; x < 3; x++) {
count = 0;
for (int y = 0; y < 3; y++)
if (matrix[y][x] == charToCheck)
count++;
if (count == 3)
return true;
}
if ((matrix[0][0] == charToCheck && matrix[1][1] == charToCheck && matrix[2][2] == charToCheck) ||
(matrix[0][2] == charToCheck && matrix[1][1] == charToCheck && matrix[2][0] == charToCheck))
return true;
return false;
}
public Board Clone() {
Board t = new Board();
if (this.player1Turn)
t.player1Turn = true;
else
t.player1Turn = false;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
t.set(i,j,this.matrix[i][j]);
}
}
return t;
}
}
Now, we can implement a method that will create one and two levels of the game tree.
public class TicTacToeExample1 {
private GeneralTree<Board> gameTree;
public TicTacToeExample1() {
Board root = new Board();
gameTree = new GeneralTree<Board>(root);
}
public void CreateOneLevelTree() {
AddLevelTo(gameTree);
}
private void AddLevelTo(ITree<Board> tree){
Board board = tree.Root();
List<Position> positions = board.AvailablePositions();
for (Position position : positions) {
System.out.println("Playing in position: "+position.toString());
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.UndoPlay(position);
}
}
public void PrintTreeToConsole() {
Utils.PrintTreeToConsole(gameTree, "");
}
public void CreateTwoLevelsTree() {
AddLevelTo(gameTree);
for (ITree<Board> tree: gameTree.getSubTrees()){
AddLevelTo(tree);
}
}
}
To test this implementation, we can create a utility class that prints the tree to the console, in a way that we can see the tree structure.
public class Utils {
public static void PrintTreeToConsole(ITree<Board> tree, String space) {
System.out.print(tree.Root().ToString(space));
if (tree.numberSubTrees() > 0) {
System.out.println();
String moreSpace = space + " ";
ITree<Board> subtree;
for ( int i=0; i< tree.numberSubTrees(); i++) {
subtree = tree.getSubTree(i);
PrintTreeToConsole(subtree, moreSpace);
}
}
}
}
Now, we can create a console app that prints a two-level game tree. Find the code below.
public class Main {
public static void main(String[] args) {
TicTacToeExample1 tic = new TicTacToeExample1();
tic.CreateTwoLevelsTree();
tic.PrintTreeToConsole();
}
}
After executing the previous code, you will get a result like a 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!