Othello, a game with 10²⁸ variations, has been cracked by a supercomputer!

Othello is also known as Othello, which is named after Shakespeare's famous play Othello. The black and white sides symbolize the protagonist Othello and his wife Desdemona; the game of chess symbolizes the interaction between the two. Now, scientists have used supercomputing clusters to exhaust all the variations of the game and cracked Othello. The lovers have gone through more than 400 years of jealousy and betrayal, regret and tears, and finally embraced each other in an equal manner.

Written by | Jiawei

A minute to learn, a lifetime to master.

——A proverb known to Othello fans around the world

I believe that most people born in the 1980s and 1990s first came into contact with Othello in an electronic dictionary called "Wenquxing". At the same time, because the "social status" of Othello is far from being comparable to that of Go, which has a strong cultural tradition, and chess, which has its own elite temperament, many people may think that Othello is just a simple and easy-to-learn children's chess game. Little do they know that Othello is different from other chess games because of its unique rules. In situations where the situation changes are limited, such as the endgame in Gobang or chess, chess players can often easily see through the situation. But even if Othello leaves only the last 6 squares empty, it is quite difficult to calculate. This relative complexity is determined by the characteristics of Othello. It is not as easy to understand "at a glance" as other chess games, so it is easy to reverse the situation. In the later stages of the game, it may take only a few rounds to make a large number of opponent's pieces turn against each other, thus reversing the situation.

Therefore, Othello not only has a theoretically astonishing number of 10^28 combinations, but also requires a very deep level of thinking. Top players even have to think about the chess strategy for the final battle from the early and middle stages.

The complexity of Othello can also be seen from the following point: the more popular Gobang (five in a row) was cracked (solved) by computer scientist Victor Allis as early as 1993, and it was proved that in the absence of special opening rules, there is a winning strategy for the first player in Gobang; but in the past 30 years, although the computing power mastered by humans has increased exponentially, it has not been possible to exhaust all the variations of Othello - until the end of October this year, Japanese computer scientist Hiroki Takizawa made a milestone breakthrough and announced that he had cracked Othello!

At the same time, the research on Othello also has a strange connection with the "coup" in the management of OpenAI that caused an earthquake in the AI ​​industry not long ago.

But before I go any further, for the benefit of those readers who are not familiar with Othello, let me first briefly introduce the rules and history of this game.

What is Reversi

Othello is also called Reversi or Othello in Chinese and Reversi or Othello in English.

The prototype of Othello was first invented by the British in the late 19th century. In the 1970s, it was developed and promoted by the Japanese Goro Hasegawa. He borrowed Shakespeare's famous play "Othello" to rename the game (Japanese "オセロ"), and then we have the Othello that everyone plays now. Why borrow Shakespeare's famous play? Because the male protagonist Othello in the play is black and his wife is white. Othello was instigated by villains and suspected his wife of infidelity, and eventually killed her with his own hands. Later, the truth came out, he regretted it and committed suicide. Othello was named after this story of the struggle between blacks and whites, so the chess pieces have two sides, black and white.

Reversi chess pieces and board. Image source: Reversi - Wikipedia

In some places, the chess pieces are red and green on the front and back. At this time, it is also called "Apple Chess" because apples are divided into red apples and green apples.

Basic rules:

• The most standard opening is to place 4 black and white pieces in the 4 squares in the center of the board. Usually the black pieces go first, and both sides take turns to place their pieces.

Othello opening. | Image source: Japan's weakest Othello AI battle platform, weakest Osero game interface

• As long as you place a piece on the board and any of your own pieces on a line (horizontal, vertical, or diagonal) that sandwiches the opponent's pieces, you can turn these opponent's pieces into your own pieces (just flip them over). The sandwiched positions must all be the opponent's pieces, and there cannot be any empty spaces. And you can only place a piece where you can flip the pieces.

• A move can flip a piece in several directions. Any trapped piece must be flipped over. A player cannot choose not to flip a piece. A newly-placed piece must be the one that is trapping the opponent's piece in order to flip the opponent's piece. A piece that is trapped by flipping the opponent's piece cannot be flipped over.

• If one player has no legal moves to make, he must let the other player continue to make moves until he has a legal move. If neither player has any legal moves to make, the game is over.

The side with more pieces on the board at the end of the game wins. If the number of pieces is the same, it is a draw.

Zermelo's theorem and the solved game

The study of any chess game is inseparable from the famous theorem published by German mathematician Zermelo in 1913:

In a finite game between two people, if both players have perfect information and luck is not involved in the game, then one of the first or second players must have a winning/unbeatable strategy.

Note that many people do not understand this theorem correctly, and even think it is just an obvious nonsense. To highlight the significance of the theorem, please think about the game of "Rock, Paper, Scissors".

Without cheating, "Rock, Paper, Scissors" is a game of luck, and there is no winning strategy. So why can we believe that a non-luck game must have a winning/unbeatable strategy? There is indeed a fundamental difference between games that are mixed with luck and games that are not mixed with luck, but this is by no means obvious and requires mathematical proof.

Here is a popular proof for easy understanding: We assume that both players are infinitely wise. If one player loses at a certain move (such as being checkmated in chess), then he will still lose after retracting his move, otherwise it will contradict our "infinite wisdom" (because he made a wrong move in the previous move). By analogy, we know that the outcome of the game is determined at the beginning - that is, one player has a winning strategy.

In fact, Zermelo's theorem is the cornerstone of perfect information game theory. From this we know that in every conventional chess game that can be played in a finite number of moves, there is a side that is sure to win or at least unbeatable. The subsequent question is: find the side that has an unbeatable strategy.

When we confirm that there is a winning/unbeatable strategy for the first or second player in a game, we say that the game is a solved game. There is no unified standard translation for solved game at present, but it can be directly translated into solved or cracked game.

For cracked games, there are three levels of strength.

Ultra-weak solution: A theoretical proof that one party can guarantee to win the game, or the game will inevitably end in a draw, but no specific winning or drawing method is required. This solution only requires the use of mathematical tools to analyze the abstract properties of the game without exhausting all possibilities.

Weak solution: Give an algorithm that can guarantee that a player wins the game or that no player loses the game, starting from the initial state of the game. This solution usually requires exhausting all branches of the game tree or using a pre-generated database.

Strong solution: Give an algorithm that can start from any state of the game and give the best move, regardless of whether the previous move was perfect. This solution requires exhausting all nodes of the game tree or using a pre-generated database.

In 1993, Gobang was cracked. In October this year, Othello was cracked. We now know that if two gods with infinite computing power were to play Othello, they would always end up in a tie. In other words, Othello is a very fair game. The first or second player does not gain the slightest advantage. This is consistent with the feeling of a high-level Othello player.

At the same time, because it is a weak solution, Takumi Takizawa, a bioinformatician and computer scientist from Preferred Networks, a Japanese startup AI research and development company, also enumerated the best strategies for both players from the beginning of the game.

(It should be noted that humans have not cracked Go and chess. Although today’s chess-playing AIs are far more powerful than humans, they have not found the most correct way to play. They have simply found a more correct way to play than we humans.)

Technology and significance

Since the infancy of computer science, completely cracking pure strategy games such as chess has been considered an extraordinary achievement of human intelligence. It has also been a major topic in the field of artificial intelligence (AI) ever since. Early researchers included Charles Babbage and Claude Elwood Shannon. As machine learning techniques and computing power have improved, humans have created AIs with super-high chess skills (such as the landmark AlphaGo), but these super AIs cannot perfectly crack these games. Not long ago, it was generally believed that Othello was too complex to be cracked. So it has always been a grand challenge in the field of artificial intelligence.

In order to crack Othello, Takumi Takizawa used modern technology to enhance Edax, a chess program that was already very powerful in the 1990s, and then broke the task into more manageable parts. He first analyzed the situation when there were 50 empty spaces on the board, and then examined all meaningful situations when there were 36 empty spaces. He was pleasantly surprised to find that it seemed that the existing computing power was sufficient to support a weak solution to Othello.

The path in bold is an optimal branch. A perfect player should follow the bold strategy tree for the corresponding position. | Image source: OTHELLO IS SOLVED

He ran his program on a supercomputing cluster owned by Preferred Networks called MN-J, which includes the MN-3 supercomputer, currently ranked 11th in the world in terms of energy efficiency (ranked 1st in 2020).

Finally, Takizawa announced in his paper “Othello is Solved” that he had cracked Othello. This was a major achievement for mankind, demonstrating the great progress of computer science and artificial intelligence technology.

Another thing worth noting is that the number of positions that actually need to be explored to crack Othello is much smaller than the number estimated in previous studies. Takizawa believes this is because his team has a more sophisticated search algorithm configuration. It was precisely because the estimated amount of calculations was very large that many people were discouraged. Perhaps the lesson of this story is that paper analysis is always shallow, and you must practice it to know it well.

Reversi and AI

Japan is probably the country with the most Othello fans. According to statistics from 2005, there are about 60 million Othello fans in Japan (about 15 million Japanese shogi fans, about 5 million Go fans, and about 3 million chess fans).

Therefore, it is only natural that Japanese scientists finally cracked Othello. Takizawa looks forward to a breakthrough in chess in the future. The complexity of chess is 15 orders of magnitude higher than that of Othello. Cracking chess is even one of the driving forces behind the development of computer and AI technology.

However, in addition to super AI, some people are planning to do the opposite. Japanese AI company AVILEN feels that today's chess AI is too powerful, so it has developed a black and white chess AI called "Othello". Its goal is to lose to human players as much as possible, rather than pursuing victory like other AIs.

The principle of this AI is to modify the AI's understanding of the rules of Othello so that the AI ​​always chooses the most disadvantageous move for itself, while giving the human player the greatest advantage. In this way, it is difficult for human players to lose to the AI, and even some special strategies are needed to do so. Othello publicly challenges human players online. As of July 29, 2019, it has played 220,000 games and won only more than 1,000 games, with a winning rate of less than 0.5%. It even attracted challenges from some professional Othello players, who wanted to see if they could lose to it.

Some researchers believe that Othello breaks the conventional thinking in the field of artificial intelligence and shows another possibility of AI. It also triggers some people's thinking about AI, such as whether AI has its own will and whether AI can understand human emotions...

To a certain extent, the AI ​​experiment on Othello does provide clues for the above thinking.

On November 17, OpenAI, which has become a leader in the field of AI by developing ChatGPT and GPT-4, announced without warning that the former CEO Sam Altman was dismissed by the board of directors. This was seen as a "coup". The subsequent plot was even more ups and downs, and many details have not yet been disclosed.

One of the theories is that OpenAI has made another major breakthrough in the field of AI, and their chief scientist Ilya Sutskever has doubts about the latest technology and does not want to commercialize it, so he has a disagreement with Sam Altman. Eventually, the conflict intensified and triggered a major purge of management. Of course, we later learned that Ilya regretted it again and decided to stand on Altman's side to oppose the board's resolution.

So in which direction is OpenAI most likely to achieve a breakthrough? In fact, Ilya revealed to the media not long ago that he believes:

“When you train a large neural network to accurately predict the next word in a variety of texts, you are actually building a model of the world. These texts are essentially a mapping of the real world. Neural networks are constantly learning about all aspects of the world, covering humans, human environments, expectations, dreams, motivations, and so on. AI learns to compress, abstract, and represent the human world in a usable way.”

The above statement may seem confusing, but to use a popular analogy related to the theme of this article, it is like showing a chess record to AI without telling it that it is a chess record. In the end, AI learned to play chess, but it didn't know it was playing chess.

Whether OpenAI has verified this concept - proving that the Large Language Model (LLM) ultimately re-represents the world in language simply by learning language - we don't know yet, but another recent Othello study supports this theory.

Image source: https://openreview.net/forum?id=DeG07_TcZvT

The researchers used 20 million sequence samples sampled from a large number of actual game matches to train a neural network called OthelloGPT. OthelloGPT does not understand the rules of the game or the game concepts represented by the input sequence, it only comes into contact with the sequence string of text tags. Similar to the training of large language models for natural language, the training goal of OthelloGPT is to predict the next possible string in the sequence.

After obtaining enough chess records, OthelloGPT can accurately predict future legal chess moves, even for strings that have never been seen in the training data (that is, sequences in chess records)!

OthelloGPT does not know that it is playing Othello, but by reading a large number of chess records (strings of letters and numbers), it finds the rules and actually learns to play chess. Although for OthelloGPT, it is just predicting the generation pattern of the string.

Finally, if any of you become interested in Othello after reading this article, I would like to recommend an introductory book, “Othello Guide” (written by Brian Rose), which can be found online.

References

[1] OTHELLO IS SOLVED, 2310.19387.pdf (arxiv.org)

[2] Reversi - Wikipedia

[3] Japan's weakest Othello AI battle platform: The Weakest Osero | PROJECTS (Project) | AVILEN Co., Ltd.

This article is supported by the Science Popularization China Starry Sky Project

Produced by: China Association for Science and Technology Department of Science Popularization

Producer: China Science and Technology Press Co., Ltd., Beijing Zhongke Xinghe Culture Media Co., Ltd.

Special Tips

1. Go to the "Featured Column" at the bottom of the menu of the "Fanpu" WeChat public account to read a series of popular science articles on different topics.

2. Fanpu provides a function to search articles by month. Follow the official account and reply with the four-digit year + month, such as "1903", to get the article index for March 2019, and so on.

Copyright statement: Personal forwarding is welcome. Any form of media or organization is not allowed to reprint or excerpt without authorization. For reprint authorization, please contact the backstage of the "Fanpu" WeChat public account.