I'm writing an AI for a chess type game based on the MCTS algorithm. I can do backpropagation if the game was simulated, but it's a bit expensive. Instead, I do an alpha-beta with a small depth. What formula should be used to recalculate the “weight” of the parent node during backpropagation? Input data: weights and number of visits of all child nodes.
[{W0, N0}, {W1, N1}, ...]`
What to find out: Wp
. Parent node weight.
By weight, I mean the n/N value (the expectation of points scored or the probability of winning if it's a no-draw-game).
I tried using the weight of the best child element for the parent. It works, but I think it can be done better.
inline void Backpropagation(Node* node) {
while (node != NULL) {
float p = 0;
long n = 0;
node->p = 0;
for (int i = 0; i < node->length; i++) {
Node* child = node->childs[i];
if (1 - child->p > node->p) node->p = 1 - child->p;
n += child->n;
}
node->n = n;
if (node != root) this->Unmove();
node = node->parent;
}
}
Also, this approach does not use the number of visits at all. Which is wrong, it seems to me.