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 yahoogroups.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.
- 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.
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:
- the obvious way, count the groups and if n=1, it's a win. This took
512uSec 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
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.
- 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
. 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
