Reversi

Reversi is a board game for two players also known as Othello. It is played on a board with 8 rows and 8 columns. The rules are quite simple. It can be played online in many places on the web, person against person or person against computer. Of course you can also play it using a chess board and a bunch of coins, head is white and tail is black.

Like many board games Reversi is difficult to win against a computer because - despite the simple rules - there are many possibilities for each move and it is hard to 'look ahead' as far as computers can do. But of course the computer can be set to play easy. Sometimes a game ends with much of the board left empty (when all pieces of one of the players are turned over). So what is the lowest number of game turns before a game can end this way?

Wikipedia has a good article on Reversi.
It includes the following passage: "Mathematically, Othello still remains unsolved. Experts have not yet figured out what the outcome of a game will be where both sides have perfect play. However, analysis of thousands of high-quality games (most of them computer-generated) has led to the conclusion that, on the standard 8-by-8 board, perfect play on both sides results in a draw. When generalizing the game 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.^[4] On 4-by-4 and 6-by-6 boards under perfect play, the second player wins."

I wasted a few CPU cycles trying to verify that last statement, toy around with other questions, and look at n-by-n boards in general. This blog contains the results.