Adversarial Search: Minimax Quiz

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.