# Go on Graphs

## 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 oponent 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.

## Generate graphs

## 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.)