# Go on Graphs

## Intuitive rules

• Each player colors in turn an uncolored node of a graph G with her/his own color.
• A group is a connected set of nodes with same color.
• A group without any uncolored neighbor is « taken », that is all its nodes are uncolored.
• The goal of each player is that the graph has more nodes colored with his/her color than other player(s).

## Team playing

• Each team has a color.
• Each team colors a node in turn.
• Inside each team, each member colors a node in turn. Advice between team members are forbidden.

## Precise rules (famine version similar to Chinese rules)

• A graph G and a half integer K (called komi) are given.
• A coloring of G with the three colors « free », « black » and « white » is maintained; all nodes are initially free.
• Two players, « black » and « white », color in turn one free node into their color; black plays first.
• Two counters, one per player are also maintained; if K >= 0, white has initially K points and black has 0 points, otherwise black has -K points and white has 0 points.
• A group is a connected set of nodes which are either all black or all white.
• A group is « taken » if no node of the group at has a free neighbor (such a free node is called a liberty of the group).
• If an opponent group is taken after a player colors a node, the group nodes are recolored as free. If no opponent group is taken, the group of the just colored node may be taken, in which case its nodes are recolored as free. When a group of k nodes is taken, the counter of the player whose color is different from that of the group is incremented by k.
• A move (coloring a node and removing taken groups if applicable) is forbidden if it produces a coloring of the graph already seen (when such situation occurs, it is called a ko).
• A player having k > 0 points can pass instead of moving; in that case his/her counter of points is decremented by 1 (to k-1 points).
• The game ends when a player cannot move or pass in which case the other player wins.

## Graph theory

• Komi parameter: We define the komi of G as the maximum integer K such that black has a winning strategy on G.

## Some references

• Segerman note on general graph Go. (Several variants of Go on a graph.)
• David Benson, Life in the game of Go, Information Sciences 10, p.17-29, 1976. (Formal definition of eyes.)
• John Tromp and Gunnar Farnebäck, Combinatorics of Go, International conference on Computers and Games, p.84-99, CG’2006. (Number of positions and games.)