void compute_strategy_recursive_to_leaf()

in csrc/liars_dice/recursive_solving.cc [76:134]

• 50 lines of code
• 10 McCabe index (conditional complexity)

void compute_strategy_recursive_to_leaf(
    const Game& game, const Tree& tree, int node_id,
    const Pair<std::vector<double>>& beliefs,
    const SubgameSolverBuilder& solver_builder, bool use_samplig_strategy,
    TreeStrategy* strategy) {
  auto& node = tree[node_id];
  auto& state = node.state;
  if (game.is_terminal(state)) return;

  auto solver = solver_builder(game, node_id, state, beliefs);
  solver->multistep();

  // Tree traversal queue storing tuples:
  //   (full_node_id, partial_node_id, unnormalized beliefs at the node).
  // We do BFS traversal. For each node:
  // - copy the policy from the partial (solver) tree to strategy.
  // - add children to the queue with propoer believes.
  // - for non-termial leaves of the solver tree, do a recursive call.
  std::deque<std::tuple<int, int, Pair<std::vector<double>>>> traversal_queue;
  traversal_queue.emplace_back(node_id, 0, beliefs);

  const TreeStrategy& partial_strategy = use_samplig_strategy
                                             ? solver->get_sampling_strategy()
                                             : solver->get_strategy();
  const TreeStrategy& partial_belief_strategy =
      use_samplig_strategy ? solver->get_belief_propogation_strategy()
                           : solver->get_strategy();
  const Tree& partial_tree = solver->get_tree();
  while (!traversal_queue.empty()) {
    auto [full_node_id, partial_node_id, node_reaches] =
        std::move(traversal_queue.front());
    traversal_queue.pop_front();
    (*strategy)[full_node_id] = partial_strategy[partial_node_id];
    const auto& full_node = tree[full_node_id];
    const auto& partial_node = partial_tree[partial_node_id];
    assert(partial_node.num_children() == 0 ||
           partial_node.num_children() == full_node.num_children());
    assert(partial_node.state == full_node.state);
    for (int i = 0; i < partial_node.num_children(); ++i) {
      auto child_reaches = node_reaches;
      const int pid = full_node.state.player_id;
      const int action = game.get_bid_range(full_node.state).first + i;
      for (int hand = 0; hand < game.num_hands(); ++hand) {
        child_reaches[pid][hand] *=
            partial_belief_strategy[partial_node_id][hand][action];
      }
      traversal_queue.emplace_back(full_node.children_begin + i,
                                   partial_node.children_begin + i,
                                   child_reaches);
    }
    if (partial_node.num_children() == 0 && full_node.num_children() != 0) {
      normalize_beliefs_inplace(node_reaches[0]);
      normalize_beliefs_inplace(node_reaches[1]);
      compute_strategy_recursive_to_leaf(game, tree, full_node_id, node_reaches,
                                         solver_builder, use_samplig_strategy,
                                         strategy);
    }
  }
}