Directed Acyclic Graph

A directed acyclic graph (DAG) is a directed graph that contains no directed cycles. See the Wikipedia article for more background information on DAGs.

In Go, we can use a DAG to model sequences of moves, where vertices represent positions, and a directed edge link vertex u to vertex v if the position at v can be reached by making a move from the position at u. In other words, sequences are directed paths in the DAG. Note that the graph is directed as there is a sense of forwardness as more moves are played, and the graph is acyclic as positions do not repeat in most rule sets due to superko rules (see ko rules). When two different sequences from the same starting vertex leads to the same ending vertex, we say that a transposition has occurred.

Note that a directed tree is a kind of DAG in which any two vertices are connected by exactly one path. Game trees such as SGF files typically store a main line or actual game sequence together with possible variations and branches. However, a strict tree representation causes duplication of subtrees when the sequences contain transpositions, which makes annotations and other commenting tasks inefficient. As transpositions often occur in Go problems such as life-and-death problems, goproblems.com automatically detects transpositions in SGF files and links them together, effectively forming some kind of a DAG.

Phelan: Interesting, didn't know that goproblems used something like that. Do you think it could be used outside of that context? I mean, could it be used as a new go game format?

unkx80: This feature isn't documented. When I took a closer look at the SGFs embedded in the HTML source, it appears that the SGF format itself is unchanged, so I have amended the text.

Phelan: Ah, ok. Thanks.

Charles Matthews: In cyclic positions taxonomy the consequences of dropping the 'acyclic' condition, for local positions on a sub-board, are explored mathematically.

This is intended as as systematic way forward through the many ko-like positions.

I proposed there that one should identify the nodes of the 'best' DAG underlying a cyclic position as levels of the corresponding ko-like phenomenon. -- Charles

The branching of variations of lines of play form structures that are called trees in mathematics (graph theory) and computer science, and increasingly in common parlance. When two branches grow together, the structure is called a Directed Acyclic Graph (DAG). The best SGF editors (such as CGoban2, gGo, etcetera) handle graphs very well, but do not handle DAGs at all.

-- Hu of KGS

Confused: A DAG capable editor would bring you back to the main line (or another line) if a variation ends in a position that is already present in that line. This would be a cool feature to show, that both variations leads to the same end and the continuations from there are identical.

The editor at GoProblems.com indicates merged branches.