Reversi

Screen dump of WZebra 4.1, a Reversi program by Gunnar Andersson and Lars Ivansson

Reversi is a strategic board game played by two parties on an eight-by-eight square grid with pieces that have two distinct sides. Coin-like markers with a light and a dark face are typical.

The origin of the game is rather controversial. Japanese believe it was invented in Japan [1] in the 1970s but some resources say the game was in existence before that.[2] In Japan, the game was introduced in 1975 by Goro Hasegawa, who wrote How to win at Othello. It was named after the Shakespeare play Othello.

Mattel produces reversi equipment under the name Othello. Othello is a registered trademark of Tsukuda Original, licensed by Anjar Co.

The number of legal positions in Reversi is estimated to be at most 10²⁸, and it has a game-tree complexity of approximately 10⁵⁸. In 1980 the program The Moor beat the reigning world champion, and since that time computer programs have competed near the world championship level. One of the world's strongest Othello AI is Logistello, which beat the human champion Takeshi Murakami 6:0 in 1997.

Human beings cannot generally win against computer intelligence in Reversi because computers can look ahead much further than humans can. Reversi has not yet been solved, however - we don't know the result of the game with perfect play on both sides.

When Reversi is generalized so that it can be played 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.

Rule

Each of the two sides corresponds to one player; we will call them light and dark after the sides of Othello pieces, but "heads" and "tails" is equally feasible so long as each marker has sufficiently distinctive sides.

Originally, Reversi didn't have a starting position to begin from. Later it adopted Othello's rules which state that the game begins with four markers placed in a square in the middle of the grid, two facing light-up (indicated by o in our diagrams), two pieces with the dark side up (indicated by *). The light player makes the first move.

  *o
  o*  (one of the possible starting positions)

Light must place a piece with the light side up on the grid, so that there is a straight (horizontal, vertical, or diagonal) line between the new piece and another light piece, with at least one dark piece between them. In the above situation, light has the following options indicated by dots:

  .
 .*o
  o*.
   .

After placing the piece, light is entitled to turn around all dark pieces between the new piece and the next light piece on a straight line, should one exist. All reversed pieces now show the light side, and light can use them in later moves -- unless dark was able to turn them back in the mean time.

If light decided to put a piece in the topmost location (all choices are equivalent at this time), one piece will be turned around:

  o
  oo
  o*

Now it is dark's turn. This player operates under the same rules, with the roles reversed: A dark piece is laid down so that one or more straight lines of light pieces can be turned around. Possiblities at this time:

 .o.
  oo
 .o*

Dark takes the left alternative and is able to turn around one piece:

  o
  oo
 ***

Players take alternating turns. Should one player be unable to make a valid move it is the other player's turn again. When both players are unable to move, the game ends. This is the case when the grid has filled up, or when one player has no more pieces on the board. The player with more pieces available at the end wins.

Another difference between Reversi and Othelloo is that in Reversi each player owns 32 pieces at the start of the game. Once a player has placed 32 pieces (including the initial 2 pieces placed on the centre squares) that player may not make any further moves. He/she is not allowed to use any of the opponent's pieces. In Othello all the pieces belong to both players equally; they are in a pool from which both may draw in order to make a move.

Strategy

Pieces are flipped very quickly and easily, so it's not very important, and in fact typically detrimental to try to gain a majority of pieces early in the game. Corners, mobility, edge play, parity, endgame play and look ahead are the key elements of good Othello strategy.

Corners

Corners, once played, cannot be flipped, and can be used to anchor groups of pieces (starting with the adjacent edges) that also cannot be flipped. So capturing a corner is often an effective strategy when the opportunity arises.

Mobility

An opponent playing with reasonable strategy will not so easily relinquish the corner or any other good moves. So to achieve these good moves, you must force your opponent to play moves which relinquish those good moves. The best way to achieve that is to reduce the number of available moves of your opponent. If you reduce the number of legal moves your opponent can make, then sooner or later she will be forced to make a move undesirable to her. An ideal position to be in is to have all your pieces in the center surrounded by your opponents pieces. In such situations you can dictate what moves your opponent can make.

When moves seem equal with respect to what moves you will leave yourself and will be open to your opponent, playing a minimum piece strategy will tend to be more beneficial. This is because minimizing your discs will tend to leave fewer discs for your opponent to flip in subsequent moves of the game. One should not play the minimum disc strategy to an extreme, however, as this also can quickly lead a lack of mobility.

Edges

While playing pieces to edges may seem sound (because they are not so easily flipped) they can often be detrimental. Edge pieces can anchor flips that influence moves to all regions of the board. Because of that, this can, sooner or later, poison later moves that you make by causing you to flip too many pieces and open up many moves for your opponent. However sometimes playing to an edge which cannot easily be responded to will leave your opponent with significantly fewer moves than any other moves.

The square immediately diagonally adjacent to the corner (called the X-square) played in the early and middle game is typically a guarantee of losing that corner. Playing to the edge squares adjacent to the corner can typically lead to tactical traps involving sacrificing one corner, or simply playing out the edge in a specific sequence.

In general you should avoid edge play in the early and middle game if you can avoid it, unless you can gain larger concessions in terms of mobility or a mass of unflippable pieces.

Parity

As play progresses regions of the board will typically section themselves off, where neither side can prevent the other from playing arbitrarily into those regions. By simply counting out the number of squares in a region, one can notice if it is odd or even. If it is odd, then by playing there first, you can force your opponent to be the first to play outside of that region. This is achieved by simply playing into that region any time there is an odd number of squares available, and not playing into it when there is an even number of squares. If you take into consideration certain squares in a region that seem to be very bad (like an X-square or an edge square that leads to an obvious trap) then you can either force your opponent to play elsewhere or concede to playing one of these bad squares.

Look ahead and Endgame

Like any good strategy for chess, or checkers, it is not sufficient to only consider the current situation on the board. For each move you consider you must consider possible responses from your opponent, then the subsequent responses you will make to those moves and so on. The aspects of the current position may not be relevant a few moves down the road. So when optimizing your mobility, gaining corners or anything else, you should consider how best to do this for the long term rather than just for the next move.

For the endgame (the last 20 or so moves of the game) the strategies will typically change. Special techniques such as sweeping, gaining access, and the details of move order can have a large impact on the outcome of the game. Unfortunately at these late stages of the game, there are no hard set rules. The best you can do is try to look ahead and get a feel for what will lead to the best final outcome.

Game trivia

Since about 1980 there has been a yearly world Othello championship. Each country is allowed to send a maximum of 3 players.
Othello has its greatest following in Japan.
Good computer players are far stronger than any human player.

Othello World Championship

Year	Location	World Champion	Country	Team	Runner Up	Country
1977	Tokyo	Hiroshi Inoue	Japan	N/A	Thomas Heiberg	Norway
1978	New York	Hideshi Maruoka	Japan	N/A	Carol Jacobs	USA
1979	Rome	Hiroshi Inoue	Japan	N/A	Jonathan Cerf	USA
1980	London	Jonathan Cerf	USA	N/A	Takuya Mimura	Japan
1981	Brussels	Hideshi Maruoka	Japan	N/A	Brian Rose	USA
1982	Stockholm	Kunihiko Tanida	Japan	N/A	David Shaman	USA
1983	Paris	Ken'Ichi Ishii	Japan	N/A	Imre Leader	Britain
1984	Melbourne	Paul Ralle	France	N/A	Ryoichi Taniguchi	Japan
1985	Athens	Masaki Takizawa	Japan	N/A	Paolo Ghirardato	Italy
1986	Tokyo	Hideshi Tamenori	Japan	N/A	Paul Ralle	France
1987	Milan	Ken'Ichi Ishii	Japan	USA	Paul Ralle	France
1988	Paris	Hideshi Tamenori	Japan	Britain	Graham Brightwell	Britain
1989	Warsaw	Hideshi Tamenori	Japan	Britain	Graham Brightwell	Britain
1990	Stockholm	Hideshi Tamenori	Japan	France	Didier Piau	France
1991	New York	Shigeru Kaneda	Japan	USA	Paul Ralle	France
1992	Barcelona	Marc Tastet	France	Britain	David Shaman	Britain
1993	London	David Shaman	USA	USA	Emmanuel Caspard	France
1994	Paris	Masaki Takizawa	Japan	France	Karsten Feldborg	Denmark
1995	Melbourne	Hideshi Tamenori	Japan	USA	David Shaman	USA
1996	Tokyo	Takeshi Murakami	Japan	Britain	Stephane Nicolet	France
1997	Athens	Makoto Suekuni	Japan	Britain	Graham Brightwell	Britain
1998	Barcelona	Takeshi Murakami	Japan	France	Emmanuel Caspard	France
1999	Milan	David Shaman	Netherlands	Japan	Tetsuya Nakajima	Japan
2000	Copenhagen	Takeshi Murakami	Japan	USA	Brian Rose	USA
2001	New York	Brian Rose	USA	USA	Raphael Schreiber	USA
2002	Amsterdam	David Shaman	Netherlands	USA	Ben Seeley	USA
2003	Stockholm	Ben Seeley	USA	Japan	Makoto Suekuni	Japan

Literature

Othello: Brief and Basic, An introduction to strategy and tactics for the game of Othello, Ted Landau, 1987
Othello: From Beginner to Master, Randy Fang, 2003

External links