A two-player, zero-sum, perfect information game is one in which both opponents have all of the information about the state of the game available to them, and any gain in advantage for one is a loss of advantage for the other. Such games include tic-tac-toe, Connect Four, checkers, and chess. In this chapter, we will study how to create an artificial opponent that can play such games with great skill. In fact, the techniques discussed in this chapter, coupled with modern computing power, can create artificial opponents that play simple games of this class perfectly and that can play complex games beyond the ability of any human opponent.
As with most of our more complex problems in this book, we will try to make our solution as generic as possible. In the case of adversarial search, that means making our search algorithms non-game-specific. Let’s start by defining some simple interfaces that define all of the ways to access state that our search algorithms will need. Later, we can implement those interfaces for the specific games we are interested in developing (tic-tac-toe and Connect Four) and feed the implementations into the search algorithms to make them “play” the games. Here are those interfaces.
package chapter8;
public interface Piece {
Piece opposite();
}