Reversi - Othello AI

Black: 2 White: 2 Your turn
Opening: None

About Reversi

Reversi is a strategic board game for two players played on an 8x8 board. Players take turns placing stones of their color on the board to surround the opponent's stones and flip them to their own color. The goal of the game is to have more stones of your color than your opponent at the end of the game.

Heuristic Used

This implementation uses a heuristic based on positional weighting on the board. Each cell on the board is assigned a weight according to its strategic importance (for example, corners have the highest value). The AI utilizes the Minimax algorithm with alpha-beta pruning to predict the best possible move up to a certain search depth.

Research on the Game Othello - Reversi

Introduction

Chess, Go, and Reversi are among the most popular strategic and combinatorial games. These games have existed for a considerable time and truly deserve the title of "royal games." In this article, I will discuss one of the lesser-known games from this trio: Reversi. In terms of complexity, it is simpler than both Chess and Go, featuring more straightforward rules. This simplicity is its charm—it has the easiest rules, and games are relatively quick to play.

I have been playing this game for 17 years. Gradually, as a beginner, I discovered the simplest strategies and noticed that certain positions are more critical than others. The most important are the corners, followed by the edges, and finally the interior. The first player to occupy the corners gains an advantage, often leading to victory. This was my beginner's perspective. Most beginners in this game tend to develop a greedy technique during play, aiming to have the most stones of their color flipped. However, this approach reduces their mobility, giving the opponent greater flexibility and, consequently, a significant advantage towards the end of the game.

Artificial Intelligence

It’s no coincidence that programs and artificial intelligence, with their algorithms, today leave no chance for humans to overcome them. Interestingly, it was Reversi that machines mastered faster than Chess or Go. In the game, they use the most effective algorithms, continuously improving their strategies, and primarily in Reversi, they plan up to 30 moves ahead, utilizing extensive libraries of verified openings. By the mid to late game, they can foresee all possible outcomes, which is nearly impossible for humans, even with the best strategies. For more details, refer to articles on artificial intelligence (AlphaGo, AlphaZero) available on this website.

WOC Players

Upon analyzing games of top players, known as WOC (World Championship) players, I concluded that even the best players cannot overcome a loss of -20 stones by the end of the game (depending on the game’s opening). This means they lose by at least 20 stones (with their best performance using more complex openings). This is quite substantial. If a human cannot find the perfect move, even a good move may not be sufficient, as making just one imperfect move can lead to defeat by the program.

Championship in Prague 2018:

After watching several matches of top players, I must say that WOC players do not manage to play perfect moves even remotely. Matches are often decided by chance in the game's final stages. Even the best players make numerous poor moves that flip positional advantages multiple times, from player X to player Y and vice versa. If you were to play against any player in this championship using the best Reversi program, the results would likely show players not managing to secure more than 10 stones out of 64. The top players would finish around 44:20 in favor of the program. The program decisively defeats them with a significant lead. This championship in Prague was ultimately won by a young Japanese player.

Why Did This Young Japanese Player Win?

Besides recent improvements, his gameplay reflects better current raw strength (combinatorial abilities) slightly superior to his opponents in the top three. However, the two older players have greater experience, and in the match against the older Japanese top player, luck played a significant role. In the final game, his gameplay demonstrates better current combinatorial vision, which likely decided the match.

Championship Tokyo 2019:

After watching several matches of top players, I must say that WOC players do not manage to play perfect moves even remotely. Matches are often decided by chance in the game's final stages. Even the best players make numerous poor moves that flip positional advantages multiple times, from player X to player Y and vice versa. If you were to play against any player in this championship using the best Reversi program, the results would likely show players not managing to secure more than 10 stones out of 64. The top players would finish around 44:20 in favor of the program. The program decisively defeats them with a significant lead. This championship in Prague was ultimately won by a young Japanese player.

Game Analysis

Opening: Tiger, up to the 11th move.
Mid-Game: The young Takahashi deviates to C4 instead of the ideal, perfect move to D7, resulting in a loss of 2 stones by the game's end.
From this point, maintaining a perfect line of moves is impossible. The young Japanese player makes errors at F8 and G5, leading to a loss of 4 stones by the end.
After two more moves, this escalates to a loss of 8 stones. The older player messes up but maintains a 4-stone advantage.
The younger player attempts to complicate the game around the 20th move, but the older player fails to capitalize on the young player's suboptimal move at B4, reducing the advantage.
Overall, the game remains balanced in the mid-game. By the 31st move, the older player makes a poor move, losing the advantage.
At the 41st move, the younger player makes another mistake, losing a small advantage.
The older player then gains a 6-stone lead by the end of the game. The older player does not make any gross errors and maintains a 4-stone advantage until the end.
The younger player ultimately loses by only 4 stones in favor of the older player.

Strategy for Perfect Play

It consists of three parts:

  1. Knowledge, Strategies, and Techniques: These contribute to victory, including a library of verified openings and in-game techniques.
  2. Experience and Memory: Derived from numerous played matches, recognizing similar patterns and positions, requiring years of practice. This is akin to training neural networks.
  3. Raw Combinatorial Strength: The ability to envision as many moves as possible and predict the game's layout by exploring numerous combinations. This requires innate talent and years of training to enhance these abilities, as discussed in articles on artificial intelligence.

These are the fundamental points a grandmaster must master. Even against the best opponents, achieving a perfect game is impossible, resulting only in a draw. AI has reached such a level that only exceptionally rare instances might result in a narrow victory otherwise. Theoretically, it's possible because no program can see the entire game from start to finish, encompassing all variations.

However, a human grandmaster can achieve a draw, but it requires perfect concentration, time, and mastery of the three components mentioned. Humans are fallible and often err in the third aspect. Additionally, humans must possess such advanced abilities that they can foresee the game's outcome at any given moment without necessarily visualizing exact layouts, but recognizing patterns that lead to their advantage.

AI, on the other hand, is incredibly creative, finding combinations humans might never see, often uncovering exceptions in Reversi strategies by exploring all possible game combinations.

In any case, if you know a sequence of perfect games and have honed your combinatorial skills, you can achieve numerous draws even against the most perfect programs. From my own experience, it's possible. Similarly, in Chess, it’s more challenging due to a larger state space, and in Go, a master might need to train, perhaps 70-100 years, to train their neural networks.