<jupyter_start><jupyter_text>Adversarial Search in GamesThe following code is based on the code provided by the book [Artificial Intelligence: A Modern Approach](http://aima.cs.berkeley.edu/) in http://aima.cs.berkeley.edu/python/readme.html.  Abstract class for modeling a game<jupyter_code>class Game:
    """A game is similar to a problem, but it has a utility for each
    state and a terminal test instead of a path cost and a goal
    test. To create a game, subclass this class and implement
    legal_moves, make_move, utility, and terminal_test. You may
    override display and successors or you can inherit their default
    methods. You will also need to set the .initial attribute to the
    initial state; this can be done in the constructor."""

    def legal_moves(self, state):
        "Return a list of the allowable moves at this point."
        abstract

    def make_move(self, move, state):
        "Return the state that results from making a move from a state."
        abstract

    def utility(self, state, player):
        "Return the value of this final state to player."
        abstract

    def terminal_test(self, state):
        "Return True if this is a final state for the game."
        return not self.legal_moves(state)

    def to_move(self, state):
        "Return the player whose move it is in this state."
        return state.to_move

    def display(self, state):
        "Print or otherwise display the state."
        print state

    def successors(self, state):
        "Return a list of legal (move, state) pairs."
        return [(move, self.make_move(move, state))
                for move in self.legal_moves(state)]

    def __repr__(self):
        return '<%s>' % self.__class__.__name__<jupyter_output><empty_output><jupyter_text>Minimax with alpha-beta pruning implementationSome auxiliary functions<jupyter_code>def argmin(seq, fn):
    """Return an element with lowest fn(seq[i]) score; tie goes to first one.
    >>> argmin(['one', 'to', 'three'], len)
    'to'
    """
    best = seq[0]; best_score = fn(best)
    for x in seq:
        x_score = fn(x)
        if x_score < best_score:
            best, best_score = x, x_score
    return best

def argmax(seq, fn):
    """Return an element with highest fn(seq[i]) score; tie goes to first one.
    >>> argmax(['one', 'to', 'three'], len)
    'three'
    """
    return argmin(seq, lambda x: -fn(x))<jupyter_output><empty_output><jupyter_text>Minimax search function<jupyter_code>def alphabeta_search(state, game, d=float('inf'), cutoff_test=None, eval_fn=None):
    """Search game to determine best action; use alpha-beta pruning.
    This version cuts off search and uses an evaluation function."""

    player = game.to_move(state)

    def max_value(state, alpha, beta, depth):
        if cutoff_test(state, depth):
            return eval_fn(state, player)
        v = -float('inf')
        for (a, s) in game.successors(state):
            v = max(v, min_value(s, alpha, beta, depth+1))
            if v >= beta:
                return v
            alpha = max(alpha, v)
        return v

    def min_value(state, alpha, beta, depth):
        if cutoff_test(state, depth):
            return eval_fn(state, player)
        v = float('inf')
        for (a, s) in game.successors(state):
            v = min(v, max_value(s, alpha, beta, depth+1))
            if v <= alpha:
                return v
            beta = min(beta, v)
        return v

    # Body of alphabeta_search starts here:
    # The default test cuts off at depth d or at a terminal state
    cutoff_test = (cutoff_test or
                   (lambda state,depth: depth>d or game.terminal_test(state)))
    eval_fn = eval_fn or (lambda state, player: game.utility(state, player))
    action, state = argmax(game.successors(state),
                           lambda ((a, s)): min_value(s, -float('inf'), float('inf'), 0))
    return action<jupyter_output><empty_output><jupyter_text>Generic playing agentsAuxiliary functions<jupyter_code>def num_or_str(x):
    """The argument is a string; convert to a number if possible, or strip it.
    >>> num_or_str('42')
    42
    >>> num_or_str(' 42x ')
    '42x'
    """
    if isnumber(x): return x
    try:
        return int(x)
    except ValueError:
        try:
            return float(x)
        except ValueError:
                return str(x).strip()

def isnumber(x):
    "Is x a number? We say it is if it has a __int__ method."
    return hasattr(x, '__int__')<jupyter_output><empty_output><jupyter_text>A player that makes a query for each move<jupyter_code>def query_player(game, state):
    "Make a move by querying standard input."
    game.display(state)
    return num_or_str(raw_input('Your move? '))<jupyter_output><empty_output><jupyter_text>A player that chooses a move at random<jupyter_code>import random

def random_player(game, state):
    "A player that chooses a legal move at random."
    return random.choice(game.legal_moves(state))<jupyter_output><empty_output><jupyter_text>A player that uses minimimax alpha-beta search<jupyter_code>def alphabeta_player(game, state):
    return alphabeta_search(state, game)<jupyter_output><empty_output><jupyter_text>A function that receives a list of players and call each player alternatively<jupyter_code>def play_game(game, *players):
    "Play an n-person, move-alternating game."
    state = game.initial
    while True:
        for player in players:
            move = player(game, state)
            state = game.make_move(move, state)
            if game.terminal_test(state):
                return game.utility(state, 0)<jupyter_output><empty_output><jupyter_text>The last-stone gameThe game is played with a heap of stones. Each player take alternatively a number $n$ of stones ($1 \le n \le 3$). The player that takes the last stone wins.An auxiliary class to define light-weight objects<jupyter_code>class Struct:
    """Create an instance with argument=value slots.
    This is for making a lightweight object whose class doesn't matter."""
    def __init__(self, **entries):
        self.__dict__.update(entries)

    def __cmp__(self, other):
        if isinstance(other, Struct):
            return cmp(self.__dict__, other.__dict__)
        else:
            return cmp(self.__dict__, other)

    def __repr__(self):
        args = ['%s=%s' % (k, repr(v)) for (k, v) in vars(self).items()]
        return 'Struct(%s)' % ', '.join(args)<jupyter_output><empty_output><jupyter_text>The following class models the last-stone game:<jupyter_code>class LastStone(Game):
    def __init__(self, stones):
        self.initial = Struct(to_move=0, heap = stones)

    def legal_moves(self, state):
        "Return a list of the allowable moves at this point."
        return range(1, min(3, state.heap) + 1)

    def make_move(self, move, state):
        "Return the state that results from making a move from a state."
        return Struct(to_move = 1 - state.to_move,
                      heap = state.heap - move)
        
    def utility(self, state, player):
        "Return the value of this final state to player."
        if state.to_move == player:
            return -1
        else:
            return 1

    def terminal_test(self, state):
        "Return True if this is a final state for the game."
        return not self.legal_moves(state)

    def to_move(self, state):
        "Return the player whose move it is in this state."
        return state.to_move

    def display(self, state):
        "Print or otherwise display the state."
        print state

    def successors(self, state):
        "Return a list of legal (move, state) pairs."
        return [(move, self.make_move(move, state))
                for move in self.legal_moves(state)]<jupyter_output><empty_output><jupyter_text>An interactive game against the computer, can you win?<jupyter_code>play_game(LastStone(10), query_player, alphabeta_player)<jupyter_output>Struct(to_move=0, heap=10)<jupyter_text>1. Design an evaluation function for the last-stone game and test it<jupyter_code>def eval_fn(state, player):
    ### Your code here ###
    return 0
    
def smart_player(game, state):
    return alphabeta_search(state, game, d = 2, eval_fn = eval_fn)


result = play_game(LastStone(10), smart_player, alphabeta_player)
if result == 1:
    print "Smart player wins"
else:
    print "Smart player loses"<jupyter_output>Smart player loses<jupyter_text>The 3-heaps last-stone gameIn this version of the game, there are three heaps instead of 1. In each turn, a player takes $n$ stones ($1 \le n \le k$) from one of the heaps. The player that takes the last stone wins. 2. Define a class that models the 3-heaps last-stone game<jupyter_code>class LastStone3Heaps(Game):
    def __init__(self, k, heap1, heap2, heap3):
        pass

    def legal_moves(self, state):
        "Return a list of the allowable moves at this point."
        pass
    
    def make_move(self, move, state):
        "Return the state that results from making a move from a state."
        pass
    
    def utility(self, state, player):
        "Return the value of this final state to player."
        pass

    def terminal_test(self, state):
        "Return True if this is a final state for the game."
        pass
    
    def to_move(self, state):
        "Return the player whose move it is in this state."
        pass
    
    def display(self, state):
        "Print or otherwise display the state."
        pass
    
    def successors(self, state):
        "Return a list of legal (move, state) pairs."
        pass<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup