## 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.

Actually, I think mimimax would work fine with more than two players - just have a ply for each one, always returning the outcome from the perspective of the root player, and have each player take the move that is best for them.

ReplyDelete