Japanese scientist conquers the board game Othello

(Left) The initial board position of 8 × 8 Othello. (Right) A diagram of an optimal game record designated by our study. The game record is “F5D6C3D3 C4F4F6F3 E6E7D7C5 B6D8C6C7 D2B5A5A6 A7G5E3B4 C8G6G4C2 E8D1F7E2 G3H4F1E1 F2G1B1F8 G8B3H3B2 H5B7A3A4 A1A2C1H2 H1G2B8A8 G7H8H7H6”. The numbers in stones indicates the order of moves, and the colors of stones indicates the final result. Our study confirms that if a deviation from this record occurs at any point, our software, playing as the opponent, is guaranteed a draw or a win. Credit: arXiv (2023). DOI: 10.48550/arxiv.2310.19387

“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.

More information:
Hiroki Takizawa, Othello is Solved, arXiv (2023). DOI: 10.48550/arxiv.2310.19387

Journal information:
arXiv

© 2023 Science X Network

Citation:
Japanese scientist conquers the board game Othello (2023, November 8)
retrieved 8 November 2023
from https://techxplore.com/news/2023-11-japanese-scientist-conquers-board-game.html

This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no
part may be reproduced without the written permission. The content is provided for information purposes only.