Noughts & Crosses (or “Tic Tac Toe” for our American friends) offers up a nice coding challenge, being not too graphically complex but still requiring the thought and logic needed behind a nice programming project. It IS of course a game where if both parties play optimally the outcome is always a draw, but how do we code “optimally”? And how do we take advantage of players who don’t?
Whilst learning Python I came across the following resource, which offers up a very nice Noughts & Crosses coding tutorial. I highly recommend the tutorials for learning Python:
http://inventwithpython.com/chapter10.html
One thing bugged me though. It is very easy to beat the AI suggested. I’ll be honest and say that I was only “99.9% sure” that regardless of going first or second, it is possible to draw or win every time. A quick google confirmed this, so let’s have a look at a way of making an unbeatable AI.
Beatable AI
The algorithm in the tutorial above may have been chosen for simplicity. It offers an AI that would certainly outplay a “random” player.
- Check for a square that CPU can win on
- Check for square that player can win on
- Move on a free corner
- Move on free center
- Move on a free side
Coding it up
Let’s code both the general game code, and the computer decision code.
Game code
Playing = True while Playing: InGame = True board = [' '] * 9 print('Would you like to go first or second? (1/2)') if input() == '1': playerMarker = '0' else: playerMarker = 'X' displayBoard(board) while InGame: if playerMarker == '0': print('Player go: (0-8)') move = int(input()) if board[move] != ' ': print('Invalid move!') continue else: move = getComputerMove(board) board[move] = playerMarker if checkWin(board, playerMarker): InGame = False displayBoard(board) if playerMarker == '0': print('Noughts won!') else: print('Crosses won!') continue if checkDraw(board): InGame = False displayBoard(board) print('It was a draw!') continue displayBoard(board) if playerMarker == '0': playerMarker = 'X' else: playerMarker = '0' print('Type y to keep playing') inp = input() if inp != 'y' and inp != 'Y': Playing = False
I leave some of the unnecessary extra stuff as an exercise: checking for valid input, counter for wins, losses, draws etc. Crosses (“X”) are the computer, noughts (“O”) are the player.
The general gist is a big outer loop, which manages each game. Within that loop is another loop that manages each turn and checks if anyone has won or if it’s a draw.
You’ll notice there are four user defined functions in the above. Note: All functions (code starting def) need to be put ABOVE the looping code.
displayBoard(board) – prints out a representation of the board to the console
def displayBoard(b): print(' | |') print(' ' + b[0] + ' | ' + b[1] + ' | ' + b[2]) print(' | |') print('-----------------') print(' | |') print(' ' + b[3] + ' | ' + b[4] + ' | ' + b[5]) print(' | |') print('-----------------') print(' | |') print(' ' + b[6] + ' | ' + b[7] + ' | ' + b[8]) print(' | |')
Take note that the board is therefore numbered like below:
checkWin(board, currentPlayer) – checks for a three in a row
def checkWin(b, m): return ((b[0] == m and b[1] == m and b[2] == m) or # H top (b[3] == m and b[4] == m and b[5] == m) or # H mid (b[6] == m and b[7] == m and b[8] == m) or # H bot (b[0] == m and b[3] == m and b[6] == m) or # V left (b[1] == m and b[4] == m and b[7] == m) or # V centre (b[2] == m and b[5] == m and b[8] == m) or # V right (b[0] == m and b[4] == m and b[8] == m) or # LR diag (b[2] == m and b[4] == m and b[6] == m)) # RL diag
checkDraw(board) – checks if board is full
def checkDraw(b): return ' ' not in b
getComputerMove(board) – returns computer move
Now, we’ve set the above game up in such a way that we can handle all the computer decisions in the function above, just by inputting the current board.
AI Code
Our game calls the “getComputerMove” function, passing only the board state, so the function is independent and will see the board and spit out the number of where it wants to go next.
Task: Make a function that can “test” if picking a particular square will mean a win. Because we don’t want to change the actual board when we test moves, we also need a function to make a temporary board.
def getBoardCopy(b): # Make a duplicate of the board. When testing moves we don't want to # change the actual board dupeBoard = [] for j in b: dupeBoard.append(j) return dupeBoard def testWinMove(b, mark, i): # b = the board # mark = 0 or X # i = the square to check if makes a win bCopy = getBoardCopy(b) bCopy[i] = mark return checkWin(bCopy, mark)
We call this first for each square to check if the computer can win, then for each square to check if the player can win (so the computer needs to block). Now we have all we need:
def getComputerMove(b): # Check computer win moves for i in range(0, 9): if b[i] == ' ' and testWinMove(b, 'X', i): return i # Check player win moves for i in range(0, 9): if b[i] == ' ' and testWinMove(b, '0', i): return i # Play a corner for i in [0, 2, 6, 8]: if b[i] == ' ': return i # Play center if b[4] == ' ': return 4 #Play a side for i in [1, 3, 5, 7]: if b[i] == ' ': return i
Problems
So we’ve got a reasonable AI. How can this be beat? In short, the computer doesn’t go center when it should. For example, with computer going first as ‘X’ and player second as ‘O’:
which can be done exactly the same way if the player goes first. Another way that works if the player(‘O’) goes first:
These wins are of course rotatable, offering up more combinations of moves that result in wins.
To test this (and other algorithms) I made a simulation script that ran 10 000 brute force games; the algorithm against a “dumb” player selecting any free square at random. The results for this algorithm:
Player first: 8088 cpu, 1410 draws, 501 player
CPU first: 9689 cpu, 254 draws, 57 player
This needs improving. The player gets a good amount of wins going first and even gets some going second!
Making it Unbeatable
Let’s try and make an algorithm that is unbeatable.
Forks
What the above is missing is the whole concept of “forks”. This is when a player makes a move that gives them two opportunities at a three in a row. It’s effectively a “checkmate in 1” situation that means the other player can’t block both three in a row possibilities, and therefore loses. In the below situation, either of the moves indicated by green crosses would create a fork for crosses.
The computer should make a move that gives itself a fork opportunity. If not, it should block moves that give the player a fork opportunity.
Coding It Up
Function to test if a move i would give two ways of winning j.
def testForkMove(b, mark, i): # Determines if a move opens up a fork bCopy = getBoardCopy(b) bCopy[i] = mark winningMoves = 0 for j in range(0, 9): if testWinMove(bCopy, mark, j) and bCopy[j] == ' ': winningMoves += 1 return winningMoves >= 2
Let’s rewrite the AI function to check for forks
def getComputerMove(b): # Check computer win moves for i in range(0, 9): if b[i] == ' ' and testWinMove(b, 'X', i): return i # Check player win moves for i in range(0, 9): if b[i] == ' ' and testWinMove(b, '0', i): return i # Check computer fork opportunities for i in range(0, 9): if b[i] == ' ' and testForkMove(b, 'X', i): return i # Check player fork opportunities for i in range(0, 9): if b[i] == ' ' and testForkMove(b, '0', i): return i # Play a corner for i in [0, 2, 6, 8]: if b[i] == ' ': return i # Play center if b[4] == ' ': return 4 #Play a side for i in [1, 3, 5, 7]: if b[i] == ' ': return i
Player first: 7764 cpu, 2036 draws, 200 player
CPU first: 9769 cpu, 231 draws, 0 player
That’s better! At least the CPU wins/draws every time it goes first. But the player can still force a win if they go first.
Tweaks
There are still some specific games that we are allowing the player to win. Firstly, the computer should preference center above corners to prevent the following scenario, where the computer is forced into blocking (board 4), allowing the player to fork (board 5).
There is also now a very special case that would still slip through the cracks if we just did the above. It is where the player has TWO squares that gives them a fork opportunity. The current algorithm finds the first one of these (board 4) and spits it out, giving the player the luxury of using the other fork (board 5)
To get round this, the computer needs to force the player to block an immediate three in a row, by choosing any side instead of the corner on board 4.
And so we have the final algorithm:
- Check for CPU win move
- Check for player win move
- Check for CPU fork opportunity
- Check for player fork opportunity, but choose to force a block if there are two potential forks
- Check center
- Check corners
- Check sides
def getComputerMove(b): # Check computer win moves for i in range(0, 9): if b[i] == ' ' and testWinMove(b, 'X', i): return i # Check player win moves for i in range(0, 9): if b[i] == ' ' and testWinMove(b, '0', i): return i # Check computer fork opportunities for i in range(0, 9): if b[i] == ' ' and testForkMove(b, 'X', i): return i # Check player fork opportunities, incl. two forks playerForks = 0 for i in range(0, 9): if b[i] == ' ' and testForkMove(b, '0', i): playerForks += 1 tempMove = i if playerForks == 1: return tempMove elif playerForks == 2: for j in [1, 3, 5, 7]: if b[j] == ' ': return j # Play center if b[4] == ' ': return 4 # Play a corner for i in [0, 2, 6, 8]: if b[i] == ' ': return i #Play a side for i in [1, 3, 5, 7]: if b[i] == ' ': return i
Let’s run the simulation one last time:
Player first: 8846 cpu, 1154 draws, 0 player
CPU first: 9731 cpu, 269 draws, 0 player
And we’ve done it!
Optional Extra: Making the Unbeatable Algorithm Better
Awesome! We now have an unbeatable algorithm. But could we do better?
“Better!?” you say. “It’s unbeatable, the job is done, let me go outside and play now, I’ve deserved it!”
Well, yes and no.
We’ve made an algorithm that can’t be beat. But that’s not quite the same as the most optimal algorithm. There are some minor improvements that would up the number of wins for the CPU against a random player. I leave this as an exercise.
The other tweak is that if move position doesn’t matter (e.g “any corner”, “any side”, “either of these two fork opportunities”) instead of checking them in order, you might want to pick one at random. This will give the player the illusion that the computer is playing differently each time.
Finally, refer to this xkcd picture of the exact optimal plays for any opponent scenario. At the end of the day, the absolute “best” algorithm would implement this as if/ else statements; both unbeatable AND giving the CPU the most opportunities to win.
and if we want to validate the move for example if a player presses 10 11 or 12 it should print Invalid input
LikeLike
Congratulations, I like the way that you explain your thought process and approach Tic-Tac-Toe in an innovating way.
LikeLike