The Lines of Action Programmer's Corner

Since it's likely to be a specialty interest, even within the obscure specialty of Lines of Action, I've moved items of interest mainly to programmers who might working on or thinking about programs that play the game. Ultimately I suppose the goal might be to have a computer tournament, but there's a long way to go before that can be a primary goal. Of much greater interest, to me anyway, is getting programs out there to help people play with each other, over the network, and to help spread the game to new people.


More Links
Links to other sites with things of interest to LOA programmers

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



The Mailing List
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 egroups.com

Generating Legal Moves


Static evaluation for nonterminal positions


The Connectivity Problem

In conversations with the authors of several LOA programs, the most commonly mentioned difficulty writing an effecient evaluator is that it is very time consuming to count the groups (to determine if the game is over). There is a way to reliably deduce ""game not over yet" in with an easy calculation, taking constant time.

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.

Oh all right, what is this better solution?

The better solution is based on combining two fairly well known facts in a novel way. One is the Totol Curvature Theorem, a well known result from calculus, which states that the total curvature around any closed figure on a plane is a multiple of 2 Pi. The quantity that is derived is commonly called "Euler Number" The second fact is that curvature is a locally countable property. For example, consider the types of 2x2 neighborhoods that can occur; there aren't very many of them! In fact, there are just four equaivalence classes, each with a characteristic curvature. So, as applied to LOA, if you incrementally maintain the counts of several types of quads, and do a little extra arithmetic to account for multiple counting, you can derive the number of objects (minus the number of holes) without actually finding the sizes and extents of the objects themselves.

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.

Experimental results

Using my program as a test bed, here are some results, using a "play self" game to provide data, timing three different strategies to determine if the game is over:
  1. the obvious way, count the groups and if n=1, it's a win. This took 512uSec per static evaluation
  2. 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
  3. using Euler number as a hint that the game is not yet over. This took 310uSec per static evaluation.
In other words, the clever, nonintuitive algorithm is not much better than the clever, obvious algorithm. This is due to two things.
  1. Method #2 is a big improvement over #1, such that the program hardly ever has to count very many stones.
  2. 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
. The good news is that Euler number alone is enough to determine that the game is not over in 99+ % of positions.

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