Memory-efficient CFU Implementation
Oskari Tammelin (ot@iki.fi)
Here is an External Sampling CFU implementation in pseudo code. For simplicity's sake, each information set is assumed to have exactly three actions.
int ExternalSamplingCFU(int player, int node, int[] hands)
if (node.IsTerminal())
return node.GetPayoff(player, hands);
if (node.player == player)
u[0] = ExternalSamplingCFU(player, node.children[0], hands);
u[1] = ExternalSamplingCFU(player, node.children[1], hands);
u[2] = ExternalSamplingCFU(player, node.children[2], hands);
node.cfu[hands[player]][0] += u[0];
node.cfu[hands[player]][1] += u[1];
node.cfu[hands[player]][2] += u[2];
return u[IndexOfMaxElement(node.cfu[hands[node.player]])];
else
maxAction = IndexOfMaxElement(node.cfu[hands[node.player]]);
node.strategy[hands[node.player]][maxAction]++;
return ExternalSamplingCFU(player, node.children[maxAction], hands);
Note that we never need to know the absolute accumulated CFU values, but only the index of the current maximum. Therefore we can instead accumulate two difference
values and use the signs and the sign of the difference of these values to figure out the index of the current maximum action:
int ExternalSamplingDCFU(int player, int node, int[] hands)
if (node.IsTerminal())
return node.GetPayoff(player, hands);
if (node.player == player)
u[0] = ExternalSamplingDCFU(player, node.children[0], hands);
u[1] = ExternalSamplingDCFU(player, node.children[1], hands);
u[2] = ExternalSamplingDCFU(player, node.children[2], hands);
node.dcfu[hands[player]][0] += u[1] - u[0];
node.dcfu[hands[player]][1] += u[2] - u[0];
return u[GetMaxAction(node.dcfu[hands[node.player]])];
else
maxAction = GetMaxAction(node.dcfu[hands[node.player]]);
node.strategy[hands[node.player]][maxAction]++;
return ExternalSamplingDCFU(player, node.children[maxAction], hands);
int GetMaxAction(int[] dcfu)
return dcfu[0] > 0 ? (dcfu[1] > dcfu[0] ? 2 : 1) : (dcfu[1] > 0 ? 2 : 0);
This saves a lot of memory in games that have only two or three possible actions like fixed limit Texas Hold'em and other fixed limit poker games.