In this post, we do a brute force solution of Tic-Tac-Toe, the well-known 3*3 game. You’ll learn how data.tree can be used to build a tree of game history, and how the resulting data.tree structure can be used to analyse the game.

This post is based on data.tree 0.2.1, which you can get from CRAN.

We want to set up the problem in a way such that each Node is a move of a player, and each path describes the entire history of a game.

We number the fields from 1 to 9. Additionally, for easy readability, we label the Nodes in an Excel-like manner, such that field 9, say, is ‘c3’:

1 2 3 4 5 6 7 8 9 10 11 12 |
fields <- expand.grid(letters[1:3], 1:3) fields ## Var1 Var2 ## 1 a 1 ## 2 b 1 ## 3 c 1 ## 4 a 2 ## 5 b 2 ## 6 c 2 ## 7 a 3 ## 8 b 3 ## 9 c 3 |

To speed up things a bit, we consider rotation, so that, say, the first move in a3 and a1 are considered equal, because they could be achieved with a 90 degree rotation of the board. This leaves us with only a3, b3, and b2 for the first move of player 1:

1 2 3 4 5 6 7 8 9 10 |
library(data.tree) ttt<- Node$new("ttt") #consider rotation, so first move is explicit ttt$AddChild("a3") ttt$a3$f ttt$AddChild("b3") ttt$b3$f ttt$AddChild("b2") ttt$b2$f ttt$Set(player = 1, filterFun = isLeaf) |

## Game play

Now we traverse the tree recursively, and add possible moves to the leaves along the way, growing it to eventually hold all possible games. To do this, we define a method which, based on a Node’s path, adds possible moves as children.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
AddPossibleMoves <- function(node) { t <- Traverse(node, traversal = "ancestor", filterFun = isNotRoot) available <- rownames(fields)[!rownames(fields) %in% Get(t, "f")] for (f in available) { child <- node$AddChild(paste0(fields[f, 1], fields[f, 2])) child$f <- as.numeric(f) child$player <- ifelse(node$player == 1, 2, 1) hasWon <- HasWon(child) if (!hasWon && child$level <= 10) AddPossibleMoves(child) if (hasWon) { child$result <- child$player print(paste("Player ", child$player, "wins!")) } else if(child$level == 10) { child$result <- 0 print("Tie!") } } return (node) } |

Note that we store additional info along the way. For example, in the line child$player <- ifelse(node$player == 1, 2, 1) , the player is deferred from the parent Node , and set as an attribute in the Node .

## Exit Criteria

Our algorithm stops whenever either player has won, or when all 9 fields are taken. Whether a player has won is determined by this function:

1 2 3 4 5 6 7 8 9 10 11 12 |
HasWon <- function(node) { t <- Traverse(node, traversal = "ancestor", filterFun = function(x) !x$isRoot && x$player == node$player) mine <- Get(t, "f") mineV <- rep(0, 9) mineV[mine] <- 1 mineM <- matrix(mineV, 3, 3, byrow = TRUE) result <- any(rowSums(mineM) == 3) || any(colSums(mineM) == 3) || sum(diag(mineM)) == 3 || sum(diag(t(mineM))) == 3 return (result) } |

## Tree creation

The following code plays all possible games. Depending on your computer, this might take a few minutes:

1 2 3 |
system.time(for (child in ttt$children) AddPossibleMoves(child)) ## user system elapsed ## 345.645 3.245 346.445 |

## Analysis

What is the total number of games?

1 2 |
ttt$leafCount ## [1] 89796 |

How many nodes (moves) does our tree have?

1 2 |
ttt$totalCount ## [1] 203716 |

What is the average length of a game?

1 2 |
mean(ttt$Get(function(x) x$level - 1, filterFun = isLeaf)) ## [1] 8.400775 |

What is the average branching factor?

1 2 |
ttt$averageBranchingFactor ## [1] 1.788229 |

How many games were won by each player?

1 2 3 4 5 6 7 |
winnerOne <- Traverse(ttt, filterFun = function(x) x$isLeaf && x$result == 1) winnerTwo <- Traverse(ttt, filterFun = function(x) x$isLeaf && x$result == 2) ties <- Traverse(ttt, filterFun = function(x) x$isLeaf && x$result == 0) c(winnerOne = length(winnerOne), winnerTwo = length(winnerTwo), ties = length(ties)) ## winnerOne winnerTwo ties ## 39588 21408 28800 |

We can, for example, look at any Node , using the PrintBoard function. This function prints the game history:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
PrintBoard <- function(node) { mineV <- rep(0, 9) t <- Traverse(node, traversal = "ancestor", filterFun = function(x) !x$isRoot && x$player == 1) field <- Get(t, "f") value <- Get(t, function(x) paste0("X", x$level - 1)) mineV[field] <- value t <- Traverse(node, traversal = "ancestor", filterFun = function(x) !x$isRoot && x$player == 2) field <- Get(t, "f") value <- Get(t, function(x) paste0("O", x$level - 1)) mineV[field] <- value mineM <- matrix(mineV, 3, 3, byrow = TRUE) rownames(mineM) <- letters[1:3] colnames(mineM) <- as.character(1:3) mineM } |

The first number denotes the move (1 to 9). The second number is the player:

1 2 3 4 5 |
PrintBoard(ties[[1]]) ## 1 2 3 ## a "O2" "X3" "O4" ## b "X5" "O6" "X7" ## c "X1" "O8" "X9" |

We could now move on to define a minimax optimisation criteria, or a heuristic search.

Exercise: Do the same for Chess!