Today, we focused on a very integral aspect of Artificial Intelligence, games, or adversarial searches. Adversarial searches examine problems that arise when we try to plan ahead in a state where other agents are planning against us. Games are different from search problems in the opponent’s unpredictability and in the time limits involved. Because of these two restrictions, game algorithms must approximate to find a a strategy that specifies a move for every possible opponent reply.
Games can be deterministic or stochastic. They can have perfect information or imperfect information. It is often beneficial to draw a 2-player, deterministic game tree to better visualize the “max” and “min”. A game can be defined as a kind of search problem with the following elements: the initial state, players, actions, results, terminal tests, and utility.
The minimax algorithm was designed for perfect play for deterministic, perfect information games. The algorithm chooses to move to the position with the highest minimax value to achieve the best payoff against an optimal opponent. The search algorithm is complete if the game tree is finite. It is optimal against the optimal opponent. Since the utility is only achieved at the end of the search, the time complexity is O(bᵐ). Since minimax uses depth-first exploration, its space complexity is O(b*m).
α–β pruning (alpha-beta pruning) makes the minimax algorithm more efficient by eliminating subtrees that are provably irrelevant. α is the best value that max has found so far along the path to the route. if v is worse than α, max will avoid the branch (prune it). β is α but defined by the minimum. Good move ordering improves the effectiveness of pruning. However, even with α–β pruning, there are resource limits. To avoid these, we can use cutoff-tests instead of terminal tests (i.e. depth-limit searches) or we can use evaluation instead of utility (the evaluation function estimates the desirability of a position).
Expectiminimax is an algorithm for nondeterministic games that gives perfect play but also handles chance nodes. As depth increases, its probability of reaching a given node shrinks.
For games with imperfect information, the algorithm calculates the probability for each possible deal. It computes the minimax value of each action in each deal, then chooses the action with the highest expected value over all deals.
Proper analysis is the intuition that the value of an action is the average of its values in all actual states is wrong. With partial observability, the value of an action depends on the information state or belief state the agent is in.
In summary, since perfection in games is unattainable, game algorithms must approximate. Uncertainty therefore constrains the assignment of values to states. Optimal decisions depend on the information state, not the real state.
Alex Tsai's AI Blog 