Post 2014 championships discussions and info

Richard,

    Interesting stuff - I'd love to hear more about your approach to identifying killer moves for the playouts (MAST is just a global weighting learnt for all moves, independent of state they are encountered in I believe - was yours the same?).

    On your numbered points:

1) Yes indeed.  In Sancho we have a similar issue, because we perform rollouts asynchronously from selection (selection passes queue rollout requests, which don't complete and update the tree until later).  The result is the same issue you were encountering, that multiple selections occur before the results of the previous are known.  We handle this by replacing the numVisits in each node with two quantities - numVisits (used by selection and updated also by selection, so that it DOES change synchronously as it is used to calculate UCT exploration values on the selected path), and numUpdates, which is an independent count used and updated on the back-propagation pass.  In the simplistic scheme numUpdates simply lags numVisits slightly in effect.  More recently (post 2014 competition) I've done some work to weight different playouts differently, and as a consequence numUpdates has now become a double rather than an int, and may diverge from numVisits somewhat.  I'll probably write a blog post on this at some point, but it's not a radical gain (it improves a few games significantly, but overall it's not a dramatic win, and probably wasn't worth the 2-3 weeks it cost me to get it all working right)

(2)/(3) I have plans to experiment with moving away from the normal back-propagation scheme of MCTS in an attempt to remove distortions that occur in a few cases (below), which I'm hoping to do by considering a node to have a score, and a confidence.  Selection then occurs based on exploitation+exploration from the children's score+confidence in the selection phase, foregoing back-propagation as a means to calculate, but rather always calculating based on the values in the immediate children (and caching on calculation, so back prop would just propagate some dirty flags).  The motivation for this (if I can make it work, which remains to be seen) are that MCTS back-prop copes badly in two important cases:
i) On transpositions, where a just expanded node might have some children (transposed into) that are well explored already
ii) On completion - i.e. - when a child's true value becomes known with complete confidence - if you propagate terminality up the tree where possible (wins that can always be chosen make the parent a win too, all children being losses makes the parent a loss), then node scores can suddenly make a step-change as they become know to be absolute wins/losses.  MCTS back-prop doesn't handle step changes like this well, and the parents will take some time to converge in light of the new information

4) Yes.  Sancho has done this since its origins in Quixote during the Coursera course.  It does indeed help a lot

I'll be very interested in how you get on with the neural networks.  Since the end of the first run Coursera course I've been wanting to apply genetic algorithms to heuristic pattern selection(which will require offline learning).  I probably still won't get round to looking into that though for at least another 6 months or so (too much lower hanging fruit still first).  I definitely think that learning techniques generally are the way forward.

Yup you have understood what I meant perfectly I think.  The transpositions just create links to nodes holding the same state that already exist, thus turning the tree into a DAG (acyclic if the game is well-formed or else there would be paths of unbounded length, which is not supposed to be allowed in a well formed game)

Thanks Andrew - that is great to know. Haven't tried anything other than 64-bit HotSpot. I tried both 1.7 and 1.8 and didn't notice any real runtime differences between them.

Richard, thinking about this a bit more, I am surprised that the randomization did not work.  Did you try just treating the exploration part of the selection formula stochastically?  That is to say instead of:

UCB = averageScore + alpha*sqrt(ln(numChildVisits)/numParentVisits);

use:

UCB = averageScore + alpha*Rand.nextDouble()*sqrt(ln(numChildVisits)/numParentVisits);

(maybe adjusting the value of alpha up also).  That should remove sensitivity to selecting multiple times before you are able to update the (virtual) visit count, and removes the need to perform updates on selection...