Using Go to Generate Directed Graph Dual Representations

[psi-go]

CW: very nerdy

I realized a while ago that games are equivalent to a ternary valued {B,0,W} square matrix (9x9, 13x13, 19x19). With this, the shades of the stones can be arbitrarily assigned numerical values. I used B = 1 and W = -1, as black absorbs light and white reflects it, but it’s arbitrary.

Adjacency matrices are used in graph theory to indicate 1 if a vertex v of a graph v_xn is linked by an edge to a different vertex v_yn, where x and y indicate the directions of matrix (board) and would correspond to the A,B,C…,T and 1,2,3…,19 directions of the board.

Since the game of go is ternary, one could create an extended adjacency matrix for an unknown directed graph. The sign of the value could be used to indicate a direction of the connected edge, such as 1 equals “from x to y” and -1 equals “from y to x”. A black stone at, say, F9 could generate a connection between two vertices labeled F and 9, whose direction goes from F to 9, whereas a white stone at F9 would indicate a connection between the vertex F and the vertex 9 as well but going from 9 to F.

All this might be confusing to those unfamiliar with spectral graph theory, but it seems to map pretty cleanly onto it. I don’t think I can give a clear description of adjacency matrices here but there are many resources about them on the internet.

For an example, I created a matrix out of the game shown here Nine Dragons Playing With A Pearl at Sensei's Library
at move #180

(note, I might have made a mistake translating the pieces to numbers in a graph, as I did it “by hand”)

If people think this is interesting, I could make the corresponding graph for it. To avoid loops, one would need a graph of < 19 + 19 = 38 vertices. Without loops, it is what is known as a Directed Acyclic Graph or DAG.

Since go games evolve through time, the graph would also change with each discrete time step (move played), and would become what is known as a temporal network.

This might have been noticed before, but it was new to me. A dedicated person might be able to analyze go games in a possibly novel way by looking at their graph-dual.

[psi-go]

In the above example, I erroneously wrote that the graph would be made out of two subgraphs of 19 vertices each, but that would only be true for a completely filled board, which doesn’t happen. Empty spaces imply no connections, and if there are vertices with no connections (edges) they don’t need to be included at all. Otherwise it’d be a graph with free floating dots around it that don’t give any info necessarily.

The matrix above would definitely generate a directed graph. The first row, using the labels from the game, would indicate that there is a connection from vertex 1 to vertex G (if it were a white stone, it’d be +1, and would be a connection from vertex G to vertex 1) for for some graph with edges contained in the set (of labels) {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T} deep breath.

Like I said, I can draw out this graph if anyone’s interested, but if others don’t seem to care I’m not going to take the time. Also if someone knows how to use software to generate directed acyclic graphs from adjacency matrices I would love to learn and any links would be appreciated

Since this shows that go can be looked at with linear algebra and graph theory, one can use the theory from those math fields to explore possibilities of games. Like finding determinants of a board-state matrix to create another related but different board-state

[GreenAsJade]

Just noting that of course there is a ton of prior art on this:

https://www.google.com/search?q=baduk+directed+graph+representation

[psi-go]

These are all really cool, but actually seem to use a different method to create a different type of graph more closely related to the layout of the board, called planar lattice graphs. This would be like if you drew lines on the board itself, something like this messy picture:

(or if it’s a strictly square lattice graph the edges would follow the lines on the board)

I don’t see anything so far about using the board layout as an adjacency matrix for a different graph (which wouldn’t necessarily have to look anything like the board). The two ways of generating graphs would be related and I’m excited to hear about people thinking in similar directions

[psi-go]

The only directed graph mention I find when I add quotes to restrict the search to include only the phrase “directed graph” also don’t seem to include the same method. Directed graphs are used to represent entire game trees, with each nodes representing whole board states.

Here’s another example of how most of these other methods seem to be using the board itself for the graph

With an adjacency matrix, the stones do not directly encode the vertices, they would encode the edges of a graph, with possible vertices at all the points on the board. If there are edges going to/from a point on the board there would be a vertex there, but the whole column of points on the board at say, 3, would all refer to one vertex labeled 3. So, if there were stones at A3, F3, P3 and I3, there would be 5 nodes implied (the other people’s graph method would make 4, one per each position): {A,F,P,I,3}. The shades of the stones would create directions for the edges, such as if P3 were a black stone, it’d be going from vertex P to vertex 3.

The resulting graph would also look different than the board, so it could give novel or at least unintuitive information about the game

edit: you’d also only need < 19 + 19 nodes (or 9 + 9, 13 + 13), instead of 19^2 like the planar lattice graphs use, so computations on ((or with??)) the resulting graphs wouldn’t be as resource intensive, but constructing the matrix in the first place might

[benjito]

Apparently the type of graph that can be represented by a Go board is interesting enough to have a name!

Oriented graphs are directed graphs having no bidirected edges (i.e. at most one of (x, y) and (y, x) may be arrows of the graph). It follows that a directed graph is an oriented graph if and only if it hasn’t any 2-cycle.

[psi-go]

Oh yes, an oriented graph is what I mean. It’s a subtype of a directed graph and they’re also they type used in theoretical neuroscience to represent information/electricity flowing through a network of neurons. Studying neuroscience and playing go during lockdowns lead me to coming up with this, I wasn’t studying the math of go.

The other type of graphs that people have used in the links following GreenAsJade’s google search are called planar lattice graphs, because the board itself is a square lattice Square lattice - Wikipedia , and it’s a flat plane so it’s “planar.”

The only thing about my method is that it’s weirdly split in two. The alphabet set of the x axis of the board and the numerical set of the y axis have no edges within them, that is, no letter (number) is connected to another letter (number).

You could combine the two graphs and make a lattice graph from paths between the stone’s positions on the board and another graph using the adjacency* matrix, and see how they relate.

*adjacency in the resulting graph, not adjacency on the board. That’s just the name of the matrices. There’s also incidence matrix, Laplacian matrix. Spectral graph theory is tons of fun, if you like that sort of thing

[psi-go]

I tried drawing the resulting graph on a circle but I realized after I was in pretty deep that I won’t be able to include the orientations of the edges. I kept it because it looks cool.

Here’s what turn 180 of Nine Dragons Playing with a Pearl encodes if all the stones were gray and the game was unplayable, aka if it’s seen as an adjacency matrix with only the elements {0,1}

It’s a pretty complex graph, and the orientation would make it more complex. If it were accurately represented – data visualization is hard but people do so with even more complex graphs – then it would be very cool. It could be animated to change per turn and give an abstract description of the flow of the game

[shinuito]

It does seem a bit arbitrary (not in bad way) to choose to make a graph by using the coordinates. I mean it’s interesting, but possibly one of a number of choices maybe?

The 19x19 grid would also have a much larger adjacency matrix for instance for each of the points, corner points having two neighbours, centre points four etc.

One could pick some arbitrary rules on filling the entries like

• fill the (p,q) entry as zero if p and q aren’t adjacent in the go grid
• fill the entry by 1 (or anything else) if both p and q contain a like coloured stone
• fill the entry by -1 if they have opposite coloured stones
• fill by 0 if one or both intersections are empty.

I guess it’s “nice” in that if Black represents 1 and white -1, and empty 0, then the above is just the product of the neighbouring entries in the board state.

Of course I can’t tell you it does anything more interesting though than what you came up with. That’s kind of what I mean by arbitrary, I can’t necessarily say which is more natural etc, partly because I’ve only minimally studied graph theory also

[psi-go]

I like that there’s a lot of different ways to generate different graphs from go, especially since there doesn’t seem to be a very large number of them, so they’re comparable.

There’s kind of a range of how smoothly something can be mapped to something abstract. Looking at a board and seeing imagining the black and white stones as polar unit values, and the empty space as zero, doesn’t feel too far of an abstraction away from what the board itself looks like, but the arbitrariness does show itself when things like choice of sign, and orientation of the board/matrix are considered.

If any of these could elucidate something about the gameplay or strategy, then they’d be useful or interesting, and any different rule would give different information about the game. All the rules you wrote out seem to rely on pieces’ physical adjacency, but the one I made has nothing to do with that so I don’t see why corner and center stones would have a diff set of values. A1 would be the vertices A and 1 with some edge going to or from it if there’s a stone there. “A” still has 19 other options to connect to, “1” also has 19, since it’s a square matrix. I could easily be missing something though, I’m all over the place

[shinuito]

@psi-go

All the rules you wrote out seem to rely on pieces’ physical adjacency,

Indeed, I was just imagining a way of encapsulating the game rules or flow of the game in such a matrix.

It starts out as all zeros for many turns, then it starts to fill up with 1s as connected groups of the same colour form, and -1s as they touch off of opposite colour stones. So the -1’s are showing borders while the 1s are showing connectivity. (well there’ll be dead stones too but maybe toward the end of the game, removing dead stones etc)

It’s not going to look visually great though, becuase there’s an arbitrary choice to order the points on the square grid, and neighbouring points in the matrix probably have nothing to do with neighbouring points on the original grid depending on the choice of ordering.

@psi-go

If any of these could elucidate something about the gameplay or strategy,

So I don’t know would they elucidate anything about strategy, but it does have some gameplay built in because it’s using the underlying grids connectivity - at least that would be my thought process.

@psi-go

The sign of the value could be used to indicate a direction of the connected edge, such as 1 equals “from x to y” and -1 equals “from y to x”. A black stone at, say, F9 could generate a connection between two vertices labeled F and 9, whose direction goes from F to 9, whereas a white stone at F9 would indicate a connection between the vertex F and the vertex 9 as well but going from 9 to F.

This kind of thing I suppose is more thinking of whether two stones lie on the same row or column right? It does also probably say something about connected groups, but probably also disconnected ones? Like two hoshis on the same side of the board will both show up as arrows from say D to some number vertex. Those stones might never be connected in the real game in a group sense, but are connected in this generated graph.

Anyway I’m just throwing out some ideas to help me understand also.

[Atorrante]

That does take me back a few years.

Spirograph

[psi-go]

inspiration for this coming from way back, I’m sure

[shinuito]

I think though one of the bigger pluses on your graph generation over the random example I gave, is that you’re not losing information. The stones are all there and represented by directed edges in the new graph.

The random example loses any information about single disconnected stones (not touching opponents stones also) for example.

[psi-go]

I don’t know how to quote in pieces like that yet, but I’ll reply to each section in order hopefully.

That seems to be a great way of re-framing the positional info of the board. If the graph looks totally different it’d be a way to think about the game without being totally anchored to its normal appearance. That’s kind of the point of any (applied) abstraction right? To willingly take a step back from some real thing and consider it from another angle.

If it says anything about the gameplay it might say something about strategy, especially if you compared the graphs of many games or compared operators on them like their eigenvalues, energies, etc. That’s where I would imagine any useful info would come from.

Yes, mine kind of slices the board line by line like that. It only could say something about strategy maybe if say I compared one of my games as a not very good player to an expert player’s game. I might be able to catch something I wouldn’t see by looking at the game board itself if I looked at algebraic graph properties instead. It doesn’t say much about positional relations though, so I wouldn’t learn a number of things that I would learn using your method or the planar lattice graph. The direction could be interpreted in a number of ways, and it comes from wondering if go could be used to represent neural networks instead of the other way around. There are probably operators on directed graphs that one could explore gameplay related information using though

[psi-go]

could just make a {0,1,2,3} valued matrix where 1 is one direction, 2 is the other, and 3 is none, 0 still being no edge