Chapter 10 - Othello

Source Code

othello.py

1. # Othello
3. import random
4. import sys
6. def drawBoard(board):
7.     # This function prints out the board that it was passed. Returns None.
8.     hline = '  +---+---+---+---+---+---+---+---+'
9.     vline = '  |   |   |   |   |   |   |   |   |'
11.     print '    1   2   3   4   5   6   7   8'
12.     print hline
13.     for y in range(8):
14.         print vline
15.         print y+1,
16.         for x in range(8):
17.             print '| %s' % (board[x][y]),
18.         print '|'
19.         print vline
20.         print hline
23. def resetBoard(board):
24.     # Blanks out the board it is passed, except for the original starting position.
25.     for x in range(8):
26.         for y in range(8):
27.             board[x][y] = ' '
29.     # Starting pieces:
30.     board[3][3] = 'X'
31.     board[3][4] = 'O'
32.     board[4][3] = 'O'
33.     board[4][4] = 'X'
34.     return board
37. def getNewBoard():
38.     # Creates a brand new, blank board data structure.
39.     board = []
40.     for i in range(8):
41.         board.append([' '] * 8)
43.     return board
46. def isValidMove(board, letter, startx, starty):
47.     # Returns True if the move to space x,y is a valid one.
48.     if not isOnBoard(startx, starty) or board[startx][starty] != ' ':
49.         return False
51.     directions = [[0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1], [-1, 0], [-1, 1]]
53.     if letter == 'X':
54.         otherLetter = 'O'
55.     else:
56.         otherLetter = 'X'
58.     for d in directions:
59.         DX = d[0]
60.         DY = d[1]
61.         x, y = startx, starty
62.         x += DX
63.         y += DY
64.         if isOnBoard(x, y):
65.             if board[x][y] == otherLetter:
66.                 # There is a piece belonging to the other player next to our piece.
67.                 x += DX
68.                 y += DY
69.                 if not isOnBoard(x, y):
70.                     continue
71.                 while board[x][y] == otherLetter:
72.                     x += DX
73.                     y += DY
74.                     if not isOnBoard(x, y): # double loop break
75.                         break
76.                 if not isOnBoard(x, y):
77.                     continue
78.                 if board[x][y] == letter:
79.                     return True
80.     return False
83. def isOnBoard(x, y):
84.     # Returns True if the coordinates are located on the board.
85.     return x >= 0 and x <= 7 and y >= 0 and y <=7
88. def getBoardWithValidMoves(board, letter):
89.     # Returns a new board with . marking the valid moves the given player can make.
90.     dupeBoard = getBoardCopy(board)
92.     for x, y in getValidMoves(dupeBoard, letter):
93.         dupeBoard[x][y] = '.'
94.     return dupeBoard
97. def getValidMoves(board, letter):
98.     # Returns a list of [x,y] lists of valid moves for the given player on the given board.
99.     validMoves = []
101.     for x in range(8):
102.         for y in range(8):
103.             if isValidMove(board, letter, x, y):
104.                 validMoves.append([x, y])
105.     return validMoves
108. def getScoreOfBoard(board):
109.     # Determine the score. Returns a dictionary with keys 'X' and 'O'.
110.     xscore = 0
111.     oscore = 0
112.     for x in range(8):
113.         for y in range(8):
114.             if board[x][y] == 'X':
115.                 xscore += 1
116.             if board[x][y] == 'O':
117.                 oscore += 1
118.     return {'X':xscore, 'O':oscore}
121. def enterPlayerLetter():
122.     # Let's the player type which letter they want to be.
123.     # Returns a list with the player's letter as the first item, and the computer's letter as the second.
124.     letter = ''
125.     while not (letter == 'X' or letter == 'O'):
126.         print 'Do you want to be X or O?'
127.         letter = raw_input().upper()
129.     # the first element in the tuple is the player's letter, the second is the computer's letter.
130.     if letter == 'X':
131.         return ['X', 'O']
132.     else:
133.         return ['O', 'X']
136. def whoGoesFirst():
137.     # Randomly choose the player who goes first.
138.     if random.randint(0, 1) == 0:
139.         return 'computer'
140.     else:
141.         return 'player'
144. def playAgain():
145.     # This function returns True if the player wants to play again, otherwise it returns False.
146.     print 'Do you want to play again? (yes or no)'
147.     return raw_input().lower().startswith('y')
150. def makeMove(board, letter, startx, starty):
151.     # Place the letter on the board at startx, starty, and flip any of the opponent's pieces.
152.     # Returns False if this is an invalid move, returns True if it is valid.
154.     if not isValidMove(board, letter, startx, starty):
155.         return False
157.     board[startx][starty] = letter
159.     directions = [[0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1], [-1, 0], [-1, 1]]
161.     if letter == 'X':
162.         otherLetter = 'O'
163.     else:
164.         otherLetter = 'X'
166.     for d in directions:
167.         DX = d[0]
168.         DY = d[1]
169.         x, y = startx, starty
170.         x += DX
171.         y += DY
172.         if isOnBoard(x, y):
173.             if board[x][y] == otherLetter:
174.                 # There is a piece belonging to the other player next to our piece.
175.                 x += DX
176.                 y += DY
177.                 if not isOnBoard(x, y):
178.                     continue
179.                 while board[x][y] == otherLetter:
180.                     x += DX
181.                     y += DY
182.                     if not isOnBoard(x, y): # break, then continue
183.                         break
184.                 if not isOnBoard(x, y):
185.                     continue
186.                 if board[x][y] == letter:
187.                     # There are pieces to flip over. Go in the reverse direction.
188.                     while True:
189.                         x -= DX
190.                         y -= DY
191.                         if x == startx and y == starty:
192.                             break
193.                         board[x][y] = letter
194.     return True
197. def getBoardCopy(board):
198.     # Make a duplicate of the board list and return the duplicate.
199.     dupeBoard = getNewBoard()
201.     for x in range(8):
202.         for y in range(8):
203.             dupeBoard[x][y] = board[x][y]
205.     return dupeBoard
208. def isOnCorner(x, y):
209.     # Returns True if the position is in one of the four corners.
210.     return (x == 0 and y == 0) or (x == 7 and y == 0) or (x == 0 and y == 7) or (x == 7 and y == 7)
213. def isSpaceFree(board, x, y):
214.     # Return true if the passed move is free on the passed board.
215.     return board[x][y] == ' '
218. def getPlayerMove(board, playerLetter):
219.     # Let the player type in their move.
220.     # Returns the move as [x, y] (or returns the strings 'hints' or 'quits')
221.     digits1to8 = '1 2 3 4 5 6 7 8'.split()
222.     move = ''
223.     while True:
224.         print 'Enter your move, or type quit to end the game, or hints to turn off/on hints.'
225.         move = raw_input()
226.         if move.lower() == 'quit':
227.             return 'quit'
228.         if move.lower() == 'hints':
229.             return 'hints'
231.         if len(move) == 2 and move[0] in digits1to8 and move[1] in digits1to8:
232.             x = int(move[0]) - 1
233.             y = int(move[1]) - 1
234.             if not isValidMove(board, playerLetter, x, y):
235.                 continue
236.             else:
237.                 break
238.         else:
239.             print 'That is not a valid move. Type the x digit (1-8), then the y digit (1-8).'
240.             print 'For example, 81 will be the top-right corner.'    
242.     return [x, y]
245. def getComputerMove(board, computerLetter):
246.     # Given a board and the computer's letter, determine where to
247.     # move and return that move as a [x, y] list.
248.     if computerLetter == 'X':
249.         playerLetter = 'O'
250.     else:
251.         playerLetter = 'X'
253.     possibleMoves = getValidMoves(board, computerLetter)
255.     # create a list of moves that are in the corners, and
256.     # always go for a corner if available.
257.     cornerMoves = []
258.     for move in possibleMoves:
259.         if isOnCorner(move[0], move[1]):
260.             cornerMoves.append(move)
261.     if len(cornerMoves) > 0:
262.         return random.choice(getHighestScoringMoves(board, computerLetter, cornerMoves))
264.     # From the list of highest scoring moves, choose one at random.
265.     return random.choice(getHighestScoringMoves(board, computerLetter, possibleMoves))
268. def getHighestScoringMoves(board, letter, moves):
269.     # Returns a list of the highest scoring moves from the list of moves.
270.     # For example, if out of the list of six moves, the highest scoring move gives
271.     # five more points, but there are three different moves that give five more points,
272.     # then return a list with those three moves.
273.     if len(moves) == 1:
274.         return moves
276.     currentScore = getScoreOfBoard(board)[letter]
278.     bestScore = -1
279.     allScores = []
281.     for i in range(len(moves)):
282.         dupeBoard = getBoardCopy(board)
283.         makeMove(dupeBoard, letter, moves[i][0], moves[i][1])
284.         scoreIncrease = getScoreOfBoard(dupeBoard)[letter] - currentScore
286.         allScores.append(scoreIncrease)
287.         if scoreIncrease > bestScore:
288.             bestScore = scoreIncrease
290.     topMoves = []
291.     for i in range(len(allScores)):
292.         if allScores[i] == bestScore:
293.             topMoves.append(moves[i])
295.     return topMoves
298. def isBoardDone(board, letter):
299.     # Return True if the player with the given letter can make a move on the board. Otherwise return False.
300.     if getValidMoves(board, letter) == []:
301.         return True
303.     for x in range(8):
304.         for y in range(8):
305.             if board[x][y] == ' ':
306.                 return False
308.     return True
311. def showPoints(playerLetter, computerLetter):
312.     # Prints out the current score.
313.     scores = getScoreOfBoard(theBoard)
314.     print 'You have %s points. The computer has %s points.' % (scores[playerLetter], scores[computerLetter])
318. print 'Welcome to Othello!'
320. while True:
321.     # Reset the board and game.
322.     theBoard = getNewBoard()
323.     resetBoard(theBoard)
324.     playerLetter, computerLetter = enterPlayerLetter()
325.     showHints = False
326.     turn = whoGoesFirst()
327.     print 'The ' + turn + ' will go first.'
329.     while True
330.         if turn == 'player':
331.             # Player's turn.
332.             if showHints:
333.                 validMovesBoard = getBoardWithValidMoves(theBoard, playerLetter)
334.                 drawBoard(validMovesBoard)
335.             else:
336.                 drawBoard(theBoard)
337.             showPoints(playerLetter, computerLetter)
338.             move = getPlayerMove(theBoard, playerLetter)
339.             if move == 'quit':
340.                 print 'Thanks for playing!'
341.                 sys.exit() # terminate the program
342.             elif move == 'hints':
343.                 showHints = not showHints
344.                 continue
345.             else:
346.                 x, y = move
347.             makeMove(theBoard, playerLetter, x, y)
349.             if isBoardDone(theBoard, computerLetter): # computerLetter, not playerLetter
350.                 break
351.             else:
352.                 turn = 'computer'
354.         else:
355.             # Computer's turn.
356.             x, y = getComputerMove(theBoard, computerLetter)
357.             drawBoard(theBoard)
358.             showPoints(playerLetter, computerLetter)
359.             raw_input('Press Enter to see the computer\'s move.')
360.             makeMove(theBoard, computerLetter, x, y)
362.             if isBoardDone(theBoard, playerLetter): # playerLetter, not computerLetter
363.                 break
364.             else:
365.                 turn = 'player'
367.     # Display the final score.
368.     scores = getScoreOfBoard(theBoard)
369.     print 'X scored %s points. O scored %s points.' % (scores['X'], scores['O'])
370.     if scores[playerLetter] > scores[computerLetter]:
371.         print 'You beat the computer by %s points! Congratulations!' % (scores[playerLetter] - scores[computerLetter])
372.     elif scores[playerLetter] < scores[computerLetter]:
373.         print 'You lost. The computer beat you by %s points.' % (scores[computerLetter] - scores[playerLetter])
374.     else:
375.         print 'The game was a tie!'
376.     
377.     if not playAgain():
378.         break

Code Explanation

1. # Othello
3. import random
4. import sys

1. def drawBoard(board):
2.     # This function prints out the board that it was passed. Returns None.
3.     hline = '  +---+---+---+---+---+---+---+---+'
4.     vline = '  |   |   |   |   |   |   |   |   |'
6.     print '    1   2   3   4   5   6   7   8'

1.     print hline
2.     for y in range(8):
3.         print vline
4.         print y+1,
5.         for x in range(8):
6.             print '| %s' % (board[x][y]),
7.         print '|'
8.         print vline
9.         print hline

1. def resetBoard(board):
2.     # Blanks out the board it is passed, except for the original starting position.
3.     for x in range(8):
4.         for y in range(8):
5.             board[x][y] = ' '

1.     # Starting pieces:
2.     board[3][3] = 'X'
3.     board[3][4] = 'O'
4.     board[4][3] = 'O'
5.     board[4][4] = 'X'
6.     return board

1. def getNewBoard():
2.     # Creates a brand new, blank board data structure.
3.     board = []
4.     for i in range(8):
5.         board.append([' '] * 8)
7.     return board

1. def isValidMove(board, letter, startx, starty):
2.     # Returns True if the move to space x,y is a valid one.
3.     if not isOnBoard(startx, starty) or board[startx][starty] != ' ':
4.         return False

1.     directions = [[0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1], [-1, 0], [-1, 1]]
3.     if letter == 'X':
4.         otherLetter = 'O'
5.     else:
6.         otherLetter = 'X'

1.     for d in directions:
2.         DX = d[0]
3.         DY = d[1]
4.         x, y = startx, starty
5.         x += DX
6.         y += DY

1.         if isOnBoard(x, y):
2.             if board[x][y] == otherLetter:
3.                 # There is a piece belonging to the other player next to our piece.
4.                 x += DX
5.                 y += DY
6.                 if not isOnBoard(x, y):
7.                     continue

1.                 while board[x][y] == otherLetter:
2.                     x += DX
3.                     y += DY
4.                     if not isOnBoard(x, y): # double loop break
5.                         break

1.                 if not isOnBoard(x, y):
2.                     continue
3.                 if board[x][y] == letter:
4.                     return True
5.     return False

1. def isOnBoard(x, y):
2.     # Returns True if the coordinates are located on the board.
3.     return x >= 0 and x <= 7 and y >= 0 and y <=7

1. def getBoardWithValidMoves(board, letter):
2.     # Returns a new board with . marking the valid moves the given player can make.
3.     dupeBoard = getBoardCopy(board)
5.     for x, y in getValidMoves(dupeBoard, letter):
6.         dupeBoard[x][y] = '.'
7.     return dupeBoard

1. def getValidMoves(board, letter):
2.     # Returns a list of [x,y] lists of valid moves for the given player on the given board.
3.     validMoves = []
5.     for x in range(8):
6.         for y in range(8):
7.             if isValidMove(board, letter, x, y):
8.                 validMoves.append([x, y])
9.     return validMoves

1. def getScoreOfBoard(board):
2.     # Determine the score. Returns a dictionary with keys 'X' and 'O'.
3.     xscore = 0
4.     oscore = 0
5.     for x in range(8):
6.         for y in range(8):

1.             if board[x][y] == 'X':
2.                 xscore += 1
3.             if board[x][y] == 'O':
4.                 oscore += 1
5.     return {'X':xscore, 'O':oscore}

1. def enterPlayerLetter():
2.     # Let's the player type which letter they want to be.
3.     # Returns a list with the player's letter as the first item, and the computer's letter as the second.
4.     letter = ''
5.     while not (letter == 'X' or letter == 'O'):
6.         print 'Do you want to be X or O?'
7.         letter = raw_input().upper()

1.     # the first element in the tuple is the player's letter, the second is the computer's letter.
2.     if letter == 'X':
3.         return ['X', 'O']
4.     else:
5.         return ['O', 'X']

1. def whoGoesFirst():
2.     # Randomly choose the player who goes first.
3.     if random.randint(0, 1) == 0:
4.         return 'computer'
5.     else:
6.         return 'player'

1. def playAgain():
2.     # This function returns True if the player wants to play again, otherwise it returns False.
3.     print 'Do you want to play again? (yes or no)'
4.     return raw_input().lower().startswith('y')

1. def makeMove(board, letter, startx, starty):
2.     # Place the letter on the board at startx, starty, and flip any of the opponent's pieces.
3.     # Returns False if this is an invalid move, returns True if it is valid.
5.     if not isValidMove(board, letter, startx, starty):
6.         return False

1.     board[startx][starty] = letter
3.     directions = [[0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1], [-1, 0], [-1, 1]]
5.     if letter == 'X':
6.         otherLetter = 'O'
7.     else:
8.         otherLetter = 'X'

1.     for d in directions:
2.         DX = d[0]
3.         DY = d[1]
4.         x, y = startx, starty
5.         x += DX
6.         y += DY

1.         if isOnBoard(x, y):
2.             if board[x][y] == otherLetter:
3.                 # There is a piece belonging to the other player next to our piece.
4.                 x += DX
5.                 y += DY

1.                 if not isOnBoard(x, y):
2.                     continue

1.                 while board[x][y] == otherLetter:
2.                     x += DX
3.                     y += DY

1.                     if not isOnBoard(x, y): # break, then continue
2.                         break
3.                 if not isOnBoard(x, y):
4.                     continue

1.                 if board[x][y] == letter:
2.                     # There are pieces to flip over. Go in the reverse direction.
3.                     while True:
4.                         x -= DX
5.                         y -= DY
6.                         if x == startx and y == starty:
7.                             break
8.                         board[x][y] = letter
9.     return True

1. def getBoardCopy(board):
2.     # Make a duplicate of the board list and return the duplicate.
3.     dupeBoard = getNewBoard()
5.     for x in range(8):
6.         for y in range(8):
7.             dupeBoard[x][y] = board[x][y]
9.     return dupeBoard

1. def isOnCorner(x, y):
2.     # Returns True if the position is in one of the four corners.
3.     return (x == 0 and y == 0) or (x == 7 and y == 0) or (x == 0 and y == 7) or (x == 7 and y == 7)

1. def isSpaceFree(board, x, y):
2.     # Return true if the passed move is free on the passed board.
3.     return board[x][y] == ' '

1. def getPlayerMove(board, playerLetter):
2.     # Let the player type in their move.
3.     # Returns the move as [x, y] (or returns the strings 'hints' or 'quits')
4.     digits1to8 = '1 2 3 4 5 6 7 8'.split()
5.     move = ''

1.     while True:
2.         print 'Enter your move, or type quit to end the game, or hints to turn off/on hints.'
3.         move = raw_input()
4.         if move.lower() == 'quit':
5.             return 'quit'
6.         if move.lower() == 'hints':
7.             return 'hints'

1.         if len(move) == 2 and move[0] in digits1to8 and move[1] in digits1to8:
2.             x = int(move[0]) - 1
3.             y = int(move[1]) - 1
4.             if not isValidMove(board, playerLetter, x, y):
5.                 continue
6.             else:
7.                 break

1.         else:
2.             print 'That is not a valid move. Type the x digit (1-8), then the y digit (1-8).'
3.             print 'For example, 81 will be the top-right corner.'    

1.     return [x, y]

1. def getComputerMove(board, computerLetter):
2.     # Given a board and the computer's letter, determine where to
3.     # move and return that move as a [x, y] list.
4.     if computerLetter == 'X':
5.         playerLetter = 'O'
6.     else:
7.         playerLetter = 'X'
9.     possibleMoves = getValidMoves(board, computerLetter)

1.     # create a list of moves that are in the corners, and
2.     # always go for a corner if available.
3.     cornerMoves = []
4.     for move in possibleMoves:
5.         if isOnCorner(move[0], move[1]):
6.             cornerMoves.append(move)
7.     if len(cornerMoves) > 0:
8.         return random.choice(getHighestScoringMoves(board, computerLetter, cornerMoves))

1.     # From the list of highest scoring moves, choose one at random.
2.     return random.choice(getHighestScoringMoves(board, computerLetter, possibleMoves))

1. def getHighestScoringMoves(board, letter, moves):
2.     # Returns a list of the highest scoring moves from the list of moves.
3.     # For example, if out of the list of six moves, the highest scoring move gives
4.     # five more points, but there are three different moves that give five more points,
5.     # then return a list with those three moves.
6.     if len(moves) == 1:
7.         return moves
9.     currentScore = getScoreOfBoard(board)[letter]
11.     bestScore = -1
12.     allScores = []

1.     for i in range(len(moves)):
2.         dupeBoard = getBoardCopy(board)
3.         makeMove(dupeBoard, letter, moves[i][0], moves[i][1])
4.         scoreIncrease = getScoreOfBoard(dupeBoard)[letter] - currentScore
6.         allScores.append(scoreIncrease)
7.         if scoreIncrease > bestScore:
8.             bestScore = scoreIncrease

1.     topMoves = []
2.     for i in range(len(allScores)):
3.         if allScores[i] == bestScore:
4.             topMoves.append(moves[i])

1.     return topMoves

1. def isBoardDone(board, letter):
2.     # Return True if the player with the given letter can make a move on the board. Otherwise return False.
3.     if getValidMoves(board, letter) == []:
4.         return True

1.     for x in range(8):
2.         for y in range(8):
3.             if board[x][y] == ' ':
4.                 return False
6.     return True

1. def showPoints(playerLetter, computerLetter):
2.     # Prints out the current score.
3.     scores = getScoreOfBoard(theBoard)
4.     print 'You have %s points. The computer has %s points.' % (scores[playerLetter], scores[computerLetter])

1. print 'Welcome to Othello!'
3. while True:
4.     # Reset the board and game.
5.     theBoard = getNewBoard()
6.     resetBoard(theBoard)
7.     playerLetter, computerLetter = enterPlayerLetter()
8.     showHints = False
9.     turn = whoGoesFirst()
10.     print 'The ' + turn + ' will go first.'

1.     while True
2.         if turn == 'player':
3.             # Player's turn.
4.             if showHints:
5.                 validMovesBoard = getBoardWithValidMoves(theBoard, playerLetter)
6.                 drawBoard(validMovesBoard)
7.             else:
8.                 drawBoard(theBoard)

1.             showPoints(playerLetter, computerLetter)
2.             move = getPlayerMove(theBoard, playerLetter)

1.             if move == 'quit':
2.                 print 'Thanks for playing!'
3.                 sys.exit() # terminate the program
4.             elif move == 'hints':
5.                 showHints = not showHints
6.                 continue
7.             else:
8.                 x, y = move
9.             makeMove(theBoard, playerLetter, x, y)

1.             if isBoardDone(theBoard, computerLetter): # computerLetter, not playerLetter
2.                 break
3.             else:
4.                 turn = 'computer'

1.         else:
2.             # Computer's turn.
3.             x, y = getComputerMove(theBoard, computerLetter)
4.             drawBoard(theBoard)
5.             showPoints(playerLetter, computerLetter)
6.             raw_input('Press Enter to see the computer\'s move.')
7.             makeMove(theBoard, computerLetter, x, y)

1.             if isBoardDone(theBoard, playerLetter): # playerLetter, not computerLetter
2.                 break
3.             else:
4.                 turn = 'player'

1.     # Display the final score.
2.     scores = getScoreOfBoard(theBoard)
3.     print 'X scored %s points. O scored %s points.' % (scores['X'], scores['O'])
4.     if scores[playerLetter] > scores[computerLetter]:
5.         print 'You beat the computer by %s points! Congratulations!' % (scores[playerLetter] - scores[computerLetter])
6.     elif scores[playerLetter] < scores[computerLetter]:
7.         print 'You lost. The computer beat you by %s points.' % (scores[computerLetter] - scores[playerLetter])
8.     else:
9.         print 'The game was a tie!'

1.     if not playAgain():
2.         break

Things Covered In This Chapter: