Adversarial Search

Adversarial Search

Adversarial search, or Minimax search, is an algorithm to try to result with the best outcome of a situation while also accounting for the actions of an opponent. It is similar to other simpler search algorithms in that it creates a tree of the possible states and tries to walk down it. At every other level of the tree, the algorithm must account for the opponent. In most cases when the opponent is choosing, you expect the opponent to choose the worst outcome for you and the best outcome for them. This search has many uses and is applied in many games.

In games where minimax is applicable there can only be two players. A good example of a game for this is the game of checkers. It is a simple game so it is possible for a computer to compute all the possible moves in the game. If played correctly, the game is actually impossible to lose. A minimax algorithm is a great algorithm to use for this game. You can quantify the goals of the game. For example, if you win the game, you get infinite points. If you lose the game, you lose infinity points. If you lose a piece, you lose a point. If the opponent loses a piece, you gain a point. The minimax algorithm can then look down the tree to see where the possible moves are that would give it the most points.

We can assume that the opponent wants us to get the least number of points possible as well. To apply this to checkers for example, we wouldn’t want to move our piece in front of the opponent’s piece. This would allow for the opponent to immediately jump and remove our piece, decreasing our number of points.

There is a slight oddity of behavior though when encountered with a board that is impossible to win. Say you only have one piece left that is in a corner. The entire rest of the board, save a few empty spaces around you, are your opponent’s pieces. The algorithm won’t choose to fight as long as possible. It will just accept defeat and choose any path that might or might not lead straight towards your loss. This might not really matter because you’ve already analyzed every possible play on the board and have concluded that there is no way for you to win. But it is an interesting habit nonetheless.