## November 9, 2023

Computer Scientist Solves The Game of Othello (The Physics arXiv Blog, 11/07/23))

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 BilllionCheckers (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."

Posted by Orrin Judd at November 9, 2023 5:22 AM