On Wed, Jun 3, 2009 at 00:56, Michael Williams <[email protected]> wrote: > Two things: Firstly, I'm storing (only in RAM) the precalculated Winrate > and InvSqrtVisits and keeping them updated. > So my UCT formula went from > > Wins / Visits + sqrt(lnParentVisits / Visits) > > to > > WinRate + sqrtLnParentVisits * InvSqrtVisits; > > This has a memory cost, but I don't care so much about RAM since I can send > the nodes to disk. > > And the second thing is to store in the parent node a reference to what is > likely the UCT-best child node. If the parent has been visited > 100*boardspaces times, I will go directly to the likely-best child with > probability 2047/2048. Anytime a proper UCT loop occurs, the likely-best > reference is updated (about 90% of the time there is no change, so I think > it's safe).
This is quite similar to epsilon trick described here: http://www.mimuw.edu.pl/~lew/files/epsilon_trick.pdf in short when you calculate best UCT child you visit it max(best.visit_count * epsilon, 1) times with epsilon = 0.05 for instance It works well both for new and old nodes, but you have to keep the counter of visits. The soft way would be to recalculate best child with probability min(1, 1/(best.visit_count*epsilon)). Both variants of ET can give you some guarantees about the way the tree is explored. Łukasz > > > Jason House wrote: >> >> That sounds like a good optimization. What did you do? >> >> Sent from my iPhone >> >> On Jun 2, 2009, at 3:16 PM, Michael Williams <[email protected]> >> wrote: >> >>> Update: After concentrating on tightening the UCT loop, I've optimized >>> myself back into needing the SDD :/ >>> >>> But now I should be able to get to 20B nodes in just one day. >>> >>> (still only doing 7x7 Go) >>> >>> >>> Michael Williams wrote: >>>> >>>> Yes, when memory is full, I save and free all leaf nodes (which is the >>>> vast majority). Nodes are loaded as needed. >>>> Don Dailey wrote: >>>>> >>>>> >>>>> On Mon, Jun 1, 2009 at 4:57 PM, Michael Williams >>>>> <[email protected] <mailto:[email protected]>> wrote: >>>>> >>>>> I've optimized my disk access to the point where I'm mostly CPU >>>>> limited now, even when using a standard hard disk instead of an SSD. >>>>> I can now create trees of up to about 30 billion nodes, which would >>>>> take about a week. The simulation rate is continuously going down >>>>> because so much time is spent in UCT loops in the huge tree. >>>>> >>>>> >>>>> That's impressive. Are you doing things which move parts of the tree >>>>> onto the disk and back when needed? I'm curious about the details! >>>>> >>>>> - Don >>>>> >>>>> >>>>> >>>>> >>>>> >>>>> >>>>> Don Dailey wrote: >>>>> >>>>> >>>>> >>>>> On Mon, Jun 1, 2009 at 11:22 AM, Isaac Deutsch <[email protected] >>>>> <mailto:[email protected]> <mailto:[email protected] <mailto:[email protected]>>> >>>>> wrote: >>>>> >>>>> >>>>> > Well, I'll take that over crashing with an out-of-memory >>>>> error. :) >>>>> >>>>> Still, pruning seems better to me and has the same effect. ;p >>>>> >>>>> >>>>> But is it better? I think it's not so obvious without thorough >>>>> testing. >>>>> >>>>> Pruning throw away information that is lost forever and may need >>>>> to be recalculated. Requiring more simulations does not throw >>>>> out results, but results in some inefficiencies. So it's not >>>>> clear to me which is better - it may even be that it depends on >>>>> how much you push it. I am just guessing but I would guess >>>>> that pruning is better in the short term, worse in the longer >>>>> term. Imagine a search at a corespondence level, where the >>>>> computer thinks for 24 hours. Which method is best there? >>>>> Could you use hard disk or SSD? Using some kind of caching >>>>> system, where you relegate the oldest unvisited nodes to the >>>>> hard dirve. It may be that nodes you might normally prune are >>>>> unlikely to get used again but if they do you still have the >>>>> data. This is no good unless you can guarantee that the disk >>>>> is used very infrequently - but with SSD it may be more >>>>> practical. >>>>> >>>>> >>>>> - Don >>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 >>>>> Flatrate und >>>>> Telefonanschluss nur 17,95 Euro/mtl.!* >>>>> http://portal.gmx.net/de/go/dsl02 >>>>> _______________________________________________ >>>>> computer-go mailing list >>>>> [email protected] >>>>> <mailto:[email protected]> >>>>> <mailto:[email protected] >>>>> <mailto:[email protected]>> >>>>> >>>>> http://www.computer-go.org/mailman/listinfo/computer-go/ >>>>> >>>>> >>>>> >>>>> >>>>> ------------------------------------------------------------------------ >>>>> >>>>> >>>>> _______________________________________________ >>>>> computer-go mailing list >>>>> [email protected] <mailto:[email protected]> >>>>> http://www.computer-go.org/mailman/listinfo/computer-go/ >>>>> >>>>> >>>>> _______________________________________________ >>>>> computer-go mailing list >>>>> [email protected] <mailto:[email protected]> >>>>> http://www.computer-go.org/mailman/listinfo/computer-go/ >>>>> >>>>> >>>>> >>>>> >>>>> ------------------------------------------------------------------------ >>>>> >>>>> _______________________________________________ >>>>> computer-go mailing list >>>>> [email protected] >>>>> http://www.computer-go.org/mailman/listinfo/computer-go/ >>> >>> _______________________________________________ >>> computer-go mailing list >>> [email protected] >>> http://www.computer-go.org/mailman/listinfo/computer-go/ >> >> _______________________________________________ >> computer-go mailing list >> [email protected] >> http://www.computer-go.org/mailman/listinfo/computer-go/ >> > > _______________________________________________ > computer-go mailing list > [email protected] > http://www.computer-go.org/mailman/listinfo/computer-go/ > _______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
