Do Nested Monte Carlo Algorithm always find the best score where score is the number of moves on the leftmost path

Question

I am studying Nested Monte Carlo Algorithm addressing the problem of guiding the search toward better states when there is no available heuristic. It uses nested levels of random games in order to guide the search. It consists in two functions : nested(position, level) and sample(position)

The basic sample function just plays a random game from a given position, we use the function play(position, move) which plays the move in the position and returns the resulting position.

int sample (position)
1  while not end of game # I don't understand why did he wrote a while
2    position = play (position,random move)
3  return score

If it just played a random game from a given position, shouldn't it have been without a while and only this : position = play (position,random move) ? And where does he get the score ?

The Nested Monte-Carlo Search function plays a game, choosing at each step of the game the move that has the highest score of the lower level Nested Monte-Carlo Search. At each step the algorithm

1. tries all possible moves
2. plays a nested search at the lower level after each move
3. memorizes the move associated to the best score of the lower level searches.

As the samples are randomized, it is not guaranteed that a nested search will always improve on previous searches or even lower level searches. In order not to lose the best moves of the best sequence found by a previous search, the algorithm memorizes the best sequence. If none of the moves improve on the best sequence, the move of the best sequence is played, otherwise the best sequence is updated with the newly found sequence and the best move is played:

int nested (position, level)
1  best score = -1
2  while not end of game
3    if level is 1
4      move = argmax_m (sample (play (position, m)))
5    else
6      move = argmax_m (nested (play (position, m), level - 1))
7    if score of move > best score
8      best score = score of move
9      best sequence = seq. after move
10   bestMove = move of best sequence
11   position = play (position,bestMove)
12 return score

In the following example he claims that if depth first search has one chance out of two of choosing the wrong move at the root, A level 1 Nested Monte-Carlo Search will always find the best score.

Yet I don't get why for the first step. I have some difficulties when starting playing move = argmax_m (sample ( play (position, m)))

$$move = \underbrace{argmax_m (\overbrace{sample ( \underbrace{play (position, m)}_{(1)})}^{(2)})}_{(3)}$$

1. so we move first for a given unkown position m. I believe it is chosen by argmax_m. Yet, how can it chose between both nodes ? Where do we test the score ?
2. Why randomness here ?
3. Where can we test the argmax_m ?

Answer 1

You've asked many questions. The usual rule on this site is to ask one question per post.

The definition of sample is correct. play evaluates where you end up after making a single move. sample evaluates the result of a game where both players randomly choose a move.

In other words, imagine a particularly stupid strategy, where both players randomly pick a move (blindly, without taking into account the position or any other strategy; it's purely random) at each step. Starting from position, you could simulate playing out a full game and see what happens. The resulting score (which player won) gives you a very crude approximation of how you should evaluate position. For instance, suppose in that random playout, the first player happens to win. Then we might suspect that position is better for the first player than the second player. Obviously, this is a crude approximation, but it's just a start. And that's what sample computes.

So that approach computes the level-0 approximation of the evaluation of each position.

Of course, given a way to compute an evaluation score for any position, that gives you a way to play the game: whenever it is your turn, look at all possible moves you could make, evaluate the resulting position, and pick whichever move takes you to the position that looks most favorable for you. That's what the logic is doing with the argmax. So, this gives you a level-0 strategy.

Now we're ready to talk about how to compute a level-1 approximation of the evaluation of each position. Basically, we simulate doing a playout -- we simulate playing the game -- but now rather than using a blind random strategy, we use a slightly smarter strategy. In particular, each player uses the level-0 strategy described above to decide how to move. So now simulate a game where both players are using the level-0 strategy, starting from position, and keep going until the end of the game. See which player wins. This is your level-1 evaluation of position.

You can use the level-1 evaluation to form a level-1 strategy: always make the move that leads to the position whose level-1 evaluation is as favorable as possible.

And now you can probably see how to use this idea to form a level-2 evaluation, and a level-2 strategy, and a level-3 evaluation, and so on. That's the idea of nested Monte Carlo.