0
$\begingroup$

I am currently training a self-playing Monte-Carlo-Tree-Search (MCTS) algorithm with a neural network prior, and it seems to be working pretty well. However one problem I have is when I compare my new iteration of the player against the previous version to see whether the new one is an improvement over the previous one.

Ideally I want to compare the two players to play 20 games of Tic Tac Toe with each being the first player in 10 of them. But what ends up happening is that each of those 10 games play out identically (because the MCTS in each player is reset at the beginning of each game, and since they are playing to win, they both take the play with highest probability, rather than randomly drawing actions based on the probabilities, so each player is making exactly the same decisions as they did in the previous game).

So I understand why this isn't working, however I'm not sure what people commonly do to fix this problem? I could choose to not reset the MCTS between each game?, but that also feels like a weird fix, since the players are then still learning as the games are played, and game 10 would be quite different from game 1, but maybe that is just how people normally do this?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
1
$\begingroup$

If I understand your question correctly, your goal is to figure out whether or not the quality of your neural network is improving as training progresses.

The core issue seems to be that you do this by evaluating the playing strength of MCTS+DNN agents, but... the game of Tic-Tac-Toe is so simple, that an MCTS agent even with a completely random DNN (or no DNN at all) is likely already capable of optimal play. So, you cannot measure any improvement in playing strength.

I would suggest one of the following two solutions:

  1. Instead of evaluating the playing strength of an MCTS+DNN agent, just evaluate the playing strength of a raw DNN without any search. You could simply make this agent play according to the policy head of the network (proportionally or by maximising over its outputs), and ignore the value head. A pure MCTS (without neural network) could be used as the opponent to evaluate against (or you could evaluate against past versions of your DNN).

  2. If you do want to continue evaluating MCTS+DNN agents, you could try to severely constrain the amount of computation the MCTS part is allowed to use, such that the MCTS by itself can no longer guarantee optimal play. For example, you could let your MCTS run only, say, 10 or 20 iterations for every root state encountered.

Improve this answer
$\endgroup$
6
  • $\begingroup$ No that is not the issue. I already have more complicated games to evaluate my setup on as well. For tic tac toe, I am already using so few MCTS steps that it isn't playing optimally, but all of that is besides the point. The issue I am having is that my MCTS algorithm is deterministic and since tic tac toe starts the same way each time (with an empty board) and since I reset my MCTS algorithm after each game, then the games ends out playing out in exactly the same way, so even if I ask two MCTS algorithm to play 20 games against each other, they just end up playing the same game 20 times. $\endgroup$
    – Tue
    Feb 20 at 20:00
  • $\begingroup$ If you're already using so few iterations that it's playing suboptimally, I don't think it should be deterministic anymore. How many iterations are you using exactly? After running that number of iterations, how do you let your MCTS select its move to play? I assume picking whichever move maximises the visit count? In this case, you may have many ties, in which case it'd be very good to use random tie-breaking. The same holds during selection phase (PUCB1 equation): use random tie-breaking. $\endgroup$
    – Dennis Soemers ♦
    Feb 21 at 10:10
  • $\begingroup$ It is deterministic since there is no element of a MCTS-NN algorithm that is random. This is regardless of whether the algorithm is playing optimally or suboptimally. For a normal MCTS algorithm without neural networks, the random element comes from the playout, where random moves are typically selected, but this randomness is removed with neural networks. $\endgroup$
    – Tue
    Feb 21 at 11:40
  • 1
    $\begingroup$ @Tue Usually in larger setups I'd still expect there to be some subtle random influences (e.g., random tie-breaking, randomness from multi-threading in parallelised MCTSes, and/or random variance in number of MCTS iterations you can manage to run in given time budget), but I can see why none of those may apply in your setting. My next recommendations would be: (i) just evaluate DNN by itself, with proportional sampling instead of argmax, as I mentioned in answer, or (ii) make your MCTS sample actions proportionally to visit counts, or $\endgroup$
    – Dennis Soemers ♦
    Feb 21 at 12:00
  • 1
    $\begingroup$ (iii) instead of starting evaluating games from empty board, start one evaluation game from every possible opening move. Of course, the disadvantage of the last suggestion is that you no longer evaluate your agent's ability to select a good first move in the "real" (empty) starting state. Oh, and one more suggestion: (iv) run evaluation games against (multiple different) agents that do have some degree of randomness themselves (such as low-budget, untrained MCTSes with random playouts and low iteration counts). $\endgroup$
    – Dennis Soemers ♦
    Feb 21 at 12:02
0
$\begingroup$

MCTS bandit phase chooses an action via UCB(1) algorithm. For a given $Q(s,a)$ and the visit counts of non-leaf node, it chooses an action branch in the tree to descend via:

$$ a = \arg \max_{a'}\left[Q(s,a') + c \sqrt{\frac{\log N}{N(s,a')}}\right]$$

The $c$ parameter is the exploration temperature. If $c \gg Q$ then the second term always wins and the algorithm should be randomly exploring the whole game tree, without any value-based preference. So, one possible problem could be that your $c$ is too low.

Another possible problem is a pretty common misconception about the way MCTS works. It could be that for a single actual in-game move you are performing one MCTS search step. That's not how it is supposed to work - MCTS can be considered as an online "improvement" algorithm for offline learned value function - one should be performing multiple MCTS searches and build a reasonably large search tree for every in-game move one performs. Quoting Wikipedia:

Rounds of search are repeated as long as the time allotted to a move remains. Then the move with the most simulations made (i.e. the highest denominator) is chosen as the final answer.

Improve this answer
$\endgroup$
11
  • $\begingroup$ I think you are talking about something slightly different here. The value of c or the number of mcts search steps are irrelevant here. The problem is that before each game I reset the MCTS algorithm, and since the actions are chosen as argmax as you also have in your equation, then the MCTS will always arrive at exactly the same best action as it did in the previous game since the algorithm is deterministic and my initial configuration is the same for each game. Based on your reply I'm guessing that I'm not supposed to reset the MCTS algorithm before each game. $\endgroup$
    – Tue
    Feb 20 at 14:06
  • $\begingroup$ @Tue your $Q$ should change though, shouldn't it? Or it just could be that MCTS just perfectly explores the game tree (you said it was tic-tac toe?) then the same perfect game would be played. $\endgroup$
    – Kostya
    Feb 20 at 14:09
  • $\begingroup$ Yes my Q will change, as the game progresses, but it will change in exactly the same way in the next game I play since I have once again reset the MCTS algorithm. $\endgroup$
    – Tue
    Feb 20 at 14:21
  • $\begingroup$ @Tue You mentioned the "neural network prior". I assumed you train it or something? The randomness usually comes from the noise in the value estimation in the leaf nodes. $\endgroup$
    – Kostya
    Feb 20 at 14:42
  • 1
    $\begingroup$ "Dirichlet noise" means that you generate a random sample from a (centered) Dirichlet distribution (e.g. numpy.random.dirichlet) and add it to your prior. I don't understand how you can call that "deterministic". $\endgroup$
    – Kostya
    Feb 20 at 21:02
0
$\begingroup$

I have to answer since I can't comment yet. I have the exact same problem, all evaluation games make the same moves again and again.

I currently pick a random first action for both players, but it feels like there should be a better solution. I guess I could reuse the MCTS but that seems like an even worse hack.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .