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.

Min-max 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 scores the state based on a heuristic after making the respective move. Min-max search attempts to discover as many states in the future as possible; but due to memory and computation limitations, discovering the entire game tree may not be realistic, so it searches to a specified depth. Min-max search simulates the turns taken by each player, so the depth specified is directly linked to the number of turns between both players. 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 min-max 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 min-max search algorithm tries to minimize making moves where the opponent will have an advantage or a winning state and maximize making moves that give the agent an advantage or a winning state.

Minimax algorithm

To use min-max search in the Connect Four example, the algorithm essentially makes all possible moves from a current game state; then it determines all possible moves from each of those states until it finds the path that is most favorable. 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. Min-max search tries to maximize the positive score for the agent.

Try 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 win it for itself. This AI is using min-max search to find the best move to make. See the AI thinking section for insights into the AI’s decision-making process.