Japanese scientist conquers the board game Othello

"Othello is now solved." With that summation, a researcher at a Japanese computer company confirmed yet another milestone in supercomputing achievement.

Othello, a 140-year-old game rooted in the Shakespearean drama of the same name that depicts conflict between the Moor of Venice and Desdemona, does not seem complex at first glance. It is played on a board with black and white disks strategically positioned in squares along eight rows and eight columns.

The challenge, according to bioinformatician Hiroki Takizawa, is to conceive a game plan "with no mistake made by either player."

"[That] has long been a grand challenge in computer science," he said. "In this paper, we announce that we have weakly solved Othello."

Applied to game theory, a "weak" solution refers to an algorithm that ensures either a win against any possible moves by an opponent from the beginning of a game, or a draw. A "strong" solution is an algorithm yielding perfect moves from any board position even after mistakes by either of two players are made.

The task of "solving" Othello is a huge one. There are 10 octillion possible game positions, which means if you happened to have a laptop at the birth of the universe and began testing one move per second, you'd still be far from completion today.

Such a task is almost child's play for today's massively parallel computer systems.

Takizawa utilized his company's MN-J supercomputing cluster to take on the task. Although more powerful computers have been constructed in the last few years, the MN-J system includes an energy-efficient component that, with 21.1 gigaflops per watt of power, was considered the world's most powerful in 2020. It is now No. 11.

Takizawa expanded upon Edax, a computer program that was first used to analyze Othello strategy years ago.

"Our breakthrough came by improving search efficiency and modifying the latest Othello software," Takizawa said.

"The Othello result is a monumental achievement for humanity," Takizawa said, "which demonstrates the remarkable advances in computer science and AI technology. Solving Othello has been one of the grand challenges for AI."

Computers have been crunching numbers and besting world champions in numerous games for years.

IBM's DeepBlue conquered World Chess Champion Gary Kasparov in 1997, the first time a computer beat a human chess player in formal game pay.

Similarly, Google's AlphaGo in 2016 defeated the world champion Go payer Lee Sedol, considered one of the game's strongest players in history. Go is considered more challenging than chess. While brute force calculations are successfully used in machine chess play, that approach is not as productive in Go, where computer strategy relies more on reinforcement learning.

And computers have been programmed to play Connect-4—a game with 4.5 trillion grid scenarios—perfectly; they never lose.

Takizawa acknowledges that some may question the legitimacy of computation proofs. Memory faults and CPU glitches can't be ruled out, he said. However, he noted that Error Checking and Correction memory was utilized throughout the process. He stressed that even in the event of a computer error, the chance of overturning his conclusion "is extremely low."

His report, "Othello is solved," was uploaded to the preprint server arXiv.

© 2023 Science X Network