Newer
Older
"""Games, or Adversarial Search. (Chapter 5)
"""
import collections
import math
import random
infinity = math.inf
# ______________________________________________________________________________
# Minimax Search
def minimax_decision(state, game):
"""Given a state in a game, calculate the best move by searching
forward all the way to the terminal states. [Fig. 5.3]"""
player = game.to_move(state)
def max_value(state):
if game.terminal_test(state):
return game.utility(state, player)
v = -infinity
for a in game.actions(state):
v = max(v, min_value(game.result(state, a)))
return v
def min_value(state):
if game.terminal_test(state):
return game.utility(state, player)
v = infinity
for a in game.actions(state):
v = min(v, max_value(game.result(state, a)))
return v
# Body of minimax_decision:
return argmax(game.actions(state),
lambda a: min_value(game.result(state, a)))
# ______________________________________________________________________________
def alphabeta_full_search(state, game):
"""Search game to determine best action; use alpha-beta pruning.
As in [Fig. 5.7], this version searches all the way to the leaves."""
player = game.to_move(state)
def max_value(state, alpha, beta):
if game.terminal_test(state):
return game.utility(state, player)
v = -infinity
for a in game.actions(state):
v = max(v, min_value(game.result(state, a), alpha, beta))
if v >= beta:
return v
alpha = max(alpha, v)
return v
def min_value(state, alpha, beta):
if game.terminal_test(state):
return game.utility(state, player)
v = infinity
for a in game.actions(state):
v = min(v, max_value(game.result(state, a), alpha, beta))
if v <= alpha:
return v
beta = min(beta, v)
return v
beta = infinity
v = min_value(game.result(state, a), best_score, beta)
if v > best_score:
best_score = v
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))
beta = infinity
v = min_value(game.result(state, a), best_score, beta, 1)
if v > best_score:
best_score = v
# ______________________________________________________________________________
# Players for Games
def query_player(game, state):
"Make a move by querying standard input."
game.display(state)
return eval(input('Your move? '))
def random_player(game, state):
"A player that chooses a legal move at random."
def alphabeta_player(game, state):
return alphabeta_full_search(state, game)
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)
if game.terminal_test(state):
return game.utility(state, game.to_move(game.initial))
# ______________________________________________________________________________
# Some Sample Games
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 actions,
result, 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."""
"Return a list of the allowable moves at this point."
"Return the state that results from making a move from a state."
def utility(self, state, player):
"Return the value of this final state to player."
def terminal_test(self, state):
"Return True if this is a final state for the game."
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."
def __repr__(self):
return '<%s>' % self.__class__.__name__
"""The game represented in [Fig. 5.2]. Serves as a simple test case."""
succs = dict(A=dict(a1='B', a2='C', a3='D'),
B=dict(b1='B1', b2='B2', b3='B3'),
C=dict(c1='C1', c2='C2', c3='C3'),
D=dict(d1='D1', d2='D2', d3='D3'))
utils = dict(B1=3, B2=12, B3=8, C1=2, C2=4, C3=6, D1=14, D2=5, D3=2)
initial = 'A'
return self.succs[state][move]
def utility(self, state, player):
if player == 'MAX':
return self.utils[state]
else:
return -self.utils[state]
def terminal_test(self, state):
return state not in ('A', 'B', 'C', 'D')
def to_move(self, state):
return ('MIN' if state in 'BCD' else 'MAX')
GameState = collections.namedtuple('GameState', 'to_move, utility, board, moves')
class TicTacToe(Game):
"""Play TicTacToe on an h x v board, with Max (first player) playing 'X'.
A state has the player to move, a cached utility, a list of moves in
the form of a list of (x, y) positions, and a board, in the form of
a dict of {(x, y): Player} entries, where Player is 'X' or 'O'."""
def __init__(self, h=3, v=3, k=3):
self.h = h
self.v = v
self.k = k
moves = [(x, y) for x in range(1, h+1)
for y in range(1, v+1)]
self.initial = GameState(to_move='X', utility=0, board={}, moves=moves)
"Legal moves are any square not yet taken."
return state.moves
if move not in state.moves:
return state # Illegal move has no effect
board = state.board.copy()
board[move] = state.to_move
moves = list(state.moves)
moves.remove(move)
return GameState(to_move=('O' if state.to_move == 'X' else 'X'),
utility=self.compute_utility(board, move, state.to_move),
board=board, moves=moves)
def utility(self, state, player):
"Return the value to player; 1 for win, -1 for loss, 0 otherwise."
return (state.utility if player == 'X' else -state.utility)
def terminal_test(self, state):
"A state is terminal if it is won or there are no empty squares."
return state.utility != 0 or len(state.moves) == 0
def display(self, state):
board = state.board
for x in range(1, self.h+1):
for y in range(1, self.v+1):
def compute_utility(self, board, move, player):
"If X wins with this move, return 1; if O return -1; else return 0."
if (self.k_in_row(board, move, player, (0, 1)) or
self.k_in_row(board, move, player, (1, 0)) or
self.k_in_row(board, move, player, (1, -1)) or
self.k_in_row(board, move, player, (1, 1))):
return (+1 if player == 'X' else -1)
else:
return 0
def k_in_row(self, board, move, player, xxx_todo_changeme):
"Return true if there is a line through move on board for player."
x, y = move
while board.get((x, y)) == player:
n += 1
x, y = x + delta_x, y + delta_y
x, y = move
while board.get((x, y)) == player:
n += 1
x, y = x - delta_x, y - delta_y
return n >= self.k
class ConnectFour(TicTacToe):
"""A TicTacToe-like game in which you can only make a move on the bottom
row, or in a square directly above an occupied square. Traditionally
played on a 7x6 board and requiring 4 in a row."""
def __init__(self, h=7, v=6, k=4):
TicTacToe.__init__(self, h, v, k)
return [(x, y) for (x, y) in state.moves
if y == 1 or (x, y-1) in state.board]