"""
 chomp.py

 For a description of the game,
 see http://en.wikipedia.org/wiki/Chomp

  $ python chomp.py

   p a a a a
   a a a a a
   a a a a a

  player random chooses (1, 4) 

   p a a a a
   a a a a  
   a a a a  

  player computer chooses (2, 0) 

   p a a a a
   a a a a  
            
  player random chooses (1, 0) 

   p a a a a

  player computer chooses (0, 1) 

   p        

 Done.

 (And since the random player must take the poison p,
  the computer player wins.)

 Jim Mahoney | cs.marlboro.edu | MIT License | Apr 2013
"""

from random import randrange

# --- game representation ------------------------------

# board      p a a a a a a
#            a a a a a a a
#            a a a a a a a   height        top left is 'p'oison
#            a a a a a a a                 others are  'a'pples
#            a a a a a a a
#
#                width
#
# On each turn, a player 'chomp's a rectangle below and to the right
# of a given (row,col) spot, with 0 <= col < width and 0 <= row < height
#
# The board is a matrix of 'p' and 'a' characters.
# After each move, the appropriate 'a' characters are replaced with ' '.
#
# The game is represented as a list of (row,col) moves,
# and the board is calculated when needed ... which means
# that this implementation is *not* a particularly fast one;
# it's written to be (relatively) simple to understand.
#
# Since every 'a' on the board is a possible move, the branching
# ratio (the number of possible moves at each point in the tree
# of possible positions) gets large quickly as the board size
# increases, as does the search depth needed to fully search
# the tree to the end of the game. 

width = 5    # of board        
height = 3   # of board

def initial_board():
    """ Return initial board[i][j] , 'p' top left, 'a' everywhere else """
    board = [None]*height
    board[0] = ['p'] + ['a'] * (width - 1)   # i.e. ['p', 'a', 'a', ...]
    for i in range(1, height):
        board[i] = ['a'] * width             # i.e. ['a', 'a', 'a', ...]
    return board

def game2board(game):
    """ Here a 'game' is a list of moves. Do them, and return a board. """
    board = initial_board()
    for (row,col) in game:               # each move is a coord on the board
        for c in xrange(col, width):
            for r in xrange(row, height):
                board[r][c] = ' '
    return board

def game2string(game):
    """ Return string representation of board from list of moves (i.e. game) """
    board = game2board(game)
    result = ""
    for row in board:
        result += '   ' + ' '.join(row) + '\n'
    return result[:-1]                          # omit last newline

def get_random_move(game):
    """ Return a random legal move """
    # The implementation here is slow and simple:
    # keep on picking random spots on the board until
    # we happen to pick one that's a legal move.
    board = game2board(game)
    while True:
        row = randrange(0, height)
        col = randrange(0, width)
        if board[row][col] == 'a':
            return (row,col)
    
# --- game specific routines needed by template ------------------

def do_move(game, move):
    """ Modify game by applying move. (Return nothing). """
    # A game is a list of moves; append this one.
    game.append(move)

def undo_move(game, move):
    """ Modify game by reversing move. (Return nothing). """
    # A game is a list of moves; remove the last move made
    game.pop()

def moves(game):
    """ Return list of moves to consider. """
    # For best alphabeta pruning, put likely candidates first.
    # Any cell with an 'a' is a possible move.
    board = game2board(game)
    result = []
    for col in xrange(width):
        for row in xrange(height):
            if board[row][col] == 'a':
                result.append((row,col))
    return result

def finished(game):
    """ Return True if game is done. """
    # The game is done if there are no 'a' characters on the board.
    board = game2board(game)
    for col in xrange(width):
        for row in xrange(height):
            if board[row][col] == 'a':
                return False
    return True

def evaluate(game):
    """ Return value of game position from the point of view the
        player whose turn it is to move. value > 0 for winning,
        < 0 for losing, larger (smaller) is better (worse)."""
    # The value here may be clear (if the game is over),
    # or an approximate heuristic value at the maximum search depth.
    game_value = width*height - len(game)   # positive
    if finished(game):        # For this game, when it's over, 
        return -game_value    # player whose turn it is to move has lost.
    else:
        return None           # Not end of game: no evaluation yet.

def new_game():
    """ Here a game is a list of moves, so a new game is an empty list """
    return []

# This is the max number of moves, i.e. search the whole tree.
search_depth = height * width   

# --- generic game infrastructure from template ---------------------

inf = float('inf')

def alphabeta(game, depth, alpha, beta):
    """ Return (value, move) """
    if depth <= 0 or finished(game):
        return (evaluate(game), None)
    best_move = None
    for move in moves(game):
        do_move(game, move)
        (value, junk) = alphabeta(game, depth-1, -beta, -alpha)
        value = -value        # This is the min/max flip of perspective.
        undo_move(game, move)
        if value >= beta:
            return (value, best_move)
        if value > alpha:
            (alpha, best_move) = (value, move)
    return (alpha, best_move)

def other(player):
    """ Return other player
        >>> other('computer')
        'random'
        >>> other('random')
        'computer'
    """
    if player == 'random':
        return 'computer'
    else:
        return 'random'

def main():
    game = new_game()
    player = 'random'
    print
    while not finished(game):
        print game2string(game)
        print
        if player == 'random':
            move = get_random_move(game)
        elif player == 'computer':
            (value, move) = alphabeta(game, search_depth, -inf, inf)
        print " player %s chooses %s " % (player, str(move))
        print
        do_move(game, move)
        player = other(player)
    print game2string(game)
    print
    print "Done."


if __name__ == "__main__":
    import doctest
    doctest.testmod()
    main()