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

Question

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)

Answer 1

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.