2

I want to create a multi-line string that can be printed out or displayed via curses. This string displays the moves and variations of a go/weiqi/baduk game from an sgf file using unicode characters. Each vertical line of stones is supposed to represent one line of moves while variations show off to the side. I could not find other code that makes a tree using this compact layout. I am hoping to include this work in a console based program to create, analyze, or interact with game records. What I have below, so far, just makes a simple tree. I am looking to make the tree look like the diagram further below. Bonus points if there can be some helper functionality for background highlighting from the root node to the current selected node. That part comes later.

Note for clarity. The main variation of the game record starts from the root node and follows the chain of first children. That chain should show as the left most line of nodes. Each alternative variation should show in subsequent columns.

Current Code:

# import module that converts sgf file to nodes
# https://github.com/sanderland/pysgf
# https://github.com/jtauber/sgf/blob/master/examples/ff4_ex.sgf
from pysgf import SGF

# ◯ represents a black stone played
# ⬤ represents a white stone played
# ⛶ represents the root or other node

class SGFNode:
    # Simplified node class for demonstration.
    # The parse_file function from the imported module, as used
    # below, will make the tree using nodes like this one.
    def __init__(self, parent=None, properties=None, name=None):
        self.children = []
        self.properties = defaultdict(list)
        self.parent = parent
        if   "B" in self.properties: self.name = f"◯ "
        elif "W" in self.properties: self.name = f"⬤ "
        else: self.name = f"⛶ "
    def depth(self): ...
    def nodes_in_tree(self): ...
    def nodes_from_root(self): ...

def print_tree(node, last=True, header=''):
    size = node.board_size
    other = "…" if len(node.properties) > 1 else " "
    blank = "  "
    elbow = "╰─"
    pipe = "│ "
    tee = "├─"

    if   "B" in node.properties: print(f"{header}{elbow if last else tee}◯ ")
    elif "W" in node.properties: print(f"{header}{elbow if last else tee}⬤ ")
    else: print(f"{header}{elbow if last else tee}⛶ ")

    if len(node.children) > 0:
        for i, child in enumerate(node.children):
            print_tree(
                node=child, 
                header=f"{header}{blank if last else pipe}", 
                last=i == len(node.children) - 1,
            )


root = SGF.parse_file("./examples/ff4_ex.sgf")
print_tree(root)

Current Output:

╰─⛶ 
  ├─◯ 
  │ ╰─⬤ 
  │   ╰─◯ 
  │     ╰─⬤ 
  │       ╰─◯ 
  │         ╰─⬤ 
  │           ╰─◯ 
  │             ╰─⬤ 
  │               ╰─◯ 
  │                 ╰─⬤ 
  │                   ╰─◯   
  │                     ╰─⬤ 
  │                       ╰─◯ 
  ├─⛶ 
  │ ╰─⛶ 
  │   ╰─⛶ 
  │     ╰─⛶ 
  ├─⛶ 
  │ ╰─⛶ 
  │   ╰─⛶ 
  │     ╰─⛶ 
  ├─◯ 
  │ ├─⬤ 
  │ │ ├─◯ 
  │ │ ├─◯ 
  │ │ ├─◯ 
  │ │ ╰─◯ 
  │ ├─⬤ 
  │ ├─⬤ 
  │ ├─⬤ 
  │ ├─⬤ 
  │ ╰─⬤ 
  ╰─◯ 
    ╰─⬤ 
      ╰─◯ 
        ╰─⬤ 
          ╰─◯ 
            ╰─⬤ 
              ╰─◯ 
                ╰─⬤  
                  ╰─◯   
                    ╰─⬤ 
                      ╰─◯ 
                        ╰─⬤ 
                          ╰─◯  
                            ╰─⬤   
                              ╰─◯   
                                ╰─⬤   
                                  ╰─◯   
                                    ╰─⬤   
                                      ╰─◯   
                                        ╰─⬤   
                                          ╰─◯

Desired Output:

⛶─┬─┬─┬─────────────────╮
◯ ⛶ ⛶ ◯───────┬─┬─┬─┬─╮ ◯
⬤ ⛶ ⛶ ⬤─┬─┬─╮ ⬤ ⬤ ⬤ ⬤ ⬤ ⬤
◯ ⛶ ⛶ ◯ ◯ ◯ ◯           ◯
⬤ ⛶ ⛶                   ⬤
◯                       ◯
⬤                       ⬤
◯                       ◯
⬤                       ⬤
◯                       ◯
⬤                       ⬤
◯                       ◯
⬤                       ⬤
◯                       ◯
                        ⬤
                        ◯
                        ⬤
                        ◯
                        ⬤
                        ◯
                        ⬤
                        ◯

ff4_ex.sgf

(;FF[4]AP[Primiview:3.1]GM[1]SZ[19]GN[Gametree 1: properties]US[Arno Hollosi]

(;B[pd]N[Moves, comments, annotations]
C[Nodename set to: "Moves, comments, annotations"];W[dp]GW[1]
C[Marked as "Good for White"];B[pp]GB[2]
C[Marked as "Very good for Black"];W[dc]GW[2]
C[Marked as "Very good for White"];B[pj]DM[1]
C[Marked as "Even position"];W[ci]UC[1]
C[Marked as "Unclear position"];B[jd]TE[1]
C[Marked as "Tesuji" or "Good move"];W[jp]BM[2]
C[Marked as "Very bad move"];B[gd]DO[]
C[Marked as "Doubtful move"];W[de]IT[]
C[Marked as "Interesting move"];B[jj];
C[White "Pass" move]W[];
C[Black "Pass" move]B[tt])

(;AB[dd][de][df][dg][do:gq]
  AW[jd][je][jf][jg][kn:lq][pn:pq]
N[Setup]C[Black & white stones at the top are added as single stones.

Black & white stones at the bottom are added using compressed point lists.]
;AE[ep][fp][kn][lo][lq][pn:pq]
C[AddEmpty

Black stones & stones of left white group are erased in FF[3\] way.

White stones at bottom right were erased using compressed point list.]
;AB[pd]AW[pp]PL[B]C[Added two stones.

Node marked with "Black to play".];PL[W]
C[Node marked with "White to play"])

(;AB[dd][de][df][dg][dh][di][dj][nj][ni][nh][nf][ne][nd][ij][ii][ih][hq]
[gq][fq][eq][dr][ds][dq][dp][cp][bp][ap][iq][ir][is][bo][bn][an][ms][mr]
AW[pd][pe][pf][pg][ph][pi][pj][fd][fe][ff][fh][fi][fj][kh][ki][kj][os][or]
[oq][op][pp][qp][rp][sp][ro][rn][sn][nq][mq][lq][kq][kr][ks][fs][gs][gr]
[er]N[Markup]C[Position set up without compressed point lists.]

;TR[dd][de][df][ed][ee][ef][fd:ff]
 MA[dh][di][dj][ej][ei][eh][fh:fj]
 CR[nd][ne][nf][od][oe][of][pd:pf]
 SQ[nh][ni][nj][oh][oi][oj][ph:pj]
 SL[ih][ii][ij][jj][ji][jh][kh:kj]
 TW[pq:ss][so][lr:ns]
 TB[aq:cs][er:hs][ao]
C[Markup at top partially using compressed point lists (for markup on white stones); listed clockwise, starting at upper left:
- TR (triangle)
- CR (circle)
- SQ (square)
- SL (selected points)
- MA ('X')

Markup at bottom: black & white territory (using compressed point lists)]
;LB[dc:1][fc:2][nc:3][pc:4][dj:a][fj:b][nj:c]
[pj:d][gs:ABCDEFGH][gr:ABCDEFG][gq:ABCDEF][gp:ABCDE][go:ABCD][gn:ABC][gm:AB]
[mm:12][mn:123][mo:1234][mp:12345][mq:123456][mr:1234567][ms:12345678]
C[Label (LB property)

Top: 8 single char labels (1-4, a-d)

Bottom: Labels up to 8 char length.]

;DD[kq:os][dq:hs]
AR[aa:sc][sa:ac][aa:sa][aa:ac][cd:cj]
  [gd:md][fh:ij][kj:nh]
LN[pj:pd][nf:ff][ih:fj][kh:nj]
C[Arrows, lines and dimmed points.])

(;B[qd]N[Style & text type]
C[There are hard linebreaks & soft linebreaks.
Soft linebreaks are linebreaks preceeded by '\\' like this one >o\
k<. Hard line breaks are all other linebreaks.
Soft linebreaks are converted to >nothing<, i.e. removed.

Note that linebreaks are coded differently on different systems.

Examples (>ok< shouldn't be split):

linebreak 1 "\\n": >o\
k<
linebreak 2 "\\n\\r": >o\

k<
linebreak 3 "\\r\\n": >o\
k<
linebreak 4 "\\r": >o\
k<]

(;W[dd]N[W d16]C[Variation C is better.](;B[pp]N[B q4])
(;B[dp]N[B d4])
(;B[pq]N[B q3])
(;B[oq]N[B p3])
)
(;W[dp]N[W d4])
(;W[pp]N[W q4])
(;W[cc]N[W c17])
(;W[cq]N[W c3])
(;W[qq]N[W r3])
)

(;B[qr]N[Time limits, captures & move numbers]
BL[120.0]C[Black time left: 120 sec];W[rr]
WL[300]C[White time left: 300 sec];B[rq]
BL[105.6]OB[10]C[Black time left: 105.6 sec
Black stones left (in this byo-yomi period): 10];W[qq]
WL[200]OW[2]C[White time left: 200 sec
White stones left: 2];B[sr]
BL[87.00]OB[9]C[Black time left: 87 sec
Black stones left: 9];W[qs]
WL[13.20]OW[1]C[White time left: 13.2 sec
White stones left: 1];B[rs]
C[One white stone at s2 captured];W[ps];B[pr];W[or]
MN[2]C[Set move number to 2];B[os]
C[Two white stones captured
(at q1 & r1)]
;MN[112]W[pq]C[Set move number to 112];B[sq];W[rp];B[ps]
;W[ns];B[ss];W[nr]
;B[rr];W[sp];B[qs]C[Suicide move
(all B stones get captured)])
)

(;FF[4]AP[Primiview:3.1]GM[1]SZ[19]C[Gametree 2: game-info

Game-info properties are usually stored in the root node.
If games are merged into a single game-tree, they are stored in the node\
 where the game first becomes distinguishable from all other games in\
 the tree.]
;B[pd]
(;PW[W. Hite]WR[6d]RO[2]RE[W+3.5]
PB[B. Lack]BR[5d]PC[London]EV[Go Congress]W[dp]
C[Game-info:
Black: B. Lack, 5d
White: W. Hite, 6d
Place: London
Event: Go Congress
Round: 2
Result: White wins by 3.5])
(;PW[T. Suji]WR[7d]RO[1]RE[W+Resign]
PB[B. Lack]BR[5d]PC[London]EV[Go Congress]W[cp]
C[Game-info:
Black: B. Lack, 5d
White: T. Suji, 7d
Place: London
Event: Go Congress
Round: 1
Result: White wins by resignation])
(;W[ep];B[pp]
(;PW[S. Abaki]WR[1d]RO[3]RE[B+63.5]
PB[B. Lack]BR[5d]PC[London]EV[Go Congress]W[ed]
C[Game-info:
Black: B. Lack, 5d
White: S. Abaki, 1d
Place: London
Event: Go Congress
Round: 3
Result: Balck wins by 63.5])
(;PW[A. Tari]WR[12k]KM[-59.5]RO[4]RE[B+R]
PB[B. Lack]BR[5d]PC[London]EV[Go Congress]W[cd]
C[Game-info:
Black: B. Lack, 5d
White: A. Tari, 12k
Place: London
Event: Go Congress
Round: 4
Komi: -59.5 points
Result: Black wins by resignation])
))

Edits:

  1. Fixed topology of desired output.
  2. Added note to clarify intention.
Improve this question
6
  • What logic determines that in the second output the order of the top-level children is the same as in the first output, except for the last child, which has become first in the second output? Commented Sep 22 at 10:07
  • maybe create 2D array (list of rows) and put elements using coordinates x,y and later display all rows. Commented Sep 22 at 12:50
  • 1
    Hello Ali, could you edit your question and attach an minimal-reproducible-example and the contents of “ff4_ex.sgf” so we can test it? (as text, not images). Commented Sep 22 at 13:07
  • @trincot I manually made the desired output tree so I might have made a mistake. The main variation of the game record starts from the root node and follows the chain of first children. That chain should show as the left most line of nodes. Each alternative variation should show in subsequent columns. Hope that clears it up. Commented Sep 26 at 23:07
  • @furas Thanks for the idea to use node properties to determine a (row, col) to place the node marker. The depth is already a property available on each node which can be used to give the row number. I need to think of a way to get the column number. Commented Sep 26 at 23:11

1 Answer 1

Reset to default
1

There seem to be two conversions you are looking for:

  1. The tree output should be transposed, so it grows its levels downward instead of sideways.
  2. In this transposed format, the first child of a node is to appear in the same column, without additional shift/indentation.

We could take these steps:

  1. Convert that tree to a matrix, where you could first aim for the more intuitive lay-out that closely resembles your first output, except that first-children, appear in the same row (not the next).

  2. Pad the rows so they have the size, and then transform this matrix

  3. Add connector characters in this matrix (─, ┬, and ╮)

  4. Create an output string from that matrix

Here is an implementation:

import re

def tree_to_matrix(node):
    def recur(node, row):
        symbol = "⛶⬤◯"[
                2 if "B" in node.properties else ("W" in node.properties)
        ]
        row.append(symbol)
        if not node.children:
            yield row
        depth = len(row)
        for i, child in enumerate(node.children):
            yield from recur(child, row)
            row = [" "] * depth

    return list(recur(node, []))

def matrix_padded(matrix, value=None):
    width = max(map(len, matrix)) # all rows should grow to get this size
    return [row + [value] * (width - len(row)) for row in matrix]
        
def matrix_transposed(matrix):
    return list(zip(*matrix))

def matrix_connectors_added(matrix):
    def reversed_connectors(row, succ):
        symbol = None
        for up, down in zip(row[::-1], succ[::-1]):
            if down != " ":
                if up == " ":
                    up = symbol or "╮"
                    symbol = "┬"
                else:
                    symbol = None
            elif up == " " and symbol:
                up = "─"
            yield up

    return [
        reversed(list(reversed_connectors(row, succ)))
        for row, succ in zip(matrix, matrix[1:])
    ] + matrix[-1:]  # last row has no connectors

def matrix_to_str(matrix):
    return re.sub(r"  ([─┬╮])", r"──\1",
                  "\n".join(("  ").join(row) for row in matrix))

# Taking all steps together:
def tree_to_str(root):
    mat = tree_to_matrix(root)
    mat = matrix_padded(mat, " ")
    mat = matrix_transposed(mat)
    mat = matrix_connectors_added(mat)
    return matrix_to_str(mat)


# Main
root = SGF.parse_file("./examples/ff4_ex.sgf")
print(tree_to_str(root))
Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Thank you for your time and consideration with your answer. The nodes already have 3 of 4 of the items in your bullet list: node.depth, node.name, node.children. Just the second bullet is missing. I will think about how to add it -- perhaps some kind of modified sum of list index numbers along the way from root to node. Anyway. Let me look at and consider your implementation.
Please be aware that depth and height are different concepts. And it is in my answer because your question specifies a desired output that is only possible when nodes are re-ordered. If that is not required, and the order should not be altered, then please update the desired output in your question. In that case the code can be simplified.
Looks like I did mess up my manually made desired output. I fixed it so that the chain of first children is the left most column and each variation is in a subsequent column. Thanks for spotting my mistake. I thought the depth and height were complementary. Looks like there is more too it. Thanks for the clarity.
After you updated the desired output in your question, I have removed the need for sorting from my answer, which also means no new nodes need to be created. Please check.
Thank you again for helping out. This new code does what I was asking for so I accepted the answer. I just want to try and understand how this matrix_connectors_added function works. Looks like it (1) loops through the rows of the matrix as pairs of the current and next rows (2) loops through those pairs in reverse (3) applies logic to corresponding items from the current and next row (4) and finally just appends the last row since it is neither included in the row pairing above nor will it ever have connectors anyway.
It is the logic applied in (3) that I want to make sure I understand. So far, I understand that (a) it starts by applying no connector symbol by default unless one of the following checks is triggered. (b) if next-row-item is not blank and current-row-item is blank then add an elbow connector. (c) if next-row-item is not blank and current row item is not blank then is still none. (d) if next-row-item is blank and current-row-item is blank then apply the straight connector. I did not understand what is happening with logic for the tee connector.
The logic for getting the elbow or the tee is the same: which one of the two will be placed depends on the value of symbol. Whenever symbol is None it means we arrived at a new set of children, and an elbow should be placed. If symbol is not None it means we already visited a sibling of the current child, and so a tee is needed. That tee character is the value of symbol (when it is not None) and so the or expression will just evaluate to the tee symbol in that case.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.