Proficient.
Put your skills to the test.

Problem summary

Generate a mixed strategy for a one-card poker game. Each player receives a different random card, the dealer contributes A chips, and a single bet has size B. Either player is equally likely to act first. An opponent knows your strategy and chooses a best response. This is an output-only optimization task.

Constraints

2 ≤ N ≤ 50; 1 ≤ A,B ≤ 20; every probability lies in [0,1].

Worked example

The official example is a valid nonunique strategy. The generator prints different probabilities; test syntax and payoff rather than exact text.

2 2 1

1 open: check
1 check: bet 0.5
1 bet: fold
1 check-bet: fold 0.9
2 open: bet 0.8
2 check: bet
2 bet: call
2 check-bet: call 0.8

Solution analysis

1. Model the game with a fixed first and second player. There are four information sets per card: first-player open, second-player after check, second-player facing bet, and first-player facing check-bet. At each information set store regrets for its two legal actions. Subtract A/2 from each player’s payoff, making the game zero sum without changing any preference. Showdown utilities are ±A/2 without bets and ±(A/2+B) after a call; the bettor wins A/2 after a fold.
2. Use full-tree counterfactual regret minimization. Freeze strategies at the start of each iteration using normalized positive regrets (uniform if none are positive). Traverse all ordered pairs of distinct cards, compute both action utilities, and add the difference from the current expected utility multiplied by the opponent’s reach probability. For the second player negate first-player utility. Accumulate the average strategy weighted by the acting player’s own reach probability.
3. Output the reach-weighted averages after 100000 iterations. A single generated strategy combines first-player open/check-bet with second-player check/bet; since the game chooses the first player uniformly this is the required behavior in every situation. The official example is one valid strategy, not an optimal reference and not the generator’s deterministic output.
4. Regret minimization converges to equilibrium in this finite perfect-recall zero-sum game as iterations increase. A finite iteration count is an approximation: the generator always produces syntactically valid strategies, but does not certify a particular expected payoff, exact equilibrium or maximum contest score. Offline users can increase iterations and evaluate the result against a best response before packaging files.

Why it works

Each recursion node corresponds to a legal decision history, and terminal utilities exactly match chip changes after centering by A/2. Opponent-reach weighting produces counterfactual action regrets while own-reach weighting produces the behavioral average strategy. Regret matching keeps action probabilities nonnegative and summing to one, so every output line describes a valid mixed strategy. The standard finite perfect-recall regret-minimization guarantee makes average exploitability tend to zero; no finite-run optimality claim is used.

Watch out. Ordinary action-frequency averaging is incorrect at information sets reached with different own probabilities. The first and second players maximize opposite centered utilities. Never claim an exact or full-score strategy from an uncertified finite run.

Offline approximate strategy generator. Redirect each released test to poker.0x.out, validate all4N lines and best-response payoff, then ZIP outputs. Finite CFR iterations do not guarantee full score; increase the iteration constant for additional optimization.

#include<iostream>
#include<vector>
#include<array>
#include<iomanip>
#include<algorithm>
using namespace std;
struct Information{
    array<double,2>regret{},change{},average{},strategy{};
};
int n;
double ante,betSize;
vector<array<Information,4>>info;
double traverse(int first,int second,int node,double reachFirst,double reachSecond){
    // Nodes: open, after check, after bet, after check-bet.
    int player=(node==0||node==3)?0:1;
    int card=player==0?first:second;
    auto&state=info[card][node];
    double win=first>second?1:-1;
    array<double,2>utility{};
    if(node==0){
        utility[0]=traverse(first,second,1,reachFirst*state.strategy[0],reachSecond);
        utility[1]=traverse(first,second,2,reachFirst*state.strategy[1],reachSecond);
    }
    else if(node==1){
        utility[0]=win*ante/2;
        utility[1]=traverse(first,second,3,reachFirst,reachSecond*state.strategy[1]);
    }
    else{
        utility[0]=(node==2?1:-1)*ante/2;
        utility[1]=win*(ante/2+betSize);
    }
    double value=state.strategy[0]*utility[0]+state.strategy[1]*utility[1];
    double ownReach=player==0?reachFirst:reachSecond;
    double otherReach=player==0?reachSecond:reachFirst;
    double sign=player==0?1:-1;
    for(int action=0;action<2;++action){
        state.change[action]+=otherReach*sign*(utility[action]-value);
        state.average[action]+=ownReach*state.strategy[action];
    }
    return value;
}
int main(){
    cin>>n>>ante>>betSize;
    info.resize(n);
    const int iterations=100000;
    for(int iteration=0;iteration<iterations;++iteration){
        for(auto&card:info){
            for(auto&state:card){
                double total=max(0.0,state.regret[0])+max(0.0,state.regret[1]);
                for(int action=0;action<2;++action){
                    state.strategy[action]=total>0?max(0.0,state.regret[action])/total:0.5;
                    state.change[action]=0;
                }
            }
        }
        for(int a=0;a<n;++a){
            for(int b=0;b<n;++b){
                if(a!=b){
                    traverse(a,b,0,1,1);
                }
            }
        }
        for(auto&card:info){
            for(auto&state:card){
                for(int action=0;action<2;++action){
                    state.regret[action]+=state.change[action];
                }
            }
        }
    }
    const array<const char*,4>names{"open","check","bet","check-bet"};
    cout<<fixed<<setprecision(12);
    for(int card=0;card<n;++card){
        for(int node=0;node<4;++node){
            const auto&state=info[card][node];
            double probability=state.average[1]/(state.average[0]+state.average[1]);
            cout<<card+1<<' '<<names[node]<<": "<<(node<2?"bet":"call")<<' '
                    <<probability<<'\n';
        }
    }
}