aima/games.py
def alphabeta_search(state, game, d=4, 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)
        v = -infinity
        for a in game.actions(state):
            v = max(v, min_value(game.result(state, a),
                                 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)
        v = infinity
        for a in game.actions(state):
            v = min(v, max_value(game.result(state, a),
                                 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: game.utility(state, player))
    return argmax(game.actions(state),
                  lambda a: min_value(game.result(state, a),
                                      -infinity, infinity, 0))
def alphabeta_search(state, game, d=4, 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)
        v = -infinity
        for a in game.actions(state):
            v = max(v, min_value(game.result(state, a),
                                 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)
        v = infinity
        for a in game.actions(state):
            v = min(v, max_value(game.result(state, a),
                                 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: game.utility(state, player))
    return argmax(game.actions(state),
                  lambda a: min_value(game.result(state, a),
                                      -infinity, infinity, 0))
def alphabeta_search ( state , game , d = 4 , cutoff_test = None , eval_fn = None ) : player = game . to_move ( state ) def max_value ( state , alpha , beta , depth ) : if cutoff_test ( state , depth ) : return eval_fn ( state ) v = - infinity for a in game . actions ( state ) : v = max ( v , min_value ( game . result ( state , a ) , 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 ) v = infinity for a in game . actions ( state ) : v = min ( v , max_value ( game . result ( state , a ) , 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 : game . utility ( state , player ) ) return argmax ( game . actions ( state ) , lambda a : min_value ( game . result ( state , a ) , - infinity , infinity , 0 ) )
Search game to determine best action; use alpha-beta pruning.
    This version cuts off search and uses an evaluation function.
Search game to determine best action ; use alpha - beta pruning . This version cuts off search and uses an evaluation function .