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

TicTacToe.py

from TicTacToeUtil import *

Per the style guide,


Wildcard imports (from 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.

StackExchange Code Review Q#69010, answer score: 8