Adversarial search and constraint satisfaction notes — Unit 3

Previous search environments (like puzzle solving) assumed no other agents in the environment. In competitive environments, the agent's goals conflict with other agents. This is Adversarial Search, commonly known as Games.

⇒1.1 Game Characteristics in AI

• Deterministic: No dice rolling (e.g., Chess, Checkers).
• Fully Observable: You can see the whole board.
• Two-Player, Zero-Sum: What is good for Player 1 is exactly equally bad for Player 2.
• Time Limits: Unlike A* which computes the absolute perfect path forever, Game AI must make a move within seconds.

The fundamental algorithm for zero-sum games. We define two players: MAX and MIN. MAX wants to maximize the score, MIN wants to minimize the score.

⇒2.1 How it works

The algorithm generates a game tree down to the terminal states (win, lose, draw) and assigns a Utility value (+1, -1, 0). It then backs up these values to the root.

• If it is MAX's turn to move, it returns the maximum value of its children.
• If it is MIN's turn to move, it returns the minimum value of its children.

Minimax assumes that the opponent will play perfectly optimally.

The problem with Minimax is that the game tree for Chess has `10^120` nodes. It is impossible to search to the end. Alpha-Beta Pruning is an optimization that skips evaluating branches that mathematically cannot influence the final decision.

⇒3.1 The Principle

If you have an idea that is demonstrably bad (because the opponent can crush you if you take it), do not waste computing power analyzing exactly how bad it is. Just discard it.

• Alpha (α): The value of the best (highest) choice we have found so far at any choice point along the path for MAX.
• Beta (β): The value of the best (lowest) choice we have found so far at any choice point along the path for MIN.

Alpha-beta pruning mathematically guarantees it will return the exact same move as standard Minimax, but it can cut the search time exponentially, allowing the AI to look twice as many moves ahead.

Even with Alpha-Beta pruning, we cannot search to the end of a chess game. We must use a Cutoff Test (e.g., stop searching after 10 moves).

⇒5.1 The Heuristic

When we stop searching, we are not at a terminal state (nobody has won yet). We must use a Heuristic Evaluation Function to estimate who is winning.

For chess, a simple evaluation function is counting material: `f(n) = (PawnValuePawns + KnightValueKnights) - (OpponentPawnValue*OpponentPawns...)`.

In standard search, a state is just a 'black box'. In a CSP, the state is defined by a set of variables, each with a value. The problem is solved when all variables have a value that satisfies all the rules (constraints).

⇒6.1 Classic Examples

• Sudoku: Variables are the 81 cells. Domain is {1-9}. Constraints are that rows/columns/boxes cannot have duplicates.
• Map Coloring: Coloring a map so no two adjacent countries have the same color.
• Job Scheduling: Assigning shifts to workers so no worker does back-to-back night shifts.

CSPs are solved using Backtracking Search (a form of DFS).

⇒7.1 Backtracking

The algorithm assigns a value to one variable at a time. If it reaches a point where a variable has no legal values left (because of previous choices), it 'backtracks' (undoes) the previous choice and tries a different one.

⇒7.2 Optimization: Forward Checking

Whenever a variable X is assigned, look at all unassigned variables connected to X, and instantly delete from their domains any values inconsistent with X. If any unassigned variable's domain becomes empty, backtrack immediately.