MCTS (дерево+Монте-Карло)

1function mcts(root: Node, sims: number, rng: () => number): Node {
2  const C = 1.4 // UCT-константа исследования
3 
4  for (let i = 0; i < sims; i++) {
5    // 1. Selection: спуск по UCT-максимумам
6    let node = root
7    while (node.children.length > 0 && !hasUntried(node)) {
8      node = bestUCT(node, C)
9    }
10 
11    // 2. Expansion: один непробованный ребёнок
12    const child = expandRandom(node, rng)
13 
14    // 3. Simulation: случайный плейаут до конца
15    const winner = playout(child, rng)
16 
17    // 4. Backpropagation: победы текут вверх
18    for (let n = child; n; n = n.parent) {
19      n.visits++
20      if (won(n, winner)) n.wins++
21    }
22  }
23 
24  return bestChild(root) // самый посещаемый
25}
26 
27function uct(n: Node, C: number): number {
28  return n.wins / n.visits + C * Math.sqrt(Math.log(n.parent!.visits) / n.visits)
29}