Intelligent search

Informed search means that the algorithm has some context of the specific problem being solved, instead of blindly searching breadth-first or depth-first. Heuristics are a way to represent this information. Often called a rule of thumb, a heuristic is a rule or set of rules used to evaluate a state. It can be used to define criteria that a state must satisfy or measure the performance of a specific state. A heuristic is used when a clear method of finding an optimal solution is not possible. A heuristic can be interpreted as an educated guess and should be seen more as a guideline rather than as a scientific truth with respect to the problem that is being solved. When you’re ordering a pizza at a restaurant, for example, your heuristic of how good it is may be defined by the ingredients and type of base used. If you enjoy extra tomato sauce, extra cheese, mushrooms, and pineapple on a thick base with crunchy crust, a pizza that includes more of these will be more appealing to you and achieve a better score for your heuristic. A pizza that contains fewer of those attributes will be less appealing and achieve a poorer score.

Adversarial search

Adversarial search is characterized by opposition or conflict. Adversarial problems require us to anticipate, understand, and counteract the actions of the opponent in pursuit of a goal. Examples of adversarial problems include two-player turn-based games such as Tic-Tac-Toe and Connect Four. The players take turns for the opportunity to change the state of the environment of the game to their favor. A set of rules dictates how the environment may be changed and what the winning and end states are. These are often called Zero-Sum Games: for one player to win (+10), the other must lose (-10). The total sum of the outcome is always zero.

Let’s explore the game of Connect Four to explore adversarial problems. Connect Four is a game consisting of a grid in which players take turns dropping tokens into one of the columns. The tokens in a specific column pile up, and any player who manages to create four adjacent sequences of their tokens—vertically, horizontally, or diagonally wins. If the grid is full, with no winner, the game results in a draw.

Minimax search aims to build a tree of possible outcomes based on moves that each player could make and favor paths that are advantageous to the agent while avoiding paths that are favorable to the opponent. To do so, this type of search simulates possible moves assuming that both players play perfectly. The opponent will always choose the move that hurts the agent most, and the agent will always choose the move that helps itself most. Because the full game tree is usually too large to search completely, the algorithm only looks ahead to a specified depth. A depth of 4, for example, means that each player has had 2 turns. Player A makes a move, player B makes a move, player A makes another move, and player B makes another move.

Heuristics

The minimax algorithm uses a heuristic score to make decisions. This score is defined by a crafted heuristic and is not automatically learned by the algorithm. If we have a specific game state, every possible valid outcome of a move from that state will be a child node in the game tree.

Assume that we have a heuristic that provides a score in which positive numbers are better than negative numbers. By simulating every possible valid move, the minimax search algorithm tries to avoid moves where the opponent will gain an advantage and favor moves that strengthen the agent’s position.

Minimax algorithm

To use minimax search in the Connect Four example, the algorithm evaluates all possible moves from a current game state, then all possible responses to those moves, until it reaches the search depth limit. Game states that result in a win for the agent return a score of 10, and states that result in a win for the opponent return a score of -10. Minimax tries to maximize the positive score for the agent while assuming the opponent will do the opposite.

Why pruning matters

Even in a game as approachable as Connect Four, the number of possible futures grows quickly. From a single position, the algorithm may need to consider several legal moves, then several responses to each of those, then several replies to those responses. That branching explosion is why heuristics and pruning matter so much. Without them, intelligent search would become too slow to feel intelligent.

Try to beat the AI at Connect Four

The game below is Connect Four. Try to create a row, column, or diagonal of four tokens of your color to win the game. The AI will try to prevent you from winning and win for itself. Start a new game, make your first move, and then watch the AI thinking section to see how the search tree and evaluation scores change in response. You can also increase the search depth to make the opponent stronger, though that usually means more search work and slower thinking.

This toy only searches a shallow slice of the full game tree, but that is enough to reveal the core idea: intelligent play often comes from evaluating promising futures, not from checking everything exhaustively.