Natural Stone Placement

Natural Stone Placement is a simple algorithm for organic-looking stone placement on virtual gobans. I (Niclas Mattsson) developed the algorithm because I feel that much of the aesthetics of Go played on a real goban lies in the chaotic bustle of stones clashing against each other, and I have been wondering for some time now why no computer-based gobans (known to me) feature irregular stone placement. So, in the hope of improving the aesthetics of virtual Go, I hereby release this algorithm to the public domain. Feel free to implement it in any software, free or commercial, but I appeal to your sense of honor as a Go player when I ask in return that you credit me and link to this page.

Example:

Have a look at the following animated gif of the famous Ear Reddening Game where the stones bump around organically, complements of the algorithm below. For me, this is Wabi Sabi! I've tried to make the board and stone dimensions realistically asymmetric. Unfortunately I didn't have time to go for the full Monty with stone textures, 3D goban, etc. (see below). I aimed for a fairly subtle but still readily apparent look to the stone randomness, but this is easily tweaked for more or less effect using the parameters below. Anyway, I think it's pretty cool how a new stone "elbows its way" into a crowd.

General idea:

1. Generate normally distributed random X- and Y-coordinates for each stone. The standard deviation is a measure of the randomness of stone placement and should be tweakable by the end-user. Don't be too conservative here - we fix collisions next.

2. Determine if the new stone to be placed overlaps any of its four immediate neighbors.

3. Fix conflicts by generating new "conservative" X-coordinates for both overlapping stones. The conservative placements are generated using lower standard deviations, typically around half the default value for free stones. For example, suppose there is a conflict with its left neighbor. First we re-center the X-coordinates of both stones. After the adjustment of the left stone, we may have caused an overlap with *its* left neighbor (which in turn may conflict with the next, etc.). Resolve this using a recursive function call, only checking to the left, stopping when there is no overlap (usually only a stone or two away). Repeat for the other three directions. Notice we do not adjust Y-coordinates when resolving problems in the X-direction. This conserves much of the randomness on the board, although off-center stone placements tend to become a bit more orderly as things get crowded. Also notice that overlap still occurs - just like on a real goban.

4. Finally, refresh the goban, possibly with new coordinates for some stones.

Algorithm in meta-code:

The algorithm below is complete with mostly everything that concerns the physical placement of the stones. Higher level tasks like checking for and removing dead stones is not my concern here. The code has been somewhat edited for clarity, e.g. not all parameters needed are passed to the functions, the four Check_Neighbor functions could be lumped together into one, etc. Also, I take a simplistic "refresh all stones every move"-approach.

% First some parameters, in units relative to horizontal width between lines

stone_radius = 0.5 * 22.2/22;  % the diameter of a stone is very slightly larger than square width
aspect_ratio = 23.6/22;        % square length/width
std_deviation = 0.07;          % so typical random placement is 7 percent off center
max_deviation = 0.12;          % let's not go crazy, no more than 12 percent off for any stone
low_std_deviation = 0.04;      % corresponding value for conservative placement (to re-center after collision)
low_max_deviation = 0.07;      % ditto

% Now declare some important variables

xcoord(1..19, 1..19):  float;  % Coordinate offset X-direction
ycoord(1..19, 1..19):  float;  % Coordinate offset Y-direction
stone(1..19, 1..19): integer;  % Stone placed here, 0: none  1: black  2:  white
x,y:  integer;                 % Hold board coordinates, 1..19

% Some procedures to help out

function offset = Generate_Coord(std_dev, max_dev)
% Generates coordinate offset
offset = max(-max_dev, min(max_dev,std_dev*randnormal(0,1)) );  % Nice one-liner: takes a random number (standard normal distribution),
return;                                                         % scales by std_dev and truncates outliers outside the range [-max_dev..max_dev]

function Check_Left_Neighbor(x,y)
% Check adjacent left stone for overlap and re-center both
if x-1 >= 1 and stone(x-1,y) then                                          % if there's a stone to the left ...
   if 2*stone_radius-1+xcoord(x-1,y)-xcoord(x,y) > 0 then                  % ... and the stones overlap ...
      xcoord(x,y) = Generate_Coord(low_std_deviation,low_max_deviation);   % ... then give this stone new conservative X offset
      xcoord(x-1,y) = Generate_Coord(low_std_deviation,low_max_deviation); % ... and its left neighbor too.
      Check_Left_Neighbor(x-1,y);                                          % Finally, see if this causes more collisions further to the left (recursive call)
   endif;
endif;
return;

function Check_Right_Neighbor(x,y)
% Same comments as above
if x+1 <= 19 and stone(x+1,y) then
   if 2*stone_radius-1+xcoord(x,y)-xcoord(x+1,y) > 0 then
      xcoord(x,y) = Generate_Coord(low_std_deviation,low_max_deviation);
      xcoord(x+1,y) = Generate_Coord(low_std_deviation,low_max_deviation);
      Check_Right_Neighbor(x+1,y);
   endif;
endif
return;

function Check_Up_Neighbor(x,y)
% Same comments as above
if y-1 >= 1 and stone(x,y-1) then
   if 2*stone_radius-aspect_ratio+ycoord(x,y-1)-ycoord(x,y) > 0 then         % note 'aspect_ratio' here instead of 1 (rectangle, not square)
      ycoord(x,y) = Generate_Coord(low_std_deviation,low_max_deviation);
      ycoord(x,y-1) = Generate_Coord(low_std_deviation,low_max_deviation);
      Check_Up_Neighbor(x,y-1);
   endif;
endif;
return;

function Check_Down_Neighbor(x,y)
% Same comments as above
if y+1 <= 19 and stone(x,y+1) then
   if 2*stone_radius-aspect_ratio+ycoord(x,y)-ycoord(x,y+1) > 0 then
      ycoord(x,y) = Generate_Coord(low_std_deviation,low_max_deviation);
      ycoord(x,y+1) = Generate_Coord(low_std_deviation,low_max_deviation);
      Check_Down_Neighbor(x,y+1);
   endif;
endif;
return;

function Draw_Board()
% Draws the goban, details excluded.

function Place_Stone(x,y,color)
% Place a black or white stone at (x,y), details excluded. Coordinates (x,y) here are exact floating point placements of the stone's center.

function Fit_Stone(x,y)
% MAIN - fit a stone at (x,y) and make adjustments
xcoord(x,y) = Generate_Coord(std_deviation,max_deviation);
ycoord(x,y) = Generate_Coord(std_deviation,max_deviation);
Check_Left_Neighbor(x,y);
Check_Right_Neighbor(x,y);
Check_Up_Neighbor(x,y);
Check_Down_Neighbor(x,y);
Draw_Board();
for i = 1..19                            % Refresh board and all stones
   for j = 1..19
      if stone(i,j) then
         Place_Stone(i+xcoord(i,j),aspect_ratio*(j+ycoord(i,j)),stone(i,j));
      endif;
   endfor;
endfor;
return;

Example 2: Ordinary square goban with normal stone placement

For comparison, here is how the same game looks on an ordinary goban. Of course, this is a special case of my algorithm, obtainable using the parameters: std_deviation = 0; low_std_deviation = 0 and aspect_ratio = 1.

My ideal virtual goban

• 3D goban with nice wood texture (the OpenGL goban of glGo is a good example)
• slate and shell stone textures - which rotate randomly (CGoban does this beautifully)
• correct non-square dimensions for lines and correct stone size (slightly too big for the line width)
• natural stone placement for a nice busy battleground look

So, which developer will be first to give me this? I've done my part now!

Reader comments below:

tderz: I am impressed!
It´s the first time that I see something ´moving´ on Senseis and then your idea is interesting.
At present, some únnatural´ impossible overlaps are disturbing and should be avoided, IMO.

Dave: You should check out the "fuzzy stone placement" option in kombilo. If memory serves Ulrich Görtz implemented this a few years ago in the earliest versions.

RueLue: The SunXi Go-screensaver has this feature too.

NiclasMattsson: Thanks tderz for the feedback, and Dave and RueLue for pointing out these applications. I'm glad other people are thinking in the same terms. My purpose isn't to claim originality of this idea (although I hadn't seen the other applications), but to place my algorithm in the public domain in the hope that it finds its way into Go clients.

sjd123: Wow, that boards pretty cool!

eddie?: Looks nice. Maybe I'll implement it in my long-running, on-going proces of a fully 3D GO game. However, I think that the 'randomness' is not correct. I think that, for example, we tend to place stones slightly above the line when placing the stone in the lower part of the board, and slightly below the line when placing in the upper part (same for left and right). Also, placing a stone right next to another stone can also lead to variants in the placement. Last, I've seen players 'slide' the stone in position. I'd like to implement this also, however I don't have a algorithm on the movements (when slide the stone from left to right, how far, etc) yet. I think it'll be cool to also have this.

TheCount: Yeh, very nice. It's good that the stones all look a bit different too.

Calvin: Of course, a real natural stone placement would have the occasional stone slamming down, sending 3 or 4 nearby stones careening off the board, like a nuclear tesuji. Then they would be re-assembled in slightly different locations, but I digress...

Michael?: I'd have to get used to that. I'm not sure if the application of it makes sense to actually play Go that way. It certainly is great from a computational point of view.

kendfrey?: This algorithm inspired me to create my own version. Right now it's nothing more than a piece of art.