Source code for easyAI.AI.Negamax

"""
The standard AI algorithm of easyAI is Negamax with alpha-beta pruning
and (optionnally), transposition tables.
"""

import pickle
        
LOWERBOUND, EXACT, UPPERBOUND = -1,0,1
inf = float('infinity')

def negamax(game, depth, origDepth, scoring, alpha=+inf, beta=-inf,
             tt=None):
    """
    This implements Negamax with transposition tables.
    This method is not meant to be used directly. See ``easyAI.Negamax``
    for an example of practical use.
    This function is implemented (almost) acccording to
    http://en.wikipedia.org/wiki/Negamax
    """
    
    alphaOrig = alpha
    
    # Is there a transposition table and is this game in it ?
    lookup = None if (tt is None) else tt.lookup(game)
    
    if lookup != None:
        # The game has been visited in the past
        
        if lookup['depth'] >= depth:
            flag, value = lookup['flag'], lookup['value']
            if flag == EXACT:
                if depth == origDepth:
                    game.ai_move = lookup['move']
                return value
            elif flag == LOWERBOUND:
                alpha = max( alpha, value)
            elif flag == UPPERBOUND:
                beta = min( beta, value)
                
            if alpha >= beta:
                if depth == origDepth:
                    game.ai_move = lookup['move']
                return value
        
        
        
    if (depth == 0) or game.is_over():
        score = scoring(game)
        if score == 0:
            return score
        else:
            return  (score - 0.01*depth*abs(score)/score)
    
    
    if lookup != None:
        # Put the supposedly best move first in the list
        possible_moves = game.possible_moves()
        possible_moves.remove(lookup['move'])
        possible_moves = [lookup['move']] + possible_moves
        
    else:
        
        possible_moves = game.possible_moves()

    
    
    state = game
    best_move = possible_moves[0]
    if depth == origDepth:
        state.ai_move = possible_moves[0]
        
    bestValue = -inf
    unmake_move = hasattr(state, 'unmake_move')
    
    
    for move in possible_moves:
        
        if not unmake_move:
            game = state.copy() # re-initialize move
        
        game.make_move(move)
        game.switch_player()
        
        move_alpha = - negamax(game, depth-1, origDepth, scoring,
                               -beta, -alpha, tt)
        
        if unmake_move:
            game.switch_player()
            game.unmake_move(move)
        
        # bestValue = max( bestValue,  move_alpha )
        if bestValue < move_alpha:
            bestValue = move_alpha
            best_move = move

        if  alpha < move_alpha :
                alpha = move_alpha
                # best_move = move
                if depth == origDepth:
                    state.ai_move = move
                if (alpha >= beta):
                    break

    if tt != None:
        
        assert best_move in possible_moves
        tt.store(game=state, depth=depth, value = bestValue,
                 move= best_move,
                 flag = UPPERBOUND if (bestValue <= alphaOrig) else (
                        LOWERBOUND if (bestValue >= beta) else EXACT))

    return bestValue

        
[docs]class Negamax: """ This implements Negamax on steroids. The following example shows how to setup the AI and play a Connect Four game: >>> from easyAI.games import ConnectFour >>> from easyAI import Negamax, Human_Player, AI_Player >>> scoring = lambda game: -100 if game.lose() else 0 >>> ai_algo = Negamax(8, scoring) # AI will think 8 turns in advance >>> game = ConnectFour([Human_Player(), AI_Player(ai_algo)]) >>> game.play() Parameters ----------- depth: How many moves in advance should the AI think ? (2 moves = 1 complete turn) scoring: A function f(game)-> score. If no scoring is provided and the game object has a ``scoring`` method it ill be used. win_score: Score above which the score means a win. This will be used to speed up computations if provided, but the AI will not differentiate quick defeats from long-fought ones (see next section). tt: A transposition table (a table storing game states and moves) scoring: can be none if the game that the AI will be given has a ``scoring`` method. Notes ----- The score of a given game is given by >>> scoring(current_game) - 0.01*sign*current_depth for instance if a lose is -100 points, then losing after 4 moves will score -99.96 points but losing after 8 moves will be -99.92 points. Thus, the AI will chose the move that leads to defeat in 8 turns, which makes it more difficult for the (human) opponent. This will not always work if a ``win_score`` argument is provided. """ def __init__(self, depth, scoring=None, win_score=+inf, tt=None): self.scoring = scoring self.depth = depth self.tt = tt self.win_score= win_score def __call__(self,game): """ Returns the AI's best move given the current state of the game. """ scoring = self.scoring if self.scoring else ( lambda g: g.scoring() ) # horrible hack self.alpha = negamax(game, self.depth, self.depth, scoring, -self.win_score, +self.win_score, self.tt) return game.ai_move