2009/5/12 terry mcintyre <terrymcint...@yahoo.com> > Are we approaching a point where it would be practical to precompute the > opening tree to some depth, cache the results on SSD, and incrementally > improve that knowledge based upon subsequent games? >
I have had a theory for a long time that the best way to build a "book" (in an automated way) is to build a playing engine, they should look the same. In several other games, people have created techniques for remembering computations to be used later as some kind learning algorithm or book building procedure. For instance by hashing the principle variation of every opening sequence you play to be loaded up later when you need it. Or keeping statistics on which moves work best and perhaps mini-maxing that data. But if that is really the best way to produce a good opening move over time, why not generalize the idea? For ANY move of the game pretend you are trying to build a position to put in some kind of opening system, or do whatever it is that you would do if this is a position you expect to encounter many times. The basic principle is to remember in some fashion, what you spent precious time learning in the first place. But this idea must be applicable in some recursive fashion so that it also becomes your move generating algorithm. Monte Carlo Tree Search comes pretty close to that. If you had some efficient method of keeping the entire tree around on disk, then you need never forget anything you learned and when a new game starts you basically take up where you left off. It's not difficult to keep the entire tree if you have the storage (or to keep the first 20 moves or something) but I don't know if there is a very efficient way to operate on a massive table like this that is on disk. One of the benefits of an opening book system is to save thinking time for later moves. You could do this by noticing that you already have a lot of data for some position and thus you allocate much less time to that move. - Don > > Terry McIntyre <terrymcint...@yahoo.com> > > On general principles, when we are looking for a solution of a social > problem, we must expect to reach conclusions quite opposed to the usual > opinions on the subject; otherwise it would be no problem. We must expect to > have to attack, not what is commonly regarded as objectionable, but what is > commonly regarded as entirely proper and normal. > > > – John Beverley Robinson, 1897 > > ------------------------------ > *From:* Michael Williams <michaelwilliam...@gmail.com> > *To:* computer-go <computer-go@computer-go.org> > *Sent:* Tuesday, May 12, 2009 10:18:28 AM > *Subject:* Re: [computer-go] Implications of a CPU vs Memory trend on MCTS > > In my system, I can retrieve the children of any node at a rate of about > 100k nodes/sec. > > And I can save nodes at a rate of over 1M nodes/sec (this is much faster > because in my implementation, the operation is sequential on disk). > > Those numbers are from 6x6 testing. > > > Don Dailey wrote: > > This is probably a good solution. I don't believe the memory has to be > very fast at all because even with light playouts you are doing a LOT of > computation between memory accesses. > > All of this must be tested of course. In fact I was considering if > disk memory could not be utilized as a kind of cache. The secret would be > to store complete trees in disk memory, trees that are not likely to be > utilized but can be utilized in a pinch. The tree store and retrieved must > outweigh by a large factor the amount of time spent creating the tree in the > first place in order for this to pay off. > > My guess is that this is impractical, but it's fun to think about how it > might be done. I'm not sure how to do it without having a caching > nightmare. > > > > > > - Don > > > > > > > > On Tue, May 12, 2009 at 12:41 PM, Michael Williams < > michaelwilliam...@gmail.com <mailto:michaelwilliam...@gmail.com>> wrote: > > > > Don Dailey wrote: > > > > On Tue, May 12, 2009 at 12:16 PM, Michael Williams > > <michaelwilliam...@gmail.com > > <mailto:michaelwilliam...@gmail.com> > > <mailto:michaelwilliam...@gmail.com > > <mailto:michaelwilliam...@gmail.com>>> wrote: > > > > I have a trick ;) > > > > I am currently creating MCTS trees of over a billion nodes on > > my 4GB > > machine. > > > > > > Ok, I'll bite. What is your solution? > > > > > > I use an SSD. There are many details, of course. But it's still in > > the works and I'm still making lots of changes and adjustments. I > > seem to be able to "solve" (there are lots of definitions) 6x6 Go in > > that when I use a komi of 3.5, it is unable to find a winning line > > for white and when I use 4.5, it is unable to find a winning line > > for black. > > > > > > _______________________________________________ > > computer-go mailing list > > computer-go@computer-go.org <mailto: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/ > > > _______________________________________________ > 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/
