A passing conversation with my supervisor
Video games have been a part of my life for about as long as I can remember. From Paperboy and The Last Ninja on the Commodore 64 when I was barely old enough to operate a keyboard, to Mario Kart 8 and Zelda on the Nintendo Switch, as a postdoc at Caltech, working on quantum computing and condensed matter physics. Up until recently, I have kept my two lives separate: my love of video games and my career in quantum physics.
The realization that I could combine quantum physics with games came during an entertaining discussion with my current supervisor, Gil Refael. Gil and I were brainstorming approaches to develop a quantum version of Tetris. Instead of stopping and laughing it off, or even keeping the idea on the horizon, Gil suggested that we talk to Spyridon (Spiros) Michalakis for some guidance.
This is not the story of Quantum Tetris (yet), but rather the story of how we made a quantum version of a much older, and possibly more universally known game. This is a new game that Spiros and myself have been testing at elementary schools.
And so I am super excited to be able to finally present to you: Quantum TiqTaqToe! As of right now, the app is available both for Android devices and iPhone/iPad:
Previous quantum games
Gil and I knew that Spiros had been involved in prior quantum games (most notably qCraft and Quantum Chess), so he seemed like the perfect contact point. He was conveniently located on the same campus, and even in the same department. But more importantly, he was curious about the idea and eager to talk.
After introducing the idea of Quantum Tetris, Spiros came up with an alternative approach. Seeing as this was going to be my first attempt at creating a video game, not to mention building a game from the ground up with quantum physics, he proposed to put me in touch with Chris Cantwell and help him improve the AI for Quantum Chess.
I thought long and hard about this proposition. Like five seconds. It was an amazing opportunity. I would get to look under the hood of a working and incredibly sophisticated video game, unlike any game ever made: the only game in the world I knew of that was truly based on quantum physics. And I would be solving a critical problem that I would have to deal with eventually, by adapting a conventional, classical rules-based game AI for quantum.
Fun and Games
My first focus was to jump on Quantum Chess full-force, with the aim of helping Chris implement a new AI player for the game. After evaluating some possible chess-playing AI engines, including state-of-the-art players based off of Google’s AlphaZero, we landed on Stockfish as our best candidate for integration. The AI is currently hot-swappable though, so users can try to develop their own!
While some of the work for implementing the AI could be done directly using Chris’s C++ implementation of Quantum Chess, other aspects of the work required me to learn the program he had used to develop the user interface. That program is called Unity. Unity is a free game development program that I would highly recommend trying out and playing around with.
This experience was essential to the birth of Quantum TiqTaqToe. In my quest to understand Unity and Quantum Games, I set out to implement a “simple” game to get a handle on how all the different game components worked together. Having a game based on quantum mechanics is one thing; making sure it is fun to play requires an entirely different skill set.
Perspective
Classic Tic-Tac-Toe is a game in which two players, called X and O, take turns in placing their symbols on a 3×3 grid. The first player to get 3 of their symbols in a line (diagonally, vertically or horizontally) wins. The game goes as far back as ancient Egypt, and evidence of the game has been found on roof tiles dating to 1300 BC [1].
Many variations of the game have existed across many cultures. The first print reference to a game called “tick-tack-toe” was in 1884. In the US the game was renamed “tic-tac-toe” sometime in the 20th century. Here’s a random fun fact: in Dutch, the game is most often referred to as “Butter-Cheese-and-Eggs” [2]. In 1952, computer scientist Alexander S. Douglas at the University of Cambridge turned it into one of the first computer games, featuring an AI player that could play perfect games against a human opponent.
Combinatorics has determined that whoever plays first will win 91 out of 138 possible board combinations. The second player will win in 44 boards. However, if both players play optimally, looking ahead through all the possible future outcomes, neither player should ever win and the game always ends in a draw, in one of only 3 board combinations.
In Quantum TiqTaqToe, with the current ruleset, we don’t yet know if a winning strategy exists.
I explicitly refer to the current ruleset because we currently limit the amount of quantumness in the game. We want to make sure the game is fun to play and ‘graspable’ for now. In addition, it turns out there already is a game called Quantum TicTacToe, developed by Allan Goff [3]. That version of TicTacToe has similar concepts but has a different set of rules.
The Game
A typical game of Quantum TiqTaqToe will look very much like regular Tic-Tac-Toe until one of the players decides to make a quantum move:
At this point, the game board enters into a superposition. The X is in each position with 50/50 chance; in one universe the X is on the left and in the other it is on the right. Neither player knows how things will play out. And the game only gets more interesting from here. The opponent can choose to place their O in a superposition between an empty square and a square occupied by a quantum X.
Et voilà, player O has entangled his fate with his opponent’s. Once the two squares become entangled, the only outcomes are X-O or O-X, each with probability ½. Interestingly, since the game is fully quantum, the phase between the two entangled outcomes can in principle be leveraged to create interesting plays through destructive and constructive interference. The app features a simple tutorial (to be updated) that teaches you these moves and a few others. There are boards that classically result in a draw but are quantumly “winnable”.
A quick note on the quantumness
The squares in TiqTaqToe are all fully quantum. I represent them as qutrits (like qubits, but instead of having states 0 and 1 my qutrits have states 0, 1 and 2), and moves made by the players are unitary operations acting on them. So the game consists of these essential elements:
- The squares of the 3×3 grid are turned into qutrits (Empty, X, O). Each move is a unitary gate operation on those qutrits. I’ll leave the details of the math out, but for the case of qubits check out Chris’ detailed writeup on Quantum Chess [4].
- Quantum TiqTaqToe allows you to select two squares in the grid, providing you with the option of creating a superposition or an entangled state. For the sake of simplicity (i.e. keeping the game fun to play and ‘graspable’ for now), no more than 3 squares can be involved in a given entangled state.
I chose to explicitly track sets of qutrits that share a Hilbert space. The entire quantum state of the game combines these sets with classical strings of the form “XEEOXEOXE”, indicating that the first square is an X, the second is Empty, etc.
Victory in the multiverse
So, when does the game end if these quantum states are in play? In Quantum TiqTaqToe, the board collapses to a single classical state as soon as it is full (i.e. every square is non-empty). The resulting state is randomly chosen from all the possible outcomes, with a probability that is equal to the (square of the) wave-function amplitude (basic quantum mechanics). If there is a winner after the collapse, the game ends. Otherwise, the game continues until either there is a winner or until there are no more moves to be made (ending in a draw). On top of this, players get the option to forfeit their move for the opportunity to cause a partial collapse of the state, by using the collapse-mode. Future versions may include other ways of collapse, including one that does not involve rolling dice! [5]
Can you beat the quantum AI?
Due to quantum physics and the collapse of the state, the game is inherently statistical. So instead of asking: “Can I beat my opponent in a game of Quantum TiqTaqToe?” one should ask “If I play 100 games against my opponent, can I consistently win more than 50 of them?”
You can test your skill against the in-game quantum AI to see if you’ve indeed mastered Quantum TiqTaqToe yet. At the hardest setting, winning even 30% of the time after, say, 20 games may be extraordinary. The implementation of this AI, by the way, would have been a blog-post by itself. For the curious, I can say it is based on the ExpectiMiniMax algorithm. As of the moment of this writing, the hardest AI setting is not available in the app yet. Keep your eyes out for an update soon though!
The future
“Perhaps kids who grow up playing quantum games will acquire a visceral understanding of quantum phenomena that our generation lacks.” – John Preskill, in his recent article [6].
From the get-go, Quantum TiqTaqToe (and Quantum Chess) have had outreach as a core motivation. Perhaps future quantum engineers and quantum programmers will look back on their youth and remember playing Quantum TiqTaqToe as I remember my Commodore 64 games. I am convinced that these small steps into the realm of Quantum Games are only just the beginning of an entirely new genre of fun and useful games.
In the meantime, we are hard at work implementing an Online mode so you can play with your fellow human friends remotely too. This online mode, plus the option of fighting a strong quantum AI, will be unlockable in-game through a small fee (unless you are an educator who wishes to introduce quantum physics in class through this game; those use cases are fee-free courtesy of IQIM and NSF). Each purchase will go towards supporting the future development of exciting new Quantum TiqTaqToe features, as well as other exciting Quantum Games (Tetris, anyone?)
Just in case you missed it: the app is available both for Android devices and iPhone/iPad right now:
I really hope you enjoy the game, and perhaps use it to get your friends and family excited about quantum physics. Oh, and start practicing! You never know if the online mode will bring along with it a real Quantum TiqTaqToe Tournament down the road 😉
References
[1] https://en.wikipedia.org/wiki/Tic-tac-toe
[2] The origin of this name in Dutch isn’t really certain as far as I know. Alledgedly, it is a left-over from the period in which butter, cheese and eggs were sold at the door (so was milk, but that was done separately since it was sold daily). The salesman had a list with columns for each of these three products, and would jot down a cross or a zero whenever a customer at an address bought or declined a product. Three crosses in a row would earn them praise from the boss.
[3] https://en.wikipedia.org/wiki/Quantum_tic-tac-toe
[4] https://arxiv.org/abs/1906.05836
[5] https://en.wiktionary.org/wiki/God_does_not_play_dice_with_the_universe
Quantum Frontiers 
Good, I have spent lots and lots of hours with Paperboy on C64, too. The quantum tic-tac-toe is surely deeper – but is there a way to make it at least as entertaining as the classical one?
The Dutch name story sounds persuasive. We have a harder dilemma for the Czech name. In Czech, the game is known as piškvorky which is plural for piškvorka. One theory is that it’s a name of a beetle, not a truly real one, but a hybrid of two words. The second theory which actually makes some sense is that it’s from Slovak “piš do čtvorca”, i.e. “write into a square”, which was misunderstood and changed to “piškvorka”.
Awesome, interesting to learn that this well-known game has acquired funky names in different languages. Also, since classical tic-tac-toe is included as a subset of tiq-taq-toe, I’d say it is *at least* as entertaining 😉 Thanks for checking it out though!
Pingback: Four short links: 16 July 2019 | Technology News and Markets
Pingback: Four short links: 16 July 2019 – sportsguru
It would be good to hear more about model you are using to ensure unitarity of each step. It was a problem of many previous attempt with the game (including Wikipedia example). And there is also difficulties with quantum analogies of sequential games (In fact, I do not sure, how this issue is resolved in mentioned Christopher Cantwell work as well)
Perhaps I misunderstand your concern, but let me try to clarify this a bit more. For TiqTaqToe I literally represent each of the 9 squares as a qutrit, and moves are literally implemented as unitary matrices acting on them (e.g. like the qutrit generalization of the square-root swap gate here https://en.wikipedia.org/wiki/Quantum_logic_gate). So I am certain that at every step of the game, the full quantum state can be obtained from the ‘all-empty’ (each qutrit in the 0 state, let’s say) by unitary gates only. There is of course a *classical* layer of logic on top that checks which move the user is trying to input, and disallows certain moves to be made to keep the game playable. Does that answer some of the concerns you had?
I am concerned not about obtaining unitarity from all-empty, but about making unitary operation for each step. The game has set of positions marked by number of step Sk = S1,S2,…,S9 and I supposed the quantum version at each step respecting rule of game should provide unitary operation for transition between superposition of states from Sk to superposition of states in Sk+1, but in previous examples of implementation the unitary operators itself are not provided. So I wonder about construction of such operators, because it is not quite clear how to do that after considering particular examples of configurations.
PS: I mean Sk is set of accessible positions at step k, e.g. 9 positions for S1, 72 positions for S2 etc.
There are actually more than 9 configuration possible for S1 in this game, since you can also select 2 squares instead of just one. But let’s leave that aside for now.
I can represent every configuration of the game as a string of 9 characters such as “EEEEEEEEE” for all-empty, or “XEEEEEEEE” for the state with an X on the first (top-left) square.
So let’s do an example. We start from “EEEEEEEEE”, and player X performs a quantum superposition move on squares 3 and 8. We will now have two non-zero configurations in the Hilbert space: “EEXEEEEEE” + “EEEEEEEXE”, both with amplitude 1/sqrt(2). This move, in the game, is encoded as follows. I consider the two qutrits at squares 3 and 8, and extract their quantum state. In this case, they start in the state “EE”. This is one out of 9 possible states (two qutrits), and I could construct a basis such as (“EE”, “EX”, “EO”, “XE”, “XX”, “XO”, “OE”, “OX”, “OO”) in which this state would be (1,0,0,0,0,0,0,0). The unitary operator for superposition can then be written in this basis as a 9×9 matrix, and when applied to the state would give me back something like (0,1,0,1,0,0,0,0,0)/sqrt(2), telling me that the new state of squares 3 and 8 is “XE” + “EX”.
Player O can then make another superposition, let’s say on squares 1 and 2, so that we have “OEXEEEEEE” + “EOXEEEEEE” + “OEEEEEEXE” + “EOEEEEEXE” with adjusted amplitudes. If it had been an entangling move, we would’ve gotten other amplitudes again, etc.
In other words, **I keep track of the entire (sparse) quantum state of the game**, and player moves are literally unitary operators acting on pairs of qutrits. When the player selects two squares I know exactly what that unitary operator would do to the quantum state, and I update it accordingly. In fact the number of states in the Hilbert space for 9 qutrits is 3^9, but not all of them are valid game configurations (and many of them are just rotations/mirrors of others). So I could (and did, at some point) really pre-compute those unitary matrices and track the entire non-sparse state. It’s just that there is really no need for that, and it uses more memory than necessary.
Does that clarify things a bit more?
Thank you, for explanation, but it is again rather description using states, not operators. If it is compatible with principles of QM? – you considered some state |a> that may be in some superposition of basic “classical” states and your program have full knowledge about that, i.e. formally may use map U(a)|a>, and in general, it is nonlinear map. The problem is similar with discussed in no-cloning theorem and may be illustrated already using your example with two first step, but I afraid it would be too long discussion. In short, I did not see an appropriate consideration of sequential quantum gates in a literature.
Sorry for mistype, should be ‘sequential games’, not ‘gates’, of course
Pingback: Auction-based Tic Tac Toe: Solution | Combinatorics and more
Pingback: Quantum tic-tac-toe, Stanley Kubrick and Moon landing fakes, why become a particle theorist? – MrPyro
I am afraid the quantum games and the AI described in this post is unlikely to lead any generation of players to learn or intuit quantum mechanical phenomena discovered in nature since they’re different in many regards. Introducing entanglement rules might provide a sense different from the conventional games of statistical probabilities but by no means adequate in characteristics to understand the quantum phenomena of nature that has an infinite varieties of fields and forces to influence the outcomes.
Pingback: Dört kısa bağlantılar: 16 Temmuz 2019 – Haber, Son Dakika Haber ve Güncel Son Haberler
Pingback: Jogo da Velha quântico – Computação e Informação Quântica
Pingback: Bas|ket>ball: A Game for Young Students Learning Quantum Computing | Quantum Frontiers
Pingback: AW Academy & Teak – Mika Le Gall
Pingback: Rock Paper Scissors: A Quantum Computing Twist - Featured Today Only
Pingback: Rock Paper Scissors: A Quantum Computing Twist – Data Science Austria
Pingback: Rock Paper Scissors: A Quantum Computing Twist | by Kory Becker | Might, 2023 – Comand Osia
Pingback: Rock Paper Scissors: A Quantum Computing Twist | by Kory Becker | Could, 2023 – Endelivered
Pingback: Rock Paper Scissors: A Quantum Computing Twist | By Kory Becker | May, 2023 - TrandingNews
Pingback: Rock Paper Scissors: A Quantum Computing Twist | by Kory Becker | May, 2023 - Earth Prime News Media
Pingback: Rock Paper Scissors: A Quantum Computing Twist | by Kory Becker | May, 2023 – SynopticX
Pingback: Rock Paper Scissors: A Quantum Computing Twist | By Kory Becker | May, 2023 - Künstliche Intelligenz Die Zukunft Ganz Nah
Pingback: Rock Paper Scissors: A Quantum Computing Twist | by Kory Becker | Could, 2023 - Metaverse