Unbeatable Tic Tac Toe with Monte Carlo Tree Search Part 1: Rendering

As a programmer creating a basic two player Tic Tac Toe game is not a hard thing to do but for me, creating a computer opponent that could beat you at Tic Tac Toe or any board game was always a question mark so...

1. Introduction

As a programmer creating a basic two player Tic Tac Toe game is not a hard thing to do but for me, creating a computer opponent that could beat you at Tic Tac Toe or any board game was always a question mark so recently I set out to find how this wizardry is done in modern board games.

In these series of posts I’m going to share with you step by step my process of creating a Tic Tac Toe game and add a Monte Carlo Tree Search to have ( almost ) unbeatable AI.

2. Tools & Technologies

We’re going to use JavaScript and HTML5 Canvas to create our game. Here I’m assuming you have basic knowledge of JavaScript/HTML and how to get 2D context from canvas.

3. Code Setup

The HTML part of the code is quite simple, all we need is a canvas tag that is centered in our document:

Here I’m using ReqireJS to make our code a little bit cleaner. If you don’t already know about it, it is basically a library to help you load JS files on demand and gives you a callback to know when they’re loaded. Download it from its website and put it inside “js” folder.

Next we setup our GmaeBoardRenderer class. This class is going to draw our board background and played positions. Here is structure of our class:

4. Drawing X’s and O’s

The most important method in this class is the “drawCells” function which takes the board state ( array of 9 integers ) and draws whats already played on each cell:

First we loop through each cell state and we draw “X” if our state is 1 ( Player 1 ) or “O” if our state is 2, otherwise our cell is empty and we draw nothing.

Since boardState is one dimensional array, we need a way to know how each element in state array maps to rows and columns. To find columns ( x value ) of our cells we use remainder of division ( % ) by number of columns which is 3 in our case. It makes a loop effect for our columns going from 0 to 2 for each row. To find which row our element resides on, we simply divide our element index by number of rows and floor that value to get a number in range of 0 – 2.

Next we convert our rows and columns to pixel coordinates by multiplying ( scaling ) with our cell size ( it is our canvas width/height divided by 3 ). Since canvas default origin ( 0, 0 ) is on top-left corner it gives us top-left corner of each cell. We can use those values to draw our “X” and “O”s:

drawX draws two lines to form an “X” in middle of our cell. It starts from top left [js]this.ctx.moveTo(x + offset, y + offset);[/js] and draws a line to bottom right corner and bottom-left to top-right corner. The offset variable is there so our “X” does not stick to cell corners and its 25% of our cell size. This way no matter how big or small our board gets we always have consistent drawing and padding.

To draw “O” we draw a circle on center of our cell using “arc” function and using “stroke” to make it visible. We find cell center coordinates by adding half of cell size to top left corner of the cell. I decided to make the circle size 70 percent of cell divided by 2 ( since we need the circle’s radius and not its diameter )

5. Drawing Grid Lines

We draw the grid lines by drawing 2 horizontal and 2 vertical lines like below:

Again offset is there so lines does not start from edge of our canvas.

6. Detecting Cell Clicks

We need one more missing ingredient to have a complete board rendering class which is finding which cell index is clicked/tapped on so we can use it to change our game state later.

First we have to convert our cursor coordinate which starts from top left of our document ( origin or 0,0 ) to a coordinate relative to our canvas origin:

Then we check if that coordinate falls inside one of our cells:

We already saw how to find top-left coordinate of each cell, now we need to check if our clicked coordinates is inside one of our cell bounds. If the point is inside a box horizontally, it needs to be greater or equal to left coordinate of cell AND its less than or equal to right side of cell ( hence [js] xCordinate + this.cellSize [/js] ). Same logic applies vertically as well and it needs to be true in order for our point ( x, y pair ) to fall inside one of the cells.

Once we found which cell is clicked on we convert x, y pair back to 1D coordinates by [js] y * 3 + x [/js] so we can use it later to modify our game state array.

7. Putting it Altogether

Here you can view complete class file. Notice that I added a custom canvas event so we get clicked cell index conveniently outside of this class. We can now use this class to create a simple two player Tic Tac Toe game:

8. Conclusion

We learned to render our game board and adding some user interaction using mouse events. As an exercise you can extend this class to animate X’s and O’s as the game state changes. In next post we will explore Monte Carlo Tree Search algorithm to make a smart opponent for our game.