Tic Tac Toe (Python)

From LiteratePrograms

Other implementations: C++ | Python

This is a simple implementation of the "tic tac toe" game in Python using a brute-force complete minimax algorithm.

After the usual imports, we have a utility function that's used in the algorithm:

<<tictactoe.py>>=
import operator, sys, random, time
def allEqual(list):
    """returns True if all the elements in a list are equal, or if the list is empty."""
    return not list or list == [list[0]] * len(list)

This function tests if all elements in a list are equal. We need this to test the winning conditions.

Next, we have a few constants to enhance readability:

<<tictactoe.py>>=
Empty = ' '
Player_X = 'x'
Player_O = 'o'

In C/C++ I would probably have used enums to code the state of a position on the board (or encoded it in the bits of an integer), but in Python encoding them as strings seems most logical. It makes debugging a little easier and the output code is a one-liner that way.

Now, next we have a class that represents the current state of the game. This class actually contains all of the TicTacToe-specific "business-logic", so it should be possible to replace it with a different class for different games (if they're not too complex for the algorithm).

<<tictactoe.py>>=
class Board:
    """This class represents a tic tac toe board state."""
    def __init__(self):
        """Initialize all members."""
        self.pieces = [Empty]*9
        self.field_names = '123456789'

The board is actually stored as a list of 9 strings, carrying the values Empty for an empty square or Player_X/Player_O for one of the players. I thought about using a two-dimensional array, but that really would have made the algorithm more complex. So, the board actually looks like this:

                |                  |
self.pieces[0]  |  self.pieces[1]  |  self.pieces[2]
                |                  |
----------------------------------------------------
                |                  |
self.pieces[3]  |  self.pieces[4]  |  self.pieces[5]
                |                  |
----------------------------------------------------
                |                  |
self.pieces[6]  |  self.pieces[7]  |  self.pieces[8]
                |                  |

The "field_names"-String is only used to give "names" to each of the squares on the field, so they can be mapped to user inputs. Replace it with "789456123" if you want a Numeric-Keyboard-Style input, or "qweasdzxc" if you'd like to enter your moves on the QWERTY-Keys.

The next is a minimalistic output-function:

<<tictactoe.py>>=
    def output(self):
        """Display the board on screen."""
        for line in [self.pieces[0:3], self.pieces[3:6], self.pieces[6:9]]:
            print ' '.join(line)

This function determines if one of the players has won the game. As everybody knows, a player has won if she has three of her own pieces in a row, vertical, horizontal or diagonal; The array 'winning_rows' stores the indices for each of these 8 winning-rows, and the function checks each of these in a loop:

<<tictactoe.py>>=
    def winner(self):
        """Determine if one player has won the game. Returns Player_X, Player_O or None"""
        winning_rows = [[0,1,2],[3,4,5],[6,7,8], # vertical
                        [0,3,6],[1,4,7],[2,5,8], # horizontal
                        [0,4,8],[2,4,6]]         # diagonal
        for row in winning_rows:
            if self.pieces[row[0]] != Empty and allEqual([self.pieces[i] for i in row]):
                return self.pieces[row[0]]

This function tells the players what moves are legal at the current board position. For tic-tac-toe, that's simply the positions on the board with no player on it. Note: For tic-tac-toe, this simply returns a list of indices into the pieces-array. For a different game, it could well return something like ["a2-a3", "a2-a4", "b2-b3", ...] or anything else that encodes the legal moves.

<<tictactoe.py>>=
    def getValidMoves(self):
        """Returns a list of valid moves. A move can be passed to getMoveName to 
        retrieve a human-readable name or to makeMove/undoMove to play it."""
        return [pos for pos in range(9) if self.pieces[pos] == Empty]

This function tests if the game as all over yet. The order of the functions may seem confusing, but I don't like functions calling other functions that are declared further below (although that's no problem in Python, so feel free to move it around).

<<tictactoe.py>>=
    def gameOver(self):
        """Returns true if one player has won or if there are no valid moves left."""
        return self.winner() or not self.getValidMoves()

Now, as getValidMoves only returned opaque Move-Things, we need to give outside-callers the ability to do something with these moves. (Note: This is one of the points where a strict type-system actually would increase readability, I think!)

<<tictactoe.py>>=
    def getMoveName(self, move):
        """Returns a human-readable name for a move"""
        return self.field_names[move]
    def makeMove(self, move, player):
        """Plays a move. Note: this doesn't check if the move is legal!"""
        self.pieces[move] = player
    def undoMove(self, move):
        """Undoes a move/removes a piece of the board."""
        self.makeMove(move, Empty)

Now, we have the board type, let's implement the human player:

<<tictactoe.py>>=
def humanPlayer(board, player):
    """Function for the human player"""
    board.output()
    possible_moves = dict([(board.getMoveName(move), move) for move in board.getValidMoves()])
    move = raw_input("Enter your move (%s): " % (', '.join(sorted(possible_moves))))
    while move not in possible_moves:
        print "Sorry, '%s' is not a valid move. Please try again." % move
        move = raw_input("Enter your move (%s): " % (', '.join(sorted(possible_moves))))
    board.makeMove(possible_moves[move], player)

And now, the actual minimax-algorithm (I implemented it using local functions; In my mind, keeping the global namespace tidy is a good thing, and by the way, it saves some arguments to the sub-functions as they have access to local variables):

<<tictactoe.py>>=
def computerPlayer(board, player):
    """Function for the computer player"""
    t0 = time.time()
    board.output()
    opponent = { Player_O : Player_X, Player_X : Player_O }

The idea of the algorithm is simple: go through all possible moves recursively, and find those that ensure the best possible outcome no matter what the opponent does. So, the first thing we need is a function that tells us if what happened is good or bad:

<<tictactoe.py>>=
    def judge(winner):
        if winner == player:
            return +1
        if winner == None:
            return 0
        return -1

If I won -> good (+1), if nobody won, still ok (0), otherwise -> bad (-1).

Now, the next sub-function (recursively) evaluates a move, and checks if the players can win the game. After it's done, it restores the Board state to it's previous state, so I can use the same Board object all the time. In the end, it returns +1, 0 or -1, just as the "judge"-function above, with the same meanings:

<<tictactoe.py>>=
    def evaluateMove(move, p=player):
        try:
            board.makeMove(move, p)
            if board.gameOver():
                return judge(board.winner())
            outcomes = (evaluateMove(next_move, opponent[p]) for next_move in board.getValidMoves())

The last line calculates all outcomes of all the next possible moves after the move to be checked. I'm using Python's-Generator-Feature here, so "outcomes" will be calculated lazily, and I can skip in the middle if I see that move's bad anyway. (Replace it with "outcomes = [evaluateMove(next_move, opponent[p]) for next_move in board.getValidMoves()]" to see the difference!)

The next few lines find out if this is a good or bad. The idea is simple: If it's my turn, I can't decide which move comes next (it's the opponent's turn then), so I have to expect the worst; Thus, I'll return the worst outcome outcome I've calculated above.

<<tictactoe.py>>=
            if p == player:
                #return min(outcomes)
                min_element = 1
                for o in outcomes:
                    if o == -1:
                        return o
                    min_element = min(o,min_element)
                return min_element
            else:
                #return max(outcomes)
                max_element = -1
                for o in outcomes:
                    if o == +1:
                        return o
                    max_element = max(o,max_element)
                return max_element

Note that the commented "return min(outcomes)"/"return max(outcomes)" would have done exactly the same thing, but with one major diadvantage: they'll evaluate the whole list. As I know the list can only contain the values +1/0/-1, I can skip evaluating it if I find a -1 (if I'm searching for the minimum) or a +1 (if I want the maximum).

Remember that I promised that the function restored the original board state? Well, here it does, no matter what happens:

<<tictactoe.py>>=
        finally:
            board.undoMove(move)

So, now we have a function that tells us if a move is good or bad. The only thing left to do is to call it for every available move and pick out the best one available (I use shuffle so the computer won't play the same game every time):

<<tictactoe.py>>=
    moves = [(move, evaluateMove(move)) for move in board.getValidMoves()]
    random.shuffle(moves)
    moves.sort(key = lambda (move, winner): winner)
    print "computer move: %0.3f ms" % ((time.time()-t0)*1000)
    print moves
    board.makeMove(moves[-1][0], player)

So much for the players, here's the main function that actually calls them:

<<tictactoe.py>>=
def game():
    """The game function"""
    b = Board()
    turn = 1
    while True:
        print "%i. turn" % turn
        humanPlayer(b, Player_O)
        if b.gameOver(): 
            break
        computerPlayer(b, Player_X)
        if b.gameOver(): 
            break
        turn += 1

I guess a higher-order-function guru could have used the fact that "humanPlayer" and "computerPlayer" have the same signature to make this loop a lot shorter, but I really don't know how to do that without getting unreadable.

<<tictactoe.py>>=
    b.output()
    if b.winner():
        print 'Player "%s" wins' % b.winner()
    else:
        print 'Game over'
if __name__ == "__main__":
    game()

Note: If run this by double-clicking on windows, it'll just close the window when the game is over. Insert a raw_input()-statement in the end if you want to avoid this.

Problems with Python 3000

There are many differences between Python 3000 and Python 2.x. These differences makes you not able to play that game.

At first you need to replace every print-statement by a print()-function. This is quite simple, because you just have to put brackets around the printed text.

The raw_input()-function must be replaced by a input()-function.

A very special and disturbing change to Python 3000 concerning to that case: lambda-expressions do not get tuples in old ways. For example: the Python 2.x code says lambda (x,y): y. Python 3000 doesn't work with pattern-matching in lambda-expressions. You have to join tuple-elements to one simple variable. So lambda x_y: x_y[1] would return the wanted output.

And: you do not need a raw_input() or in correct syntax input() at the bottom line of the code to execute the program on windows.

Download code