Adversarial Search Problems

adversarial search problems - games

• In adversarial search, the agent maximizes utility rather than minimizing cost (which is done for standard search problems)
• Solution to adversarial search problem: strategy
• strategy - the recommended best possible move given some configuration of the agent(s) and their opponent(s)

game tree - a tree where the nodes are game states and edges are moves

Types of adversarial search problems

• zero-sum games - deterministic, turn-taking, two-player games (pure competition between the two players)
• In zero-sum games, the sum of the utilities of the game agents is zero (i.e. equal and opposite utilities)
• stochastic games - games with probabilistic outcomes
• cooperative games - games in which players have common interests and utility function
• general games - games in which agents have independent utilities (cooperation, indifference, competition, etc. are all possible)

Components of an adversarial search problem

• initial state: specifies how the game is set up at the start 
• players: the players that have the move in the state 
• actions function: a function that returns the set of legal moves in a state 
• transition function (successor function): a function that defines the result of a move 
• terminal test: returns True when the game is over and False when it is not 
• utility function: defines the final numeric value for a game that ends in a terminal state for a specified player 
• utility (of a state) - value of an outcome of that state 
• value (of a state) - the best achievable outcome (utility) from that state (the value of the state is the best value among its chidren's values) 
• The value of a terminal state is its utility (the value of terminal states are known) 
• The value of a non-terminal state is the best value among the values of its children

Zero-sum game algorithms

• Minimax

minimax value

• minimax - an adversarial search algorithm to solve a zero-sum game through performing post-order traversal of the game tree 
• Minimax algorithm runs under the assumption that the opponents always play optimally (that the opponents always choose the best options for themselves in that round) 
• Minimax game tree 

• The game tree that minimax algorithm builds is composed of levels representing the two players alternating turns 
• MIN - the opponent who prefers to move to a state of minimum value (to make max lose, which will make min win); the player that minimizes the result 
• MAX - the opponent who prefers to move to a state of maximum value (to make max win); the player that maximizes the result 
• Time complexity: $O(b^m)$, where $m$ is the maximum depth of the game tree and $b$ is the branching factor (i.e. the number of legal moves at each level)
• The minimax algorithm performs a complete DFS of the game tree
• Space complexity:
• $O(b*m)$ for an algorithm that generates actions/successors all at once (like DFS)
• $O(m)$ for an algorithm that generates actions/successors one at a time
• Optimizations to minimax

• Alpha-beta pruning 

• alpha-beta pruning - a pruning search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its minimax search tree 
• Maintains two values, $\alpha$ and $\beta$, which represent the minimum score that the maximizing player is assured of and the maximum score that the minimizing player is assured of.
• Alpha-beta pruning search updates the values of and as it goes along and prunes the remaining branches at a node (terminates the recursive call) as soon as the value of the current node is known to be worse than the current or value for MAX or MIN, respectively.
• Alpha-beta pruning has no effect on minimax value computed for the root, but values of the intermediate nodes might be different

• Depth-limited minimax search (via evaluation functions)

• evaluation function - a heuristic function that allows us to approximate the true utility (outcome) of a state without doing a complete search of a tree; a function that takes in a state and outputs an estimate of the true minimax value of that node 
• An evaluation function returns an estimate of the expected utility of the game from a given position 
• Applying an evaluation function to states in a search turns non-terminal states to leaves (to avoid searching all the way down the tree's original leaves (the full depth)) 

Other game algorithms

• Expectimax

• expectimax - an adversarial search algorithm for stochastic games; a generalization of minimax
• Expectimax is used when we do not know whether our opponent(s) will make the optimal move from any state, and so we consider the expectation over the moves they may choose to make 
• expectimax tree - a generalized minimax tree with MAX and chance nodes (in place of the MIN nodes of zero sum game trees)
• Chance nodes consider the average case (rather than the worst case scenario); chance nodes compute the expected utility over its children  

expectimax value

• Expectiminimax

• expectiminimax - an adversarial search algorithm for general games; a hybrid of expectimax and minimax
• expectiminimax tree - a generalized minimax tree with MIN, MAX, and chance nodes

expectiminimax value