On Nov 13, 2007, at 7:46 AM, Jason House wrote:
On Nov 13, 2007 10:36 AM, Ian Osgood <[EMAIL PROTECTED]> wrote:
I like Forth. I got excited about UCT around the time of the Computer
Olympiad and wrote a bitmap-based 9x9 program. What is the general
impression on bitmap vs. mailbox board representations for Monte
Carlo readouts?
I never went down the road of bitmap based go because I had not
clever way to efficiently track captures. How did you get around
this hurdle?
I never claimed efficiency.
What do you mean by "track captures"? You mean detect when a string
loses all its liberties? That is simply when the intersection of the
set of empty points with the string expanded once is the empty set.
This can only happen to strings bordering a move, so I do the check
there:
\ liberties of a string
\ liberties == neighbors & empty
\ b w . 0 0 1
\ . w . -> 1 0 1
\ . b b 0 0 0
: liberties ( [s] -- [l] )
expand empty bd-top bd-and ;
: capture ( s -- )
DUP empty bd-or enemy bd-xor ;
\ check for liberties at each dilation for an early cutoff
: ?capture ( x y -- )
2DUP enemy bd-@ IF
bbit 1 ( [s] count )
BEGIN
expand
empty bd-top bd-intersects? IF \ liberties? exit
bdrop DROP EXIT THEN
enemy bd-top bd-and
bd-top bd-count TUCK =
UNTIL \ no liberties: capture
bd-top capture bdrop DROP
ELSE
2DROP THEN ;
: check-captures ( x y -- )
OVER 1+ OVER ?capture
OVER 1- OVER ?capture
2DUP 1+ ?capture
1- ?capture ;
Currently, my program does very little incremental storage,
recalculating strings when needed.
Ian
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
