"""
 game_engine_template.py

 Fill in the pieces below to implement a specific game.

 The alphabeta search engine is tricky to get right.  The code here
 should work if the evaluate(game) routine provides the value from
 the point of view of the player who's turn it is to move.

 The players here are a randomly moving player alternating with a
 computer alphabeta search player. The game is displayed in text
 between each move.

 This code assumes that 'game' is a data structure or object which can
 be modified by making and unmaking moves.  This allows one copy of
 the game to be used throughout the search tree.

 See the chomp.py file for an example of this template
 being used to implement a simple game.

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

# --- game specific routines needed by template ------------------
#     Edit these to match your particular game.

def game2string(game):
    """ Return a string version of the current game position. """
    return '?'

def get_random_move(game):
    """ Return a randomly chosen legitimate move """
    # What type of data you return will depend on your game representation.
    return '?'

def do_move(game, move):
    """ Modify game by applying move. (Return nothing). """
    # For example, if game is a list of moves; append this move, e.g.
    # game.append(move)
    pass

def undo_move(game, move):
    """ Modify game by reversing move. (Return nothing). """
    # For example, if a game is a list of moves; remove the last, e.g.
    # game.pop()
    pass

def moves(game):
    """ Return list of moves to consider. """
    # For best alphabeta pruning, put likely candidates first.
    return []

def finished(game):
    """ Return True if game is done. """
    return False

def evaluate(game):
    """ Return the 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.
    return 0

def new_game():
    """ Return a new game. """
    # For example, of a game is a list of moves, return an empty list.
    return []

# How many moves ahead your program will search.
# Larger numbers will give a slower, smarter computer player.
# Adjust to match the complexity of your game and move tree.
search_depth = 10

# --- generic game infrastructure from template ---------------------
#     You may not need to edit this.

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            #  the min/max flip of perspective.
        undo_move(game, move)
        if value >= beta:         #  abandon this branch
            return (value, best_move)
        if value > alpha:         #  new best move for this player
            (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()