Use this link to get 70% off the Automate the Boring Stuff online video course.
Support me on Patreon
In this chapter, we’ll make Reversegam, also known as Reversi or Othello. This two-player board game is played on a grid, so we’ll use a Cartesian coordinate system with x- and y-coordinates. Our version of the game will have a computer AI that is more advanced than our Tic-Tac-Toe AI from Chapter 10. In fact, this AI is so good that it will probably beat you almost every time you play. (I lose whenever I play against it!)
Reversegam has an 8×8 board and tiles that are black on one side and white on the other (our game will use Os and Xs instead). The starting board looks like Figure 15-1.
Figure 15-1: The starting Reversegam board has two white tiles and two black tiles.
Two players take turns placing tiles of their chosen color—black or white—on the board. When a player places a tile on the board, any of the opponent’s tiles that are between the new tile and the other tiles of the player’s color are flipped. For example, when the white player places a new white tile on space (5, 6), as in Figure 15-2, the black tile at (5, 5) is between two white tiles, so it will flip to white, as in Figure 15-3. The goal of the game is to end with more tiles of your color than your opponent’s color.
Figure 15-2: White places a new tile.
Figure 15-3: White’s move has caused one of black’s tiles to flip.
Black could make a similar move next, placing a black tile on (4, 6), which would flip the white tile at (4, 5). This results in a board that looks like Figure 15-4.
Figure 15-4: Black has placed a new tile, flipping one of white’s tiles.
Tiles in all directions are flipped as long as they are between the player’s new tile and an existing tile of that color. In Figure 15-5, white places a tile at (3, 6) and flips black tiles in two directions (marked by the lines). The result is shown in Figure 15-6.
Each player can quickly flip many tiles on the board in one or two moves. Players must always make a move that flips at least one tile. The game ends when either a player can’t make a move or the board is completely full. The player with the most tiles of their color wins.
Figure 15-5: White’s second move at (3, 6) will flip two of black’s tiles.
Figure 15-6: The board after white’s second move.
The AI we make for this game will look for any corner moves on the board it can take. If there are no corner moves available, the computer will select the move that claims the most tiles.
Here’s what the user sees when they run the Reversegam program. The text entered by the player is bold.
Welcome to Reversegam!
Do you want to be X or O?
x
The player will go first.
12345678
+--------+
1| |1
2| |2
3| |3
4| XO |4
5| OX |5
6| |6
7| |7
8| |8
+--------+
12345678
You: 2 points. Computer: 2 points.
Enter your move, "quit" to end the game, or "hints" to toggle hints.
53
12345678
+--------+
1| |1
2| |2
3| X |3
4| XX |4
5| OX |5
6| |6
7| |7
8| |8
+--------+
12345678
You: 4 points. Computer: 1 points.
Press Enter to see the computer's move.
--snip--
12345678
+--------+
1|OOOOOOOO|1
2|OXXXOOOO|2
3|OXOOOOOO|3
4|OXXOXXOX|4
5|OXXOOXOX|5
6|OXXXXOOX|6
7|OOXXOOOO|7
8|OOXOOOOO|8
+--------+
12345678
X scored 21 points. O scored 43 points.
You lost. The computer beat you by 22 points.
Do you want to play again? (yes or no)
no
As you can see, the AI was pretty good at beating me, 43 to 21. To help the player out, we’ll program the game to provide hints. The player can type hints as their move, which will toggle the hints mode on and off. When hints mode is on, all the possible moves the player can make will show up on the board as periods (.), like this:
12345678
+--------+
1| |1
2| . |2
3| XO. |3
4| XOX |4
5| OOO |5
6| . . |6
7| |7
8| |8
+--------+
12345678
As you can see, the player can move on (4, 2), (5, 3), (4, 6), or (6, 6) based on the hints shown on this board.
Reversegam is a mammoth program compared to our previous games. It’s nearly 300 lines long! But don’t worry: many of these are comments or blank lines to space out the code and make it more readable.
As with our other programs, we’ll first create several functions to carry out Reversegam-related tasks that the main section will call. Roughly the first 250 lines of code are for these helper functions, and the last 30 lines of code implement the Reversegam game itself.
If you get errors after entering this code, compare your code to the book’s code with the online diff tool at https://www.nostarch.com/inventwithpython#diff.
reversegam.py
1. # Reversegam: a clone of Othello/Reversi
2. import random
3. import sys
4. WIDTH = 8 # Board is 8 spaces wide.
5. HEIGHT = 8 # Board is 8 spaces tall.
6. def drawBoard(board):
7. # Print the board passed to this function. Return None.
8. print(' 12345678')
9. print(' +--------+')
10. for y in range(HEIGHT):
11. print('%s|' % (y+1), end='')
12. for x in range(WIDTH):
13. print(board[x][y], end='')
14. print('|%s' % (y+1))
15. print(' +--------+')
16. print(' 12345678')
17.
18. def getNewBoard():
19. # Create a brand-new, blank board data structure.
20. board = []
21. for i in range(WIDTH):
22. board.append([' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '])
23. return board
24.
25. def isValidMove(board, tile, xstart, ystart):
26. # Return False if the player's move on space xstart, ystart is
invalid.
27. # If it is a valid move, return a list of spaces that would become
the player's if they made a move here.
28. if board[xstart][ystart] != ' ' or not isOnBoard(xstart, ystart):
29. return False
30.
31. if tile == 'X':
32. otherTile = 'O'
33. else:
34. otherTile = 'X'
35.
36. tilesToFlip = []
37. for xdirection, ydirection in [[0, 1], [1, 1], [1, 0], [1, -1],
[0, -1], [-1, -1], [-1, 0], [-1, 1]]:
38. x, y = xstart, ystart
39. x += xdirection # First step in the x direction
40. y += ydirection # First step in the y direction
41. while isOnBoard(x, y) and board[x][y] == otherTile:
42. # Keep moving in this x & y direction.
43. x += xdirection
44. y += ydirection
45. if isOnBoard(x, y) and board[x][y] == tile:
46. # There are pieces to flip over. Go in the reverse
direction until we reach the original space, noting all
the tiles along the way.
47. while True:
48. x -= xdirection
49. y -= ydirection
50. if x == xstart and y == ystart:
51. break
52. tilesToFlip.append([x, y])
53.
54. if len(tilesToFlip) == 0: # If no tiles were flipped, this is not a
valid move.
55. return False
56. return tilesToFlip
57.
58. def isOnBoard(x, y):
59. # Return True if the coordinates are located on the board.
60. return x >= 0 and x <= WIDTH - 1 and y >= 0 and y <= HEIGHT - 1
61.
62. def getBoardWithValidMoves(board, tile):
63. # Return a new board with periods marking the valid moves the player
can make.
64. boardCopy = getBoardCopy(board)
65.
66. for x, y in getValidMoves(boardCopy, tile):
67. boardCopy[x][y] = '.'
68. return boardCopy
69.
70. def getValidMoves(board, tile):
71. # Return a list of [x,y] lists of valid moves for the given player
on the given board.
72. validMoves = []
73. for x in range(WIDTH):
74. for y in range(HEIGHT):
75. if isValidMove(board, tile, x, y) != False:
76. validMoves.append([x, y])
77. return validMoves
78.
79. def getScoreOfBoard(board):
80. # Determine the score by counting the tiles. Return a dictionary
with keys 'X' and 'O'.
81. xscore = 0
82. oscore = 0
83. for x in range(WIDTH):
84. for y in range(HEIGHT):
85. if board[x][y] == 'X':
86. xscore += 1
87. if board[x][y] == 'O':
88. oscore += 1
89. return {'X':xscore, 'O':oscore}
90.
91. def enterPlayerTile():
92. # Let the player enter which tile they want to be.
93. # Return a list with the player's tile as the first item and the
computer's tile as the second.
94. tile = ''
95. while not (tile == 'X' or tile == 'O'):
96. print('Do you want to be X or O?')
97. tile = input().upper()
98.
99. # The first element in the list is the player's tile, and the second
is the computer's tile.
100. if tile == 'X':
101. return ['X', 'O']
102. else:
103. return ['O', 'X']
104.
105. def whoGoesFirst():
106. # Randomly choose who goes first.
107. if random.randint(0, 1) == 0:
108. return 'computer'
109. else:
110. return 'player'
111.
112. def makeMove(board, tile, xstart, ystart):
113. # Place the tile on the board at xstart, ystart and flip any of the
opponent's pieces.
114. # Return False if this is an invalid move; True if it is valid.
115. tilesToFlip = isValidMove(board, tile, xstart, ystart)
116.
117. if tilesToFlip == False:
118. return False
119.
120. board[xstart][ystart] = tile
121. for x, y in tilesToFlip:
122. board[x][y] = tile
123. return True
124.
125. def getBoardCopy(board):
126. # Make a duplicate of the board list and return it.
127. boardCopy = getNewBoard()
128.
129. for x in range(WIDTH):
130. for y in range(HEIGHT):
131. boardCopy[x][y] = board[x][y]
132.
133. return boardCopy
134.
135. def isOnCorner(x, y):
136. # Return True if the position is in one of the four corners.
137. return (x == 0 or x == WIDTH - 1) and (y == 0 or y == HEIGHT - 1)
138.
139. def getPlayerMove(board, playerTile):
140. # Let the player enter their move.
141. # Return the move as [x, y] (or return the strings 'hints' or
'quit').
142. DIGITS1TO8 = '1 2 3 4 5 6 7 8'.split()
143. while True:
144. print('Enter your move, "quit" to end the game, or "hints" to
toggle hints.')
145. move = input().lower()
146. if move == 'quit' or move == 'hints':
147. return move
148.
149. if len(move) == 2 and move[0] in DIGITS1TO8 and move[1] in
DIGITS1TO8:
150. x = int(move[0]) - 1
151. y = int(move[1]) - 1
152. if isValidMove(board, playerTile, x, y) == False:
153. continue
154. else:
155. break
156. else:
157. print('That is not a valid move. Enter the column (1-8) and
then the row (1-8).')
158. print('For example, 81 will move on the top-right corner.')
159.
160. return [x, y]
161.
162. def getComputerMove(board, computerTile):
163. # Given a board and the computer's tile, determine where to
164. # move and return that move as an [x, y] list.
165. possibleMoves = getValidMoves(board, computerTile)
166. random.shuffle(possibleMoves) # Randomize the order of the moves.
167.
168. # Always go for a corner if available.
169. for x, y in possibleMoves:
170. if isOnCorner(x, y):
171. return [x, y]
172.
173. # Find the highest-scoring move possible.
174. bestScore = -1
175. for x, y in possibleMoves:
176. boardCopy = getBoardCopy(board)
177. makeMove(boardCopy, computerTile, x, y)
178. score = getScoreOfBoard(boardCopy)[computerTile]
179. if score > bestScore:
180. bestMove = [x, y]
181. bestScore = score
182. return bestMove
183.
184. def printScore(board, playerTile, computerTile):
185. scores = getScoreOfBoard(board)
186. print('You: %s points. Computer: %s points.' % (scores[playerTile],
scores[computerTile]))
187.
188. def playGame(playerTile, computerTile):
189. showHints = False
190. turn = whoGoesFirst()
191. print('The ' + turn + ' will go first.')
192.
193. # Clear the board and place starting pieces.
194. board = getNewBoard()
195. board[3][3] = 'X'
196. board[3][4] = 'O'
197. board[4][3] = 'O'
198. board[4][4] = 'X'
199.
200. while True:
201. playerValidMoves = getValidMoves(board, playerTile)
202. computerValidMoves = getValidMoves(board, computerTile)
203.
204. if playerValidMoves == [] and computerValidMoves == []:
205. return board # No one can move, so end the game.
206.
207. elif turn == 'player': # Player's turn
208. if playerValidMoves != []:
209. if showHints:
210. validMovesBoard = getBoardWithValidMoves(board,
playerTile)
211. drawBoard(validMovesBoard)
212. else:
213. drawBoard(board)
214. printScore(board, playerTile, computerTile)
215.
216. move = getPlayerMove(board, playerTile)
217. if move == 'quit':
218. print('Thanks for playing!')
219. sys.exit() # Terminate the program.
220. elif move == 'hints':
221. showHints = not showHints
222. continue
223. else:
224. makeMove(board, playerTile, move[0], move[1])
225. turn = 'computer'
226.
227. elif turn == 'computer': # Computer's turn
228. if computerValidMoves != []:
229. drawBoard(board)
230. printScore(board, playerTile, computerTile)
231.
232. input('Press Enter to see the computer\'s move.')
233. move = getComputerMove(board, computerTile)
234. makeMove(board, computerTile, move[0], move[1])
235. turn = 'player'
236.
237.
238.
239. print('Welcome to Reversegam!')
240.
241. playerTile, computerTile = enterPlayerTile()
242.
243. while True:
244. finalBoard = playGame(playerTile, computerTile)
245.
246. # Display the final score.
247. drawBoard(finalBoard)
248. scores = getScoreOfBoard(finalBoard)
249. print('X scored %s points. O scored %s points.' % (scores['X'],
scores['O']))
250. if scores[playerTile] > scores[computerTile]:
251. print('You beat the computer by %s points! Congratulations!' %
(scores[playerTile] - scores[computerTile]))
252. elif scores[playerTile] < scores[computerTile]:
253. print('You lost. The computer beat you by %s points.' %
(scores[computerTile] - scores[playerTile]))
254. else:
255. print('The game was a tie!')
256.
257. print('Do you want to play again? (yes or no)')
258. if not input().lower().startswith('y'):
259. break
As with our other games, we begin this program by importing modules:
1. # Reversegam: a clone of Othello/Reversi
2. import random
3. import sys
4. WIDTH = 8 # Board is 8 spaces wide.
5. HEIGHT = 8 # Board is 8 spaces tall.
Line 2 imports the random module for its randint() and choice() functions. Line 3 imports the sys module for its exit() function.
Lines 4 and 5 set two constants, WIDTH and HEIGHT, which are used to set up the game board.
Let’s figure out the board’s data structure. This data structure is a list of lists, just like the one in Chapter 13’s Sonar Treasure Hunt game. The list of lists is created so that board[x][y] will represent the character on the space located at position x on the x-axis (going left/right) and position y on the y-axis (going up/down).
This character can either be a ' ' (a space representing an empty position), a '.' (a period representing a possible move in hints mode), or an 'X' or 'O' (letters representing tiles). Whenever you see a parameter named board, it is meant to be this kind of list-of-lists data structure.
It is important to note that while the x- and y-coordinates for the game board will range from 1 to 8, the indexes of the list data structure will range from 0 to 7. Our code will need to make slight adjustments to account for this.
The board data structure is just a Python list value, but we need a nicer way to present it on the screen. The drawBoard() function takes a board data structure and displays it on the screen so the player knows where tiles are placed:
6. def drawBoard(board):
7. # Print the board passed to this function. Return None.
8. print(' 12345678')
9. print(' +--------+')
10. for y in range(HEIGHT):
11. print('%s|' % (y+1), end='')
12. for x in range(WIDTH):
13. print(board[x][y], end='')
14. print('|%s' % (y+1))
15. print(' +--------+')
16. print(' 12345678')
The drawBoard() function prints the current game board based on the data structure in board.
Line 8 is the first print() function call executed for each board, and it prints the labels for the x-axis along the top of the board. Line 9 prints the top horizontal line of the board. The for loop on line 10 will loop eight times, once for each row. Line 11 prints the label for the y-axis on the left side of the board, and it has an end='' keyword argument to print nothing instead of a new line.
This is so that another loop on line 12 (which also loops eight times, once for each column in the row) prints each position along with an X, O, ., or blank space depending on what’s stored in board[x][y]. Line 13’s print() function call inside this loop also has an end='' keyword argument so that the newline character is not printed. That will produce a single line on the screen that looks like '1|XXXXXXXX|1' (if each of the board[x][y] values were an 'X').
After the inner loop is done, the print() function calls on lines 15 and 16 to print the bottom horizontal line and x-axis labels.
When the for loop on line 13 prints the row eight times, it forms the entire board:
12345678
+--------+
1|XXXXXXXX|1
2|XXXXXXXX|2
3|XXXXXXXX|3
4|XXXXXXXX|4
5|XXXXXXXX|5
6|XXXXXXXX|6
7|XXXXXXXX|7
8|XXXXXXXX|8
+--------+
12345678
Of course, instead of X, some of the spaces on the board will be the other player’s mark (O), a period (.) if hints mode is turned on, or a space for empty positions.
The drawBoard() function will display a board data structure on the screen, but we need a way to create these board data structures as well. The getNewBoard() function returns a list of eight lists, with each list containing eight ' ' strings that will represent a blank board with no moves:
18. def getNewBoard():
19. # Create a brand-new, blank board data structure.
20. board = []
21. for i in range(WIDTH):
22. board.append([' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '])
23. return board
Line 20 creates the list that contains the inner lists. The for loop adds eight inner lists inside this list. These inner lists have eight strings to represent eight empty spaces on the board. Together, this code creates a board with 64 empty spaces—a blank Reversegam board.
Given the board’s data structure, the player’s tile, and the x- and y-coordinates for the player’s move, the isValidMove() function should return True if the Reversegam game rules allow a move on those coordinates, and False if they don’t. For a move to be valid, it must be on the board and also flip at least one of the opponent’s tiles.
This function uses several x- and y-coordinates on the board, so the xstart and ystart variables keep track of the x- and y-coordinates of the original move.
25. def isValidMove(board, tile, xstart, ystart):
26. # Return False if the player's move on space xstart, ystart is
invalid.
27. # If it is a valid move, return a list of spaces that would become
the player's if they made a move here.
28. if board[xstart][ystart] != ' ' or not isOnBoard(xstart, ystart):
29. return False
30.
31. if tile == 'X':
32. otherTile = 'O'
33. else:
34. otherTile = 'X'
35.
36. tilesToFlip = []
Line 28 checks whether the x- and y-coordinates are on the game board and whether the space is empty using the isOnBoard() function (which we’ll define later in the program). This function makes sure both the x- and y-coordinates are between 0 and the WIDTH or HEIGHT of the board minus 1.
The player’s tile (either the human player or the computer player) is in tile, but this function will need to know the opponent’s tile. If the player’s tile is X, then obviously the opponent’s tile is O, and vice versa. We use the if-else statement on lines 31 to 34 for this.
Finally, if the given x- and y-coordinate is a valid move, isValidMove() returns a list of all the opponent’s tiles that would be flipped by this move. We create a new empty list, tilesToFlip, that we’ll use to store all the tile coordinates.
In order for a move to be valid, it needs to flip at least one of the opponent’s tiles by sandwiching the current player’s new tile with one of the player’s old tiles. That means that the new tile must be next to one of the opponent’s tiles.
The for loop on line 37 iterates through a list of lists that represents the directions the program will check for an opponent’s tile:
37. for xdirection, ydirection in [[0, 1], [1, 1], [1, 0], [1, -1],
[0, -1], [-1, -1], [-1, 0], [-1, 1]]:
The game board is a Cartesian coordinate system with x- and y-directions. There are eight directions to check: up, down, left, right, and the four diagonal directions. Each of the eight two-item lists in the list on line 37 is used for checking one of these directions. The program checks a direction by adding the first value in the two-item list to the x-coordinate and the second value to the y-coordinate.
Because the x-coordinates increase as you go to the right, you can check the right direction by adding 1 to the x-coordinate. So the [1, 0] list adds 1 to the x-coordinate and 0 to the y-coordinate. Checking the left direction is the opposite: you would subtract 1 (that is, add -1) from the x-coordinate.
But to check diagonally, you need to add to or subtract from both coordinates. For example, adding 1 to the x-coordinate and adding -1 to the y-coordinate would result in checking the up-right diagonal direction.
Figure 15-7 shows a diagram to make it easier to remember which two-item list represents which direction.
Figure 15-7: Each two-item list represents one of the eight directions.
The for loop at line 37 iterates through each of the two-item lists so that each direction is checked. Inside the for loop, the x and y variables are set to the same values as xstart and ystart, respectively, using multiple assignment at line 38. The xdirection and ydirection variables are set to the values in one of the two-item lists and change the x and y variables according to the direction being checked in that iteration of the for loop:
37. for xdirection, ydirection in [[0, 1], [1, 1], [1, 0], [1, -1],
[0, -1], [-1, -1], [-1, 0], [-1, 1]]:
38. x, y = xstart, ystart
39. x += xdirection # First step in the x direction
40. y += ydirection # First step in the y direction
The xstart and ystart variables will stay the same so that the program can remember which space it originally started from.
Remember, for a move to be valid, it must be both on the board and next to one of the other player’s tiles. (Otherwise, there aren’t any of the opponent’s tiles to flip, and a move must flip over at least one tile to be valid.) Line 41 checks this condition, and if it isn’t True, the execution goes back to the for statement to check the next direction.
41. while isOnBoard(x, y) and board[x][y] == otherTile:
42. # Keep moving in this x & y direction.
43. x += xdirection
44. y += ydirection
But if the first space checked does have the opponent’s tile, then the program should check for more of the opponent’s tiles in that direction until it reaches one of the player’s tiles or the end of the board. The next tile in the same direction is checked by using xdirection and ydirection again to make x and y the next coordinates to check. So the program changes x and y on lines 43 and 44.
Next, we check whether there are adjacent tiles that can be flipped over.
45. if isOnBoard(x, y) and board[x][y] == tile:
46. # There are pieces to flip over. Go in the reverse
direction until we reach the original space, noting all
the tiles along the way.
47. while True:
48. x -= xdirection
49. y -= ydirection
50. if x == xstart and y == ystart:
51. break
52. tilesToFlip.append([x, y])
The if statement on line 45 checks whether a coordinate is occupied by the player’s own tile. This tile will mark the end of the sandwich made by the player’s tiles surrounding the opponent’s tiles. We also need to record the coordinates of all of the opponent’s tiles that should be flipped.
The while loop moves x and y in reverse on lines 48 and 49. Until x and y are back to the original xstart and ystart position, xdirection and ydirection are subtracted from x and y, and each x and y position is appended to the tilesToFlip list. When x and y have reached the xstart and ystart position, line 51 breaks the execution out of the loop. Since the original xstart and ystart position is an empty space (we ensured this was the case on lines 28 and 29), the condition for line 41’s while loop will be False. The program moves on to line 37, and the for loop checks the next direction.
The for loop does this in all eight directions. After that loop is done, the tilesToFlip list will contain the x- and y-coordinates of all our opponent’s tiles that would be flipped if the player moved on xstart, ystart. Remember, the isValidMove() function is only checking whether the original move was valid; it doesn’t actually permanently change the data structure of the game board.
If none of the eight directions ended up flipping at least one of the opponent’s tiles, then tilesToFlip will be an empty list:
54. if len(tilesToFlip) == 0: # If no tiles were flipped, this is not a
valid move.
55. return False
56. return tilesToFlip
This is a sign that this move is not valid and isValidMove() should return False. Otherwise, isValidMove() returns tilesToFlip.
The isOnBoard() function is called from isValidMove(). It does a simple check to see whether given x- and y-coordinates are on the board. For example, an x-coordinate of 4 and a y-coordinate of 9999 would not be on the board since y-coordinates only go up to 7, which is equal to WIDTH - 1 or HEIGHT - 1.
58. def isOnBoard(x, y):
59. # Return True if the coordinates are located on the board.
60. return x >= 0 and x <= WIDTH - 1 and y >= 0 and y <= HEIGHT - 1
Calling this function is shorthand for the Boolean expression on line 72 that checks whether both x and y are between 0 and the WIDTH or HEIGHT subtracted by 1, which is 7.
Now let’s create a hints mode that displays a board with all possible moves marked on it. The getBoardWithValidMoves() function returns a game board data structure that has periods (.) for all spaces that are valid moves:
62. def getBoardWithValidMoves(board, tile):
63. # Return a new board with periods marking the valid moves the player
can make.
64. boardCopy = getBoardCopy(board)
65.
66. for x, y in getValidMoves(boardCopy, tile):
67. boardCopy[x][y] = '.'
68. return boardCopy
This function creates a duplicate game board data structure called boardCopy (returned by getBoardCopy() on line 64) instead of modifying the one passed to it in the board parameter. Line 66 calls getValidMoves() to get a list of x- and y-coordinates with all the legal moves the player could make. The board copy is marked with periods in those spaces and returned.
The getValidMoves() function returns a list of two-item lists. The two-item lists hold the x- and y-coordinates for all valid moves of the tile given to it for the board data structure in the board parameter:
70. def getValidMoves(board, tile):
71. # Return a list of [x,y] lists of valid moves for the given player
on the given board.
72. validMoves = []
73. for x in range(WIDTH):
74. for y in range(HEIGHT):
75. if isValidMove(board, tile, x, y) != False:
76. validMoves.append([x, y])
77. return validMoves
This function uses nested loops (on lines 73 and 74) to check every xand y-coordinate (all 64 of them) by calling isValidMove() on that space and checking whether it returns False or a list of possible moves (in which case the move is valid). Each valid x- and y-coordinate is appended to the list in validMoves.
You may have noticed that the program checks whether isValidMove() on line 75 returns False even though this function returns a list. To understand how this works, you need to learn a bit more about Booleans and the bool() function.
The bool() function is similar to the int() and str() functions. It returns the Boolean value form of the value passed to it.
Most data types have one value that is considered the False value for that data type. Every other value is considered True. For example, the integer 0, the floating-point number 0.0, an empty string, an empty list, and an empty dictionary are all considered to be False when used as the condition for an if or loop statement. All other values are True. Enter the following into the interactive shell:
>>> bool(0)
False
>>> bool(0.0)
False
>>> bool('')
False
>>> bool([])
False
>>> bool({})
False
>>> bool(1)
True
>>> bool('Hello')
True
>>> bool([1, 2, 3, 4, 5])
True
>>> bool({'spam':'cheese', 'fizz':'buzz'})
True
Conditions are automatically interpreted as Boolean values. This is why the condition on line 75 works correctly. The call to the isValidMove() function either returns the Boolean value False or a nonempty list.
If you imagine that the entire condition is placed inside a call to bool(), then line 75’s condition False becomes bool(False) (which, of course, evaluates to False). And a condition of a nonempty list placed as the parameter to bool() will return True.
The getScoreOfBoard() function uses nested for loops to check all 64 positions on the board and see which player’s tile (if any) is on them:
79. def getScoreOfBoard(board):
80. # Determine the score by counting the tiles. Return a dictionary
with keys 'X' and 'O'.
81. xscore = 0
82. oscore = 0
83. for x in range(WIDTH):
84. for y in range(HEIGHT):
85. if board[x][y] == 'X':
86. xscore += 1
87. if board[x][y] == 'O':
88. oscore += 1
89. return {'X':xscore, 'O':oscore}
For each X tile, the code increments xscore on line 86. For each O tile, the code increments oscore on line 88. The function then returns xscore and oscore in a dictionary.
The enterPlayerTile() function asks the player which tile they want to be, either X or O:
91. def enterPlayerTile():
92. # Let the player enter which tile they want to be.
93. # Return a list with the player's tile as the first item and the
computer's tile as the second.
94. tile = ''
95. while not (tile == 'X' or tile == 'O'):
96. print('Do you want to be X or O?')
97. tile = input().upper()
98.
99. # The first element in the list is the player's tile, and the second
is the computer's tile.
100. if tile == 'X':
101. return ['X', 'O']
102. else:
103. return ['O', 'X']
The for loop will keep looping until the player enters X or O in either upper- or lowercase. The enterPlayerTile() function then returns a two-item list, where the player’s tile choice is the first item and the computer’s tile is the second. Later, line 241 calls enterPlayerTile() and uses multiple assignment to put these two returned items in two variables.
The whoGoesFirst() function randomly selects who goes first and returns either the string 'computer' or the string 'player':
105. def whoGoesFirst():
106. # Randomly choose who goes first.
107. if random.randint(0, 1) == 0:
108. return 'computer'
109. else:
110. return 'player'
The makeMove() function is called when a player wants to place a tile on the board and flip the other tiles according to the rules of Reversegam:
112. def makeMove(board, tile, xstart, ystart):
113. # Place the tile on the board at xstart, ystart and flip any of the
opponent's pieces.
114. # Return False if this is an invalid move; True if it is valid.
115. tilesToFlip = isValidMove(board, tile, xstart, ystart)
This function modifies in place the board data structure that is passed. Changes made to the board variable (because it is a list reference) will be made to the global scope.
Most of the work is done by isValidMove() on line 115, which returns a list of x- and y-coordinates (in a two-item list) of tiles that need to be flipped. Remember, if the xstart and ystart arguments point to an invalid move, isValidMove() will return the Boolean value False, which is checked for by line 117:
117. if tilesToFlip == False:
118. return False
119.
120. board[xstart][ystart] = tile
121. for x, y in tilesToFlip:
122. board[x][y] = tile
123. return True
If the return value of isValidMove() (now stored in tilesToFlip) is False, then makeMove() will also return False on line 118.
Otherwise, isValidMove() returns a list of spaces on the board to put down the tiles (the 'X' or 'O' string in tile). Line 120 sets the space that the player has moved on. Line 121 for loop sets all the tiles that are in tilesToFlip.
The getBoardCopy() function is different from getNewBoard(). The getNewBoard() function creates a blank game board data structure that has only empty spaces and the four starting tiles. getBoardCopy() creates a blank game board data structure but then copies all of the positions in the board parameter with a nested loop. The AI uses the getBoardCopy() function so it can make changes to the game board copy without changing the real game board. This technique was also used by the Tic-Tac-Toe program in Chapter 10.
125. def getBoardCopy(board):
126. # Make a duplicate of the board list and return it.
127. boardCopy = getNewBoard()
128.
129. for x in range(WIDTH):
130. for y in range(HEIGHT):
131. boardCopy[x][y] = board[x][y]
132.
133. return boardCopy
A call to getNewBoard() sets up boardCopy as a fresh game board data structure. Then the two nested for loops copy each of the 64 tiles from board to the duplicate board data structure in boardCopy.
The isOnCorner() function returns True if the coordinates are on a corner space at coordinates (0, 0), (7, 0), (0, 7), or (7, 7):
135. def isOnCorner(x, y):
136. # Return True if the position is in one of the four corners.
137. return (x == 0 or x == WIDTH - 1) and (y == 0 or y == HEIGHT - 1)
Otherwise, isOnCorner() returns False. We’ll use this function later for the AI.
The getPlayerMove() function is called to let the player enter the coordinates of their next move (and check whether the move is valid). The player can also enter hints to turn hints mode on (if it is off) or off (if it is on). Finally, the player can enter quit to quit the game.
139. def getPlayerMove(board, playerTile):
140. # Let the player enter their move.
141. # Return the move as [x, y] (or return the strings 'hints' or
'quit').
142. DIGITS1TO8 = '1 2 3 4 5 6 7 8'.split()
The DIGITS1TO8 constant variable is the list ['1', '2', '3', '4', '5', '6', '7', '8']. The getPlayerMove() function uses DIGITS1TO8 a couple times, and this constant is more readable than the full list value. You can’t use the isdigit() method because that would allow 0 and 9 to be entered, which are not valid coordinates on the 8×8 board.
The while loop keeps looping until the player types in a valid move:
143. while True:
144. print('Enter your move, "quit" to end the game, or "hints" to
toggle hints.')
145. move = input().lower()
146. if move == 'quit' or move == 'hints':
147. return move
Line 146 checks whether the player wants to quit or toggle hints mode, and line 147 returns the string 'quit' or 'hints', respectively. The lower() method is called on the string returned by input() so the player can type HINTS or Quit and still have the command understood.
The code that called getPlayerMove() will handle what to do if the player wants to quit or toggle hints mode. If the player enters coordinates to move on, the if statement on line 149 checks whether the move is valid:
149. if len(move) == 2 and move[0] in DIGITS1TO8 and move[1] in
DIGITS1TO8:
150. x = int(move[0]) - 1
151. y = int(move[1]) - 1
152. if isValidMove(board, playerTile, x, y) == False:
153. continue
154. else:
155. break
The game expects that the player has entered the x- and y-coordinates of their move as two numbers without anything between them. Line 149 first checks that the size of the string the player typed in is 2. After that, it also checks that both move[0] (the first character in the string) and move[1] (the second character in the string) are strings that exist in DIGITS1TO8.
Remember that the game board data structures have indexes from 0 to 7, not 1 to 8. The code prints 1 to 8 when the board is displayed in drawBoard() because nonprogrammers are used to numbers beginning at 1 instead of 0. So to convert the strings in move[0] and move[1] to integers, lines 150 and 151 subtract 1 from x and y.
Even if the player has entered a correct move, the code needs to check that the move is allowed by the rules of Reversegam. This is done by the isValidMove() function, which is passed the game board data structure, the player’s tile, and the x- and y-coordinates of the move.
If isValidMove() returns False, line 153 continue statement executes. The execution then goes back to the beginning of the while loop and asks the player for a valid move again. Otherwise, the player did enter a valid move, and the execution needs to break out of the while loop.
If the if statement’s condition on line 149 was False, then the player didn’t enter a valid move. Lines 157 and 158 instruct them on how to correctly enter moves:
156. else:
157. print('That is not a valid move. Enter the column (1-8) and
then the row (1-8).')
158. print('For example, 81 will move on the top-right corner.')
Afterward, the execution moves back to the while statement on line 143, because line 158 is not only the last line in the else block but also the last line in the while block. The while loop will keep looping until the player enters a valid move. If the player enters x- and y-coordinates, line 160 will execute:
160. return [x, y]
Finally, if line 160 executes, getPlayerMove() returns a two-item list with the x- and y-coordinates of the player’s valid move.
The getComputerMove() function is where the AI algorithm is implemented:
162. def getComputerMove(board, computerTile):
163. # Given a board and the computer's tile, determine where to
164. # move and return that move as an [x, y] list.
165. possibleMoves = getValidMoves(board, computerTile)
Normally you use the results from getValidMoves() for hints mode, which will print . on the board to show the player all the potential moves they can make. But if getValidMoves() is called with the computer AI’s tile (in computerTile), it will also find all the possible moves that the computer can make. The AI will select the best move from this list.
First, the random.shuffle() function will randomize the order of moves in the possibleMoves list:
166. random.shuffle(possibleMoves) # Randomize the order of the moves.
We want to shuffle the possibleMoves list because it will make the AI less predictable; otherwise, the player could just memorize the moves needed to win because the computer’s responses would always be the same. Let’s look at the algorithm.
Corner moves are a good idea in Reversegam because once a tile has been placed on a corner, it can never be flipped over. Line 169 loops through every move in possibleMoves. If any of them is on the corner, the program will return that space as the computer’s move:
168. # Always go for a corner if available.
169. for x, y in possibleMoves:
170. if isOnCorner(x, y):
171. return [x, y]
Since possibleMoves is a list of two-item lists, we’ll use multiple assignment in the for loop to set x and y. If possibleMoves contains multiple corner moves, the first one is always used. But since possibleMoves was shuffled on line 166, which corner move is first in the list is random.
If there are no corner moves, the program will loop through the entire list of possible moves and find out which results in the highest score. Then bestMove is set to the highest-scoring move the code has found so far, and bestScore is set to the best move’s score. This is repeated until the highest-scoring possible move is found.
173. # Find the highest-scoring move possible.
174. bestScore = -1
175. for x, y in possibleMoves:
176. boardCopy = getBoardCopy(board)
177. makeMove(boardCopy, computerTile, x, y)
178. score = getScoreOfBoard(boardCopy)[computerTile]
179. if score > bestScore:
180. bestMove = [x, y]
181. bestScore = score
182. return bestMove
Line 174 first sets bestScore to -1 so that the first move the code checks will be set to the first bestMove. This guarantees that bestMove is set to one of the moves from possibleMoves when it returns.
On line 175, the for loop sets x and y to every move in possibleMoves. Before simulating a move, line 176 makes a duplicate game board data structure by calling getBoardCopy(). You’ll want a copy you can modify without changing the real game board data structure stored in the board variable.
Then line 177 calls makeMove(), passing the duplicate board (stored in boardCopy) instead of the real board. This will simulate what would happen on the real board if that move were made. The makeMove() function will handle placing the computer’s tile and flipping the player’s tiles on the duplicate board.
Line 178 calls getScoreOfBoard() with the duplicate board, which returns a dictionary where the keys are 'X' and 'O', and the values are the scores. When the code in the loop finds a move that scores higher than bestScore, lines 179 to 181 will store that move and score as the new values in bestMove and bestScore. After possibleMoves has been fully iterated through, bestMove is returned.
For example, say that getScoreOfBoard() returns the dictionary {'X':22, 'O':8} and computerTile is 'X'. Then getScoreOfBoard(boardCopy)[computerTile] would evaluate to {'X':22, 'O':8}['X'], which would then evaluate to 22. If 22 is larger than bestScore, bestScore is set to 22, and bestMove is set to the current x and y values.
By the time this for loop is finished, you can be sure that bestScore is the highest possible score a move can get, and that move is stored in bestMove.
Even though the code always chooses the first in the list of these tied moves, the choice appears random because the list order was shuffled on line 166. This ensures that the AI won’t be predictable when there’s more than one best move.
The showPoints() function calls the getScoreOfBoard() function and then prints the player’s and computer’s scores:
184. def printScore(board, playerTile, computerTile):
185. scores = getScoreOfBoard(board)
186. print('You: %s points. Computer: %s points.' % (scores[playerTile],
scores[computerTile]))
Remember that getScoreOfBoard() returns a dictionary with the keys 'X' and 'O' and values of the scores for the X and O players.
That’s all the functions for the Reversegam game. The code in the playGame() function implements the actual game and calls these functions as needed.
The playGame() function calls the previous functions we’ve written to play a single game:
188. def playGame(playerTile, computerTile):
189. showHints = False
190. turn = whoGoesFirst()
191. print('The ' + turn + ' will go first.')
192.
193. # Clear the board and place starting pieces.
194. board = getNewBoard()
195. board[3][3] = 'X'
196. board[3][4] = 'O'
197. board[4][3] = 'O'
198. board[4][4] = 'X'
The playGame() function is passed 'X' or 'O' strings for playerTile and computerTile. The player to go first is determined by line 190. The turn variable contains the string 'computer' or 'player' to keep track of whose turn it is. Line 194 creates a blank board data structure, while lines 195 to 198 set up the initial four tiles on the board. The game is now ready to begin.
Before getting the player’s or computer’s turn, we need to check whether it is even possible for either of them to move. If not, then the game is at a stalemate and should end. (If only one side has no valid moves, the turn skips to the other player.)
200. while True:
201. playerValidMoves = getValidMoves(board, playerTile)
202. computerValidMoves = getValidMoves(board, computerTile)
203.
204. if playerValidMoves == [] and computerValidMoves == []:
205. return board # No one can move, so end the game.
Line 200 is the main loop for running the player’s and computer’s turns. As long as this loop keeps looping, the game will continue. But before running these turns, lines 201 and 202 check whether either side can make a move by getting a list of valid moves. If both of these lists are empty, then neither player can make a move. Line 205 exits the playGame() function by returning the final board, ending the game.
If the game is not in a stalemate, the program determines whether it is the player’s turn by checking whether turn is set to the string 'player':
207. elif turn == 'player': # Player's turn
208. if playerValidMoves != []:
209. if showHints:
210. validMovesBoard = getBoardWithValidMoves(board,
playerTile)
211. drawBoard(validMovesBoard)
212. else:
213. drawBoard(board)
214. printScore(board, playerTile, computerTile)
Line 207 begins an elif block containing the code that runs if it is the player’s turn. (The elif block that starts on line 227 contains the code for the computer’s turn.)
All of this code will run only if the player has a valid move, which line 208 determines by checking that playerValidMoves is not empty. We display the board on the screen by calling drawBoard() on line 211 or 213.
If hints mode is on (that is, showHints is True), then the board data structure should display . on every valid space the player could move, which is accomplished with the getBoardWithValidMoves() function. It is passed a game board data structure and returns a copy that also contains periods (.). Line 211 passes this board to the drawBoard() function.
If hints mode is off, then line 213 passes board to drawBoard() instead.
After printing the game board to the player, you also want to print the current score by calling printScore() on line 214.
Next, the player needs to enter their move. The getPlayerMove() function handles this, and its return value is a two-item list of the x- and y-coordinates of the player’s move:
216. move = getPlayerMove(board, playerTile)
When we defined getPlayerMove(), we already made sure that the player’s move is valid.
The getPlayerMove() function may have returned the strings 'quit' or 'hints' instead of a move on the board. Lines 217 to 222 handle these cases:
217. if move == 'quit':
218. print('Thanks for playing!')
219. sys.exit() # Terminate the program.
220. elif move == 'hints':
221. showHints = not showHints
222. continue
223. else:
224. makeMove(board, playerTile, move[0], move[1])
225. turn = 'computer'
If the player entered quit for their move, then getPlayerMove() would return the string 'quit'. In that case, line 219 calls sys.exit() to terminate the program.
If the player entered hints for their move, then getPlayerMove() would return the string 'hints'. In that case, you want to turn hints mode on (if it was off) or off (if it was on).
The showHints = not showHints assignment statement on line 221 handles both of these cases, because not False evaluates to True and not True evaluates to False. Then the continue statement moves the execution to the start of the loop (turn has not changed, so it will still be the player’s turn).
Otherwise, if the player didn’t quit or toggle hints mode, line 224 calls makeMove() to make the player’s move on the board.
Finally, line 225 sets turn to 'computer'. The flow of execution skips the else block and reaches the end of the while block, so execution jumps back to the while statement on line 200. This time, however, it will be the computer’s turn.
If the turn variable contains the string 'computer', then the code for the computer’s turn will run. It is similar to the code for the player’s turn, with a few changes:
227. elif turn == 'computer': # Computer's turn
228. if computerValidMoves != []:
229. drawBoard(board)
230. printScore(board, playerTile, computerTile)
231.
232. input('Press Enter to see the computer\'s move.')
233. move = getComputerMove(board, computerTile)
234. makeMove(board, computerTile, move[0], move[1])
After printing the board with drawBoard(), the program also prints the current score with a call to showPoints() on line 230.
Line 232 calls input() to pause the script so the player can look at the board. This is much like how input() was used to pause the Jokes program in Chapter 4. Instead of using a print() call to print a string before a call to input(), you can do the same thing by passing the string to print to input().
After the player has looked at the board and pressed ENTER, line 233 calls getComputerMove() to get the x- and y-coordinates of the computer’s next move. These coordinates are stored in variables x and y using multiple assignment.
Finally, x and y, along with the game board data structure and the computer’s tile, are passed to the makeMove() function. This places the computer’s tile on the game board in board to reflect the computer’s move. Line 233 call to getComputerMove() got the computer’s move (and stored it in variables x and y). The call to makeMove() on line 234 makes the move on the board.
Next, line 235 sets the turn variable to 'player':
235. turn = 'player'
There is no more code in the while block after line 235, so the execution loops back to the while statement on line 200.
That’s all the functions we’ll make for Reversegam. Starting at line 239, the main part of the program runs a game by calling playGame(), but it also displays the final score and asks the player whether they want to play again:
239. print('Welcome to Reversegam!')
240.
241. playerTile, computerTile = enterPlayerTile()
The program starts by welcoming the player on line 239 and asking them whether they want to be X or O. Line 241 uses the multiple assignment trick to set playerTile and computerTile to the two values returned by enterPlayerTile().
The while loop on line 243 runs each game:
243. while True:
244. finalBoard = playGame(playerTile, computerTile)
245.
246. # Display the final score.
247. drawBoard(finalBoard)
248. scores = getScoreOfBoard(finalBoard)
249. print('X scored %s points. O scored %s points.' % (scores['X'],
scores['O']))
250. if scores[playerTile] > scores[computerTile]:
251. print('You beat the computer by %s points! Congratulations!' %
(scores[playerTile] - scores[computerTile]))
252. elif scores[playerTile] < scores[computerTile]:
253. print('You lost. The computer beat you by %s points.' %
(scores[computerTile] - scores[playerTile]))
254. else:
255. print('The game was a tie!')
It begins by calling playGame(). This function call does not return until the game is finished. The board data structure returned by playGame() will be passed to getScoreOfBoard() to count the X and O tiles to determine the final score. Line 249 displays this final score.
If there are more of the player’s tiles than the computer’s, line 251 congratulates the player for winning. If the computer won, line 253 tells the player that they lost. Otherwise, line 255 tells the player the game was a tie.
After the game is finished, the player is asked whether they want to play again:
257. print('Do you want to play again? (yes or no)')
258. if not input().lower().startswith('y'):
259. break
If the player does not type a reply that begins with the letter y, such as yes or YES or Y, then the condition on line 258 evaluates to True, and line 259 breaks out of the while loop that started on line 243, which ends the game. Otherwise, this while loop naturally loops, and playGame() is called again to begin the next game.
The Reversegam AI may seem almost unbeatable, but this isn’t because the computer is smarter than we are; it’s just much faster! The strategy it follows is simple: move on the corner if you can, and otherwise make the move that will flip over the most tiles. A human could do that, but it would be time-consuming to figure out how many tiles would be flipped for every possible valid move. For the computer, calculating this number is simple.
This game is similar to Sonar Treasure Hunt because it makes use of a grid for a board. It is also like the Tic-Tac-Toe game because there’s an AI that plans out the best move for the computer to make. This chapter introduced only one new concept: that empty lists, blank strings, and the integer 0 all evaluate to False in the context of a condition. Other than that, this game used programming concepts you already knew!
In Chapter 16, you’ll learn how to make AIs play computer games against each other.