ICGA web site - this is mainly another "links" page, but I won't duplicate all the links here.

There has been a surge of interest in LOA programming, so I've established a mailing list for devotees to share their obsession. Links to subscribe and so on can be found at yahoogroups.com

The "obvious" effecient solution incrementally maintains a count of groups, and updates the groups incrementally as moves are made. A recursive enumeration of each group is performed to determine the new group topology. Most of the proposed implementations I've hear of are along the same lines. There is a better solution.

**Q0**,**Q2**, and**Q4**; quads with no pieces, two pieces adjacent, or all four squares occupied. These have no curvature, and are not important to determining the number of groups.**Q1**; quads with one out of four squares occupied. These have Pi/2 curvature.**Qd**; quads with two pieces on a diagonal. These have -Pi curvature, because in LOA they are considered to be connected. If they were considered disconnected, as is the case in "Go", then the curvature would be +Pi. It's easy to visualize the curvature of Qd's if you imagine that the diagonal's slightly overlap, or just fail to meet, depending on if you want to consider diagonals to be connected or not.**Q3**; quads with three out of four squares occupied. These have -Pi/2 curvature.

The actual formula for Euler number(W) is 4W=n(Q1)-n(Q3)-2n(Qd)

This last qualification, about the number of holes, is the reason why this method isn't a complete solution. If the number of objects according to the quad count is greater than one, then the game is definitely not over. If the number of objects is one or fewer, then it is necessary to use some other method to determine if it really is a win, or if there are holes.

These quad counts are basic measurements which might also be useful in other ways; consider Qd's are very weak and easy to cut, whereas Q3 and Q4 are solid and impossible to cut with a single capture.

- the obvious way, count the groups and if n=1, it's a win. This took
**512**uSec per static evaluation - the obvious improvement, count only the first group, and if the number
of stones in the first group is all of them, it's a win. This took
**325**uSec per static evaluation - using Euler number as a hint that the game is not yet over. This took
**310**uSec per static evaluation.

- Method #2 is a big improvement over #1, such that the program hardly ever has to count very many stones.
- the bookeeping to incrementally update the quad counts, which determine
the euler number, is pretty expensive;
**52**usec per change; and there are 2 or 3 changes per move

**Conclusion:** quad counting is a useful, but not world-beating, improvement.
Perhaps the major benefit of this counting method will be that the quad counts
themselves will be useful in the static evaluator.

Another amusing side note; my former employer, Information International,
built a special purpose computer called a BIP (binary image processor) which
used this algorithm as part of an early OCR system. I cut some of my best
programming teeth while working on this beast, which is why I happen to be
familiar with this obscure pair of results. The original publication
was *IEEE transactions on Computers, Volume C-20 Number 5, May 1971 (good
luck finding that!). *I have scanned and converted this classic to
gif files that are small enough and legible enough to read or print out.
11 Pages: 1 2 3 4 5 6 7 8 9 10 11

E-mail: | Go to BoardSpace.net home page |