# Minimax Tic-Tac-Toe implementation

Notes:

• I know \ are against PEP8; they are for readibility
• I created this working through a tutorial
• I forgot to add blank lines, so it may be a little squished
''' Tic-Tac-Toe Minimax Program by Peter'''

#Tutorial found at: http://giocc.com/concise-implementation-of-minimax-through-higher-order-functions.html'''
class GameState:
def __init__(self,board):
self.board = board
self.winning_combos = [[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]]
def is_gameover(self):
'''returns if a game_state has been won or filled up'''
if self.board.count('X') + self.board.count('O') == 9:
return True
for combo in self.winning_combos:
if (self.board[combo] == 'X' and self.board[combo] == 'X' and self.board[combo] == 'X') or \
(self.board[combo] == 'O' and self.board[combo] == 'O' and self.board[combo] == 'O'):
return True
return False
def get_possible_moves(self):
'''returns all possible squares to place a character'''
squares = []
for index, square in enumerate(self.board):
if square != 'X' and square != 'O':
squares.append(index)
return squares
def get_next_state(self, move, our_turn):
'''returns the gamestate with the move filled in'''
copy = self.board[:]
if our_turn:
copy[move] = 'X'
else:
copy[move] = 'O'
return GameState(copy)
'''Named evals instead of eval to respect the eval function. http://stackoverflow.com/questions/9383740/what-does-pythons-eval-do'''
def evals(game_state):
'''score a game_state from the computers point of view, 1 = win, 0 = tie, -1 = lose'''
for combo in game_state.winning_combos:
if game_state.board[combo] == 'X' and game_state.board[combo] == 'X' and game_state.board[combo] == 'X':
return 1
elif game_state.board[combo] == 'O' and game_state.board[combo] == 'O' and game_state.board[combo] == 'O':
return -1
else:
return 0

'''max and min will call on each other recusively, until a terminal state'''
def max_play(game_state):
'''if the game is over returns score, otherwise calls min_play on it's childen (possible moves from the state) and returns the maximum'''
if game_state.is_gameover():
return evals(game_state)
return max(map(lambda move: min_play(game_state.get_next_state(move, True)), game_state.get_possible_moves()))
def min_play(game_state):
'''if the game is over returns score, otherwise calls max_play on it's childen (possible moves from the state) and returns the minimum'''
if game_state.is_gameover():
return evals(game_state)
return min(map(lambda move: max_play(game_state.get_next_state(move, False)), game_state.get_possible_moves()))

def minimax(game_state):
'''returns the max of mapping the (move, score) tuple to the possible move using  of the tuple the (score)'''
return max(map(lambda move: (move, min_play(game_state.get_next_state(move, True))), game_state.get_possible_moves()), key = lambda x: x)

def pretty_print(board):
'''prints a list by 3 chars, joined by spaces'''
print(' '.join(board[:3]))
print(' '.join(board[3:6]))
print(' '.join(board[6:9]))

'''starting board, assuming it is X's turn.'''
start_board = '_ _ _ ' + '_ O _ ' + '_ _ _'

'''Interpreting and printing start board'''
start_game_state = GameState(start_board.split(' '))
pretty_print(start_game_state.board)
'''Finding best possible move and score'''
move, score = minimax(start_game_state)
'''Displaying move and outcome'''
if score == 0:
word = 'TIE'
elif score == 1:
word = 'WIN'
else:
word = 'LOSS, who rigged the board?!?'
print('X should go at index #',move, 'Which will always result in a ' + word)
start_game_state.board[move] = 'X'
pretty_print(start_game_state.board)

• BTW \ is not against PEP8, it's just that using () are normally cleaner. Dec 9, 2016 at 13:28

1. start_board is defined as a string with spaces, then only used once with the spaces split. This means that you can completely remove the variable and do start_game_state = GameState(['_','_','_','O','_','_','_']), which the would be better formatted over multiple lines to make the layout clear:

GameState(['_','_','_',
'_','O','_',
'_','_','_'
])

2. The functions min_play, max_play, and minmax are near duplicates of eachother and should be merged into one with a second argument.

3. All three of those functions could be made clearer with a generator expression/list comprehension

4. Your comments should be written using the comment operator rather than the multi-line string operator, which should be used only for multiline comments and docstrings

5. The function get_next_state could be simplified using a ternary operator.

6. Get_possible_moves could also be simplified with a list comprehension.

7. Instead of checking if all nine squares are filled in is_gameover, you could check if no squares are free, which is faster as it only does one pass through the loop.

8. lambda x:x should be replaced with operator.itemgetter(1), which is faster.

9. is_gameover and evals are near duplicates of eachother and should be merged

Fixed code:

#Tic-Tac-Toe Minimax Program by Peter

#Tutorial found at: http://giocc.com/concise-implementation-of-minimax-through-higher-order-functions.html
from operator import itemgetter

class GameState:
def __init__(self,board):
self.board = board
self.winning_combos = [[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]]
def get_winner(self):
'''returns None if the game is still going, otherwise scores from computer's point of view (1=win, 0=tie, -1=win)'''
if self.board.count('_') == 0:
return 0
for combo in self.winning_combos:
if (self.board[combo] == 'X' and self.board[combo] == 'X' and self.board[combo] == 'X'):
return 1
elif self.board[combo] == 'O' and self.board[combo] == 'O' and self.board[combo] == 'O':
return 0
return None
def get_possible_moves(self):
'''returns all possible squares to place a character'''
return [index for index, square in enumerate(self.board) if square == '_']
def get_next_state(self, move, our_turn):
'''returns the gamestate with the move filled in'''
copy = self.board[:]
copy[move] = 'X' if our_turn else 'O'
return GameState(copy)

def play(game_state, our_turn):
'''if the game is over returns (None, score), otherwise recurses to find the best move and returns it and the score.'''
score = game_state.get_winner()
if score != None:
return None, score
moves = ((move, play(game_state.get_next_state(move, our_turn), not our_turn)) for move in game_state.get_possible_moves())
return (max if our_turn else min)(moves, key=itemgetter(1))

def pretty_print(board):
'''prints a list by 3 chars, joined by spaces'''
print(' '.join(board[:3]))
print(' '.join(board[3:6]))
print(' '.join(board[6:9]))

#Interpreting and printing board
start_game_state = GameState(['_','_','_',
'_','O','_',
'_','_','_'
])
pretty_print(start_game_state.board)
#Finding best possible move and score
move, score = play(start_game_state, True)
#Displaying move and outcome
if score == 0:
word = 'TIE'
elif score == 1:
word = 'WIN'
else:
word = 'LOSS, who rigged the board?!?'
print('X should go at index #',move, 'Which will always result in a ' + word)
start_game_state.board[move] = 'X'
pretty_print(start_game_state.board)

• Can you break this line down? ((move, play(game_state.get_next_state(move, our_turn)), not our_turn) for move in game_state.get_possible_moves()))
– PAS
Dec 12, 2016 at 15:19
• Also, is that line the same as: for move in game_state.get_possible_moves: moves.append(move, minimax(game_state.get_next_state(move, our_turn), not our_turn))
– PAS
Dec 12, 2016 at 15:28
• This code does not work :(
– PAS
Dec 12, 2016 at 17:05
• @PAS Fixed, some parens were slightly out of position. Dec 12, 2016 at 20:11
• @PAS mostly. The function I call is called play, not minmax, the argument to moves.append in your code needs to be parenthesized, game_state.get_possible_moves() is a function and thus needs parents, and my code doesn't compute the move until it is needed, whereas yours computes all of them at once. Comprehensions are generally more pythonic than for loops, though. Dec 12, 2016 at 20:15