A quantum-mechanical version of the ancient board game go has been demonstrated experimentally by physicists in China. Using entangled photons, the researchers placed go pieces (called stones) in quantum superpositions to vastly increase the complexity of the game. They foresee the technology serving as the ultimate test for machine players that use ever more sophisticated artificial intelligence (AI).
In 1997, chess grandmaster Garry Kasparov was defeated by IBM’s Deep Blue computer – but having a machine defeat a go master was considered a greater challenge given the far higher number of possible board positions in go. Game enthusiasts were therefore stunned in 2016 when the world’s leading player, South Korean Lee Sedol, was beaten by a deep-learning algorithm from AI company DeepMind known as AlphaGo.
Developers of AI programs are now looking for an even greater challenges and want to beat humans at games such as poker and the tile-based game mahjong. These involve both randomness and what is known as imperfect information – the fact that one player cannot see another player’s hand.
Challenge to AI
Now, Xian-Min Jin of Shanghai Jiao Tong University and colleagues have used the counter-intuitive effects of quantum mechanics to introduced these elements into go, which is otherwise deterministic and completely transparent. A version of “quantum go” was proposed in 2016 by physicist André Ranchin, although this, like a quantum-mechanical take on chess developed at about the same time, had an educational aim. However, Jin and colleagues have devised their system to challenge game-playing AI programs.
Go involves two players alternately placing black and white stones at the vertices of 19 rows and columns drawn on a board. Each player aims to gradually enclose a greater area of the board with their stones than is enclosed by their opponent. In the process, rival pieces are captured by encirclement.
While based on a handful of simple rules, the game has complex patterns of play. That complexity is boosted even further in quantum go by using the superposition of states. Whereas classical go involves each player laying down a single stone on each move, the quantum version has them place pairs of “entangled” stones. Both pieces remain on the board until they contact a stone at an adjacent vertex, at which point a “measurement” collapses the entangled pair so that only one stone remains in play.
As each entangled pair is added to the board, the number of possible configurations is doubled. This makes it harder for each player to work out the best course of action. As in normal go, a player can capture an opponent’s stones by placing their own pieces on all neighbouring vertices. But those pieces must be classical. If any are in an entangled state, the player will generally not know before they carry out the respective measurements which of the two stones in each pair will remain on the board, and therefore whether or not they will succeed in encircling their opponent.
Imperfect information
Jin and colleagues explain that the measuring process can be tuned by engineering the quantum entanglement. If the two stones in each pair are maximally entangled, then the outcome of the measurement will be completely random. Otherwise, one stone will have a higher probability of remaining on the board than the other. With these probabilities known only to the person positioning the stones, the game loses some of its randomness but gains an element of imperfect information.
A quantum boost for machine learning
The Chinese researchers put these ideas into practice by generating pairs of photons entangled in term of their polarizations, then sending the photons through beam splitters and measuring coincidence counts in four single-photon detectors. With one set of outputs corresponding to a “0” and another to “1”, they were able to generate and then store a random series of 0s and 1s. This series was used to assign collapse probabilities to each half of a pair of virtual stones positioned at random vertices on a virtual go board by Internet bots.
By continuously generating entangled photons and storing the measurement results, the team produced about 100 million collapse probabilities in an hour. That, they point out, is more than enough for any normal game of go. Indeed, it is enough data to support a game with 10,000 moves played on a board with 10,000 rows and columns. Analysing the distribution of 1s and 0s in time, they were also able to confirm that there was no significant correlation between one data point and the next. The data, in other words, were indeed random.
Clearly random
Jin points out that some classical physical processes could also generate the random series of 1s and 0s (as opposed to pseudo-random series produced by computers). But he says that these processes are not easy to manipulate. The randomness that his team generated, he argues, is in contrast “much clearer due to the inherent nature of quantum mechanics”.
The team points out that the exact relation between the complexity and difficulty of quantum go “is still an open question”, but argue its beauty lies in being able to cover a wide range of difficulties rather than just one. By increasing the size of the virtual go board and tuning the entanglement, they claim it should be possible to match the difficulty even of those games that hide the most information, such as mahjong. As such, they say, quantum go could provide “a versatile and promising platform for testing new algorithms for artificial intelligence”.
The team describes the machine on the arXiv server.