Score Bounded Monte-Carlo Tree Search. Cazenave, Saffidine. Computers and Games

Designed for settings where there are more than 2 possible outcomes in a game (they don’t mention scores though; they mention games that can also end in a draw)

Apply the algorithm to Seki and Go

They discuss MCTS as done with Go in practice, but say finding specific sequences of play in that setting doesn’t work well

Solvers can be used to correct this issue, as they don’t use estimates based on evaluation functions, but are instead based on real (partial) minimax solutions

There are methods for propagating optimistic and pessimistic bounds

Mention B* which I am not familiar with

The optimistic and pessimistic bounds are always correct (the true value is always between them)

Bounds seem to be backed up in the same way as in FS3

They point out how to make the algorithm more efficient in terms of doing computation only when the bounds in the children change

It is possible to do a similar thing in FS3 where we restart rollouts from a point deeper in the tree if its bound hasn’t changed (can treat the root as the last node whose bounds didn’t change). We knew about this but didn’t go in that direction just to keep the algorithm simpler

This algorithm looks like FS3 without the alpha-beta style cutoffs; it only cuts nodes whose bounds are disjoint from the bounds of the parent

Privacy & Cookies: This site uses cookies. By continuing to use this website, you agree to their use.
To find out more, including how to control cookies, see here:
Cookie Policy