2
$\begingroup$

I'm using Monte Carlo Tree Search with UCT selection to try and build an AI player for a complex multiplayer board game. My regular UCT MCTS seems to be working fine, winning with random and basic greedy players or low-depth 'paranoid' alpha-beta variant player, but I've been looking for some methods to improve it and I found RAVE.

"In RAVE, for a given game tree node N, its child nodes Ci store not only the statistics of wins in playouts started in node N but also the statistics of wins in all playouts started in node N and below it, if they contain move i (also when the move was played in the tree, between node N and a playout). This way the contents of tree nodes are influenced not only by moves played immediately in a given position but also by the same moves played later.".

I've found a lot of literature about it and it was supposed to give good results - 70%-80% win rate against basic UCT on a game of TicTacToe3D. I implemented it as a sort of benchmark, a 4x4x4 version, before trying it on my target game. But, however I tried tuning the parameters, I've been getting worse results, the win rate is at best arount 46%.

I've been calculating the node values like this:

visits[i] is a number of visits for child i of parent p that selection is performed on, wins[i] is a number of wins according to UCT, AMAFvisits and AMAFwins are assigned based on the node's source action -> updated after a finished simulation if a sourceAction (the action that changed the game state into this state) was played in the simulation by the player of the MCTS tree root node.

for (int i = 0; i < nChildren; i++) {
    if (visits[i] < 1) {
        value = Double.MAX_VALUE - rnd.nextDouble();
    }
    else if (m[i] < 1) {
        double vUCT = wins[i]/visits[i] + C*Math.sqrt(Math.log(sumVisits)/(visits[i]));
        value = vUCT;
    }
    else {
        double beta = Math.sqrt(k/(3*visits[i] + k));
        double vRAVE = (AMAFscores[i])/(m[i]) + C*Math.sqrt(Math.log(mChildren)/(m[i]));
        double vUCT = (wins[i])/(visits[i])+ C*Math.sqrt(Math.log(sumVisits)/(visits[i]));
        value = beta * vRAVE + (1 - beta) * vUCT;
        value += rnd.nextDouble() * eps;
        /*double beta = Math.sqrt(k/(3*visits[i] + k));
        double vRAVE = (AMAFscores[i])/(m[i]);
        double vUCT = (wins[i])/(visits[i]);
        value = beta * vRAVE + (1 - beta) * vUCT;
        value += C*Math.sqrt(Math.log(sumVisits)/(visits[i]));
        value += rnd.nextDouble() * eps;*/
    }
    if (maxValue <= value) {
        maxValue = value;
        index = i;
    }
}
chosen = tree.getTreeNode(children.get(index));

Here's a paint rendition of my understanding of how RAVE should work -> https://imgur.com/a/MM4K1HE. Am I missing something? Is my implementation wrong? Here's the rest of the code responsible for traversing the tree in a 'rave way': https://www.paste.org/104476. The expand function on tree expands the tree for all actions, and returns a random one which then gets visited, the others are to be visited in other iterations.

I first tested the code on k = 250 like the authors of the benchmark paper https://dke.maastrichtuniversity.nl/m.winands/documents/CIG2016_RAVE.pdf suggested and on 100, 1000 and 10000 iterations, with tree depth 20 or 50. I also experimented with other k values and other params.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.