std::vector compute_ev()

in csrc/liars_dice/subgame_solving.cc [931:973]

• 39 lines of code
• 8 McCabe index (conditional complexity)

std::vector<double> compute_ev(const Game& game, const TreeStrategy& strategy1,
                               const TreeStrategy& strategy2) {
  auto tree = unroll_tree(game);
  assert(tree.size() == strategy1.size());
  assert(tree.size() == strategy2.size());
  std::vector<std::vector<double>> op_reach_probabilities;
  init_nd(tree.size(), game.num_hands(), 0.0, &op_reach_probabilities);
  // values[node][hand] :=
  // sum_{z, node->z} sum_{op_hand}
  //  P(op_hand) pi^{-i}(z|op_hand) pi^{i}(node -> z|hand) U_i(hand, op_hand, z)
  std::vector<std::vector<double>> values(tree.size());
  const int player = 0;
  compute_reach_probabilities(tree, strategy2, get_initial_beliefs(game)[0],
                              1 - player, &op_reach_probabilities);

  for (size_t node_id = tree.size(); node_id-- > 0;) {
    const auto& node = tree[node_id];
    const auto& state = node.state;
    if (node.num_children() == 0) {
      assert(game.is_terminal(state));
      const auto last_bid = tree[node.parent].state.last_bid;
      values[node_id] = compute_expected_terminal_values(
          game, last_bid, /*inverse=*/state.player_id != player,
          op_reach_probabilities[node_id]);
    } else if (state.player_id == player) {
      values[node_id].resize(game.num_hands());
      for (auto [child_node_id, action] : ChildrenActionIt(node, game)) {
        for (int hand = 0; hand < game.num_hands(); ++hand) {
          values[node_id][hand] +=
              strategy1[node_id][hand][action] * values[child_node_id][hand];
        }
      }
    } else {
      values[node_id].resize(game.num_hands());
      for (auto child_node_id : ChildrenIt(node)) {
        for (int hand = 0; hand < game.num_hands(); ++hand) {
          values[node_id][hand] += values[child_node_id][hand];
        }
      }
    }
  }
  return values[0];
}