Tic-tac-toe in 5 minutes

About

I think there is literally noone who never played tic-tac-toe (or you may know it by different name, e.g. "3 in a row").
Just to recap - it's a game for 2 players on a 3 by 3 field. Players do turns in sequence and put X and O into empty cells. The first player who makes 3 in a row of its symbols wins the game.
This game is well explored and it is known that it ends in a draw if both players play the optimal strategy.
In today's project we will learn how to code this game in JavaScript and as a side bonus we will learn how to implement AI logics for such games that play optimal strategy and guarantees a draw (or a win if player makes a mistake).
As always, the breakdown is available and source code is in Github repository.

Link to Wikipedia: https://en.wikipedia.org/wiki/Tic-tac-toe

Live coding

Here is a live coding session that shows how it can be done.

Duration: 4:25 (coding - 4:04)

Disclaimer: never use this code in production. It was created for fun.

Breakdown

Let's break down the solution and comment on some complex or interesting things.

0:13 - start with HTML template. Similarly to other projects the game field will be generated using JavaScript function that will create tr and td elements.
Here we also define constants empty, you and ai that will represent the state of the cell.
All cells will have cell CSS class that we will define in a bit.
As this is a boilerplate code similar to other project this part of the video has 4x speed.

0:32 - CSS styling will be very simple. We need only cell class that will give a border around td element and make it rectangular. Also text inside the cell should be centered vertically and horizontally.

0:44 - time to define a number of functions that will be required.
We can add a click handler that will activate when a player clicks on a cell to make a move. For the time being it's a placeholder. Later the function will try to put X symbol into (x, y) coordinates of the field.
move function will do 2 things - first it will check if the cell where want to make a move to is empty or not. And then if it is empty - put X or O there.
gameOver function will just output a message about game outcome and will refresh the browser to start a new game.
Last piece in this block - aiMove function. It is a placeholder for now and it will deal with AI move.

1:28 - playerMove implementation is quite simple. We just try to make a move (remember that move function checks if the cell is empty).
And then either passes the move to AI or ends the game. It all depends on outcome of wins function (that is not yet implemented by the way).
Now we can do a quick check in the browser. Right now it does not have a lot of practical value, but at least we can be sure that rendering and player move parts work as expected.

1:42 - now we can implement the logics for AI.
We will start with very simple algorithm that allows AI to do random (but valid) moves. Later we will extend this implementation with something more clever.
First of all we need validMoves function that just returns array of (x, y) coordinates of empty cells. It just iterates through the whole field and checks every cell if it is empty or not.
Then findRandomMove function will take a random element of the values returned by a call to validMoves - this will be the move AI does on the next step.
Notice that there might be a situation when there are no valid moves - this means that the player just did the last (9-th move) and noone has won. It means that the game is finished with a draw.
And finally aiMove just takes value of findRandomMove and process it:

• if there is no move - it's a draw
• if there is a move and it wins the game for AI - then AI wins and game is over
• otherwise - just make a move and pass the turn to the player

We can verify how it looks in browser and see that the AI plays in very stupid way and has no chance for a win (or at least for a draw).

2:35 - wins function is in my opinion the most complex and requirs additional explanation.
On 3 by 3 field there are 8 lines that can result in a win or a loss:

• 3 vertical lines
• 3 horizontal lines
• 2 diaginal lines

We define a lineWins function that takes 4 arguments - (x, y) and (dx, dy). Basically it checks that these 3 elements have the same value:

• (x, y)
• (x + dx, y + dy)
• (x + dx + dx, y + dy + dy)

It turns out that with help of such function we can cover all cases:

• For horizontal line i we have x = 0, y = i, dx = 1, dy = 0
• For vertical line i we have x = i, y = 0, dx = 0, dy = 1
• For top-left to bottom-right diagonal - x = 0, y = 0, dx = 1, dy = 1
• For top-right to bottom-left diagonal - x = 2, y = 0, dx = -1, dy = 1

Also we can do a quick hack and check vertical and horizontal lines in one loop.
With that we can check in the browser that the game can be finished by player's win.

3:11 - now it's time to make the AI play optimal strategy.
This approach is used for other games as well so here we will learn the basics.
Main concept is that we should be able to estimate the current position and do a judgement - is it a good or a bad position for a player.
We have few scenarios where it is easy to do:

• if in current position current player wins - it's good
• if in current position opponent wins - it's bad (for the player)
• if there are no moves to do - it's a draw

Other cases require deeper analysis. For current position we know all moves that we can do (see validMoves function). Try to move each of these moves one by one and pass the move to the opponent.
It is a recursive algorithm that eventually will go though each and every possible position. And for each recursive step we return the move that leads the player to the best possible outcome.
As tic-tac-toe is a solved game this algorithm will yield moves that that will lead AI to a win or at least to a draw.
Finally we need to relace a call of findRandomMove with a call of findBestMove.

4:04 - checking the results in a browser. We can see that this time AI plays much better - it easily makes a draw. And in case player makes a mistake AI makes use of it and wins the game.

Resources

Sources: https://github.com/5minute/tic-tac-toe

See live results:https://jsfiddle.net/8kshnex7/