In an earlier post, I introduced the idea of constructing games where evaluating terminal states requires solving a problem where a quantum supremacy claim has been made.

Here I’ll make this concrete by introducing a game which I call Tangled, which has this property. In this post I’m just going to go over the basic idea. I’ll dive deeper in subsequent posts — this whole area is surprisingly meaty and exciting, and there’s lots to talk about!

A graph is a collection of vertices (think of these like little circles) and edges (lines that connect some pairs of these circles).

Tangled is a game where players take turns coloring all the edges of a game board graph one of three colors: grey, green, or purple.

The game starts with all edges unselected.

Once per game, each player can, instead of coloring an edge, select one vertex of the game board to own. If there is exactly one unselected edge and the active player has not selected their vertex yet, they have to select a vertex.

The game ends, and the winner is determined, once all edges have been colored and each player has selected exactly one vertex.

The final board state at the end of a game is the terminal state.

The winner of the game is the player whose vertex has the greatest influence in the terminal state.

The Tangled Game State

Games like chess have established ways to store game state. For a new game like Tangled, we have to come up with one ourselves! Let’s do that.

Given a game board graph with N vertices and a set of E edges {eᵢⱼ} where eᵢⱼ i<j is an edge connecting vertices i and j, every possible game state can be written as a list of N+E integers. We do so using the following scheme.

The first N elements of the state list are assigned to the N vertices. Their value is 0 if they are unselected, 1 if selected by player 1, and 2 if selected by player 2. The last E elements are assigned to the edges in dictionary order (for example, e₀₁ is first in the list if it exists, then e₀₂ , etc., all the way up to the last possible edge). The values of each element of the edge list are set to 0 if unselected, 1 if grey, 2 if green, and 3 if purple.

The initial state of all games is a list of N+E zeroes.

The terminal state of each game has exactly one 1 and one 2 in the first N elements of the list (all other vertex states are 0), and no 0 values in the last E states of the list (all edges either 1, 2, or 3).

The Tangled Action Space

There are N+3*E possible actions, corresponding to the N choices of vertex and 3 possible choices per edge.

How Many Moves Per Tangled Game?

Each player selects one vertex, and all E edges must be colored. This means each Tangled game has exactly P+E total moves, where P is the number of players, which can be up to N. For a two-player game, this gives exactly 2+E total moves per game to reach the terminal state.

Let’s see what all means in an actual game!

How Gameplay Works

I’ll start with two-player (player 1 = red, player 2 = blue) gameplay on the smallest graph we can play on — a graph with only two vertices, labeled 0 and 1, connected by a single edge (so N=2 and E=1).

The game state has N+E = 2+1 = 3 elements (two vertices, one edge). The initial state is all zeros — we can write it [0,0,0] — nothing has been selected yet.

Player 1 (red) goes first. With this game graph, a game lasts a total of three moves (player 1, then player 2 (blue), then player 1 — in general, a two-player Tangled game has a total number of moves equal to |E|+2, where |E| is the number of edges in the game board graph — in this case |E|=1). As there is exactly one unselected edge, player 1 is forced to choose a vertex as their first move. They can choose either. Let’s say player 1 (red) picks vertex 0. Then the game board looks like this.

The game state is now [1,0,0]. The first vertex (vertex 0) is owned by red, and that means we write a 1 at that position. Now player 2 (blue) gets to go. As there is still exactly one unchosen edge, they also have to select a vertex, and there’s only one choice! So they select vertex 1.

Now the game state is [1,2,0] as player 2 has selected vertex 1. Player 1 gets to choose the color of the edge, and once that is done, the game is over (all edges selected, each player has chosen a vertex), the terminal state has been determined, and the winner can then be determined. In this case, they chose to color the edge green, because why not, making the terminal state of this game [1,2,2].

Tangled can be played on arbitrary game graphs. Here’s a finished game played on the Petersen graph (N=10 vertices, E=15 edges). The game state has N+E=10+15=25 elements; the terminal state shown is [0,0,2,0,0,1,0,0,0,0, 1,3,2,3,3,3,3,2,1,1,3,1,2,3,2]. You can see in the first 10 elements (the N=10 vertices) there is exactly one 1 and one 2, and the last 15 elements (the E=15 edges) are all either 1, 2, or 3.

A finished Tangled game played on the Petersen graph. The Petersen graph is a type of graph called a snark, which I spent wayyyy too long reading about. Also it contains what Bill Macready once called a ‘witch thing’ while making air quotes, which still makes me laugh.

And here’s a terminal state on a tesseract, a game graph with N=16 vertices and E=32 edges (the vertices are the corners of a 4D cube).

A finished Tangled game played on a 4D tesseract graph. Tesseracts are cool!

Any graph can be a Tangled game graph!

Mapping Tangled onto an Ising Model

Recall from an earlier post that an Ising model is a mathematical object, defined over a set of N objects {sⱼ=±1, j=0..N-1}, parametrized by a set of N numbers {hⱼ, j=0..N-1} and N*(N-1)/2 numbers {Jᵢⱼ, i<j}, which assigns an energy to each of the possible 2ᴺ states of the system

Let’s assume:

That the jth vertex in the game board graph is mapped to the jth two-state object s
all h values are set to zero
Each edge eᵢⱼ in the game board graph is mapped to the edge between Ising objects i and j, and that edges colored grey, green and purple correspond to Jᵢⱼ=0, Jᵢⱼ=-1 and Jᵢⱼ=+1 respectively
All edges in a complete graph not in the game board graph have Jᵢⱼ=0
Any as yet unselected edges have Jᵢⱼ=0

This creates a 1-1 correspondence between a Tangled game state and an Ising model.

How To Determine Who Won a Game

When I set up the Tangled game at the beginning of this post, I said that the winner of the game is the player whose vertex has the greatest influence in the terminal state.

Influence is computed by collecting samples from some underlying probability distribution. But I still haven’t said anything about what that distribution is for Tangled! Also, the entire point of this exercise was to create a new type of game where evaluating terminal states (AKA figuring out who won) is a problem where quantum supremacy has been claimed.

Let’s connect the dots!

How to Score a Game: Step 1

First we have to have a game state. This works for any game state, but here let’s assume that we’re dealing with a terminal state (the game is finished, and we want to know who won). The first thing we do is convert the terminal state into the set of J values in an Ising model, like I described in the preceding section. This step is super easy.

How to Score a Game: Step 2

Now that we have an Ising model (a set of J values, remember for Tangled all the h values are zero), we program a D-Wave processor with these values. This is actually really easy to do using a simple python script and the D-Wave Ocean SDK. We then draw M samples (how large M should be is actually an interesting question, but let’s say e.g. M=10,000) as described in the previous blog post from the probability distribution of the quantum computer post-quantum quench through the quantum phase transition from paramagnet to spin glass state. This is the step which is supposed to be hard for non-quantum computers.

How to Score a Game: Step 3

We then compute all of the pairwise correlations from those samples, and then compute the influence for each vertex/qubit.

Call the index of player 1’s vertex k, and player 2’s vertex m, in the terminal state being evaluated (these are just the positions of the 1 and the 2 in the first N positions of the terminal state). Then the difference of the two players’ influence scores is

What are the ranges for the score? Well let’s say all but one of the vertices are locked together to always point in the same direction, and one vertex is always in the opposite direction. That would be the biggest possible score, which would be R = (V-2-1) - (-(V-1)) = V-3+V-1 = 2V-4. As the score is symmetric, the most negative possible score is -2V+4.

How to Score a Game: Step 4

Alright! We have a number R, which is the difference between the two influence values of the vertices the players picked.

Define a draw range ε=1/2.

We can now compute who won. If R > ε, player 1 wins. If R < -ε, player 2 wins. If |R| ≤ ε, it’s a draw.

As the number of vertices grows, so does the possible range of the score R (-2V+4<R<2V-4). However we’ve defined a fixed draw range of |R| ≤ 1/2. This means that the draw range as a percentage of the full score shrinks as V gets bigger. For small V it’s likely that it will be easy to distinguish draws from wins, and there will be a lot of draws, but as V grows, the density of terminal states that are close to this score should grow and also I’d expect that the number of draws could decrease significantly as an overall percentage (although I’m not sure about this!).

While we defined the simple example here using two players, the game can be extended all the way up to N players, where N is the total number of vertices on the game board.

Why Figuring Out Who Won is Hard

Our objective as Tangled players is twofold: (a) construct the underlying Ising model (by adversarially setting the J terms during game play) and (b) figure out which vertex has the highest influence given that underlying game state, and choosing that vertex at some point during the game.

If D-Wave quantum supremacy claim holds, then adjudicating terminal states in Tangled is a domain of quantum supremacy.