Reversi/Introduction
Reversi and Othello are strategic boardgames which involve play by two parties on an eight-by-eight square grid with pieces that have two distinct sides. Pieces typically appear coin-like, with a light and a dark face.
Mattel produces Reversi equipment under the name "Othello". Anjar Co licenses the registered trademark "Othello" from Tsukuda Original.
The best Othello computer programs can easily defeat the best humans. As early as 1980, the program The Moor beat the reigning world champion, and in 1997, Logistello defeated the human champion Takeshi Murakami 6:0. This dominance is not seen in games like chess, where the best computers are about equal to the best humans (although the Hydra machine may soon change that), or Go, where even average human players trounce the best computers.
Human beings cannot generally win against computer intelligence in Othello because computers can look ahead much further than humans can. Analysts have estimated the number of legal positions in Othello as at most 1028, and it has a game-tree complexity of approximately 1058. Othello still remains unsolved, however - we don't know the result of the game with perfect play on both sides.
When generalizing Othello to play on an n-by-n board, the problem of determining if the first player has a winning move in a given position is PSPACE-complete.