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://i.stack.imgur.com/naQXE.jpg. 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.
