Tangled on a 4-vertex graph

The three-vertex Tangled game board I introduced in the previous post is the smallest where one player can win (two vertex games always end in a tie). Let’s take a look at a slightly bigger graph, with N=4 vertices and E=6 edges.

A four-vertex game board

We’ll keep two players, but now use the following game board, which is a graph called K₄, the fully connected graph on four vertices:

As before, players take turns either coloring edges or selecting a vertex. For two players (P=2) there are a total of P+E=2+6=8 moves in this game — six edge colorings and two vertex picks — so each player makes 8/2 = 4 choices.

This game graph has A=24 automorphisms, listed here: [{0: 0, 1: 1, 2: 2, 3: 3}, {0: 0, 1: 1, 3: 2, 2: 3}, {0: 0, 2: 1, 1: 2, 3: 3}, {0: 0, 2: 1, 3: 2, 1: 3}, {0: 0, 3: 1, 1: 2, 2: 3}, {0: 0, 3: 1, 2: 2, 1: 3}, {1: 0, 0: 1, 2: 2, 3: 3}, {1: 0, 0: 1, 3: 2, 2: 3}, {1: 0, 2: 1, 0: 2, 3: 3}, {1: 0, 2: 1, 3: 2, 0: 3}, {1: 0, 3: 1, 0: 2, 2: 3}, {1: 0, 3: 1, 2: 2, 0: 3}, {2: 0, 0: 1, 1: 2, 3: 3}, {2: 0, 0: 1, 3: 2, 1: 3}, {2: 0, 1: 1, 0: 2, 3: 3}, {2: 0, 1: 1, 3: 2, 0: 3}, {2: 0, 3: 1, 0: 2, 1: 3}, {2: 0, 3: 1, 1: 2, 0: 3}, {3: 0, 0: 1, 1: 2, 2: 3}, {3: 0, 0: 1, 2: 2, 1: 3}, {3: 0, 1: 1, 0: 2, 2: 3}, {3: 0, 1: 1, 2: 2, 0: 3}, {3: 0, 2: 1, 0: 2, 1: 3}, {3: 0, 2: 1, 1: 2, 0: 3}], and (4 choose 2) * 2 / A * 3⁶ = 729 unique terminal states.

Enumerating and Adjudicating All Unique Terminal States Using Three Different Methods

For each of the 729 unique terminal states, I computed who won using three different solvers:

1. An exact Schrodinger Equation solver

2. A specially tuned simulated annealing solver, designed specifically to spoof the hardware

3. The D-Wave Advantage2_prototype2.4 system

All three agreed on all 729 terminal state adjudications; the results were 137 red wins (18.8%), 137 blue wins (18.8%), and 455 draws (62.4%).

Here are the unique terminal game states and their adjudicated values for all three methods. It’s a python pickle file, after you download it just do:

with open(file_path, "rb") as fp:
    K4_tangled_unique_terminal_states_adjudicated = pickle.load(fp)

The average wall clock time it took to adjudicate a terminal state with the Schrodinder Equation solver was 3.6 seconds; Simulated Annealing took 2ms to return 1,000 samples; and the quantum computer took 2.5 seconds to return 1,000 samples.

Let’s take a look at one of the terminal states, let’s say this one ([1,0,2,0,2,1,2,3,1,3]):

Player 1 (red) has selected vertex 0, player 2 (blue) has selected vertex 2, and the couplings between the vertices are as shown.

Can you intuit who is going to win? Remember green means favoring alignment, purple means favoring anti-alignment, and grey means no influence.

When we integrate the Schrodinger Equation for this problem, we get:

We see from the bottom graph that the influence of vertex 2 saturates to -3, whereas the influence of vertices 0, 1 and 3 all saturate to 1. This is because 0, 1, and 3 are preferentially reading the same values (they are all connected by green lines), whereas 2 is preferentially reading the opposite to all those as it is connected to that cluster with a purple line. In this configuration, the states |￪￪↓￪> and |↓↓￪↓> are the most likely to be observed.

In this case, red chose vertex 0 which has more influence (1) than blue’s vertex 2 (-3), the score is 1-(-3) = 4 > 1/2, so red wins!