0
$\begingroup$

I'm using CFR to solve a large imperfect-information game. One important technique for optimizing performance of this algorithm is "partial pruning", which allows the algorithm to skip updates for a player in a sequence if the other player’s current strategy does not reach the sequence with positive probability.

Can anyone help me understand how to implement this? The problem I'm having is that the utility of the information set must still be computed recursively, even if there is no regret accumulated.

For example, using the implementation provided here, the relevant section of the code is:

# Utility of information set.
util = sum(action_utils * strategy)
regrets = action_utils - util
if is_player_1:
    info_set.regret_sum += pr_2 * pr_c * regrets
else:
    info_set.regret_sum += pr_1 * pr_c * regrets
return util

If pr_2 is 0.0 (at a node belonging to player 1), then it's true that pr_2 * regrets will also be zero, making the value of regrets irrelevant. However, we still need to compute and return util for the node, which requires each child node to have been visited recursively (giving us action_utils, which is needed to compute the final util result).

I must be missing something. What can I do to actually prune this subtree? Thank you.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.