Go On A Board Without Lines / Bildstein's Implementation

This page is now a little out of date. See FreeGo for a page on my actual implementation, how it's progressing, and a discussion of the system.

Storing the position of a stone

Only the center point of the stone will be stored - the rest is implied by the radius.
The center point will be stored as an x-coordinate and a y-coordinate, each represented by a 2-byte unsigned value in the range 0-65,535.
Stones width will be approximately 1/19 of this range, i.e. 3449 units wide.
The individual units of measurement equate to approximately 7 microns on a life-sized board, which seems ample accuracy.
The reason 4-byte unsigned values are not used is that some calculations will require squaring numbers from the coordinate system, so 8-byte unsigned values would be needed for the calculations.
I'm going to call each distinct position on the board a 'pixel', even though it's a complete misnomer, because I'm used to thinking of positions on a grid in terms of pixels.
The radius^[1] will be stored as a number, representing the number of pixels that the circle extends from the center point. 0 would mean that the stone sits only on the center point, and the game would dissolve into regular, square-coordinate, go.

Connection

First, we define the minimum and maximum distances allowed between stones for them to be connected:

Zmin = 2r
Zmax = 2r + 1

Connection will then be defined by this equation:

Zmin^2 < (dx)^2 + (dy)^2 <= Zmax^2 ... (Eq.1)

where dx is the distance between the centers in the x dimension and dy is the distance between the centers in the y dimension. To visualise the maximum distance allowed, consider two stones, of radius r, aligned in the x dimension and touching in the y dimension. To visualise the minimum distance (which is not allowed), imagine the two stones being one pixel closer together.

Placing stones so they touch

A common thing for a user to want to do will be to place a stone touching another stone. An easy way for the user to do this will be to specify which stone they want their next stone to touch, and then click at a point that represents the direction they want the next stone to be placed, relative to the center of the first.
For the sake of the maths, we'll assume that the first stone is at the point (0,0) and that the user has selected as the direction point (x0, y0). Then we will want the next stone to lie (approximately) on the line:

x/y = x0/y0 ... (Eq.2)

but to satisfy Eq.1.
Then we need an algorithm to find a small set of points that satisfy Eq.2 approximately but satisfy Eq.1 exactly.
To do this, we solve Eq.2 for y in terms of x if y0 > x0, or x in terms of y otherwise (just to make sure that we don't divide by zero), then we substitute this into Eq.1 and solve for y (or x), to get this equation for y (or x):

floor(sqrt(Zmin^2*y0^2/(x0^2 + y0^2))) < y <= floor(sqrt(Zmax^2*y0^2/(x0^2 + y0^2))) ... (Eq.3)

The use of the floor function is valid because we are only interested in integral solutions. As you can see, this equation wouldn't work if y0 was zero. ^[2]
Eq.3 gives us a set of possible y (or x) values, and for each one, we can solve Eq.1 for a set of x (or y) values:

floor(sqrt(Zmin^2 - y^2)) < x <= floor(sqrt(Zmax^2 - y^2)) ... (Eq.4)

And then iterating through all resultant valid positions (x,y), we choose the one that minimises the following term:

(x0 - x)^2 + (y0 - y)^2 ... (5)

Further improvement

• Does anyone know how to take the square root of an integer?

The internet suggests this algorithm ("The Babylonian algorithm") for approximating the square root of a number Y:
Start with an approximation of the solution, called X(0).
A better approximation is X(n+1) = (Y/X(n) + X(n))/2 or
X(n+1) = (2Y + X(n)^2)/2X(n)
If we start with X(0) being a number with half as many binary digits as Y, we have a fairly good starting approximation.
Then we can just continue coming up with better approximations until X(n+1) = X(n), which is then our solution.
Turns out that we can't just terminate on X(n+1) = X(n) because then we can't find the root numbers that are 1 less than the square of an odd number. We have to terminate on X(n+1) = X(n) or X(n+1) = Y/X(n).^[3]

Different things a user might want to do.

Basically all of these options involve placing a stone as close as possible to where the user clicks, subject to some constraint:

a: Place a stone at a point
b: Place a stone touching an edge
c: Place a stone touching another stone
d: Place a stone touching an edge and a stone
e: Place a stone touching two edges
f: Place a stone touching two other stones

One of the major issues is what will happen when a user selects one of these options, tries to place the stone, and the system finds that the place they are (indirectly) requesting is not a valid position (it's too close to another stone or edge that wasn't part of the original process). So, I've created this table, that says what can go wrong with each of the above, and what to do in the event that it happens:

Start   In the way   Try again with
a       edge         b
a       stone        c
b       edge         e
b       stone        d
c       edge         d
c       stone        f
d       edge         n/a
d       stone        n/a
e       edge         n/a
e       stone        n/a
f       edge         n/a
f       stone        n/a

n/a means that there is no way to satisfy the conditions set by the user for the placement of this stone.

[1] (Sebastian:) Which radius? If you mean the radius of the stones: Why do you need to store it? By definition, the diameter is constant, so the radius should be, too. What do you mean by "as a number?" An integer? I take "the stone sits only on the center point" to mean: The stone's diameter is 1 pixel. If you define the "radius" of a stone with diameter 1 as 0, then your r = (d-1)/2 = 1724.
Bildstein: Thanks for entering into a discussion so soon :) I mean the radius of the stones. By stored, I mean the software will know. It will not be stored for each stone, but only once, globally.
By number, yes, I mean integer.

[2] (Sebastian:) Are you sure this always has a solution? If e.g. x0=~y0 then you measure along the diagonal. You only have ~.7 pixels within the interval ]Rmin,Rmax].
Bildstein: No, I'm not sure. I was, but I just tried with r=10 and (x0,y0)=(30,30), and I get 14 < x <= 14, which is obviously a problem. I'll keep working on this, because I'm sure there is some solution to Eq.1 in that direction.

For r=10, there are valid solutions at (14,15) and (15,14). I'll have to figure out how to relax Eq.3 a little to allow x=14 or x=15 in this situation.
I think we can relax Eq.3 by 1 pixel either way. It is not a strict equation, but rather provides some reasonable y values that can then be substituted into Eq.4, which is strict, to provide a set of valid points. Making this set slightly bigger is okay, because we then use (5) to find the best solution.
(Sebastian:) rubilia proposed on EuclideanGo/Discussion (in German - rubilia, would you mind translating your contribution there?) to use digitized halos, determining adjacency not in a mathematical way, but just by checking if the center is adjacent to the halo. My critique there was primarily that I didn't think it solves the problem in an accurate way. However, if someone programs an application that uses digitized halos I'd love to play it!

[3] (Sebastian:) Why do you even need the sqrt? Why not just square the inequality? You then could even get rid of the floor() function.
Bildstein: We need the sqrt because we need to know exactly which x's are valid. If we square the inequality, we get an equation in x^2, which doesn't help us establish valid positions.

(Sebastian:) I see - so the floor function is not just there for type reasons, it is instrumental. If performance is of the issue, you could use a lookup table instead. (Thanks to rubilia for the idea to pick and choose adjacent points.) It just occurred to me that performance may not be an issue since you only need this once at the entry of a new point. Anyhow, here's what I had in mind:

• Fold all values of (x0,y0) into an octant, e.g. such that y0>=0; x0>=y0.
• Neglecting the single trivial case x0=y0=0 takes care of the division by 0.
• Project (x0,y0) onto the tangent:

t := r*y0/x0

• Have two arrays ready. Defined in initialization as follows:
  • x(t) and y(t) are the coordinates of the intersection of the line ((0,0),(r,t)) with the circumference (:= set of adjacent points to the halo).
  • Note: The arrays run from 0 to r, which is manageable since your r is only 1724.
• That's it. x=x(t) and y=y(t).

Bildstein:Yes, that looks to me like it would work. And then I take it the arrays are calculated at initialisation using the algorithm I describe above.

Brent: Sorry if I missed this, but what language are you using? It doesn't have a library sqrt function or something of that sort? Why do you need to calculate the square root from scratch?

Bildstein: Hi Brent. If you missed anything, it was that we are after the integral square root, i.e. the square root of an integer. In C++, at least, there is no standard function for doing that.

Now, you might suggest that you can simply convert your integer into a double precision floating point number and use the double-precision sqrt function provided in standard C++. I think this would work, but I'm not sure (perhaps some whole numbers might get rounded down to the next lowest number during conversion, giving the wrong result). The only real problem, I suppose, is future-proofing. For example, if we later went to a 64-bit underlying representation, we would certainly lose precision in the conversion to floating point representation (IEEE 754 double precision has 52 bits of precision).

Brent: Hmm, I see. I did a little research and turned up the following on http://mathworld.wolfram.com/SquareRootAlgorithms.html:

• Start with a_1 = b_1 = 1.
• Go through successive iterations by calculating:
  • a_i = a_{i-1} + b_{i-1}*n
  • b_i = a_{i-1} + b_{i-1}
• Then the sequence {a_i/b_i} gives closer and closer rational approximations to sqrt(n). (They are actually convergents, if that means anything to you.)

For example, starting with n=3 produces the sequence of approximations 1/1, 4/2, 10/6, 28/16...

The nice thing about this method is that it uses only integers, and no divisions. The only division you have to do is at the very end (once you have a sufficiently good approximation) to divide a/b (and if all you want is an integer result you can even use integer division).

The lookup table idea given above would work too, I'm sure, although I don't think it's necessary since from what I understand performance doesn't really seem to be an issue (correct me if I'm wrong).

Bildstein: How do you know when you've done enough iterations? I suppose it's when you satisfy (a/b)^2 <= N and N < (a/b + 1)^2. You're right about performance, by the way.

Brent: That is the obvious question, isn't it... (= The reason I didn't mention anything about it above is that I wasn't quite sure and of course you can always do what you suggest above. But now I think I figured it out (it's been a while since number theory =). First of all, you can actually reduce the fractions as you go along (by finding the GCD of a and b using the Euclidean Algorithm and dividing both by it). So that, for example, it would be more correct to say that n=3 produces the approximations 1/1, 2/1, 5/3, 7/4, ... Now, if a/b is reduced, there is a result from number theory that states that the approximation error is less than 1/(2b^2). So that, for example, the error of 7/4 as an approximation to sqrt(3) must be less than 1/(2*4^2) = 1/32 = 0.03125. And sure enough, 7/4 - sqrt(3) = 0.0179... So in practice, as long as you are reducing the fractions as you go, you can keep iterating until 1/(2b^2) is less than whatever happens to be your desired tolerance. Although really you wouldn't have to compute 1/(2b^2), just stop when b becomes larger than the value which would make 1/(2b^2) small enough.

Just for fun you could also check out the Binary GCD Algorithm instead of the Euclidean... not really necessary since performance isn't an issue, but it is kind of cool. (=

ilan: Some of the theory, e.g., convergents, above quoted approximation result, appears here http://www.lix.polytechnique.fr/Labo/Ilan.Vardi/continued_fractions.ps

ilan: This method corresponds to taking powers of the fundamental unit A + B sqrt(N) (that is, so that A^2 - B^2 N = 1), which is where the recurrence relation comes from. In fact, is it multiplication by this, but written using matrix notation. On the other hand, this whole discussion is ridiculous, just assume that there is a function which does this and get on with your program, e.g., by writing your program in a symbolic algebra system, e.g., MuPad which is free.

Bildstein: Hmm, I seem to have two options at this point. One is to implement an integral square root algorithm; the other is to learn all the ins and outs of installing, developing, testing and releasing in a programming language that I've never even heard of. There is a rediculous discussion going on here, but I don't think it's the one Brent and I are having.

ilan: It just reminds me of DmxDawg posting his Physics homework in the KGS chat rooms. Likewise, I don't see why this site should include long winded discussions of numerical analysis 101 facts.

Bildstein: Fair enough. I'm always glad to see people taking an interest, anyway. Sorry about being a bit snapish (I hadn't had my morning coffe yet, if that counts as an excuse). Still, in my defense, this is a sub-page, it is called "implementation", and this discussion is happening in a foot-note.

The reason I've been spending so much time discussing and no time implementing yet is that I'm still working full time and haven't had more than a couple of minutes to put a few thoughts down on electronic paper. But this is all going to change starting at the end of this week, because as of 11 Dec 2004 I'm on leave from work for 8 weeks (yay!). Stay tuned, I'll keep everyone posted.

rubilia: Reading this, I can see two issues left to think about
(see http://upload.wikimedia.org/wikipedia/de/4/42/Schnitte_und_fast_richtungsgleich.jpg for an exemplary illustration):

1. To any pair of overlapping halos, we must be able to place exactly two new halos touching both.
2. Upwards-compatibility of game records when we increase the board resolution, which might happen anytime in the future (thanks to Sebastian, who made me aware of this)

The first is not trivial, but solvable for many halo-sizes (solved in my concept). About the second, I am not sure yet. I think, neither of our current attempts overcomes it.