L'algorithme de monte Carlo imbriqué trouve toujours le meilleur score où le score est le nombre de mouvements sur le chemin le plus à gauche

Question

j'étudie Algorithme de monte Carlo imbriqué S'attaquer au problème de guider la recherche vers de meilleurs états lorsqu'il n'y a pas d'heuristique disponible. Il utilise des niveaux imbriqués de jeux aléatoires afin de guider la recherche. Il consiste en deux fonctions: nested(position, level) et sample(position)

La fonction d'échantillon de base joue simplement un jeu aléatoire à partir d'une position donnée, nous utilisons la fonction play(position, move) qui joue le mouvement dans la position et renvoie la position résultante.

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

S'il jouait juste un jeu aléatoire à partir d'une position donnée, n'aurait pas dû se passer sans un moment et seulement ceci: position = play (position,random move) ? Et où obtient-il le score?

La fonction de recherche de Monte-Carlo imbriquée joue un jeu, en choisissant à chaque étape du jeu, le mouvement qui a le score le plus élevé de la recherche de monte-carlo de niveau inférieur. À chaque étape l'algorithme

1. essaie tous les mouvements possibles
2. joue une recherche imbriquée au niveau inférieur après chaque mouvement
3. Méorie le mouvement associé au meilleur score des recherches de niveau inférieur.

Comme les échantillons sont randomisés, il n'est pas garanti qu'une recherche imbriquée améliorera toujours les recherches précédentes ou même les recherches de niveau inférieur. Afin de ne pas perdre les meilleurs mouvements de la meilleure séquence trouvée par une recherche précédente, l'algorithme mémorise la meilleure séquence. Si aucun des mouvements ne s'améliore sur la meilleure séquence, le mouvement de la meilleure séquence est joué, sinon la meilleure séquence est mise à jour avec la séquence nouvellement trouvée et le meilleur mouvement est joué:

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

Dans l'exemple suivant, il prétend que si la première recherche a une chance sur deux de choisir le mauvais mouvement à la racine, une recherche de monte-carlore imbriquée de niveau 1 trouvera toujours le meilleur score.

Pourtant, je ne comprends pas pourquoi pour la première étape. J'ai des difficultés lorsque je commence à jouer move = argmax_m (sample ( play (position, m)))

$$ move = Underbrace {argmax_m ( overbrace {samptans ( Underbrace {play (position, m)} _ {(1)})} ^ {(2)})} _ {(3)} $$

1. Nous nous déplaçons donc en premier pour une position désactivée donnée m. Je crois qu'il est choisi par argmax_m. Pourtant, comment peut-il choisir entre les deux nœuds? Où testons-nous la partition?
2. Pourquoi le hasard ici?
3. Où pouvons-nous tester l'argmax_m?