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$

1 Answer 1

0
$\begingroup$

No implementation of RAVE in academia that I am aware of implements an exploration factor into the AMAF value (C*Math.sqrt(Math.log(mChildren)/(m[i])) into your implementation). The AMAF value is only used to bias the search towards nodes with more promising moves, and doesn't care about exploring less visited moves. That doesn't mean it isn't advantageous to do so, but I am somewhat doubtful. I would test without that term.

$\endgroup$

You must log in to answer this question.

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