[computer-go] Literature review: where to apply heuristics?

[Peter Drake]

Where are heuristics applied in UCT Go?

The following is a review of the literature regarding application of
heuristics to UCT Go. It explicitly does not address questions of how
the heuristics are generated nor of other algorithmic improvements.

Numbers are section numbers within papers.

I eagerly look forward to any comments, corrections, or expansions.

Peter Drake
http://www.lclark.edu/~drake/


Chaslot G.M.J.B., Winands M.H.M. Winands, Uiterwijk J.W.H.M., van den
Herik H.J., and Bouzy B. Progressive strategies for Monte-Carlo tree
search.
1.3.1: Add heuristic value (divided by # of playouts) to UCT value.
1.3.2: Progressive widening, similar ot Coulom below.


Rémi Coulom. Computing Elo ratings of move patterns in the game of Go.
4.1: Heavy playouts, probability distribution.
4.2: Progressive widening in tree, add nth best heuristic move after a
certain number of playouts.


Peter Drake and Steve Uurtamo. Heuristics in Monte Carlo Go.
4: Heavy playouts, roulette wheel.

Sylvain Gelly and David Silver. Combining online and offline knowledge
in UCT.
5: Heavy playouts, probability distribution, with noise introduced in
a variety of ways.
7: Value of new leaf is initialized by heuristics.

Sylvain Gelly, Yizao Wang, Rémi Munos, and Olivier
Teytaud. Modification of UCT with patterns in Monte-Carlo Go.
3.2: Heavy playouts, play any move suggested by heuristics, otherwise
randomly.
3.4: Ordering of child creation in tree.




-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://computer-go.org/pipermail/computer-go/attachments/20070607/4bd12364/attachment.htm