4
$\begingroup$

Monte Carlo Tree Search with UCT is praised for it's asymmetric tree growth, growing promising subtrees more than non-promising ones.

But in a 2-player adversarial game, when a win at one node is a loss at the node below it, wouldn't the tree growth be extremely favourable for the current player at each node, and result in a not so asymmetric tree growth?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Do you have an example for such a situation? If the game is won at a node, you have already won. How do you lose in the node below it? Considering there will be no further nodes after the game ends. $\endgroup$
    – Robin
    Commented Jul 13, 2015 at 13:51

2 Answers 2

Reset to default
1
$\begingroup$

The most explored path will be the Nash Equilibrium, because at each step we choose the best move for each player.
The asymmetry happens at each level towards the best move for the current player, thus overall the tree will not grow asymmetrically.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ I don't understand this answer. Nash equilibrium only makes sense in iterated games. Monte Carlo search is normally applied to games that are sequential games, not iterated games (each move you choose affects gameboard and affects the options open to you in the future), so the notion of a Nash equilibrium doesn't even make sense in that context. Am I missing something? $\endgroup$
    – D.W. ♦
    Commented Mar 21, 2016 at 17:41
0
$\begingroup$

With each new rollout, considering games with many traps like chess, the random playouts converge super slowly if at all. Usually based on very high rollouts and on nodes with greater exploration.. Good game play for me happens around +100000 rollouts but dependant on the game. For one rollout you are correct, but with each rollout things get incrementally better. Backpropagation over many rollouts solve this in the UCB.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Unless I've misunderstood something, this doesn't seem to answer the question. The question is talking about asymmetry of the tree but you don't seem to mention that at all. $\endgroup$
    – David Richerby
    Commented Dec 22, 2017 at 18:16
  • $\begingroup$ First players usually get a small "first to move" advantage anyway. With few rollouts the results are not symmetric or asymmetric but random. With tons of rollouts the mcts tree comes close to minimax values if the game doest have alot of traps or the game isn't sharp. If the game has sufficient traps, mcts by itself isnt optimal and play isn't ideal. $\endgroup$
    – Νικόλαος Μανωλακος
    Commented Dec 22, 2017 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.