If the speed was lowered to 10k, I'd also participate. One of these
days, I'll speed up my engine...
Sent from my iPhone
On Mar 11, 2008, at 11:18 AM, Don Dailey <[EMAIL PROTECTED]> wrote:
Don Dailey wrote:
Petr Baudis wrote:
On Mon, Mar 10, 2008 at 06:57:07PM -0400, Don Dailey wrote:
I think you may still have a bug. You should get well over 1700
with
110,000 playouts, even if they are light playouts.
Hmmm... That is going to be some tough debugging I suspect.
Perhaps I spoke too early. I am preparing a very pure version of
UCT
which I will test. In fact, it would be good if anyone else who
want's to compare numbers test too. It will be uniform random
play-outs and no special techniques in the tree such as AMAF, RAVE or
anything else like that.
Since 110,000 play-outs may be too many for some programs, I
suggest we
use a more modest value that we can standardize on that will be
convenient for modest computers and easy on resources (so that you may
be able to run 2 or more tests on better hardware.) I suggest
exactly 25,000 play-outs that we should standardize on. 50,000 will
tax my spare computer which I like to use for modest CGOS tests.
If it is agreed, I will start a 25k test. My prediction is that
this
will finish around 1600 ELO on CGOS.
I can also run a special all-time rating list if you participate
which I
believe returns more accurate ratings - you need at least 200 games to
get on the list and I believe 500 is far better to get an accurate
rating. I'm going to try to get at least 500.
- Don
P.S.
I discovered that you can set the level substantially higher (and get
away with it) if you have code to cut down the number of playouts a
lot
in endings which are nearly won or lost. Even better is to
progressively cut down the play-outs as a function of distance from
the
opening - but then we would all have to standardize on this too and it
would probably be difficult to agree on how we should do that.
But
the issue is what rating can you expect with a relatively generic
UCT-like MC implementation given some number of play-outs.
I'm working on a new program, starting from scratch. When it gets
far
enough along I will compare my numbers (and ELO) to yours.
I'm pretty sure my code is fairly well debugged now, but of
course
there may be still bugs lurking; when I have put my bots on CGOS
for the
first time it was awfully bug-ridden (and about 800 ELO
worse ;-). What
ELO rating did pure UCT bots get historically with how many
playouts?
FatMan does 20k playouts and has heavy play-outs, very similar to
the
first paper where mogo described it's play-out strategy - basically
playing a random out of atari move or a local move that fits one of
their patterns. It is rated 1800 on CGOS. The tree expansion
policy
for nodes is based on the parent count, not the child
itself. So
once the parent has 100 play-outs children are expanded
regardless of
the number of games they have seen. (Near the end of the game
in 9x9
go some moves could be tried a few times before being expanded.)
Oh, interesting! I must have misread libEGO code which seems to use
similar thresholds.
What is the justification of using the parent playout count
instead of
the node playout count itself?
I don't know if it makes much difference how this is done, and I
don't
know how everybody else is doing it. I allocate all the
children at
once and do not have to store pointers to each child, just one
pointer
to the first child and a counter so that I know how many children
there
are. On average I'm probably expanding every other time in the
middle
of the game.
I preallocate all the memory for the nodes when the program starts
instead of using malloc and free, and I assume most others are doing
something similar.
Here is my basic data structure:
typedef struct ntag
{
int wins;
int games;
int child_count; // zero until parent wins > 100
struct ntag *children; // a pointer to a place in the big
"node
pool"
mv_t mv; // move that got us here.
} node_t;
When the child nodes are allocated, they are done all at once with
this code - where cc is the number of fully legal child nodes:
// reserve space for cc entries
n->child = &(pool[pool_count]);
pool_count += cc;
overflow checking is done outside of the search routine.
There are almost certainly better schemes, I just used what
occurred
to me to be the easiest and quickest to implement without working too
hard at it.
Some programs hash each position and the tree is more abstract, no
pointers just positions leading to other positions by zobrist hash
keys
in a hash table.
My scheme probably wastes a lot of space on nodes that are left
unvisited at the leaves of the tree. But I don't waste much on
storing
pointers since I keep them in an array.
What is the state of the art on this? How is everyone else doing
it?
- Don
---
---------------------------------------------------------------------
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
