10
TIC-TAC-TOE

This chapter features a Tic-Tac-Toe game. Tic-Tac-Toe is normally played with two people. One player is X and the other player is O. Players take turns placing their X or O. If a player gets three of their marks on the board in a row, column, or diagonal, they win. When the board fills up with neither player winning, the game ends in a draw.

This chapter doesn’t introduce many new programming concepts. The user will play against a simple artificial intelligence, which we will write using our existing programming knowledge. An artificial intelligence (AI) is a computer program that can intelligently respond to the player’s moves. The AI that plays Tic-Tac-Toe isn’t complicated; it’s really just a few lines of code.

Let’s get started by looking at a sample run of the program. The player makes their move by entering the number of the space they want to take. To help us remember which index in the list is for which space, we’ll number the board like a keyboard’s number pad, as shown in Figure 10-1.

Figure 10-1: The board is numbered like the keyboard’s number pad.

Sample Run of Tic-Tac-Toe

Here’s what the user sees when they run the Tic-Tac-Toe program. The text the player enters is in bold.

Source Code for Tic-Tac-Toe

In a new file, enter the following source code and save it as tictactoe.py. Then run the game by pressing F5. If you get errors, compare the code you typed to the book’s code with the online diff tool at https://www.nostarch.com/inventwithpython#diff.

tictactoe.py

  1. # Tic-Tac-Toe
  2.
  3. import random
  4.
  5. def drawBoard(board):
  6.     # This function prints out the board that it was passed.
  7.
  8.     # "board" is a list of 10 strings representing the board (ignore
           index 0).
  9.     print(board[7] + '|' + board[8] + '|' + board[9])
 10.     print('-+-+-')
 11.     print(board[4] + '|' + board[5] + '|' + board[6])
 12.     print('-+-+-')
 13.     print(board[1] + '|' + board[2] + '|' + board[3])
 14.
 15. def inputPlayerLetter():
 16.     # Lets the player type which letter they want to be.
 17.     # Returns a list with the player's letter as the first item and the
           computer's letter as the second.
 18.     letter = ''
 19.     while not (letter == 'X' or letter == 'O'):
 20.         print('Do you want to be X or O?')
 21.         letter = input().upper()
 22.
23.     # The first element in the list is the player's letter; the second is
           the computer's letter.
 24.     if letter == 'X':
 25.         return ['X', 'O']
 26.     else:
 27.         return ['O', 'X']
 28.
 29. def whoGoesFirst():
 30.     # Randomly choose which player goes first.
 31.     if random.randint(0, 1) == 0:
 32.         return 'computer'
 33.     else:
 34.         return 'player'
 35.
 36. def makeMove(board, letter, move):
 37.     board[move] = letter
 38.
 39. def isWinner(bo, le):
 40.     # Given a board and a player's letter, this function returns True if
           that player has won.
 41.     # We use "bo" instead of "board" and "le" instead of "letter" so we
           don't have to type as much.
 42.     return ((bo[7] == le and bo[8] == le and bo[9] == le) or # Across the
           top
 43.     (bo[4] == le and bo[5] == le and bo[6] == le) or # Across the middle
 44.     (bo[1] == le and bo[2] == le and bo[3] == le) or # Across the bottom
 45.     (bo[7] == le and bo[4] == le and bo[1] == le) or # Down the left side
 46.     (bo[8] == le and bo[5] == le and bo[2] == le) or # Down the middle
 47.     (bo[9] == le and bo[6] == le and bo[3] == le) or # Down the right
           side
 48.     (bo[7] == le and bo[5] == le and bo[3] == le) or # Diagonal
 49.     (bo[9] == le and bo[5] == le and bo[1] == le)) # Diagonal
 50.
 51. def getBoardCopy(board):
 52.     # Make a copy of the board list and return it.
 53.     boardCopy = []
 54.     for i in board:
 55.         boardCopy.append(i)
 56.     return boardCopy
 57.
 58. def isSpaceFree(board, move):
 59.     # Return True if the passed move is free on the passed board.
 60.     return board[move] == ' '
 61.
 62. def getPlayerMove(board):
 63.     # Let the player enter their move.
 64.     move = ' '
 65.     while move not in '1 2 3 4 5 6 7 8 9'.split() or not
           isSpaceFree(board, int(move)):
 66.         print('What is your next move? (1-9)')
 67.         move = input()
 68.     return int(move)
 69.
 70. def chooseRandomMoveFromList(board, movesList):
 71.     # Returns a valid move from the passed list on the passed board.
72.     # Returns None if there is no valid move.
 73.     possibleMoves = []
 74.     for i in movesList:
 75.         if isSpaceFree(board, i):
 76.             possibleMoves.append(i)
 77.
 78.     if len(possibleMoves) != 0:
 79.         return random.choice(possibleMoves)
 80.     else:
 81.         return None
 82.
 83. def getComputerMove(board, computerLetter):
 84.     # Given a board and the computer's letter, determine where to move
           and return that move.
 85.     if computerLetter == 'X':
 86.         playerLetter = 'O'
 87.     else:
 88.         playerLetter = 'X'
 89.
 90.     # Here is the algorithm for our Tic-Tac-Toe AI:
 91.     # First, check if we can win in the next move.
 92.     for i in range(1, 10):
 93.         boardCopy = getBoardCopy(board)
 94.         if isSpaceFree(boardCopy, i):
 95.             makeMove(boardCopy, computerLetter, i)
 96.             if isWinner(boardCopy, computerLetter):
 97.                 return i
 98.
 99.     # Check if the player could win on their next move and block them.
100.     for i in range(1, 10):
101.         boardCopy = getBoardCopy(board)
102.         if isSpaceFree(boardCopy, i):
103.             makeMove(boardCopy, playerLetter, i)
104.             if isWinner(boardCopy, playerLetter):
105.                 return i
106.
107.     # Try to take one of the corners, if they are free.
108.     move = chooseRandomMoveFromList(board, [1, 3, 7, 9])
109.     if move != None:
110.         return move
111.
112.     # Try to take the center, if it is free.
113.     if isSpaceFree(board, 5):
114.         return 5
115.
116.     # Move on one of the sides.
117.     return chooseRandomMoveFromList(board, [2, 4, 6, 8])
118.
119. def isBoardFull(board):
120.     # Return True if every space on the board has been taken. Otherwise,
           return False.
121.     for i in range(1, 10):
122.         if isSpaceFree(board, i):
123.             return False
124.     return True
125.
126.
127. print('Welcome to Tic-Tac-Toe!')
128.
129. while True:
130.     # Reset the board.
131.     theBoard = [' '] * 10
132.     playerLetter, computerLetter = inputPlayerLetter()
133.     turn = whoGoesFirst()
134.     print('The ' + turn + ' will go first.')
135.     gameIsPlaying = True
136.
137.     while gameIsPlaying:
138.         if turn == 'player':
139.             # Player's turn
140.             drawBoard(theBoard)
141.             move = getPlayerMove(theBoard)
142.             makeMove(theBoard, playerLetter, move)
143.
144.             if isWinner(theBoard, playerLetter):
145.                 drawBoard(theBoard)
146.                 print('Hooray! You have won the game!')
147.                 gameIsPlaying = False
148.             else:
149.                 if isBoardFull(theBoard):
150.                     drawBoard(theBoard)
151.                     print('The game is a tie!')
152.                     break
153.                 else:
154.                     turn = 'computer'
155.
156.         else:
157.             # Computer's turn
158.             move = getComputerMove(theBoard, computerLetter)
159.             makeMove(theBoard, computerLetter, move)
160.
161.             if isWinner(theBoard, computerLetter):
162.                 drawBoard(theBoard)
163.                 print('The computer has beaten you! You lose.')
164.                 gameIsPlaying = False
165.             else:
166.                 if isBoardFull(theBoard):
167.                     drawBoard(theBoard)
168.                     print('The game is a tie!')
169.                     break
170.                 else:
171.                     turn = 'player'
172.
173.     print('Do you want to play again? (yes or no)')
174.     if not input().lower().startswith('y'):
175.         break

Designing the Program

Figure 10-2 shows a flowchart of the Tic-Tac-Toe program. The program starts by asking the player to choose their letter, X or O. Who takes the first turn is randomly chosen. Then the player and computer take turns making moves.

Figure 10-2: Flowchart for Tic-Tac-Toe

The boxes on the left side of the flowchart show what happens during the player’s turn, and the ones on the right side show what happens during the computer’s turn. After the player or computer makes a move, the program checks whether they won or caused a tie, and then the game switches turns. After the game is over, the program asks the player if they want to play again.

Representing the Board as Data

First, you must figure out how to represent the board as data in a variable. On paper, the Tic-Tac-Toe board is drawn as a pair of horizontal lines and a pair of vertical lines, with an X, O, or empty space in each of the nine spaces.

In the program, the Tic-Tac-Toe board is represented as a list of strings like the ASCII art of Hangman. Each string represents one of the nine spaces on the board. The strings are either 'X' for the X player, 'O' for the O player, or a single space ' ' for a blank space.

Remember that we’re laying out our board like a number pad on a keyboard. So if a list with 10 strings was stored in a variable named board, then board[7] would be the top-left space on the board, board[8] would be the top-middle space, board[9] would be the top-right space, and so on. The program ignores the string at index 0 in the list. The player will enter a number from 1 to 9 to tell the game which space they want to move on.

Strategizing with the Game AI

The AI needs to be able to look at the board and decide which types of spaces it will move on. To be clear, we will label three types of spaces on the Tic-Tac-Toe board: corners, sides, and the center. The chart in Figure 10-3 shows what each space is.

The AI’s strategy for playing Tic-Tac-Toe will follow a simple algorithm—a finite series of instructions to compute a result. A single program can make use of several different algorithms. An algorithm can be represented with a flowchart. The Tic-Tac-Toe AI’s algorithm will compute the best move to make, as shown in Figure 10-4.

Figure 10-3: Locations of the side, corner, and center spaces

Figure 10-4: The boxes represent the five steps of the “Get computer’s move” algorithm. The arrows pointing to the left go to the “Check if computer won” box.

The AI’s algorithm has the following steps:

1. See if there’s a move the computer can make that will win the game. If there is, make that move. Otherwise, go to step 2.

2. See if there’s a move the player can make that will cause the computer to lose the game. If there is, move there to block the player. Otherwise, go to step 3.

3. Check if any of the corner spaces (spaces 1, 3, 7, or 9) are free. If so, move there. If no corner space is free, go to step 4.

4. Check if the center is free. If so, move there. If it isn’t, go to step 5.

5. Move on any of the side spaces (spaces 2, 4, 6, or 8). There are no more steps because the side spaces are all that’s left if the execution reaches step 5.

This all takes place in the Get computer’s move box on the flowchart in Figure 10-2. You could add this information to the flowchart with the boxes in Figure 10-4.

This algorithm is implemented in getComputerMove() and the other functions that getComputerMove() calls.

Importing the random Module

The first couple of lines are made up of a comment and a line importing the random module so that you can call the randint() function later on:

1. # Tic-Tac-Toe
2.
3. import random

You’ve seen both these concepts before, so let’s move on to the next part of the program.

Printing the Board on the Screen

In the next part of the code, we define a function to draw the board:

 5. def drawBoard(board):
 6.     # This function prints out the board that it was passed.
 7.
 8.     # "board" is a list of 10 strings representing the board (ignore
          index 0).
 9.     print(board[7] + '|' + board[8] + '|' + board[9])
10.     print('-+-+-')
11.     print(board[4] + '|' + board[5] + '|' + board[6])
12.     print('-+-+-')
13.     print(board[1] + '|' + board[2] + '|' + board[3])

The drawBoard() function prints the game board represented by the board parameter. Remember that the board is represented as a list of 10 strings, where the string at index 1 is the mark on space 1 on the Tic-Tac-Toe board, and so on. The string at index 0 is ignored. Many of the game’s functions work by passing a list of 10 strings as the board.

Be sure to get the spacing right in the strings; otherwise, the board will look funny when printed on the screen. Here are some example calls (with an argument for board) to drawBoard() and what the function would print.

>>> drawBoard([' ', ' ', ' ', ' ', 'X', 'O', ' ', 'X', ' ', 'O'])
X| |
-+-+-
X|O|
-+-+-
 | |
>>> drawBoard([' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '])
 | |
-+-+-
 | |
-+-+-
 | |

The program takes each string and places it on the board in number order according to the keyboard number pad from Figure 10-1, so the first three strings are the bottom row of the board, the next three strings are the middle, and the last three strings are the top.

Letting the Player Choose X or O

Next, we’ll define a function to assign X or O to the player:

15. def inputPlayerLetter():
16.     # Lets the player enter which letter they want to be.
17.     # Returns a list with the player's letter as the first item and the
          computer's letter as the second.
18.     letter = ''
19.     while not (letter == 'X' or letter == 'O'):
20.         print('Do you want to be X or O?')
21.         letter = input().upper()

The inputPlayerLetter() function asks whether the player wants to be X or O. The while loop’s condition contains parentheses, which means the expression inside the parentheses is evaluated first. If the letter variable was set to 'X', the expression would evaluate like this:

If letter has the value 'X' or 'O', then the loop’s condition is False and lets the program execution continue past the while block. If the condition is True, the program will keep asking the player to choose a letter until the player enters an X or O. Line 21 automatically changes the string returned by the call to input() to uppercase letters with the upper() string method.

The next function returns a list with two items:

23.     # The first element in the list is the player's letter; the second is
          the computer's letter.
24.     if letter == 'X':
25.         return ['X', 'O']
26.     else:
27.         return ['O', 'X']

The first item (the string at index 0) is the player’s letter, and the second item (the string at index 1) is the computer’s letter. The if and else statements choose the appropriate list to return.

Deciding Who Goes First

Next we create a function that uses randint() to choose whether the player or computer plays first:

29. def whoGoesFirst():
30.     # Randomly choose which player goes first.
31.     if random.randint(0, 1) == 0:
32.         return 'computer'
33.     else:
34.         return 'player'

The whoGoesFirst() function does a virtual coin flip to determine whether the computer or the player goes first. The coin flip is done with a call to random.randint(0, 1). There is a 50 percent chance the function returns 0 and a 50 percent chance the function returns 1. If this function call returns a 0, the whoGoesFirst() function returns the string 'computer'. Otherwise, the function returns the string 'player'. The code that calls this function will use the return value to determine who will make the first move of the game.

Placing a Mark on the Board

The makeMove() function is simple:

36. def makeMove(board, letter, move):
37.     board[move] = letter

The parameters are board, letter, and move. The variable board is the list with 10 strings that represents the state of the board. The variable letter is the player’s letter (either 'X' or 'O'). The variable move is the place on the board where that player wants to go (which is an integer from 1 to 9).

But wait—in line 37, this code seems to change one of the items in the board list to the value in letter. Because this code is in a function, though, the board parameter will be forgotten when the function returns. So shouldn’t the change to board be forgotten as well?

Actually, this isn’t the case, because lists are special when you pass them as arguments to functions. You are actually passing a reference to the list, not the list itself. Let’s learn about the difference between lists and references to lists.

List References

Enter the following into the interactive shell:

>>> spam = 42
>>> cheese = spam
>>> spam = 100
>>> spam
100
>>> cheese
42

These results make sense from what you know so far. You assign 42 to the spam variable, then assign the value in spam to the variable cheese. When you later overwrite spam to 100, this doesn’t affect the value in cheese. This is because spam and cheese are different variables that store different values.

But lists don’t work this way. When you assign a list to a variable, you are actually assigning a list reference to the variable. A reference is a value that points to the location where some bit of data is stored. Let’s look at some code that will make this easier to understand. Enter this into the interactive shell:

➊ >>> spam = [0, 1, 2, 3, 4, 5]
➋ >>> cheese = spam
➌ >>> cheese[1] = 'Hello!'
   >>> spam
   [0, 'Hello!', 2, 3, 4, 5]
   >>> cheese
   [0, 'Hello!', 2, 3, 4, 5]

The code only changed the cheese list, but it seems that both the cheese and spam lists have changed. This is because the spam variable doesn’t contain the list value itself but rather a reference to the list, as shown in Figure 10-5. The list itself is not contained in any variable but rather exists outside of them.

Figure 10-5: The spam list created at ➊. Variables don’t store lists but rather references to lists.

Notice that cheese = spam copies the list reference in spam to cheese ➋, instead of copying the list value itself. Now both spam and cheese store a reference that refers to the same list value. But there is only one list because the list itself wasn’t copied. Figure 10-6 shows this copying.

Figure 10-6: The spam and cheese variables store two references to the same list.

So the cheese[1] = 'Hello!' line at ➌ changes the same list that spam refers to. This is why spam returns the same list value that cheese does. They both have references that refer to the same list, as shown in Figure 10-7.

Figure 10-7: Changing the list changes all variables with references to that list.

If you want spam and cheese to store two different lists, you have to create two lists instead of copying a reference:

>>> spam = [0, 1, 2, 3, 4, 5]
>>> cheese = [0, 1, 2, 3, 4, 5]

In the preceding example, spam and cheese store two different lists (even though these lists are identical in content). Now if you modify one of the lists, it won’t affect the other because spam and cheese have references to two different lists:

>>> spam = [0, 1, 2, 3, 4, 5]
>>> cheese = [0, 1, 2, 3, 4, 5]
>>> cheese[1] = 'Hello!'
>>> spam
[0, 1, 2, 3, 4, 5]
>>> cheese
[0, 'Hello!', 2, 3, 4, 5]

Figure 10-8 shows how the variables and list values are set up in this example.

Dictionaries work the same way. Variables don’t store dictionaries; they store references to dictionaries.

Figure 10-8: The spam and cheese variables now each store references to two different lists.

Using List References in makeMove()

Let’s go back to the makeMove() function:

36. def makeMove(board, letter, move):
37.     board[move] = letter

When a list value is passed for the board parameter, the function’s local variable is really a copy of the reference to the list, not a copy of the list itself. So any changes to board in this function will also be made to the original list. Even though board is a local variable, the makeMove() function modifies the original list.

The letter and move parameters are copies of the string and integer values that you pass. Since they are copies of values, if you modify letter or move in this function, the original variables you used when you called makeMove() aren’t modified.

Checking Whether the Player Won

Lines 42 to 49 in the isWinner() function are actually one long return statement:

39. def isWinner(bo, le):
40.     # Given a board and a player's letter, this function returns True if
          that player has won.
41.     # We use "bo" instead of "board" and "le" instead of "letter" so we
          don't have to type as much.
42.     return ((bo[7] == le and bo[8] == le and bo[9] == le) or # Across the
          top
43.     (bo[4] == le and bo[5] == le and bo[6] == le) or # Across the middle
44.     (bo[1] == le and bo[2] == le and bo[3] == le) or # Across the bottom
45.     (bo[7] == le and bo[4] == le and bo[1] == le) or # Down the left side
46.     (bo[8] == le and bo[5] == le and bo[2] == le) or # Down the middle
47.     (bo[9] == le and bo[6] == le and bo[3] == le) or # Down the right
          side
48.     (bo[7] == le and bo[5] == le and bo[3] == le) or # Diagonal
49.     (bo[9] == le and bo[5] == le and bo[1] == le)) # Diagonal

The bo and le names are shortcuts for the board and letter parameters. These shorter names mean you have less to type in this function. Remember, Python doesn’t care what you name your variables.

There are eight possible ways to win at Tic-Tac-Toe: you can have a line across the top, middle, or bottom rows; you can have a line down the left, middle, or right columns; or you can have a line across either of the two diagonals.

Each line of the condition checks whether the three spaces for a given line are equal to the letter provided (combined with the and operator). You combine each line using the or operator to check for the eight different ways to win. This means only one of the eight ways must be True in order for us to say that the player who owns the letter in le is the winner.

Let’s pretend that le is 'O' and bo is [' ', 'O', 'O', 'O', ' ', 'X', ' ', 'X', ' ', ' ']. The board would look like this:

X| |
-+-+-
 |X|
-+-+-
O|O|O

Here is how the expression after the return keyword on line 42 would evaluate. First Python replaces the variables bo and le with the values in each variable:

return (('X' == 'O' and ' ' == 'O' and ' ' == 'O') or
(' ' == 'O' and 'X' == 'O' and ' ' == 'O') or
('O' == 'O' and 'O' == 'O' and 'O' == 'O') or
('X' == 'O' and ' ' == 'O' and 'O' == 'O') or
(' ' == 'O' and 'X' == 'O' and 'O' == 'O') or
(' ' == 'O' and ' ' == 'O' and 'O' == 'O') or
('X' == 'O' and 'X' == 'O' and 'O' == 'O') or
(' ' == 'O' and 'X' == 'O' and 'O' == 'O'))

Next, Python evaluates all those == comparisons inside the parentheses to Boolean values:

return ((False and False and False) or
(False and False and False) or
(True and True and True) or
(False and False and True) or
(False and False and True) or
(False and False and True) or
(False and False and True) or
(False and False and True))

Then the Python interpreter evaluates all the expressions inside the parentheses:

return ((False) or
(False) or
(True) or
(False) or
(False) or
(False) or
(False) or
(False))

Since now there’s only one value inside each of the inner parentheses, you can get rid of them:

return (False or
False or
True or
False or
False or
False or
False or
False)

Now Python evaluates the expression connected by all those or operators:

return (True)

Once again, get rid of the parentheses, and you are left with one value:

return True

So given those values for bo and le, the expression would evaluate to True. This is how the program can tell if one of the players has won the game.

Duplicating the Board Data

The getBoardCopy() function allows you to easily make a copy of a given 10-string list that represents a Tic-Tac-Toe board in the game.

51. def getBoardCopy(board):
52.     # Make a copy of the board list and return it.
53.     boardCopy = []
54.     for i in board:
55.         boardCopy.append(i)
56.     return boardCopy

When the AI algorithm is planning its moves, it will sometimes need to make modifications to a temporary copy of the board without changing the actual board. In those cases, we call this function to make a copy of the board’s list. The new list is created on line 53.

Right now, the list stored in boardCopy is just an empty list. The for loop will iterate over the board parameter, appending a copy of the string values in the actual board to the duplicate board. After the getBoardCopy() function builds up a copy of the actual board, it returns a reference to this new board in boardCopy, not to the original one in board.

Checking Whether a Space on the Board Is Free

Given a Tic-Tac-Toe board and a possible move, the simple isSpaceFree() function returns whether that move is available or not:

58. def isSpaceFree(board, move):
59.     # Return True if the passed move is free on the passed board.
60.     return board[move] == ' '

Remember that free spaces in the board lists are marked as a single-space string. If the item at the space’s index is not equal to ' ', then the space is taken.

Letting the Player Enter a Move

The getPlayerMove() function asks the player to enter the number for the space they want to move on:

62. def getPlayerMove(board):
63.     # Let the player enter their move.
64.     move = ' '
65.     while move not in '1 2 3 4 5 6 7 8 9'.split() or not
          isSpaceFree(board, int(move)):
66.         print('What is your next move? (1-9)')
67.         move = input()
68.     return int(move)

The condition on line 65 is True if either of the expressions on the left or right side of the or operator is True. The loop makes sure the execution doesn’t continue until the player has entered an integer between 1 and 9. It also checks that the space entered isn’t already taken, given the Tic-Tac-Toe board passed to the function for the board parameter. The two lines of code inside the while loop simply ask the player to enter a number from 1 to 9.

The expression on the left side checks whether the player’s move is equal to '1', '2', '3', and so on up to '9' by creating a list with these strings (with the split() method) and checking whether move is in this list. In this expression, '1 2 3 4 5 6 7 8 9'.split() evaluates to ['1', '2', '3', '4', '5', '6', '7', '8', '9'], but the former is easier to type.

The expression on the right side checks whether the move the player entered is a free space on the board by calling isSpaceFree(). Remember that isSpaceFree() returns True if the move you pass is available on the board. Note that isSpaceFree() expects an integer for move, so the int() function returns an integer form of move.

The not operators are added to both sides so that the condition is True when either of these requirements is unfulfilled. This causes the loop to ask the player again and again for a number until they enter a proper move.

Finally, line 68 returns the integer form of whatever move the player entered. input() returns strings, so the int() function is called to return an integer form of the string.

Short-Circuit Evaluation

You may have noticed there’s a possible problem in the getPlayerMove() function. What if the player entered 'Z' or some other noninteger string? The expression move not in '1 2 3 4 5 6 7 8 9'.split() on the left side of or would return False as expected, and then Python would evaluate the expression on the right side of the or operator.

But calling int('Z') would cause Python to give an error, because the int() function can take only strings of number characters like '9' or '0', not strings like 'Z'.

To see an example of this kind of error, enter the following into the interactive shell:

>>> int('42')
42
>>> int('Z')
Traceback (most recent call last):
  File "<pyshell#3>", line 1, in <module>
    int('Z')
ValueError: invalid literal for int() with base 10: 'Z'

But when you play the Tic-Tac-Toe game and try entering 'Z' for your move, this error doesn’t happen. This is because the while loop’s condition is being short-circuited.

Short-circuiting means that an expression evaluates only part of the way, since the rest of the expression doesn’t change what the expression evaluates to. Here’s a short program that gives a good example of short-circuiting. Enter the following into the interactive shell:

>>> def ReturnsTrue():
        print('ReturnsTrue() was called.')
        return True
>>> def ReturnsFalse():
        print('ReturnsFalse() was called.')
        return False
>>> ReturnsTrue()
ReturnsTrue() was called.
True
>>> ReturnsFalse()
ReturnsFalse() was called.
False

When ReturnsTrue() is called, it prints 'ReturnsTrue() was called.' and then also displays the return value of ReturnsTrue(). The same goes for ReturnsFalse().

Now enter the following into the interactive shell:

>>> ReturnsFalse() or ReturnsTrue()
ReturnsFalse() was called.
ReturnsTrue() was called.
True
>>> ReturnsTrue() or ReturnsFalse()
ReturnsTrue() was called.
True

The first part makes sense: the expression ReturnsFalse() or ReturnsTrue() calls both of the functions, so you see both of the printed messages.

But the second expression only shows 'ReturnsTrue() was called.', not 'ReturnsFalse() was called.'. This is because Python didn’t call ReturnsFalse() at all. Since the left side of the or operator is True, it doesn’t matter what ReturnsFalse() returns, so Python doesn’t bother calling it. The evaluation was short-circuited.

The same applies for the and operator. Now enter the following into the interactive shell:

>>> ReturnsTrue() and ReturnsTrue()
ReturnsTrue() was called.
ReturnsTrue() was called.
True
>>> ReturnsFalse() and ReturnsFalse()
ReturnsFalse() was called.
False

Again, if the left side of the and operator is False, then the entire expression is False. It doesn’t matter whether the right side of and is True or False, so Python doesn’t bother evaluating it. Both False and True and False and False evaluate to False, so Python short-circuits the evaluation.

Let’s return to lines 65 to 68 of the Tic-Tac-Toe program:

65.     while move not in '1 2 3 4 5 6 7 8 9'.split() or not
          isSpaceFree(board, int(move)):
66.         print('What is your next move? (1-9)')
67.         move = input()
68.     return int(move)

Since the part of the condition on the left side of the or operator (move not in '1 2 3 4 5 6 7 8 9'.split()) evaluates to True, the Python interpreter knows that the entire expression will evaluate to True. It doesn’t matter if the expression on the right side of or evaluates to True or False, because only one value on either side of the or operator needs to be True for the whole expression to be True.

So Python stops checking the rest of the expression and doesn’t even bother evaluating the not isSpaceFree(board, int(move)) part. This means the int() and the isSpaceFree() functions are never called as long as move not in '1 2 3 4 5 6 7 8 9'.split() is True.

This works out well for the program, because if the right side of the condition is True, then move isn’t a string of a single-digit number. That would cause int() to give us an error. But if move not in '1 2 3 4 5 6 7 8 9'.split() evaluates to True, Python short-circuits not isSpaceFree(board, int(move)) and int(move) is not called.

Choosing a Move from a List of Moves

Now let’s look at the chooseRandomMoveFromList() function, which is useful for the AI code later in the program:

70. def chooseRandomMoveFromList(board, movesList):
71.     # Returns a valid move from the passed list on the passed board.
72.     # Returns None if there is no valid move.
73.     possibleMoves = []
74.     for i in movesList:
75.         if isSpaceFree(board, i):
76.             possibleMoves.append(i)

Remember that the board parameter is a list of strings that represents a Tic-Tac-Toe board. The second parameter, movesList, is a list of integers of possible spaces from which to choose. For example, if movesList is [1, 3, 7, 9], that means chooseRandomMoveFromList() should return the integer for one of the corner spaces.

However, chooseRandomMoveFromList() first checks that the space is valid to make a move on. The possibleMoves list starts as a blank list. The for loop then iterates over movesList. The moves that cause isSpaceFree() to return True are added to possibleMoves with the append() method.

At this point, the possibleMoves list has all of the moves that were in movesList that are also free spaces. The program then checks whether the list is empty:

78.     if len(possibleMoves) != 0:
79.         return random.choice(possibleMoves)
80.     else:
81.         return None

If the list isn’t empty, then there’s at least one possible move that can be made on the board.

But this list could be empty. For example, if movesList was [1, 3, 7, 9] but the board represented by the board parameter had all the corner spaces already taken, the possibleMoves list would be []. In that case, len(possibleMoves) evaluates to 0, and the function returns the value None.

The None Value

The None value represents the lack of a value. None is the only value of the data type NoneType. You might use the None value when you need a value that means “does not exist” or “none of the above.”

For example, say you had a variable named quizAnswer that holds the user’s answer to some true/false pop quiz question. The variable could hold True or False for the user’s answer. But if the user didn’t answer the question, you wouldn’t want to set quizAnswer to True or False, because then it would look like the user answered the question. Instead, you could set quizAnswer to None if the user skipped the question.

As a side note, None is not displayed in the interactive shell like other values are:

>>> 2 + 2
4
>>> 'This is a string value.'
'This is a string value.'
>>> None
>>>

The values of the first two expressions are printed as output on the next line, but None has no value, so it is not printed.

Functions that don’t seem to return anything actually return the None value. For example, print() returns None:

>>> spam = print('Hello world!')
Hello world!
>>> spam == None
True

Here we assigned print('Hello world!') to spam. The print() function, like all functions, has a return value. Even though print() prints an output, the function call returns None. IDLE doesn’t show None in the interactive shell, but you can tell spam is set to None because spam == None evaluates as True.

Creating the Computer’s AI

The getComputerMove() function contains the AI’s code:

83. def getComputerMove(board, computerLetter):
84.     # Given a board and the computer's letter, determine where to move
          and return that move.
85.     if computerLetter == 'X':
86.         playerLetter = 'O'
87.     else:
88.         playerLetter = 'X'

The first argument is a Tic-Tac-Toe board for the board parameter. The second argument is the letter the computer uses—either 'X' or 'O' in the computerLetter parameter. The first few lines simply assign the other letter to a variable named playerLetter. This way, the same code can be used whether the computer is X or O.

Remember how the Tic-Tac-Toe AI algorithm works:

1. See if there’s a move the computer can make that will win the game. If there is, take that move. Otherwise, go to step 2.

2. See if there’s a move the player can make that will cause the computer to lose the game. If there is, the computer should move there to block the player. Otherwise, go to step 3.

3. Check if any of the corners (spaces 1, 3, 7, or 9) are free. If no corner space is free, go to step 4.

4. Check if the center is free. If so, move there. If it isn’t, go to step 5.

5. Move on any of the sides (spaces 2, 4, 6, or 8). There are no more steps, because the side spaces are the only spaces left if the execution has reached this step.

The function will return an integer from 1 to 9 representing the computer’s move. Let’s walk through how each of these steps is implemented in the code.

Checking Whether the Computer Can Win in One Move

Before anything else, if the computer can win in the next move, it should make that winning move immediately.

90.     # Here is the algorithm for our Tic-Tac-Toe AI:
91.     # First, check if we can win in the next move.
92.     for i in range(1, 10):
93.         boardCopy = getBoardCopy(board)
94.         if isSpaceFree(boardCopy, i):
95.             makeMove(boardCopy, computerLetter, i)
96.             if isWinner(boardCopy, computerLetter):
97.                 return i

The for loop that starts on line 92 iterates over every possible move from 1 to 9. The code inside the loop simulates what would happen if the computer made that move.

The first line in the loop (line 93) makes a copy of the board list. This is so the simulated move inside the loop doesn’t modify the real Tic-Tac-Toe board stored in the board variable. The getBoardCopy() returns an identical but separate board list value.

Line 94 checks whether the space is free and, if so, simulates making the move on the copy of the board. If this move results in the computer winning, the function returns that move’s integer.

If none of the spaces results in winning, the loop ends, and the program execution continues to line 100.

Checking Whether the Player Can Win in One Move

Next, the code will simulate the human player moving on each of the spaces:

 99.     # Check if the player could win on their next move and block them.
100.     for i in range(1, 10):
101.         boardCopy = getBoardCopy(board)
102.         if isSpaceFree(boardCopy, i):
103.             makeMove(boardCopy, playerLetter, i)
104.             if isWinner(boardCopy, playerLetter):
105.                 return i

The code is similar to the loop on line 92 except the player’s letter is put on the board copy. If the isWinner() function shows that the player would win with a move, then the computer will return that same move to block this from happening.

If the human player cannot win in one more move, the for loop finishes, and the execution continues to line 108.

Checking the Corner, Center, and Side Spaces (in That Order)

If the computer can’t make a winning move and doesn’t need to block the player’s move, it will move to a corner, center, or side space, depending on the spaces available.

The computer first tries to move to one of the corner spaces:

107.     # Try to take one of the corners, if they are free.
108.     move = chooseRandomMoveFromList(board, [1, 3, 7, 9])
109.     if move != None:
110.         return move

The call to the chooseRandomMoveFromList() function with the list [1, 3, 7, 9] ensures that the function returns the integer for one of the corner spaces: 1, 3, 7, or 9.

If all the corner spaces are taken, the chooseRandomMoveFromList() function returns None, and the execution moves on to line 113:

112.     # Try to take the center, if it is free.
113.     if isSpaceFree(board, 5):
114.         return 5

If none of the corners is available, line 114 moves on the center space if it is free. If the center space isn’t free, the execution moves on to line 117:

116.     # Move on one of the sides.
117.     return chooseRandomMoveFromList(board, [2, 4, 6, 8])

This code also makes a call to chooseRandomMoveFromList(), except you pass it a list of the side spaces:[2, 4, 6, 8]. This function won’t return None because the side spaces are the only spaces that can possibly be left. This ends the getComputerMove() function and the AI algorithm.

Checking Whether the Board Is Full

The last function is isBoardFull():

119. def isBoardFull(board):
120.     # Return True if every space on the board has been taken. Otherwise,
           return False.
121.     for i in range(1, 10):
122.         if isSpaceFree(board, i):
123.             return False
124.     return True

This function returns True if the 10-string list in the board argument it was passed has an 'X' or 'O' in every index (except for index 0, which is ignored). The for loop lets us check indexes 1 through 9 on the board list. As soon as it finds a free space on the board (that is, when isSpaceFree(board, i) returns True), the isBoardFull() function will return False.

If the execution manages to go through every iteration of the loop, then none of the spaces is free. Line 124 will then execute return True.

The Game Loop

Line 127 is the first line that isn’t inside of a function, so it’s the first line of code that executes when you run this program.

127. print('Welcome to Tic-Tac-Toe!')

This line greets the player before the game starts. The program then enters a while loop at line 129:

129. while True:
130.     # Reset the board.
131.     theBoard = [' '] * 10

The while loop keeps looping until the execution encounters a break statement. Line 131 sets up the main Tic-Tac-Toe board in a variable named theBoard. The board starts empty, which we represent with a list of 10 single space strings. Rather than type out this full list, line 131 uses list replication. It’s shorter to type [' '] * 10 than [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '].

Choosing the Player’s Mark and Who Goes First

Next, the inputPlayerLetter() function lets the player enter whether they want to be the X or O:

132.     playerLetter, computerLetter = inputPlayerLetter()

The function returns a two-string list, either ['X', 'O'] or ['O', 'X']. We use multiple assignment to set playerLetter to the first item in the returned list and computerLetter to the second.

From there, the whoGoesFirst() function randomly decides who goes first, returning either the string 'player' or the string 'computer', and then line 134 tells the player who will go first:

133.     turn = whoGoesFirst()
134.     print('The ' + turn + ' will go first.')
135.     gameIsPlaying = True

The gameIsPlaying variable keeps track of whether the game is still being played or if someone has won or tied.

Running the Player’s Turn

Line 137’s loop will keep going back and forth between the code for the player’s turn and the computer’s turn, as long as gameIsPlaying is set to True:

137.     while gameIsPlaying:
138.         if turn == 'player':
139.             # Player's turn
140.             drawBoard(theBoard)
141.             move = getPlayerMove(theBoard)
142.             makeMove(theBoard, playerLetter, move)

The turn variable was originally set to either 'player' or 'computer' by the whoGoesFirst() call on line 133. If turn equals 'computer', then line 138’s condition is False, and the execution jumps to line 156.

But if line 138 evaluates to True, line 140 calls drawBoard() and passes the theBoard variable to print the Tic-Tac-Toe board on the screen. Then getPlayerMove() lets the player enter their move (and also makes sure it is a valid move). The makeMove() function adds the player’s X or O to theBoard.

Now that the player has made their move, the program should check whether they have won the game:

144.             if isWinner(theBoard, playerLetter):
145.                 drawBoard(theBoard)
146.                 print('Hooray! You have won the game!')
147.                 gameIsPlaying = False

If the isWinner() function returns True, the if block’s code displays the winning board and prints a message telling the player they have won. The gameIsPlaying variable is also set to False so that the execution doesn’t continue on to the computer’s turn.

If the player didn’t win with their last move, maybe their move filled up the entire board and tied the game. The program checks that condition next with an else statement:

148.             else:
149.                 if isBoardFull(theBoard):
150.                     drawBoard(theBoard)
151.                     print('The game is a tie!')
152.                     break

In this else block, the isBoardFull() function returns True if there are no more moves to make. In that case, the if block starting at line 149 displays the tied board and tells the player a tie has occurred. The execution then breaks out of the while loop and jumps to line 173.

If the player hasn’t won or tied the game, the program enters another else statement:

153.             else:
154.                 turn = 'computer'

Line 154 sets the turn variable to 'computer' so that the program will execute the code for the computer’s turn on the next iteration.

Running the Computer’s Turn

If the turn variable wasn’t 'player' for the condition on line 138, then it must be the computer’s turn. The code in this else block is similar to the code for the player’s turn:

156.         else:
157.             # Computer's turn
158.             move = getComputerMove(theBoard, computerLetter)
159.             makeMove(theBoard, computerLetter, move)
160.
161.             if isWinner(theBoard, computerLetter):
162.                 drawBoard(theBoard)
163.                 print('The computer has beaten you! You lose.')
164.                 gameIsPlaying = False
165.         else:
166.             if isBoardFull(theBoard):
167.                 drawBoard(theBoard)
168.                 print('The game is a tie!')
169.                 break
170.             else:
171.                 turn = 'player'

Lines 157 to 171 are almost identical to the code for the player’s turn on lines 139 to 154. The only difference is that this code uses the computer’s letter and calls getComputerMove().

If the game isn’t won or tied, line 171 sets turn to the player’s turn. There are no more lines of code inside the while loop, so the execution jumps back to the while statement on line 137.

Asking the Player to Play Again

Finally, the program asks the player if they want to play another game:

173.     print('Do you want to play again? (yes or no)')
174.     if not input().lower().startswith('y'):
175.         break

Lines 173 to 175 are executed immediately after the while block started by the while statement on line 137. gameIsPlaying is set to False when the game has ended, so at this point the game asks the player if they want to play again.

The not input().lower().startswith('y') expression will be True if the player enters anything that doesn’t start with a 'y'. In that case, the break statement executes. That breaks the execution out of the while loop that was started on line 129. But since there are no more lines of code after that while block, the program terminates and the game ends.

Summary

Creating a program with AI comes down to carefully considering all the possible situations the AI can encounter and how it should respond in each of those situations. The Tic-Tac-Toe AI is simple because not as many moves are possible in Tic-Tac-Toe as in a game like chess or checkers.

Our computer AI checks for any possible winning moves. Otherwise, it checks whether it must block the player’s move. Then the AI simply chooses any available corner space, then the center space, then the side spaces. This is a simple algorithm for the computer to follow.

The key to implementing our AI is to make copies of the board data and simulate moves on the copy. That way, the AI code can see whether a move results in a win or loss. Then the AI can make that move on the real board. This type of simulation is effective at predicting what is or isn’t a good move.