Computer Othello

For the arcade game, see Computer Othello (1978 arcade game).

Computer Othello

NTest - a strong othello program

Computer Othello refers to computer architecture encompassing computer hardware and computer software capable of playing the game of Othello.

Availability

There are many othello programs such as NTest, Saio, Edax, Cassio, Pointy Stone, Herakles, WZebra and Logistello that can be downloaded from the Internet for free, and play a game that when run on any up-to-date personal computer, can defeat easily the best human players. Top programs can look 30 moves ahead before each move (given the practical time) on average personal computers.

Search techniques

Computer Othello programs search for any possible legal moves as a game tree. In theory, they examine all positions / nodes, where each move by one player is called a "ply". This searching continues until a certain maximum search depth or the program determines that a final "leaf" position has been reached.

A naive implementation of this approach can only search to a small depth in a practical amount of time, so various methods have been devised to greatly speed the search for good moves. These are based on the Minimax algorithm and Alpha-beta pruning.

Evaluation Techniques

There are three different paradigms for creating evaluation functions.

Disk-square tables

Different squares have different values - corners are good and the squares next to corners are bad. Disregarding symmetries, there are 10 different positions on a board, and each of these is given a value for each of the three possibilities: black disk, white disk and empty. A more sophisticated approach is to have different values for each position during the different stages of the game; e.g. corners are more important in the opening and early midgame than in the endgame.^[1]

Mobility-based

Most human players strive to maximize mobility (number of moves available) and minimize frontier disks (disks adjacent to empty squares). These measures can be found very quickly, and they increase playing strength a lot. Most programs have knowledge of edge and corner configurations and try to minimize the number of disks during the early midgame, another strategy used by human players.^[1]

Pattern-based

Mobility maximization and frontier minimization can be broken down into local configurations which can be added together; the usual implementation is to evaluate each row, column, diagonal and corner configuration separately and add together the values, lots of different patterns have to be evaluated.^[1] The process of determining values for all configurations done by taking a large database of games played between strong players and calculating statistics for each configuration in each game stage from all the games.^[1]

The most common choice to predict the final disc difference, it used a weighted disk difference measure where the winning side gets a bonus corresponding to a number of disks.^[1]

Opening Book

Opening books aid computer programs by giving common openings that are considered good ways to counter poor openings. All strong programs use opening books and update their books automatically after each game. It is to go through all positions from all games in the game database and determine the best move not played in any database game, transposition tables are used to record positions that have been previously searched, to save researching of them.^[1] This is time-consuming as a deep search must be performed for each position, but once this is done, updating the book on the fly is easy - after each game played, all new positions are searched for the best deviation.

Other optimizations

Faster hardware and additional processors can improve Othello-playing program abilities, such as deeper ply searching that lead to be a stronger program.

Solving Othello

Strongly solved on a 4×4 and 6×6 board as a second player (white) win in a perfect play.^[2][3] Although mathematically unsolved, it's practically solved on 8×8 board (the standard one), yet computer analysis shows thousands of draw lines, although not a single line has been fully proven.^[4]

Othello 4 x 4

Othello 4x4 has considerably very small game tree and it has been solved in less than one second by many simple othello programs that use minimax method, which generated all possible positions up to almost 10 million positions, it always ends with White Win +8 in a perfect play.^[2]

Othello 6 x 6

It has been solved in less than 100 hours by many simple othello programs that use minimax method, which generated all possible positions up to almost 3.6 trillion positions, it always ends with White Win +4 in a perfect play.^[5]

Othello 8 x 8

The game tree size is estimated at 10⁵⁴ nodes and the number of legal positions estimated at less than 10²⁸. Although not mathematically solved yet, a solution could possibly be found using intensive computation with top programs on fast parallel hardware or through distributed computation. Some top programs expand their books for many years now on a couple of computers. As a result, many lines are in practice draws or wins for either side. About the three main openings: diagonal, perpendicular and parallel; it appears that both diagonal and perpendicular openings lead to drawing lines, while the parallel opening is a win for black. The drawing tree seems also bigger after the diagonal opening than after the perpendicular opening.^[6] The parallel opening has strong advantages for the black player to always win in a perfect play.^[7] Although not proven yet, practically the game always ends in a draw if both players play perfectly. On standard games, using their opening book, top programs lose less than 1% of the time.

Othello 10 x 10

The starting player (black) has increased chances of winning and it has longer mid-game. Computer analysis shows that it is highly suspected to be a draw if both players play perfectly, however it's considerably not deep enough and needs more calculations. The game tree complexity is very huge, estimated to be 10⁹⁰, with the number of legal positions estimated at 10⁴⁴.^{[citation needed]}

List of Top Othello/ Reversi Programs

1. Saio (Saio) by Benedetto Romano
2. Cyrano (Cyrano java applet) by Bruno Causse
3. Edax (Edax) by Richard Delorme
4. Ymatioun by Youri Matiounine
5. Pirate by Roger H Hughston
6. Cassio (Cassio) by Stéphane Nicolet
7. Logistello by Michael Buro
8. Zebra (Zebra) by Gunnar Anderson
9. NTest by Chris Welty
10. Herakles (Herakles) by Kostas Tournavitis
11. Pointy Stone (Pointy Stone) by Jonathan Kreuzer

See also

• Computer Go
• Computer Shogi
• Computer chess
• Computer Olympiad

Notes

1. ^ ^{a b c d e f} Writing an Othello program April 02, 2007
2. ^ ^{a b} Solution of Othello 4 x 4 September 02, 2008
3. ^ Perfect play in 6x6 Othello from two alternative starting positions November 17, 2004
4. ^ Edax 4.0 Opening Book November 01, 2008
5. ^ A free software for solving 4x4 and 6x6 othello
6. ^ Strongest othello program in term of artificial intelligent
7. ^ Saio's book

External links

• 4 x 4 Othello
• 6 x 6 Othello
• Chess programming