tictacfoe.py

#!/usr/bin/env python
#-*- coding:utf-8 -*-
import psyco
psyco.full() # Speed-up

""" Tic-tac-toe opponent using a recursive search.

Uses a recursive search and picks
the moves that give the most likely results of a win. 

The board is represented like this:
board = [[ 0, 0, 0],
         [ 0, 0, 0],
         [ 0, 0, 0]]

where a 1 means X and a 2 means O. 0 means an unmarked square."""

################################
## Display logic
################################

def cell_to_string(cell):
    """
        Converts numbers to symbols. 0 -> ' ', 1 -> 'x', 2 -> 'o'
    """
    return [' ', "×", "○"][cell]
    
def display(board):
    """
        Displays a board to the screen in a nice, human-readable form
        0 = space, 1 = X, 2 = O
    """
    print "    A   B   C"
    for count, row in enumerate(board):
        letters = [count] + [cell_to_string(s) for s in row]
        # Letters now contains a list like [2, 'x', ' ', 'o']
        
        print "%2d  %s │ %s │ %s " % tuple(letters)
        if count != 2:
            print "   ───┼───┼───"

################################
## AI Logic
################################

def filled(board):
    """
        Returns true if the board is completely filled
    """
    return min(min(row) for row in board) != 0

def valid_moves(board):
    """
        Returns a list of valid moves still left on the board
        valid_moves ( [[1,1,0], [2,0,1], [2,2,2]] ) -> [ (0, 2), (1, 1)]
    """
    for rv, row in enumerate(board):
        for cv, cell in enumerate(row):
            if cell == 0:
                yield rv, cv

def victor(board):
    """
        Returns the winner of the game. 0 means a tie.
    """
    # Horizontal wins
    for row in board:
        items = set(row)
        if len(items) == 1 and 0 not in items: # One unique item that's not 0
            return items.pop()
    
    # Vertical wins
    columns = [[row[col] for row in board] for col in xrange( len(board) )]
    for col in columns:
        items = set(col)
        if len(items) == 1 and 0 not in items:
            return items.pop()
    
    # Diagonal line (Topleft to bottom right)
    # Assumes a square board with 3 in a row
    if board[0][0] == board[1][1] == board[2][2] and board[0][0] is not 0:
        return board[0][0]
    
    # Diagonal line (Top right to bottom left)
    # Assumes a square board with 3 in a row
    if board[0][2] == board[1][1] == board[2][0] and board[0][2] is not 0:
        return board[0][2]
    
    
    return 0 # No match
    
def consider(board, move, player):
    """
        Considers all the boards until a victory is found, then
        returns the board.
    """
    alternate_player = 2 if player==1 else 1 # Swap players
    r,c = move # Get the row and the colum of the move we want to make
    
    # Make our move
    board[r][c] = player # Make our move
    
    # If somebody won or the board is filled:
    v = victor(board)
    if v is not 0 or filled(board):
        yield v # Can't do anything more.
    
    # The board is not filled.
    for new_move in valid_moves(board):
        # Finally, consider what happens here.
        for winner in consider(board, new_move, alternate_player):
            yield winner
    # Undo our first move
    board[r][c] = 0
    
    
def best_move(board, player):
    """
        Calculates the best move a player can play
        
        Tries to minimize the percentage of games the opposite player will win.
        Returns a move that gives the least percentage of possible
        games the opponent can win.
        
        This is not always the best strategy.
    """
    opponent = 1 if player == 2 else 2 # Who are we competing agaist?
    
    possibilities = [] # Holds tuples of probabilities and moves
    
    for move in valid_moves(board):
        outcomes = [0,0,0]
        for winner in consider(board, move, player):
            outcomes[winner] += 1
        percent = float(outcomes[opponent]) / sum(outcomes)
        possibilities.append((percent, move))
    
    # Now that we have a list of probabilities and moves, sort it so
    # the minimum possibility will come first
    possibilities.sort()
    
    # Then, return the first move
    return possibilities[0][1]
    

################################
## Game logic
################################

def ai_take_turn(board, player):
    """
        Asks the AI to take a turn.
    """
    print "Wait..."
    row, col = best_move(board, player) # Where should I go?
    board[row][col] = player # Make my move

def user_take_turn(board, player):
    """
        Asks the user to take a turn.
        
        User will input a choice like A2 or c 3
    """
    cell = raw_input('Enter a cell: ').upper().strip()
    cell = [char for char in cell if char is not ' ']
    while len(cell) != 2 or not cell[0].isalpha() or not cell[1].isdigit():
        print "Please enter a cell like this: A2"
        cell = raw_input('Enter a cell: ').upper().strip()
        cell = [char for char in cell if char is not ' ']
    
    rows = ['A','B','C']
    row, col = int(cell[1]), rows.index(cell[0])
    
    if (row, col) in valid_moves(board):
        board[row][col] = player
    else:
        print "That space is already taken."
        user_take_turn(board, player)
    
def new_game(first_player):
    """
        Makes a new game, alternating player and CPU.
    """
    board = [[0] * 3 for row in xrange(3)] # Starting board
    move_count = 0
    functions = [user_take_turn, ai_take_turn]
    display(board) # First time
    
    while victor(board) is 0 and not filled(board):
        # Until finished:
        function_to_use = (move_count + first_player) % len(functions)
        # Pick an altertaning function every time
        print "Move %d" % move_count
        # Make the move
        functions[function_to_use](board, function_to_use+1)

        display(board)
        
        move_count += 1
        
    # We're done!
    choices = ['Tie', 'Player', 'Computer']
    print "Winner: %s" % choices[victor(board)]
    
if __name__ == '__main__':
    """ Runs the program """
    print "Hello! Welcome to the tic-tac-toe solver."
    keep_going = 1
    while keep_going:
        user_choice = raw_input("Which should go first? 1: Computer, 2: Player? ")
        while not user_choice.isdigit() and user_choice <1 and user_choice >2:
            print "That's not a number!"
            user_choice = raw_input("Which should go first? 1: Computer, 2: Player? ")
        new_game(int(user_choice))
        keep_going = int(raw_input("Play again? 0: quit, 1: continue? "))