MCTS backpropagation with alpha-beta estimation

80 Views Asked by At

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.

0

There are 0 best solutions below