## Useful Algorithms

### Basic functions

These basic function are used to in the following algorithms. Capitals are sets of points and lowercase are single points

• R = X & Y — R contains points that are in both X and Y
•  R = X Y — R contains points that are in either X or Y
• R = X - Y — R contains points that are in X but not in Y (same as R = X & ~Y)
• R = ~X — R contains points that are not in X
• R = X.Border — R contains points that are adjacent to points in X
• R = X.Grow — R contains points in X and X.boarder
• R = X.Shrink — R contains points that are completely surrounded by points in X (same as R = X - (~X).Border)
• X[x] — returns true if X contains x
• X.Agj(x) — (X.Border)[x]
• X.empty — returns true if no stones in X
• X.any — returns true is there are any stones in X

### Groups

There are a couple ways to find groups. The fastest is to keep track of groups as you add stones to the board. The other is to generate a set of points that is the group from a given stone.

• Each time a stone is added first test if it touches any stones of the same colour. If it does then have it join that group. If it touches more than one you will have to merge those groups together. If it doesn’t touch any then it becomes a new group on it’s own.
• Here is a function that returns a point set (PS) that is the group from a location and a point set that represents all points of that colour

`PS Group (x,X)` `  PS R,T         //start empty` `  T.Add(x)       //add x to the point set T` `  while R NOT= T //Grows until it fills the group` `    R = T` `    T = T.Grow` `    T = T & X` `  return R`

### Liberties

`PS Libs (X, Y) //returns liberties points of X.  X is player stones Y is opponent stones` `  return (X.Border - Y)`

### Benson’s Algorithm : Pass Alive Groups

A chain (c) is a group of points of the player’s stones and a region (r) is a group of points of either empty or opponent’s stones. A chain is pass alive if it touches at least 2 safe regions whose empty points are liberties of the chain. A region is safe if it completely surrounded by pass alive chains.

`//Starting with an array of chains and regions` `//Every stone player stone is in exactly one chain` `//Every empty point and opponent stone is in exactly one region` `for each Region in Regions            //Iterate through each Region` `  if (Region.Shrink & empty).Any      //If there are any interior empty spaces` `    delete Region                     //Then remove the group from the list` `loop                                  //Loop though chains and regions removing unsafe ones until no more to remove` `  for each Chain in Chains            //Iterate through each Chain` `    int count = 0` `    for each Region in Regions` `      if (Chain.Border & Region).Any  //If touching a safe region` `        count++                       //Increment count` `    if count < 2                      //If not touching 2 safe regions` `      delete Chain                    //remove the chain from the list` `  PS Temp` `  for each Chain in Chains` `    Temp = Temp | Chain               //Create a Point Set that is all the safe chains` `  for each Region in Regions` `    if (Region.Border - Chain).Any    //If any point bordering the region is not in a safe chain` `      delete Region                   //Region isn't safe so remove it`