Petr,
This is not directly related to the topic of this thread, but it was
inspired by it. I hope you have found your
effective data-structure.
After playing with this some more, I ran a few comparisons between different
strategies. I wanted to show
the results for future reference. What I implemented in my bitmap-based
program is a waterfall strategy.
1) if the last move puts a group in a new atari, attempt to save it by
a) capture a neighboring group
b) if that's not possible, try to extend (only accept this move if it
removes atari status)
2) with 75% probability, pick a capturing move anywhere on the goban
accept move only if it is a valid extension for the opponent, i.e., it
would remove atari status
3) pick a uniformly random move
Detailed timings are in the attached text-file, but here is a summary:
Just finding and picking a random move takes on average 100 clock-cycles
(cc). The playout
speed for this reference case is 90 kpps on my 2.4 GHz Intel laptop on a
dedicated single thread.
For an average 112 move (9x9) game, there are an average 15 moves that
result in a new atari.
Of these 15, 30% can be saved by capturing an adjoining group (~50cc). A
further 50% can be
saved by playing an extension move (~95cc). Just adding these actions adds
on average ~13%
to the move generation routine (113cc), with the playout speed dropping by
maybe 5% (to 85 kpps).
If instead only captures are additionally considered (75% of the time), but
no atari-escapes,
the move selection becomes 55% slower (155cc). In 45% of the times we are
looking for a capture
move, one or more candidates are actually found (~23cc), but when a random
candidate is chosen
among those (~55cc), in only in 30% of the cases is it a worthwhile capture
(~50cc). The impact
on the playout speed is an appreciable drop from 90 kpps to 70 kpps.
Looking for new atari escapes first, followed by a 75% chance of looking at
general capture
moves, and finally picking a random move restores some of the playout speed
back to 74 kpps,
using 150cc for the average move selection. See the
I would be interested if anybody else could publish some comparative numbers
for how often each
type of move is played in their playout policies. Mark Boon published a
report some time ago, but
this was based on actual game records by real people.
Thanks,
René
Reference: pick random legal moves
(five identical runs, 100,000 playouts for each line)
benchmarking playouts (clock cycles)
[game] = 25780 cc, [moves] = 110.929
[game] = 25715 cc, [moves] = 110.929
[game] = 25735 cc, [moves] = 110.929
[game] = 25743 cc, [moves] = 110.929
[game] = 25971 cc, [moves] = 110.929
benchmarking playouts (wall time)
[game] = 88.8889 kpps, [moves] = 110.929
[game] = 90.1408 kpps, [moves] = 110.929
[game] = 90.1408 kpps, [moves] = 110.929
[game] = 90.1408 kpps, [moves] = 110.929
[game] = 90.1408 kpps, [moves] = 110.929
benchmarking board functions (calls/clock cycles)
[select] 110/99, [play] 106/143, [score] 61, [win] 0.42187
[select] 110/101, [play] 106/146, [score] 62, [win] 0.42187
[select] 110/99, [play] 106/144, [score] 62, [win] 0.42187
[select] 110/98, [play] 106/142, [score] 64, [win] 0.42187
[select] 110/98, [play] 106/142, [score] 58, [win] 0.42187
benchmarking move generator (calls/clock cycles, find+pick)
[moves] 110
[random] 110/43+58
[moves] 110
[random] 110/44+59
[moves] 110
[random] 110/43+58
[moves] 110
[random] 110/43+58
[moves] 110
[random] 110/43+58
Experiment 1: if last move put a group in atari, try to escape first
(five identical runs, 100,000 playouts for each line)
parameters:
try to capture an adjacent enemy group
if a capture fails, try to extend
accept the extension if it clears the atari status
benchmarking playouts (clock cycles)
[game] = 26987 cc, [moves] = 113.014
[game] = 27082 cc, [moves] = 113.014
[game] = 26893 cc, [moves] = 113.014
[game] = 27050 cc, [moves] = 113.014
[game] = 27032 cc, [moves] = 113.014
benchmarking playouts (wall time)
[game] = 88.8889 kpps, [moves] = 113.014
[game] = 86.4865 kpps, [moves] = 113.014
[game] = 86.4865 kpps, [moves] = 113.014
[game] = 86.4865 kpps, [moves] = 113.014
[game] = 84.2105 kpps, [moves] = 113.014
benchmarking board functions (calls/clock cycles)
[select] 113/117, [play] 108/145, [score] 60, [win] 0.44709
[select] 113/114, [play] 108/147, [score] 64, [win] 0.44709
[select] 113/113, [play] 108/145, [score] 63, [win] 0.44709
[select] 113/112, [play] 108/143, [score] 63, [win] 0.44709
[select] 113/112, [play] 108/144, [score] 62, [win] 0.44709
benchmarking move generator (calls/clock cycles, find+pick)
(considering local atari escapes)
[moves] 113
[atari-capture] 15/50(30%), [atari-extend] 10/95(47%)
[random] 102/42+58
[moves] 113
[atari-capture] 15/50(30%), [atari-extend] 10/96(47%)
[random] 102/42+58
[moves] 113
[atari-capture] 15/50(30%), [atari-extend] 10/95(47%)
[random] 102/41+58
[moves] 113
[atari-capture] 15/50(30%), [atari-extend] 10/96(47%)
[random] 102/41+58
[moves] 113
[atari-capture] 15/50(30%), [atari-extend] 10/95(47%)
[random] 102/41+58
Experiment 2: check for capture moves anywhere on the goban
(five identical runs, 100,000 playouts for each line)
parameters:
chance of considering a capture move: 75%
a capture move is accepted if it is a valid extension move for the oponent
benchmarking playouts (clock cycles)
[game] = 33637 cc, [moves] = 111.421
[game] = 33156 cc, [moves] = 111.421
[game] = 33147 cc, [moves] = 111.421
[game] = 33248 cc, [moves] = 111.421
[game] = 32956 cc, [moves] = 111.421
benchmarking playouts (wall time)
[game] = 71.1111 kpps, [moves] = 111.421
[game] = 70.3297 kpps, [moves] = 111.421
[game] = 69.5652 kpps, [moves] = 111.421
[game] = 68.0851 kpps, [moves] = 111.421
[game] = 66.6667 kpps, [moves] = 111.421
benchmarking board functions (calls/clock cycles)
[select] 111/155, [play] 107/150, [score] 57, [win] 0.40176
[select] 111/155, [play] 107/150, [score] 60, [win] 0.40176
[select] 111/154, [play] 107/150, [score] 58, [win] 0.40176
[select] 111/155, [play] 107/150, [score] 59, [win] 0.40176
[select] 111/154, [play] 107/150, [score] 58, [win] 0.40176
benchmarking move generator (calls/clock cycles, find+pick)
(considering captures)
[moves] 111
[capture] 83/23(45%)+38/56+48(30%)
[random] 99/42+58
[moves] 111
[capture] 83/24(45%)+37/56+48(30%)
[random] 99/42+58
[moves] 111
[capture] 83/23(45%)+38/57+48(30%)
[random] 99/42+59
[moves] 111
[capture] 83/23(45%)+37/56+49(30%)
[random] 99/42+57
[moves] 111
[capture] 83/23(45%)+37/56+48(30%)
[random] 99/42+58
Experiment 3: combine exp. 1 and exp. 2, look at atari escape moves first
(five identical runs, 100,000 playouts for each line)
benchmarking playouts (clock cycles)
[game] = 31848 cc, [moves] = 112.181
[game] = 31835 cc, [moves] = 112.181
[game] = 31930 cc, [moves] = 112.181
[game] = 31869 cc, [moves] = 112.181
[game] = 31878 cc, [moves] = 112.181
benchmarking playouts (wall time)
[game] = 73.5632 kpps, [moves] = 112.181
[game] = 72.7273 kpps, [moves] = 112.181
[game] = 73.5632 kpps, [moves] = 112.181
[game] = 73.5632 kpps, [moves] = 112.181
[game] = 73.5632 kpps, [moves] = 112.181
benchmarking board functions (calls/clock cycles)
[select] 112/152, [play] 107/142, [score] 61, [win] 0.43946
[select] 112/154, [play] 107/145, [score] 61, [win] 0.43946
[select] 112/151, [play] 107/142, [score] 57, [win] 0.43946
[select] 112/150, [play] 107/140, [score] 59, [win] 0.43946
[select] 112/151, [play] 107/141, [score] 61, [win] 0.43946
benchmarking move generator (calls/clock cycles, find+pick)
(considering local atari escapes and captures)
[moves] 112
[atari-capture] 15/44(28%), [atari-extend] 10/100(49%)
[capture] 76/22(36%)+28/56+33(10%)
[random] 99/41+59
[moves] 112
[atari-capture] 15/43(28%), [atari-extend] 10/99(49%)
[capture] 76/22(36%)+28/55+33(11%)
[random] 99/42+58
[moves] 112
[atari-capture] 15/44(28%), [atari-extend] 10/99(49%)
[capture] 76/22(36%)+28/56+33(11%)
[random] 99/42+59
[moves] 112
[atari-capture] 15/44(28%), [atari-extend] 11/99(49%)
[capture] 76/22(36%)+28/56+33(11%)
[random] 99/42+59
[moves] 112
[atari-capture] 15/44(28%), [atari-extend] 10/98(49%)
[capture] 76/22(36%)+28/56+33(11%)
[random] 99/42+58_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
