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
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
I must be missing something. What can I do to actually prune this subtree? Thank you.