[computer-go] Re: nonuniform updates to a UCT tree
Michael Williams: <49d2b6f9.1050...@gmail.com>: >Does it hurt the integrity of a UCT tree if you update it in a way that is >contrary to the >standard traverse-simulate-backup strategy? For example, what if >many simulations were run on a certain node deep in the tree and then all >those results are >backed-up the tree without doing any new traversals in between? >Aside from the time it takes to do all of those simulations, would that be a >bad thing for >the tree? >Or would the tree benefit from the increased information? Certainly. Doing multiple simulations without backpropagating the results (and treversing the tree) decreases the performance of UCT. UCT consists in a feedback process and utilizes the result of every simulation. By my experiments, batch backing-up decreases the strength of my program with around 10 ELO per the number of simulations of the batch minus one. Hideki -- g...@nue.ci.i.u-tokyo.ac.jp (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] My ongoing CGoTournament - actual results
More than ten thousand games 19x19 Go are played in my computer Go Tournament - time to again publish some results! Please have a look at my newly created site for results and more informations: www.igosoft.com All these games are played on my home PC (Windows - Intel Pentium IV - 2.6 GHz). Until now I focussed on the classical programs, so GOEMATE 2001 from Zhen Zhixing and GO++ 7.0 from Michael Reiss are still the top engines here. Recently I added a newer version of Peter Woitke´s program SUZIE for 19x19. This engine works with pure alpha-beta tree-search and a position evaluation function like most of the classical chess engines do and I think it is most remarkable how much SUZIE improved in last years without use of MonteCarlo TreeSearch techniques. SUZIE 0.40 finished third and seems to be nearly as strong as the older version of Go++ 5.0. Then FUNGO 2000 proved to be only a little bit stronger than the tested GNUGO versions 3.7.10 and 3.7.11 but weaker than GNUGO 3.7.11 on level 15. I now see that GnuGo v3.8 is released and plan to replay most of the games with this newer version as soon as possible. But first I finally want to let play the 2008 Computer Go Champion, MANYFACES v12 by David Fotland. This program offers two different engines and I want to include both, the classical but also improved engine, level "4 Kyu", still with alphabeta-TS, to replace MANYFACES 11, and the even much stronger MC-TS engine, level "2 Kyu". Than I really would be glad if I could invite more of the actual MC programs out there like MOGO, CRAZYSTONE, ZEN, FUEGO (possibly I could use the windows-executable of v0.32,SVN799 compiled by Ben Lambrechts!?), LEELA, ... and more to participate! All kinds of questions, comments or suggestions are most welcome and highly appreciated! Stefan ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Shortcuts in the tree
I think you're looking for a post by Łukasz Lew about the epsilon trick... Sent from my iPhone On Mar 31, 2009, at 8:37 PM, Michael Williams > wrote: It seems like there was a short discussion here recently about a strategy for reducing the amount of time spent updating the MCTS search tree, but now I can't find it. I don't remember much else about it. Does this ring any bells for anyone? ___ 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/
Re: [computer-go] The Zen Program
>Are your playouts simple enough so you could publish the exact algorithm in >(pseudo) source code? >I'm sure many will be interested if you are willing to share it. I need to keep details secret for a while, to retain its commercial value. But I can say that Remi's work was more important than mine. If you don't use minorization-maximization yet, I recommend studying it. -- Yamato ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Shortcuts in the tree
It seems like there was a short discussion here recently about a strategy for reducing the amount of time spent updating the MCTS search tree, but now I can't find it. I don't remember much else about it. Does this ring any bells for anyone? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] nonuniform updates to a UCT tree
Does it hurt the integrity of a UCT tree if you update it in a way that is contrary to the standard traverse-simulate-backup strategy? For example, what if many simulations were run on a certain node deep in the tree and then all those results are backed-up the tree without doing any new traversals in between? Aside from the time it takes to do all of those simulations, would that be a bad thing for the tree? Or would the tree benefit from the increased information? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Transpositions in Monte-carlo tree search
On Tue, 31 Mar 2009, Matthew Woodcraft wrote:
Jonas Kahn wrote:
You might be interested by this article, for a very complete and tested
answer. Plus the idea of grouping, but a good part of the effect seems
to me to be giving a heuristic pre-value to moves, which might be done more
efficiently otherwise:
eprints.pascal-network.org/archive/4571/01/8057.pdf
Thank you (and to the others who replied).
The idea of backing a simulation's results up to all parents ('UCT3' in
that paper) seems very dangerous to me! It's a shame they didn't have
any Go results to show for that one.
No there is no danger. That's the whole point of weighting with N_{s,a}.
N_{s,a} = number of times the node s has been visited, starting with parent a.
You can write
Value of a node a = (\sum_{s \in sons} N_{s,a} V_s) / (\sum N_{s,a})
where V_s is ideally the «true» value of node s.
In UCT2, they use V_s = Q_{s,a} the win average of simulations going
through a, and then through s.
In UCT3, they use V_s = Q_s the win average of all simulations through
s.
Assuming Markovianity (1), Q_s is a random variable with same mean as Q_{s,a}, but lower variance.
That's all.
Jonas
(1) This might be broken if you give a heuristic value to your move in
the tree based on how near it is to previous moves, but that's not
really important.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Transpositions in Monte-carlo tree search
Jonas Kahn wrote:
> You might be interested by this article, for a very complete and tested
> answer. Plus the idea of grouping, but a good part of the effect seems
> to me to be giving a heuristic pre-value to moves, which might be done more
> efficiently otherwise:
>
> eprints.pascal-network.org/archive/4571/01/8057.pdf
Thank you (and to the others who replied).
The idea of backing a simulation's results up to all parents ('UCT3' in
that paper) seems very dangerous to me! It's a shame they didn't have
any Go results to show for that one.
-M-
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The Zen Program
> Probably the most original part of Zen is in the playout. I don't think MC > simulations must be always fast, so it has a lot of hard-coded Go > knowledge. > Yamato Hello Are your playouts simple enough so you could publish the exact algorithm in (pseudo) source code? I'm sure many will be interested if you are willing to share it. Regards, Isaac -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] April 2009 KGS tournament
In message <20090331064748.227...@gmx.net>, Ingo Althöfer <3-hirn-ver...@gmx.de> writes So far, only Yamato-san has registered for Nick Wedd's next KGS tournament (to be held on April 5). It would be a shame when Zen19 would remain the only (strong) participant. Come on, gentlemen: register your engines! I am pleased to see that Aya and Fuego have now entered too. I'd like to see some more! Nick Other question: Might it be possible to find a volunteer for operating Zen19 in Pamplona? Ingo Althofer. -- Nick Weddn...@maproom.co.uk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
