On Wed, 2007-02-07 at 14:10 -0600, Matt Gokey wrote:
> I was wondering if anyone was combining an opening library with MC/UCT
> by running a large number of the simulations and storing the results.
> This seems like a pretty natural extension to save simulation time in
> the opening.
This is not particular effective if you mean to just save the tree.
But here is what I do about the opening which seems to help some:
1. Note the very first move "out of book" that the program is asked
to search. Write the move sequence to a file.
2. Have a program running off-line that processes the positions
first encountered out of book.
The program searches each position 8 times using several minutes
per search. This is to provide variety. The moves returned
from the search are placed into the opening book.
3. The moves are played in the same proportion they were chosen.
For instance if e5 is chosen 7 times and d5 1 time, the program
will play e5 7 out of 8 times.
The book searching code of course does all the board rotations and
reflections - and when a move is chosen a random orientation is chosen
if it's appropriate. For instance after the opening move e5 if
d5 is a choice then it's equally likely to play d5, f5, e4 or e6.
I'm building the book off-line and new positions are presented faster
than new book responses can be generated. So I'm taking Lazarus
off-line once in a while so the book building procedure can "catch up."
I don't know how much this really helps - it seems to not help much
until the book gets fairly large. There are 2 ways it helps of
course - the opening moves are deep searched so presumably they might
be higher quality, and the time saved can be spent to improve the
quality of the later moves.
Lazarus spends a lot more time on early moves so this makes it possible
to save a lot of time on the first 2 or 3 moves and spend it on later
moves.
I'm in a building phase now - the book is still quite small and has 91
positions at the moment. Most of the moves it's generating are 3 or
4 ply (moves) into the game, but some are as deep as 10 ply into the
game. Probably positions from opponents who have fixed playing
algorithms or books.
At some point I intend to do some kind of analysis on the win/loss
percentage of certain moves. One possibility is to mini-max the
book lines.
This way of making a book has severe disadvantages. I think it works
great on 9x9 but if the program is improved, the book is suddenly
not very relevant and you have to start over. Since I am not a
strong player I have no way of fixing up the book. I can't recognize
when it chooses a weak move or when a stronger move is available
even if it doesn't like it.
I have a hash funciton that creates a 64 bit "cannonical" hash of
the position. The same hash is produced after a rotation for
example. A book entry is a record with 3 fields, a priority
value (how many times the deep search selected this position),
the cannonical hash of the parent position and the cannonical
hash of the posiiton AFTER the move is played. This makes
collision very unlikely. The cannonical hash takes into
consideration simple ko, so if a ko is possible it will hash
differently than the same position where the ko is illegal.
- Don
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
