In a game of tic-tac-toe, (or Xs and Os, or noughts and crosses), the first player places an $X$ in one of the squares on a $3 \times 3$ board, and then the second player places an $O$, and then the first player places an $X$ again, and so on until either one of the players gets three-in-a-row and wins, or else the squares are all filled and the game ends in a draw. Tic-tac-toe is a popular game among children, but for most the game becomes uninteresting once they realize that there exists an optimal strategy: If both players follow a simple rule for where to place each piece, essentially constantly blocking each other, the game is guaranteed to end in a draw. We say that the game is "solved": There is an optimal strategy, an *algorithm* if you will, and if both players commit to following it, then the game is decided before it has even begun. But through the introduction of a little *quantum physics*, the game suddenly becomes a lot more interesting again! Fear not though: You do not need to understand any quantum physics to understand quantum tic-tac-toe—or TiqTaqToe, as it is also known. Experience has shown time and again that the ruleset is actually quite easy for new players to grasp! But finding a good *strategy* to outsmart your opponent, on the other hand, turns out to be quite challenging—even to those of us who both understand quantum physics, and who have been playing this game for a while! ### 1. Rules #### 1.1 Setup Each player is given a set of d4 dice of various colours: The first player ($X$) gets five colours, and the second player ($O$) gets four colours, so that we have nine colours in total—the same as the number of squares on the board. ![[IMG_8650.jpeg|400]] #### 1.2 Making a Move For each turn, the player will: - Place either one or two dice of a single colour that has not yet been used. - If the player chooses to place one die, then it must be placed in an empty square with the number $4$ up. - If the player chooses to place two dice (of the same colour), then the dice must be placed in two different squares, at least one of which are empty. The other square could also be empty, or it could contain one of the opponent's dice. - *You may not place a die in a square that already houses one of your own.* Let us look at each of the possible moves in turn. ##### The Classical Move If the first player places a singular die in an empty square, then they have to place the die with the number $4$ pointing up. This shows that "all" of the colour is in that square; in other words, that the probability that the die will lead to an $X$ being drawn in that same square upon observation (which happens towards the end of the game—we will get to that shortly) is $4/4 = 100\%$. ![[IMG_8652 1.jpeg|400]] ##### The Superposition Move Alternatively, the player may choose to place two dice *of the same colour* in two different squares. Then the player must place the dice with the number $2$ up. This shows that each square houses "half" of the colour. More precisely, it shows that there is a $2/4 = 50\%$ chance that the colour turns into an $X$ in the first square, and a $2/4 = 50\%$ chance that the $X$ instead ends up in the second square. ![[IMG_8653 1.jpeg|400]] Note that the squares do not have to be adjacent. ![[IMG_8654 1.jpeg|400]] So one may place either one or two dice of a colour per turn. One may *not* place more than two dice at once, and one may not place dice of a colour that was already used on a previous turn. Furthermore, it is not allowed to place dice with the numbers $1$ or $3$ facing up, even if they would sum to $4$. ##### The Entangling Move If the first player already put down a singular die, then the second player may "invade" the opponent's square by placing two dice of a colour, one in their square and the other in an empty square. As before, they will place the dice with the number $2$ pointing up. ![[IMG_8655 2.jpeg|400]] But given that we are interpreting the numbers as probabilities, this gives us something of a strange situation: The board is now telling us that there is a $100\%$ probability for an $X$ to be observed in the middle square, *and* a $50\%$ probability that an $O$ is observed in the middle square. There can't be more than one symbol per square, so this is clearly impossible. The game solves this conundrum by ruling that when player $2$ "invades" player $1s square, then they also "drag" half the opponent's colour with them over to the previously empty square. This results in the following board: ![[IMG_8656 1.jpeg|400]] Again, the squares do not need to be adjacent: ![[IMG_8666.jpeg|400]] ##### The Half-entangling Move If player $1$ started by placing two dice, ![[IMG_8659 1.jpeg|400]] then player $2$ may again "invade" one of the opponent's squares: ![[IMG_8660 1.jpeg|400]] As before, the result is that half the opponent's colour is "dragged" over to the previously empty square. ![[IMG_8661 1.jpeg|400]] Note that the blue dice on the left are now shifted to have the number $1$ pointing up. This shows that the colour has been halved again, which means that the probability that the blue dice resolves to an $X$ in the bottom square is $1/4 = 25\%$; likewise for the middle square, while the probability that it resolves to the rightmost square remains unchanged at $2/4 = 50\%$. If player $2$ so wishes, they may later spend a turn to "invade" the right square too: ![[IMG_8662 1.jpeg|400]] Again the opponent's colour is "dragged along" into the empty square: ![[IMG_8665 1.jpeg|400]] Now the blue colour is maximally spread over the board, and there is an equal probability that it will resolve to an $X$ in each of the four squares. ##### Why so many dice? Now we see why we needed four dice per colour: Because each colour can be split in up to four parts through the moves described above! The reason why we need nine colours is also simple: If each player insists on only using classical moves, then the board will only be full after nine colours have been used—and the players have simply played a game of normal tic-tac-toe! Do you see why a colour could not be split in more than four parts, for example to eights? Right: To do this, the invading player would have to break the rule mentioned at the very start, namely that you *can not place a die in a square that already houses one of your own.* In physics-speak, to be explained in Sect. 2, we say that players can't entangle with themselves. #### 1.3 The Game Ends When there are no empty squares left, there are no more legal moves to be taken, which means that it is time to figure out how where on the board the pieces represented by the various colours end up. This is decided via—you guessed it—dice rolls! Say we ended up with the following board. Here, player $1s ($X$) colours are green, light blue, dark blue, and purple, while player $2$ ($O$) has the colours orange, yellow, and grey. ![[IMG_8681.jpeg|400]] We start with the easiest colours to resolve: The square at the bottom right has a $100\%$ probability of housing an $X$ (since the colour green belongs to player $1$), and the leftmost square has a $100\%$ probability of containing an $O$ (since grey belongs to player $2$). ![[IMG_8668 1.jpeg|400]] (We made some $X$/$O$ tokens to make the game more easily replayable, but simply writing the symbols with a pen or pencil works just as well.) Next, we choose a colour and roll it. Here it does not matter which colour we roll first—the probability of each player winning is unaffected by the order we decide the colours, and a winner is only announced after *all* the colours have been resolved. This is because in this game, it is possible for *both* players to get a three-in-a-row. That's a draw! (If one player gets two three-in-a-rows and the other player gets just one three-in-a-row, the standard ruleset would still call the game a draw, but you could alternatively decide that each three-in-a-row counts as one point, and tally points to determine a winner. Just make sure that you and your opponent agree on the ruleset *before* you start rolling!) Let's roll one of the purple dice next. They tell us that there is a $50\%$ chance that there is an $X$ in the bottom left square, and a $50\%$ chance that the $X$ is in the upper right square instead. Before rolling, announce to your opponent how the result should be interpreted. Here's a suggested standard rule: Pick up one of the two purple dice from the board. On a roll of $1$ or $2$, the piece is in the square that you picked the die up from, and on a roll of $3$ or $4$, the piece is in the other square. You pick up the bottom left die, and announce: "If I roll a $1$ or a $2$, then the $X$ is in the bottom left square, and if I roll a $3$ or a $4$, then the $X$ is in the top right square." Then you roll. Say you rolled a $2$; then we get the following board: ![[IMG_8669 1.jpeg|400]] Let us roll the dark blue die next. You announce out loud: "If I get a $1$ or a $2$, then the $X$ is in the upper left square, and if I roll a $3$ or a $4$, then it is in the middle top square." You roll a $3$, and so we get the following board: ![[IMG_8670 1.jpeg|400]] But now that we know that the middle top square houses an $X$, we also know that the $O$ represented by the orange dice can *not* be in the middle top square, meaning that it *has* to be on the top left! And so, without having to roll the orange die, we automatically get the following board: ![[IMG_8671 1.jpeg|400]] Next, let's have player $2$ roll the yellow die. They announce: "If I get a $1$ or a $2$, the $O$ is in the middle square, and if I roll a $3$ or a $4$, then it is in the lower middle square." They roll a $1$, and capture the middle: ![[IMG_8672 1.jpeg|400]] Now we know that the light blue die can *not* be in the middle, and we are back to a $50/50$ chance of it being either in the lower middle square or the rightmost square: ![[IMG_8673 1.jpeg|400]] Let us roll the final die. You announce: "If I roll a $1$ or a $2$ then the $X$ is in the lower middle square, and if I roll a $3$ or a $4$ then it is in the rightmost square." Player $1$ is hoping to roll a $1$ or a $2$—and this time they are lucky! ![[IMG_8674 1.jpeg|400]] There are three $X$s in a row in the lower row, while player $2$ has nothing. Player $1$ wins! #### 1.4 The Game Continues If we start with the same board we had previously, ![[IMG_8681.jpeg|400]] we could also have ended up with the following outcome, had the purple dice landed differently: ![[IMG_8677 1.jpeg|400]] None of the players have won, and there are still empty squares left. Then the game continues, starting with the next turn after whoever played last before rolling! Note that the $X$s and $O$s can no longer be "invaded"—they are no longer in a quantum state, and so the players can *only* use the empty squares. As usual, the first player can choose to put down either one or two dice. But the particular board we ended up with here is an interesting one, because there is a winning move for *either* player, given that they get to go first! Do you see it? Right! Since player $1$ put down the last dice before rolling (which is how they got four pieces on the board while player $2$ only got three), player $2$ is next. If they then make a superposition move and place a colour in both squares, then there are no more empty squares left, so that a new round of dice rolling commences. ![[IMG_8678 1.jpeg|400]] However, *regardless* of the outcome, the result is that $O$ gets three-in-a-row, while $X$ gets nothing! In other words, player $2$ has already won, without even having to roll anything. What's more, had player $1$ been out first after the first round of rolling, they could have made the very same move and also been guaranteed victory! We see that being first out after a round of dice-rolling could be very advantageous. ##### Last-player Advantage? The moral of the above is that, while there is a small first-player advantage in the game (since they could end up with one more piece on the board than their opponent), there also seems to be a certain kind of *last*-player advantage, in the sense that whenever a player finds themselves with two empty squares left on the board, they get to decide whether to initiate rolling right away (by placing dice in both squares), robbing the opponent of the opportunity to place their final piece, but also giving them the opportunity to be first out after measurement in the event that no winner was determined yet; *or* to leave the final square to the opponent, and thus be in the advantageous position of being first after rolling, *provided* no one wins right away. Which move is better will strongly depend on the state of the board that is about to be rolled, and might for experienced players involve some quick mental calculations! Interestingly, it is always possible for player $2$ to play such that they *either* end up with two empty squares left (and thus get to decide who goes last), *or* one empty square left (and thus get to go last themself). Do you see how? ### 2. What has all this got to do with Quantum Physics? Like many other quantum games, quantum tic-tac-toe was developed with the goal of giving the players an *intuition* for the famously non-intuitive world of quantum mechanics, by having the players interact directly with the strange rules that govern tiny particles like atoms and electrons, which are the building blocks of our very existence. [To quote the physicist John Preskill](https://arxiv.org/pdf/1801.00862): > Physicists often say that the quantum world is counter-intuitive because it is so foreign to ordinary experience. That’s true now, but might it be different in the future? Perhaps kids who grow up playing quantum games will acquire a visceral understanding of quantum phenomena that our generation lacks. Here are some of the defining features of quantum physics, and how they are represented in the game. #### 2.1 Superposition Whenever you place two dice of the same colour, you could say that you are placing a piece that is "two places at once". Physicists would say that the piece is in a "superposition" of being either here or there, and it is this very same phenomenon that was famously illustrated by Erwin Schrödinger in his thought experiment "Schrödinger's Cat", in which a cat is put in a superposition state of being both dead and alive at the same time! ![[Pasted image 20240927183409.png|400]] #### 2.2 Entanglement When you "invade" one of the opponent's squares and "drag" a part of their colour over to another square, you are *entangling* your piece with the piece of the opponent. In other words, you end up with conditional probabilities of the form "if $X$ is here, then $O$ must be there!" We say that the probabilities are "correlated", and that the pieces are "entangled". What's special about our quantum universe, is that once entanglement has been created between two particles, then they remain entangled no matter how far you separate them from each other. This is true even if I were to send one particle in an "$X$ or $Oquot; state to the other side of the galaxy, while keeping the other particle (which is in an "$O$ or $Xquot; state) here: The *moment* my particle here is observed, and thus "decides" to be one or the other value, then the other particle will *immediately* "decide" to be the other value, even though it is on the opposite side of the Milky Way! In other words: *This effect does not obey the universal speed of light limit imposed by the theory of relativity!* This allegedly made Albert Einstein uneasy, who is said to have called entanglement "spooky action at a distance". And yet the math works out *just* so that faster-than-light communication is *still* impossible—which among other things would have allowed you to send messages backwards in time! It is almost as if the universe needed an effect that didn't obey the speed limit, but managed to choose its laws in *just* the right way so that the effect can't be used to *do* anything faster than the speed of light. ![[Pasted image 20240927190400.png|350]] #### 2.3 Observation Quantum particles are shy: In order for a particle to remain in a quantum state, you can't *look* at it—or listen to it, or in any other way observe it. In real experiments one actually needs to spend considerable effort to isolate quantum particles in order for them to exhibit any quantum effects at all. This is why, even though it underlies all of our existence, it took all the way until 1905 to identify any quantum effects! When you observe a quantum particle, all quantum effects like superposition and entanglement instantly *collapse*, and you end up with a so-called *classical* particle, which is to say a particle that behaves the way you might expect a marble to behave—or in our case, like the $X$s and $O$s of normal tic-tac-toe! When we roll the dice, we are *observing* the board by *collapsing* the quantum state of one piece at a time—and just like in nature, this happens in a truly *random* fashion: By the rolling of dice! This was also something that displeased Einstein. He was deeply skeptical about the completeness his colleauges' formulation of quantum physics, and is known to have stated that "God does not play dice!" But today we know that he was wrong: Whether or not there sits a God behind the tapestry of our universe, there *must* be randomness—such as you get from rolling dice—involved in the deepest laws of nature that make up our existence! ### 3. About the Game Quantum tic-tac-toe, or TiqTaqToe, was created by [Evert van Nieuwenburg](https://www.universiteitleiden.nl/en/staffmembers/evert-van-nieuwenburg#tab-1), a Dutch quantum physicist, after he was tasked with helping create a new and better AI for the computer game [Quantum Chess](https://quantumrealmgames.com/play/). But before he set to work on this monumental task, he decided to warm up his quantum game development chops by trying his hands on "quantumifying" a simpler game—and thus quantum tic-tac-toe was born! Evert's version of TiqTaqToe is available to play online at [tiqtaqtoe.com](https://tiqtaqtoe.com). Quantum Chess is available via [Steam](https://store.steampowered.com/app/453870/Quantum_Chess/), and one can even find several quantum chess tournaments on [YouTube](https://youtu.be/6wTtWLnEnwQ?si=Vpr4aqrx3Zyzia5e). This board game version of quantum tic-tac-toe was developed by myself after stumbling upon the TiqTaqToe website and falling for the simple beauty, yet surprising depth, of the game. Over time I got frustrated with both how hard it was to experiment with strategies without having physical pieces in front of me, and also by how hard it was to talk my friends into logging on to the website to play against me. A board game version—one even small enough to fit in my pocket—solved both problems at once! I have played hundreds of games since, against friends and strangers alike—and I *still* haven't managed to come up with a winning strategy! #### 3.1 Variations of the Game ##### Limited Quantumness One can make the game simpler by limiting what quantum moves are available to the players, for example you might disallow the "entanglement" move, so that the placement of two dice at once can only involve two empty squares. This might be a helpful step in introducing the game to new, particularly younger players. It turns out that this version of the game, which you can play on [tiqtaqtoe.com](https://tiqtaqtoe.com) by choosing "Minimal Quantumness", *does* have an optimal strategy! Are you able to find it? ##### Quantum-only Going the opposite direction, one could also disallow the *classical* move, forcing players to use *only* quantum moves. In this version of the game, this is as simple as requiring that each player place two dice per turn. ##### Point Tallying As already mentioned, if both players end up with three-in-a-rows after observing the board, one could let each three-in-a-row count as one point. Then, situations might arise in which both players get three-in-a-rows, and yet a winner is declared. If multiple games are played in a row, the players might then also keep track of their scores to decide a winner at the end based on the total points earned. As another variant, one might let the game continue until all squares contain a piece before points are tallied and a winner is declared. This would mean that even if one player got a three-in-a-row after the first round of dice-rolling, the game would continue as long as there are empty squares left. ##### More Quantum! I am currently developing more advanced rulesets, which include a quantum phenomenon not present in the base game, namely *phases*. Now, probabilities come with either a $+$ or a $-$ sign, which among other things means that they might *cancel* each other! To follow the development of these rulesets, check out these pages: - [[TiqTaqToe with Phase Cancellations]] - [[Notater TiqTaqToe with basis changes]] - [[Fully Quantum TiqTaqToe (v1)]] If you have a TiqTaqToe dice set, you can already try your hands at the two first ones! (The third one still needs a bit more love.) ### Get the Game! This game does not exist in any officially produced edition (yet!), so if you want a set you have to put it together yourself. d4 dice can be bought in most board game stores (e.g. [Outland](https://www.outland.no) in Norway), but this could turn out costly if you need to find and buy 36 individual dice of matching colours. By looking a bit online, you will be able to find cheaper alternatives, and several websites sell d4 dice of varying colours in bulk, allowing you to order and put together to your own set. If you are in the Trondheim area you could also contact me at [email protected], as I sometimes have an extra set or two lying around.