Artificial Intelligence: A Modern Approach |

"""Games, or Adversarial Search. (Chapters 6) """from utils import * import random

# Minimax Searchdefminimax_decision(state, game):"""Given a state in a game, calculate the best move by searching forward all the way to the terminal states. [Fig. 6.4]"""player = game.to_move(state)defmax_value(state): if game.terminal_test(state): return game.utility(state, player) v = -infinity for (a, s) in game.successors(state): v = max(v, min_value(s)) return vdefmin_value(state): if game.terminal_test(state): return game.utility(state, player) v = infinity for (a, s) in game.successors(state): v = min(v, max_value(s)) return v # Body of minimax_decision starts here: action, state = argmax(game.successors(state), lambda ((a, s)): min_value(s)) return action

defalphabeta_full_search(state, game):"""Search game to determine best action; use alpha-beta pruning. As in [Fig. 6.7], this version searches all the way to the leaves."""player = game.to_move(state)defmax_value(state, alpha, beta): if game.terminal_test(state): return game.utility(state, player) v = -infinity for (a, s) in game.successors(state): v = max(v, min_value(s, alpha, beta)) if v >= beta: return v alpha = max(alpha, v) return vdefmin_value(state, alpha, beta): if game.terminal_test(state): return game.utility(state, player) v = infinity for (a, s) in game.successors(state): v = min(v, max_value(s, alpha, beta)) if v <= alpha: return v beta = min(beta, v) return v # Body of alphabeta_search starts here: action, state = argmax(game.successors(state), lambda ((a, s)): min_value(s, -infinity, infinity)) return actiondefalphabeta_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)defmax_value(state, alpha, beta, depth): if cutoff_test(state, depth): return eval_fn(state) v = -infinity 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 vdefmin_value(state, alpha, beta, depth): if cutoff_test(state, depth): return eval_fn(state) v = infinity 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: game.utility(state, player)) action, state = argmax(game.successors(state), lambda ((a, s)): min_value(s, -infinity, infinity, 0)) return action

# Players for Gamesdefquery_player(game, state):"Make a move by querying standard input."game.display(state) return num_or_str(raw_input('Your move? '))defrandom_player(game, state):"A player that chooses a legal move at random."return random.choice(game.legal_moves())defalphabeta_player(game, state): return alphabeta_search(state, game)defplay_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, players[0])

# Some Sample GamesclassGame:"""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."""deflegal_moves(self, state):"Return a list of the allowable moves at this point."abstractdefmake_move(self, move, state):"Return the state that results from making a move from a state."abstractdefutility(self, state, player):"Return the value of this final state to player."abstractdefterminal_test(self, state):"Return True if this is a final state for the game."return not self.legal_moves(state)defto_move(self, state):"Return the player whose move it is in this state."return state.to_movedefdisplay(self, state):"Print or otherwise display the state."print statedefsuccessors(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__classFig62Game(Game):"""The game represented in [Fig. 6.2]. Serves as a simple test case. >>> g = Fig62Game() >>> minimax_decision('A', g) 'a1' >>> alphabeta_full_search('A', g) 'a1' >>> alphabeta_search('A', g) 'a1' """succs = {'A': [('a1','B'), ('a2','C'), ('a3','D')],'B': [('b1','B1'), ('b2','B2'), ('b3','B3')],'C': [('c1','C1'), ('c2','C2'), ('c3','C3')],'D': [('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'defsuccessors(self, state): return self.succs.get(state, [])defutility(self, state, player): if player =='MAX': return self.utils[state] else: return -self.utils[state]defterminal_test(self, state): return state not in ('A','B','C','D')defto_move(self, state): return if_(state in'BCD','MIN','MAX')classTicTacToe(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): update(self, h=h, v=v, k=k) moves = [(x, y) for x in range(1, h+1) for y in range(1, v+1)] self.initial = Struct(to_move='X', utility=0, board={}, moves=moves)deflegal_moves(self, state):"Legal moves are any square not yet taken."return state.movesdefmake_move(self, move, state): 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 Struct(to_move=if_(state.to_move =='X','O','X'), utility=self.compute_utility(board, move, state.to_move), board=board, moves=moves)defutility(self, state):"Return the value to X; 1 for win, -1 for loss, 0 otherwise."return state.utilitydefterminal_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) == 0defdisplay(self, state): board = state.board for x in range(1, self.h+1): for y in range(1, self.v+1): print board.get((x, y),'.'), printdefcompute_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 if_(player =='X', +1, -1) else: return 0defk_in_row(self, board, move, player, (delta_x, delta_y)):"Return true if there is a line through move on board for player."x, y = move n = 0 # n is number of moves in row 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 n -= 1 # Because we counted move itself twice return n >= self.kclassConnectFour(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)deflegal_moves(self, state):"Legal moves are any square not yet taken."return [(x, y) for (x, y) in state.moves if y == 0 or (x, y-1) in state.board]

AI: A Modern Approach by Stuart Russell and Peter Norvig | Modified: Jul 18, 2005 |