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