# Tic Tac Toe game that uses Minimax algorithm to pick the best move

I written a Tic Tac Toe game, which allows you to play against another person or the AI (The AI can also play against itself, which should always result in a tie).

The AI uses the Minimax algorithm to pick the best move. I'm not very experienced with Python, so I'm wondering if my code uses any bad practices and styles. Any feedback is welcome.

TicTacToe.py

from TicTacToeUtil import *

PLAYER_HUMAN = 'H'
GAME_CONTINUE = 0
done = GAME_CONTINUE
move = -1
clear = "\n" * 100

player_type = {'X': '', 'O': ''}
player_turn = ' '
game_board = range(9)
game_board_legend = range(9)

#Generate game board and legend
for i in game_board:
game_board[i] = ' '
game_board_legend[i] = str(i)

#Setup the game and retrieve game settings
while player_type['X'] != 'H' and player_type['X'] != 'A':
player_type['X'] = raw_input("Is player X human or AI?\nEnter \'H\' for human, \'A\' for AI: ")
player_type['X'] = player_type['X'].upper()

while player_type['O'] != 'H' and player_type['O'] != 'A':
player_type['O'] = raw_input("Is player O human or AI?\nEnter \'H\' for human, \'A\' for AI: ")
player_type['O'] = player_type['O'].upper()

while player_turn != 'X' and player_turn != 'O':
player_turn = raw_input("Who should go first?\nEnter \'X\' for player X, \'O\' for player O: ")
player_turn = player_turn.upper()

#Clear the screen
print clear

while done == GAME_CONTINUE:

#Human gets a turn
if(player_type[player_turn] == PLAYER_HUMAN):

print "Your turn (Player " + player_turn + ")"
print_board(game_board)
print "\n Legend:\n"
print_board(game_board_legend)

move = get_user_move(game_board)

game_board[move] = player_turn
done = GameState.check_win(game_board)

if done != GAME_CONTINUE:
break

#Computer plays a turn
else:
print "Waiting for " + player_turn + "\'s turn"
game_tree = generate_game_tree(game_board, player_turn)
move = generate_best_move(game_tree, player_turn)
game_board[int(move)] = player_turn
done = GameState.check_win(game_board)

if done != GAME_CONTINUE:
break

#Switch to the next player
player_turn = 'X' if player_turn == 'O' else 'O'
print clear

#Print final results
print_board(game_board)

if done == 'X':
print "The winner is player X!"
elif done == 'O':
print "The winner is player O!"
else:
print "It's a tie!"


TicTacToeUtil.py

class GameState:
def __init__(self, game_board, move, player):
self.game_board = list(game_board)
self.move = move
self.children = []
self.game_end = False

def generate_children(self, player):
moves = [i for i, x in enumerate(self.game_board) if x == ' ']

for move in moves:
child = GameState(self.game_board, move, player)
child.game_board[move] = player
child.set_winner()

if child.game_end == False:
child.generate_children('X' if player == 'O' else 'O')
self.children.append(child)
else:
self.children.append(child)

def set_winner(self):
#X is given a positive score, O is given a negative score
winner = GameState.check_win(self.game_board)
if winner == 'X':
self.score = 1
self.game_end = True
elif winner == 'O':
self.score = -1
self.game_end = True
elif winner == -1:
self.score = 0
self.game_end = True
else:
self.score = 0
self.game_end = False

@staticmethod
def check_win(game_board):
winning_moves = [[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]]
for moves in winning_moves:
if game_board[moves[0]] == game_board[moves[1]] and game_board[moves[1]] == game_board[moves[2]] and game_board[moves[0]] != ' ':
return game_board[moves[0]]

if ' ' not in game_board:
return -1

return 0

def get_user_move(game_board):
while True:
move = raw_input("Enter 0-8: ")

if not move.isdigit():
print "Input is not a number. Please enter an integer between 0-8"
continue
else:
move = int(move)

if not 0 <= move <= 8:
print "Input not between 0-8. Please enter an integer between 0-8"
elif game_board[move] != ' ':
print "Move is already taken. Pick another move"
else:
break

return move

def print_board(b):
print '|' + b[0] + '|' + b[1] + '|' + b[2] + '|\n'
print '|' + b[3] + '|' + b[4] + '|' + b[5] + '|\n'
print '|' + b[6] + '|' + b[7] + '|' + b[8] + '|\n'

def generate_game_tree(game_board, current_player):
root = GameState(game_board, ' ', ' ')
root.generate_children(current_player)
return root

def generate_best_move(game_tree, player):
best_move = game_tree.move

if player == 'X':
best_score = -999
else:
best_score = 999

if game_tree.game_end == True:
return best_move

for game_state in game_tree.children:
if game_state.game_end == True:
score = game_state.score
else:
score = minimax(game_state, 'X' if player == 'O' else 'O')

if player == 'X':
if score > best_score:
best_move = game_state.move
best_score = score
else:
if score < best_score:
best_move = game_state.move
best_score = score

return best_move

def minimax(game_tree, player):
score_list = []

if game_tree.game_end == True:
return game_tree.score

for game_state in game_tree.children:
if game_state.game_end == True:
score_list.append(game_state.score)
else:
game_state.score = minimax(game_state, 'X' if player == 'O' else 'O')

#We don't need to generate the whole game tree, just return
#the branch that will result in a win
if player == 'X' and game_state.score == 1:
return game_state.score
if player == 'O' and game_state.score == -1:
return game_state.score

score_list.append(game_state.score)

if player == 'X':
return max(score_list)

else:
return min(score_list)

• Welcome to Code Review! This is a good question and I'm sure you will get helpful reviews! Nov 5, 2014 at 19:43

## TicTacToe.py

from TicTacToeUtil import *


Per the style guide,

Wildcard imports (from <module> import *) should be avoided, as they make it unclear which names are present in the namespace, confusing both readers and many automated tools.

In this case that would be a bit unwieldy:

from TicTacToeUtil import (GameState,
get_user_move,
...,
...)


which suggests that some of this could be restructured (see below).

Also, four spaces should be used for indentation, rather than two, and line lengths should be under 80 characters (you could use multiline strings for your input prompts, for example - see Avoiding Python multiline string indentation for formatting).

You have an odd mix of constants and variables (good work on the naming convention, although clear should be CLEAR) at the top of the file, and it runs straight into the body of the script. It is not good practice to have code running directly in a script; you should wrap it in a function (or more than one) and guard the entry point behind if __name__ == '__main__':.

As I've just mentioned naming conventions, more from PEP-0008:

Modules should have short, all-lowercase names. Underscores can be used in the module name if it improves readability.

So this should be tic_tac_toe.py and the other should be tic_tac_toe_util.py.

Rather than simple inline comments, consider providing proper docstrings (this will also be easier and clearer if you split the code into functions).

The control flow seems a bit wonky. For example:

while done == GAME_CONTINUE:

...

if done != GAME_CONTINUE:
break


One of those is redundant!

if(player_type[player_turn] == PLAYER_HUMAN):


is not style guide-compliant, this would generally be written:

if player_type[player_turn] == PLAYER_HUMAN:


Explicit string concatenation 'foo' + 'bar' is generally discouraged, use string formatting, so e.g.:

print "Your turn (Player " + player_turn + ")"


could be:

print "Your turn (Player {0})".format(player_turn)


You could make the code more generic by treating the two players equally. If you adopted a more OOP approach, you could have a simple list of Player objects, each of which implemented a method make_move(board), then simply switch back and forth:

while True:
players[0].make_move(game_board)
if GameState.check_win(game_board):
break
players = players[::-1]


Now after the loop, you know players[0] won.

Here's a suggested overall structure:

def create_player(symbol):
"""Takes user input on player type and returns a Player."""

def pick_player(symbols):
"""Allow user to choose one of the symbols."""

def play_game(game_board, players):
"""Contains the main game loop."""

def main():
"""Overall control of the game.

Create two Players  with symbols 'X' and 'O' and a GameBoard,
pick_player for first and play_game.

"""

if __name__ == '__main__':
main()


## TicTacToeUtil.py

So how to implement the above suggestions? The OOP you have currently employed is a bit awkward, with GameState, a class containing a mix of concerns, alongside several functions that I think should probably be encapsulated as object behaviour. I would suggest something like:

class GameBoard(object): # all classes should be new-style
"""Handles the current and future states of a tic-tac-toe board.

Encompasses GameState, some of get_user_move, generate_game_tree
and print_board.

"""

class Player(object):
"""Metaclass for the next two classes.

All Players will have a symbol attribute and a make_move method
(which will just 'raise NotImplementedError' here).

"""

class HumanPlayer(Player):
"""Handles all the user input stuff.

Encompasses the rest of get_user_move.

"""

class ComputerPlayer(Player):
"""Handles AI stuff.

Encompasses generate_best_move and minimax.

"""


Note that moving those functions into classes makes the import from the top of the answer easy:

from tic_tac_toe_util import ComputerPlayer, GameBoard, HumanPlayer


get_user_move would generally be implemented with a try, rather than str.isdigit; look at e.g. Asking the user for input until they give a valid response.

print_board could also be neater, for example using zip, slicing and str.join:

for row in zip(b[::3], b[1::3], b[2::3]):
print '|'.join(row)


Or, as above, use str.format.