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


  1. 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)
  2. Apply the algorithm to Seki and Go
  3. They discuss MCTS as done with Go in practice, but say finding specific sequences of play in that setting doesn’t work well
    1. 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
  4. There are methods for propagating optimistic and pessimistic bounds
    1. Mention B* which I am not familiar with
    2. The optimistic and pessimistic bounds are always correct (the true value is always between them)
    3. Bounds seem to be backed up in the same way as in FS3
  5. They point out how to make the algorithm more efficient in terms of doing computation only when the bounds in the children change
    1. 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
  6. 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 
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: