Re: [computer-go] Re: Depth-first UCT
On Wed, Aug 13, 2008 at 1:29 PM, Hideki Kato [EMAIL PROTECTED] wrote: Rémi Coulom: [EMAIL PROTECTED]: Gian-Carlo Pascutto wrote: The *paper* about MTD(f) is extremely interesting because it shows that many best-first algorithms can be rewritten as depth-first algorithms. It happened for SSS, it happened for proof-number search. Who will make it happen for UCT? Actually, there was a paper presented at the 2007 Computer-Game Workshop in Japan entitled Depth-First UCT and its Application to Go, by Haruhiro Yoshimoto, Akihiro Kishimoto, Tomoyuki Kaneko, and Kazuki Yoshizoe. Abstract in English: The UCT algorithm is a representative best-first search algorithm that has been popularly used in Monte Carlo Go. This paper presents the DFUCT (Depth-First UCT) algorithm, which is an efficient depth-first variant of UCT. Experimental results in Go show that DFUCT achieves 3% improvement in running time, while the solving abilities of DFUCT and UCT are comparable. This paper is written in Japanese. Thank you for the translation. cheers stuart ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Depth-first UCT
Interesting. Could you (or someone else) explain how DFUCT works? I'd imagine it doesn't save all the nodes in memory, but that seems rather counterintuitive. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Depth-first UCT
Zach Wegner: [EMAIL PROTECTED]: Interesting. Could you (or someone else) explain how DFUCT works? I'd imagine it doesn't save all the nodes in memory, but that seems rather counterintuitive. As far as I understand, The basic idea is that DFUCT continues searching avoiding going back to root node if possible. To do this, DFUCT saves the number of wins, the number of visits and the sum of number of visits of the brothers of two nodes at root those ucb values are the maximum (first) and next to the maximum (second), in a stack. The authors claimed in the paper that although DFUCT does not behave the same as UCT when the third node at root comes up to the second, it's so rare that can be ignored. Hideki -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Depth-first UCT
Oops. Hideki Kato: [EMAIL PROTECTED]: Zach Wegner: [EMAIL PROTECTED]: Interesting. Could you (or someone else) explain how DFUCT works? I'd imagine it doesn't save all the nodes in memory, but that seems rather counterintuitive. As far as I understand, The basic idea is that DFUCT continues searching avoiding going back to root node if possible. To do this, DFUCT saves the number of wins, the number of visits and the sum of number of visits of the brothers of two nodes at root those ucb values are the maximum (first) and next two nodes should be two arcs (moves). to the maximum (second), in a stack. The authors claimed in the paper that although DFUCT does not behave the same as UCT when the third node at root comes up to the second, third node should be third arc. it's so rare that can be ignored. Sorry for mistakes. Hideki -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
