On Jul 20, 2007, at 10:58 AM, Jason House wrote:
On 7/20/07, Ian Osgood <[EMAIL PROTECTED]> wrote:
My beginner UCT program (http://www.quirkster.com/forth/fgp.html)
uses bitboards because it is very simple to express the rules of Go
using bit operations. However, a mailbox board which contains
references into string objects which incrementally merge, split, and
track their properties (stones, liberties, neighboring enemy strings)
is likely to be faster in the long run and on larger boards, though
far more complicated to implement correctly.
I've thought about bit boards, but my big stumbling block is how to
efficiently handle captures. I can't think of any way to detect
zero-liberty chains without explicitly specifying a chain to
check. Given a specific position (say the neighbor of a point
played), I don't know how to look up the chains surrounding it
efficiently. Have you been able to solve any of these problems?
I make no claims about efficiency. When making a move (: makemove) I
check each neighbor (: check-captures) for being captured (: ?
capture). I build the chain bitmap for a neightbor stone (: string)
when needed by repeated dilation (BEGIN expand) AND the bitmap of our
own stones (bover-and) until it stops growing (bd-top bd-count TUCK =
UNTIL). The liberty bitmap (: liberties) is then one more dilation
(expand) AND the empty bitmap (empty bd-top bd-and). If that bitmap
is empty (bdup liberties b0=) then we capture the string (bd-top
capture), which is just removing it from the enemy bitmap (enemy bd-
xor) and adding it to the empty bitmap (empty bd-or).
That's a lot of work, especially toward the endgame when the groups
get large, hence my comment that a higher-level incremental
representation is a better way to go in the long run.
I did look at the code, but the language is sufficiently foreign to
me that it's not easy to zero in on one function and know what it's
doing. What language is it written in?
Forth, my favorite tinkering language. Like Haskell, Lisp, and Prolog
it can expand your mind in unaccustomed directions.
Ian
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
