Tangled on a 3-vertex graph
In the previous post, I introduced the Tangled game, and we analyzed a two-player two-vertex variant. It wasn’t very interesting, because there was no way for either player to win — every game had to end in a draw! Here we’ll work through the smallest game board where one player can win. This game has three vertices.
A 3-vertex game board
We’ll keep P=2 players, but now use the following game board:
This game board graph has N=3 vertices and E=3 edges. As before, players take turns either coloring edges or selecting a vertex. There are P+E =2+3=5 moves in this game — three edge colorings and two vertex picks.
We store game state as a list with N+E=6 entries like this: [v₀,v₁,v₂,e₀₁,e₀₂,e₁₂]. The first three entries are the vertex states. An unselected vertex is labeled 0. A selected vertex is labeled by the number of the player that chose it (in this case, 1 or 2). The last three entries are the edge states. An unselected edge is labeled 0, a grey edge (zero coupling) is labeled 1, a green edge (preferring alignment AKA ferromagnetic) is labeled 2, and a purple edge (preferring anti-alignment AKA antiferromagnetic) is labeled 3.
Games always start with the game state all zeros. For the 3-vertex 3-edge game, that means [0,0,0,0,0,0]. The terminal states must have exactly one 1 and one 2 in the first three list members, and the final three can be any combination of 1, 2, or 3. We can upper bound the possible number of terminal states by 2 * (3 choose 2) * 3³ = 6 * 27 = 162 (in general, for a P-player game with N vertices and E edges, the upper bound on the number of terminal states is 2 * (N choose P) * 3ᴱ, exponential in the number of edges).
Game Board Symmetries
An automorphism of a graph is a way of mapping the graph to itself while preserving all of its structure. It’s a symmetry of the graph. This is important in practice for Tangled, as there are in general several board configurations that are equivalent, so we don’t need to evaluate all of them!
For this small graph, the automorphism group (the set of all automorphisms) contains six elements, given by the following mappings of vertices: [{0: 0, 1: 1, 2: 2}, {0: 0, 2: 1, 1: 2}, {1: 0, 0: 1, 2: 2}, {1: 0, 2: 1, 0: 2}, {2: 0, 0: 1, 1: 2}, {2: 0, 1: 1, 0: 2}] (you can also check this out which explains why). How to read this is that each element maps vertices from:to, and under that map, the graph retains all its properties. So for example {2: 0, 0: 1, 1: 2} means map vertex 2 to vertex 0; vertex 0 to vertex 1; and vertex 1 to vertex 0; and you have the same graph.
Enumerating and Adjudicating All Unique Terminal States Using Three Different Methods
For each of the 162/6 = 27 unique terminal states, I computed who won using three different solvers:
An exact Schrodinger Equation solver
A specially tuned simulated annealing solver, designed specifically to spoof the hardware
The D-Wave Advantage2_prototype2.4 system (an actual real-life quantum computer!)
All three agreed on all 27 terminal state adjudications; the results were 7 red wins (25.9%), 7 blue wins (25.9%), and 13 draws (48.1%).
Here are the unique terminal game states and their adjudicated values: [[[0, 1, 2, 1, 1, 1], 'draw'], [[0, 1, 2, 1, 1, 2], 'draw'], [[0, 1, 2, 1, 1, 3], 'draw'], [[0, 1, 2, 1, 2, 1], 'blue'], [[0, 1, 2, 1, 2, 2], 'draw'], [[0, 1, 2, 1, 2, 3], 'blue'], [[0, 1, 2, 1, 3, 1], 'red'], [[0, 1, 2, 1, 3, 2], 'draw'], [[0, 1, 2, 1, 3, 3], 'red'], [[0, 1, 2, 2, 1, 1], 'red'], [[0, 1, 2, 2, 1, 2], 'draw'], [[0, 1, 2, 2, 1, 3], 'red'], [[0, 1, 2, 2, 2, 1], 'draw'], [[0, 1, 2, 2, 2, 2], 'draw'], [[0, 1, 2, 2, 2, 3], 'draw'], [[0, 1, 2, 2, 3, 1], 'red'], [[0, 1, 2, 2, 3, 2], 'red'], [[0, 1, 2, 2, 3, 3], 'red'], [[0, 1, 2, 3, 1, 1], 'blue'], [[0, 1, 2, 3, 1, 2], 'draw'], [[0, 1, 2, 3, 1, 3], 'blue'], [[0, 1, 2, 3, 2, 1], 'blue'], [[0, 1, 2, 3, 2, 2], 'blue'], [[0, 1, 2, 3, 2, 3], 'blue'], [[0, 1, 2, 3, 3, 1], 'draw'], [[0, 1, 2, 3, 3, 2], 'draw'], [[0, 1, 2, 3, 3, 3], 'draw']].
The average wall clock time it took to adjudicate a terminal state with the Schrodinder Equation solver was 2.3 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 a specific terminal state, let’s say this one:
Player 1 (red) has selected vertex 0, player 2 (blue) has selected vertex 2, and the couplings between the vertices are as shown, giving terminal state [1,0,2,2,1,1], which under the automorphism {0:1, 1:0, 2:2} is equivalent to [0,1,2,2,1,1].
Can you intuit who the winner is here? Remember winning requires the influence of one color to be at least 1/2 higher than the other color. Green means the vertices want to be the same, and grey means no influence at all. Does red have more influence, or blue? Does it have enough to win?
When we integrate the Schrodinger Equation for this problem, we can obtain all pairwise correlations and influence during the course of the computation:
We see from the bottom graph that the influence of vertex 2 saturates to 0, whereas the influence of vertices 0 and 1 both saturate to 1, which is greater than 1/2 and therefore wins! This is because 0 and 1 are preferentially reading the same values |￪￪> or |↓↓> (they are all connected by a green line), whereas 2 is not correlated to either of the other two as it only has grey lines connected to it.
In this case, red chose vertex 0 which has more influence (1) than blue’s vertex 2 (0), and the difference is greater than 1/2, so red wins!
What All The Winning Terminal States Look Like
For this 3-vertex Tangled variant, there are exactly 7 unique red win terminal states and 7 unique blue win terminal states, all shown in the image below (there are multiple other terminal states that initially look different but are the same under the automorphism group of the graph). Remember that grey edges mean no effect, green edges want the connected vertices to be the same state, and purple edges want the connected vertices to be different states, and that winning means having more influence, which means more of the other vertices tend to have the same state.
For example in the leftmost blue win, vertices 0 and 2 are locked together by the green edge, and so there will always be agreement between those two values, whereas the red vertex isn’t coupled to anything so it will have zero correlation with the vertex 0 — vertex 2 cluster. In the next one over it’s even worse for red, as red will always disagree with the bigger vertex 0 — vertex 2 cluster! In the next one over, the winning blue vertex isn’t coupled to anything, but the losing red vertex 1 is anti-correlated to vertex 0, which penalizes red’s influence.
You can keep doing this for all the states for both sides winning and start to see some patterns. Although I’m not sure whether these patterns for such a small graph are meaningful for larger graphs!
Blue Wins:
[[0, 1, 2, 1, 2, 1], [0, 1, 2, 1, 2, 3], [0, 1, 2, 3, 1, 1], [0, 1, 2, 3, 1, 3], [0, 1, 2, 3, 2, 1], [0, 1, 2, 3, 2, 2], [0, 1, 2, 3, 2, 3]]
Red Wins:
[[0, 1, 2, 1, 3, 1], [0, 1, 2, 1, 3, 3], [0, 1, 2, 2, 1, 1], [0, 1, 2, 2, 1, 3], [0, 1, 2, 2, 3, 1], [0, 1, 2, 2, 3, 2], [0, 1, 2, 2, 3, 3]]