Tree-representation

Path: <= CGT path =>
    Keywords: Theory, Software

Other than showing a board, pieces and so on, there are several commonly-used ways of describing games.

The tree-representation has plenty going for it, especially in computing terms. In fact it corresponds to writing games as conventional data structures [1]. Unfortunately it is the worst way to display data using a keyboard.

Article created by Charles Matthews; graphics, discussion & See also added later

Table of contents

Textual notation for a tree

The normal convention uses the slash[2] ‘|’ as notation for the basic tree-forming operation, and {(*) and (*)} for the left- and right-hand separators. Inside them (*) stands for any unordered list of games.

Therefore {G,...|H,...} is to be read as a crunched-onto-one-line notation for a tree with a root, left-hand 'branch' a list G,... of games and right-hand 'branch' another list H,... of games. Since each of G, H and so on may in turn be represented as a tree, with enough paper one can draw the entire tree. Books on CGT follow the universal computer science convention that trees have a root at the top and leaves below.

In this notation, we read G and so on as Left's options ('moves') and H,... as Right's options. Left isn't allowed to play (choose) in the right-hand side, though there is no reason at all that some of the games on the right of the slash can't co-incide with some on the left. In fact in games like Nim which are impartial that's exactly what happens: the lists on the left and on the right are always the same.

People use || and ||| and so on to save on some { and }: the more ||| the closer the slash is to the root. A bit deplorable, that, in my view.

Alternative: algebraic notation

Readers of Winning Ways will know that an alternative approach is to invent an algebra of games, with operations and notations for common games. This seems much less useful for the purposes of go than for the general theory (which is indeed extremely general, and aims at unifying phenomena over a broad sweep of ludic territory).

Text-graphics representation

Graphically, one can render the tree more intuitively, though less compactly. Here on SL we have only text-graphics, making it quite awkward. It is however feasible, at least for small trees, and we can even annotate them with count of the resulting positions or the value of the moves:

  A            A
 / \          / \
B   C      B(+1) C
   / \          / \
  D   E        D E(-3)
 / \          / \
F   G      F(20) G(-2)

Notes and discussion

Data structures

[1] This is natural if one assumes a certain attitude to combinatorics, a flourishing if junior branch of mathematics. Combinatorics can be considered to deal with the representative behaviour of typical data structures of some type. This would be my definition of the subject matter: combinatorialists tend to argue in terms of proofs and techniques for those.

The reduction to canonical form is a typical (successful) combinatorial procedure, combing out 'data' not needed in a game for the usual purposes.

Data structures without explicit constraints on their structure tend to be 'ragged', and the number of possibilities grows fast in typical cases (the 'combinatorial explosion'). What this might have to do with go is that the explosion of possibilities is familiar to players; but strong players in general feel that go is 'tidy' and 'equitable' – you might say this corresponds to ideas of shape and exchange which are well-researched working concepts.

Nomenclature: ‘slash’ or ‘bar’

[2] Bill: Charles is correct that the vertical bar (|) is called slash in this notation. See Winning Ways or On Numbers and Games.
Anon: Vertical bar or pipe (|) is called slash (/) ? Is plus (+) called minus (-) as well ? How far does this deliberate misnaming extend? Berlekamp's Mathematical Go calls | bar on page 16 where it is introduced. Slash does not appear in the index. | appears in the index on pages 16 and 45. He seems to have abandoned this silliness. Its not that the rose smells less sweet with a different name. Its that no one understands why the flower you insist on calling an orchid has thorns.b
xela: The English word slash has many different meanings in different contexts. If there is an existing convention of using it this way in this context, then giving it a different name on SL would only cause confusion. For what it's worth, there are other contexts in which the symbol "+" is called or and "-" is called not. Sometimes "/" is called over or divided by. And so on. It has nothing to do with thorns.

Bill: Well, both Winning Ways and On Numbers and Games have recently been reprinted. Someone could check to see if the terminology has changed. But anyway, as far as quoting Charles is concerned, I believe he studied some CGT under John Conway at Cambridge. There is no doubt that | was called slash at that time.

Also, I believe that the use of | to represent a software pipe came later. Should we then say that that was wrong, since | already meant slash?

Patrick Traill: Looking at Unicode tables I see that slash is only used for ‘/’, ‘|’ is just called ‘vertical bar’ and ‘\’ ‘backslash’. (And a thorn is, of course, ‘Ž’ / ‘ž’ as in Old English and Icelandic.) This is, at least, what the GNOME character map on my Linux says. The second (2001) edition of ONAG does not mention ‘slash’ or ‘bar’ in the index; the second (2004) edition of WW has only ‘slash’, meaning ‘|’, which I find unfortunate (is that is due to too many years programming?). Better to follow Berlekamp (1994!) and call it ‘bar’, the more so as his work is the most concerned with go!

See also

For more examples, see the article Count. (As of 2018-09-12, perhaps worth moving some of those here.)


Path: <= CGT path =>
Tree-representation last edited by PJTraill on September 18, 2018 - 02:12
RecentChanges · StartingPoints · About
Edit page ·Search · Related · Page info · Latest diff
[Welcome to Sensei's Library!]
RecentChanges
StartingPoints
About
RandomPage
Search position
Page history
Latest page diff
Partner sites:
Go Teaching Ladder
Goproblems.com
Login / Prefs
Tools
Sensei's Library