Adversarial Search in Games

The following code is based on the code provided by the book Artificial Intelligence: A Modern Approach in http://aima.cs.berkeley.edu/python/readme.html.

Abstract class for modeling a game



In [86]:

    
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__

Minimax with alpha-beta pruning implementation

Some auxiliary functions



In [87]:

    
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))

Minimax search function



In [98]:

    
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

Generic playing agents

Auxiliary functions



In [99]:

    
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__')

A player that makes a query for each move



In [100]:

    
def query_player(game, state):
    "Make a move by querying standard input."
    game.display(state)
    return num_or_str(raw_input('Your move? '))

A player that chooses a move at random



In [101]:

    
import random

def random_player(game, state):
    "A player that chooses a legal move at random."
    return random.choice(game.legal_moves(state))

A player that uses minimimax alpha-beta search



In [102]:

    
def alphabeta_player(game, state):
    return alphabeta_search(state, game)

A function that receives a list of players and call each player alternatively



In [103]:

    
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)

The last-stone game

The 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



In [104]:

    
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)

The following class models the last-stone game:



In [114]:

    
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)]

An interactive game against the computer, can you win?



In [ ]:

    
play_game(LastStone(10), query_player, alphabeta_player)









    



Struct(to_move=0, heap=10)

1. Design an evaluation function for the last-stone game and test it



In [113]:

    
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"









    



Smart player loses

The 3-heaps last-stone game

In 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



In [ ]:

    
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