Adversarial Search: Minimax Quiz

Study Notes

The 8 Queens Puzzle

The 8 queens puzzle is a problem where a queen attacks any piece in the same row, column, or diagonal.
The goal is to find a solution where 8 queens can be placed on a chessboard without attacking each other.

The Travelling Problem

The initial state is In(Arad), with applicable actions being {Go(Sibiu), Go(Timisoara), Go(Zerind)}.
The transition model is specified by the function RESULT(s, a), which returns the state that results from action a in state s.
The goal state is {In(Bucharest)}, and the path cost is a function that assigns a numeric cost to each path.

Search Trees

A node denotes some state or value.
The root is the top node in a tree, and a child is a node directly connected to another node when moving away from the root.
A parent is the converse notion of a child, and a leaf is a node with no children.
An internal node is a node with at least one child.
An edge is the connection between one node and another.
The depth is the distance between a node and the root, and the level is the number of edges between a node and the root +1.
The height is the number of edges on the longest path between a node and a descendant leaf, and the breadth is the number of leaves.

Minimax Algorithm

Minimax is a search algorithm used for decision-making in games like chess and tic-tac-toe.
The algorithm assumes that both players, Max and Min, play optimally.
The minimax value is the best achievable utility against an optimal adversary.
The minimax algorithm computes the utility of being in a state, assuming both players play optimally from there until the end of the game.
The algorithm propagates minimax values up the tree once terminal nodes are discovered.

Adversarial Search

Adversarial search is a search algorithm used for decision-making in games like chess and tic-tac-toe.
The algorithm assumes that both players, Max and Min, play optimally.
The algorithm computes the utility of being in a state, assuming both players play optimally from there until the end of the game.
The algorithm propagates minimax values up the tree once terminal nodes are discovered.

Minimax Example

If the state is a terminal node, the value is the utility of the state.
If the state is a Max node, the value is the highest value of all successor node values.
If the state is a Min node, the value is the lowest value of all successor node values.

Properties of Minimax

The minimax algorithm is optimal and complete, meaning it will find the best move if the game tree is finite.
The time complexity of the algorithm is O(bd), where b is the branching factor and d is the depth of the game tree.
The space complexity of the algorithm is O(bd).

Alpha-Beta Pruning

Alpha-beta pruning is a variant of the minimax algorithm that reduces the number of nodes to be evaluated.
The algorithm keeps track of two bounds, α and β, which are the current lower bound on Max's outcome and the current upper bound on Min's outcome, respectively.
The algorithm propagates α and β values down during the search to be used for pruning.
The algorithm updates α and β values by propagating upwards values of terminal nodes.
The algorithm prunes any remaining branches whenever α ≤ β.

Real-time Decisions

Real-time decisions are necessary in games like chess, where moves have to be made in a reasonable amount of time.
One solution is to bound the depth of search and replace utility(s) with eval(s), an evaluation function that estimates the value of current board configurations.
The evaluation function is a heuristic that ranks terminal states in the same way as the true utility function.
The evaluation function is typically a linear weighted sum of features, which are domain-specific characteristics of the game.

Description

Test your knowledge on finding the optimal strategy for Max using the minimax algorithm in adversarial search. Understand the depth-first search of the game tree, the minimax principle, and propagating minimax values up the tree.