Anybody who has played tic-tac-toe has probably worked out that the game can always be drawn, provided neither player makes a mistake. Indeed, it is straightforward to create an algorithm that guarantees a win or draw regardless of the moves made by the opponent.
This is a trivial example of a game that has been “solved” – one in which the outcome is determined from the start. There are many others that have also been solved but plenty that have not.
For game theorists and computer scientists, the difficulty in solving a game generally depends on the number of possible positions. For example, the game of Connect 4 on a 6x7 grid has 4,531,985,219,092 possible positions. Computer scientists solved this in 1988 by showing that the player who goes first can always force a win.
Billion Billlion
Checkers (or Draughts) is significantly more complex, with 500 billion billion possible board positions. This was not solved until 2007 when computer scientists showed that if both sides play perfectly, the game is always drawn.
Now Hiroki Takizawa, a bioinformatician at Preferred Networks, a computing company in Japan, has solved Othello (or Reversi), a game with 10 to the power of 28 positions. “Solving Othello, determining the outcome of a game with no mistake made by either player, has long been a grand challenge in computer science,” says Takizawa, going on to announce: “Othello is now solved.”
Othello is a 2-person board game played on an 8x8 grid that was invented in England in 1883. The game became popular in Japan, the U.S., and other countries in the 1970s with the World Championships having taken place annually since 1977 (except during the COVID-19 pandemic).
Players alternately place counters onto the board with either their black or white side facing upwards. The game’s uniqueness turns on the ability to flip black counters to white (and vice versa) when framed by counters of the opposite color. This flipping makes it particularly hard for human players to look ahead, hence the game’s difficulty.
Computer algorithms have no such trouble, of course, and have regularly beaten human players since the 1990s. Now Takizawa has modified one of these algorithms, a program called Edax, to solve the game by brute force.
Two factors have made this possible. Takizawa modified Edax to make it better suited to this kind of Othello problem-solving and then broke down the task into more manageable parts. He looked at the problem after 14 spaces had been taken with 50 empty spaces left on the board. He then looked again when there were only 36 empty spaces left.
He then ran his program on a supercomputing cluster called MN-J, owned by Preferred Networks. This cluster includes MN-3, currently ranked the 11th most powerful supercomputer in the world in terms of energy efficiency (in 2020 it was ranked No 1).
Brute Force
The result is a brute force proof that perfect play by both players leads to a draw.
That lays the foundations for a computer program that always plays the perfect game. "The Othello result is a monumental achievement for humanity," says Takizawa, getting perhaps a little carried away.
There are potential problems with Takizawa’s proof. Mathematicians have long voiced concerns that computer proofs cannot be relied on because there is no way of knowing whether a computer error might have occurred.
Takizawa acknowledges this. “Naturally, computational errors due to CPU or memory faults cannot be entirely ruled out,” he admits. “However, as the vast majority of calculations were executed on a computer cluster with Error Checking and Correction memory, we believe the results to be nearly indisputable.”
So what next for game-playing computer scientists? Takizawa speculates that chess could be the next game to be solved as a grand challenge. However, that will require significantly more work. The number of game positions in chess is a staggering 10 to the power of 43.
Takizawa thinks the sheer size of this search space means that solving it will require theoretical breakthroughs as well as computational brute force.
If you have got some spare time — and access to a spare supercomputer — why not give it a shot!
Ref: Othello Is Solved : arxiv.org/abs/2310.19387
