Reversi (Othello)

Two players take turn placing reversible disks on a square board. Moves reverse one or more of the opponent's disks.

Description

The game is played on a $n \times n$ board. Each location of the board is either empty or occupied by a reversible disk which are white on one side and black on the other. Players take turn placing reversible disks on empty locations. After each move, all pieces of the opponent’s color that lie on an horizontal, vertical, or 45-degrees segment that connects the newly placed piece with one of the same color are flipped over. A move needs to cause at least one disk to flip. If no valid move exists, the player’s turn is skipped. When no valid moves are left the game terminates and the player with the most disks of its color wins (draws are allowed).

The classical game is played on a $8 \times 8$ board with 2 white (resp. black) disks initially placed on the main diagonal (resp. antidiagonal) of the central $2 \times 2$ square.

Computational complexity

Determining whether the first player has a winning strategy is PSPACE-complete [1].

References

[1] S. Iwata, T. Kasai, “The Othello game on an n*n board is PSPACE-complete”, Theoretical Computer Science, 1994.

▸ ▾ Cite this page

@misc{cog:reversi,
    author = "{CoG contributors}",
    title  = "{Reversi (Othello) --- Complexity of Games}",
    year   = "2024",
    url    = "https://www.isnphard.com/i/reversi/",
    note   = "[Online; accessed 2024-05-28]"
}