3
$\begingroup$

In this blog toward the end, the author writes the following: pic_0 pic

For the sake of my question, let’s assume that a terminal state gives a reward of +1 for a win and -1 for a loss.

When the author says “for any two consecutive nodes this perspective is opposite,” does that mean that if $Q_i$ is positive (for example, 4) for player A at a given node, the same node will have the negative of that value for player B (-4 in my hypothetical)?

Do I need to compute two statistics to store the node value (one for each player) or can I simply store statistics for one player and flip the sign at every consecutive node?

$\endgroup$
2
$\begingroup$

In UCT, the value of Q(vi) / N(vi) is bounded between 0 and 1. Normally when applying MCTS to 2-player games, what happens is the following:
N(vi) corresponds to the total number of games simulated in node vi.
Q(vi) corresponds to the total number of games simulated and won in node vi.
So in each simulation Q(vi) will add +1 to the winning player and +0 to the losing player.

In a tree representation of a 2-player game, each level will represent player A and player B alternately. So you will add 1 to every other node. I don't think it makes sense to add negative values to Qi.

So to answer your question: You only need to store N and Q for each node, where N is the total number of times that node was in the path of a simulated node and Q is the number of times it won, out of those simulations.

I can give you the example of the way I implemented that part, in a board game I saved in the state class a variable which said who the next player was ( 1 or 2). So I would know that in that state (each node is a state) the player who made the last move was the other one (by the formula: player = 3 - next_player), and I would add 1 to the Qi of those nodes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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