CP is surprisingly useless in real life, but that doesn't mean you can't use it to beat your friends at "casual" games.↵
↵
# Statement↵
↵
In the app "2 Player Games", there is this game yazy played somewhat often in Singapore. The rules are as follows:↵
↵
Each player has 11 turns. Each turn starts by you rolling five fair 6-sided die. Then, you have $2$ rerolls. In each reroll, you pick a subset of dice to "lock". The dice that are not "lock" will be rerolled. After using some of your rerolls, you pick a category out of the following $11$ not yet chosen, and your score is described below.↵
↵
1. $1 \times \text{number of dice with 1}$↵
2. $2 \times \text{number of dice with 2}$↵
3. $3 \times \text{number of dice with 3}$↵
4. $4 \times \text{number of dice with 4}$↵
5. $5 \times \text{number of dice with 5}$↵
6. $6 \times \text{number of dice with 6}$↵
7. Sum of dice rolls if some number $x$ appears in at least $3$ die, $0$ otherwise.↵
8. Sum of dice rolls if some number $x$ appears in at least $4$ die, $0$ otherwise.↵
9. $25$ if some number $x$ appears in $3$ die and another number $y$ appears in $2$ die, $0$ otherwise.↵
10. $40$ if the die rolls are $1,2,3,4,5$ or $2,3,4,5,6$ in some order, $0$ otherwise.↵
11. $50$ if some number $x$ appears in all $5$ die, $0$ otherwise.↵
↵
The winner is the player with higher score.↵
↵
Since I wanted to all $0$ of my friends at it, I decided to write a program to find the maximum expected value.↵
↵
Note: Having the maximum expected value does not mean you win with maximum probability (a player who always gets a score of $2$ will beat a player with $99$ percent chance of having a score of $1$ and $1$ percent chance of having a score of $10^9$), but I believe trying to maximise the probability of winning is much harder.↵
↵
# Solution↵
↵
Simulating all turns is too slow. Instead, we note that to find the maximum score from a given position, we only need to consider these:↵
↵
- Which categories have not been chosen↵
- The current state of the dice↵
- The number of rerolls left↵
↵
The current score of the player is irrelevant, as we can simply add it to the expected value found. For example, if the expected score of a player with $0$ current score, categories $1$ to $6$ not yet chosen, and $3$ rerolls left is $59$, the expected score of a player with $10$ current score, categories $1$ to $6$ not yet chosen, and $3$ rerolls left is $69$.↵
↵
Therefore, this leads us to formulate a DP, where $dp[\text{mask}][\text{state}][\text{rerolls}]$ is the maximum expected score if the categories not chosen are represented by the bitmask $\text{mask}$, the state of the dice is represented by $\text{state}$, and $\text{rerolls}$ is the number of rerolls left.↵
↵
This DP gives us $2^{11} \times 6^5 \times 3 = 4.7 \times 10^7$ states. This seems somewhat reasonable until we realise that we have over $42$ transitions to consider, which are:↵
↵
- Picking $1$ of the $11$ categories↵
- Picking $1$ out of the $32$ subsets to lock, and rerolling↵
↵
In the second case, we have to consider all possible dice combinations we may get when rerolling, which takes too long.↵
↵
To speed up our DP, notice that there is essentially no difference between a dice combination of $62451$ and $12456$ (besides re-ordering). Thus, by stars and bars, the number of distinct dice combinations is $\binom{10}5 = 252$, giving us $2^{11} \times 252 \times 3 = 1.5 \times 10^6$ states, and a transition complexity of approximately $32 \times 252 = 8064$. At this point, I stopped optimising my code and wrote out my DP (which took 10min to run with the `O3` flag), only to realise that me doing this is the reason why I struggle to make friends. Anyways, the maximum expected score is $165.76$.↵
↵
<spoiler summary="Implementation">↵
The code below computes the DP. It outputs an encoded database containing optimal moves to `tablebase.txt`.↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
using ld = long double;↵
vector<array<int,6>> cnt;↵
int factorial[10];↵
template<typename F>↵
void init(int n, vector<int> cur, F callback) {↵
if(cur.size() == 6) {↵
callback(cur);↵
return;↵
}↵
int tot = accumulate(cur.begin(),cur.end(),0);↵
for(int i=(cur.size()==5?n-tot:0);i<=n-tot;i++) {↵
cur.push_back(i);↵
init(n,cur,callback);↵
cur.pop_back();↵
}↵
}↵
int diceTotal(int state) {↵
int total = 0;↵
for(int i=0;i<6;i++)↵
total += (i + 1) * cnt[state][i];↵
return total;↵
}↵
int score(int state, int act) {↵
if(act < 6)↵
return (act + 1) * cnt[state][act];↵
if(act == 6 || act == 7) { // please don't leave a comment just because of this line↵
int maxCnt = *max_element(cnt[state].begin(),cnt[state].end());↵
return (maxCnt >= (act - 3) ? diceTotal(state) : 0);↵
}↵
if(act == 8) {↵
int maxPos = max_element(cnt[state].begin(),cnt[state].end()) - cnt[state].begin();↵
if(cnt[state][maxPos] != 3)↵
return 0;↵
cnt[state][maxPos] -= 3;↵
int secondMaxCnt = *max_element(cnt[state].begin(),cnt[state].end());↵
cnt[state][maxPos] += 3;↵
if(secondMaxCnt != 2)↵
return 0;↵
return 25;↵
}↵
if(act == 9) {↵
int maxCnt = *max_element(cnt[state].begin(),cnt[state].end());↵
return (maxCnt == 1 && (cnt[state][0] == 0 || cnt[state][5] == 0) ? 40 : 0);↵
}↵
if(act == 10) {↵
int maxCnt = *max_element(cnt[state].begin(),cnt[state].end());↵
return (maxCnt >= 5 ? 50 : 0);↵
}↵
assert(0);↵
}↵
vector<int> stateToDice(int state) {↵
array<int,6> stateCnt = cnt[state];↵
vector<int> diceRoll;↵
for(int i=0;i<6;i++)↵
for(int j=0;j<stateCnt[i];j++)↵
diceRoll.push_back(i);↵
return diceRoll;↵
}↵
int countToState(array<int,6> stateCnt) {↵
return lower_bound(cnt.begin(),cnt.end(),stateCnt)-cnt.begin();↵
}↵
vector<pair<array<int,6>,ld>> diceCombinations(int n) {↵
vector<pair<array<int,6>,ld>> combinations;↵
init(n,{},[n,&combinations](vector<int> v) {↵
array<int,6> a;↵
long double probability = pow(1.0l/6,n);↵
probability *= factorial[n];↵
for(int i=0;i<6;i++) {↵
a[i] = v[i];↵
probability /= factorial[a[i]];↵
}↵
combinations.push_back({a,probability});↵
});↵
return combinations;↵
}↵
vector<pair<int,ld>> newStates(int state, int keep) {↵
vector<int> diceRoll = stateToDice(state);↵
array<int,6> diceCount;↵
for(int i=0;i<6;i++)↵
diceCount[i] = 0;↵
int reroll = 0;↵
for(int i=0;i<5;i++) {↵
if(keep & (1 << i))↵
diceCount[diceRoll[i]]++;↵
else↵
reroll++;↵
}↵
vector<pair<int,ld>> states;↵
for(auto [combination, probability]: diceCombinations(reroll)) {↵
for(int i=0;i<6;i++)↵
combination[i] += diceCount[i];↵
states.push_back({countToState(combination),probability});↵
}↵
return states;↵
}↵
string encode = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";↵
// dp[bt][i][j]: unused bitmask = bt, rolls left = i, dice display = j↵
pair<ld,int> dp[2048][3][252];↵
int main() {↵
factorial[0] = 1;↵
for(int i=1;i<10;i++)↵
factorial[i] = i * factorial[i-1];↵
init(5,{},[](vector<int> v) {↵
array<int,6> a;↵
for(int i=0;i<6;i++)↵
a[i] = v[i];↵
cnt.push_back(a);↵
});↵
// expval[bt]: expected value with unused bitmask = bt↵
ld expval[2048];↵
expval[0] = 0;↵
ofstream fout("tablebase.txt");↵
for(int bt=1;bt<2048;bt++) {↵
printf("bitmask %d\n",bt);↵
for(int i=0;i<3;i++)↵
for(int j=0;j<252;j++) {↵
dp[bt][i][j] = {-1,-1};↵
for(int act=0;act<11;act++)↵
if(bt&(1<<act))↵
dp[bt][i][j] = max(dp[bt][i][j],{expval[bt&(~(1<<act))]+score(j,act),act});↵
if(i > 0)↵
for(int keep=0;keep<31;keep++) {↵
long double newScore = 0;↵
for(auto [combination, probability]: newStates(j,keep))↵
newScore += dp[bt][i-1][combination].first * probability;↵
dp[bt][i][j] = max(dp[bt][i][j], {newScore,keep+11});↵
}↵
fout << encode[dp[bt][i][j].second];↵
}↵
fout << "\n";↵
expval[bt] = 0;↵
for(auto [combination, probability]: newStates(0,0))↵
expval[bt] += dp[bt][2][combination].first * probability;↵
cout << "Expected value: " << expval[bt] << "\n";↵
}↵
cout << expval[2047];↵
}↵
```↵
↵
The code below plays the game using the database computed above.↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
using ld = long double;↵
vector<array<int,6>> cnt;↵
int factorial[10];↵
template<typename F>↵
void init(int n, vector<int> cur, F callback) {↵
if(cur.size() == 6) {↵
callback(cur);↵
return;↵
}↵
int tot = accumulate(cur.begin(),cur.end(),0);↵
for(int i=(cur.size()==5?n-tot:0);i<=n-tot;i++) {↵
cur.push_back(i);↵
init(n,cur,callback);↵
cur.pop_back();↵
}↵
}↵
int countToState(array<int,6> stateCnt) {↵
return lower_bound(cnt.begin(),cnt.end(),stateCnt)-cnt.begin();↵
}↵
string encode = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";↵
string actions[11] = {"Count 1s", "Count 2s", "Count 3s", "Count 4s", "Count 5s", "Count 6s", "3 of a kind", "4 of a kind", "3 + 2", "Sequence of 5", "5 of a kind"};↵
int main() {↵
init(5,{},[](vector<int> v) {↵
array<int,6> a;↵
for(int i=0;i<6;i++)↵
a[i] = v[i];↵
cnt.push_back(a);↵
});↵
ifstream fin("tablebase.txt");↵
string tablebase[2048];↵
for(int i=1;i<2048;i++)↵
fin >> tablebase[i];↵
int bitmask = 2047;↵
for(int i=0;i<11;i++) {↵
for(int j=3;j--;) {↵
cout << "Input dice rolls, e.g. 26155: ";↵
string s;↵
cin >> s;↵
array<int,6> cnt;↵
for(int i=0;i<6;i++)↵
cnt[i] = 0;↵
for(int i=0;i<5;i++)↵
cnt[s[i]-'1']++;↵
int stateNumber = countToState(cnt);↵
int action = encode.find(tablebase[bitmask][j*252+stateNumber]);↵
if(action < 11) {↵
cout << actions[action] << "\n";↵
bitmask &= ~(1<<action);↵
break;↵
} else {↵
action -= 11;↵
vector<pair<int,int>> vec;↵
for(int i=0;i<5;i++)↵
vec.push_back({s[i]-'1',i});↵
sort(vec.begin(),vec.end());↵
vector<int> keep;↵
for(int i=0;i<5;i++)↵
if(action&(1<<i))↵
keep.push_back(vec[i].second + 1);↵
sort(keep.begin(),keep.end());↵
cout << "lock [";↵
for(int i=0;i<(int)keep.size();i++) {↵
if(i) cout<<",";↵
cout << keep[i];↵
}↵
cout << "] and reroll\n";↵
}↵
}↵
}↵
}↵
```↵
↵
</spoiler>↵
↵
↵
# Statement↵
↵
In the app "2 Player Games", there is this game yazy played somewhat often in Singapore. The rules are as follows:↵
↵
Each player has 11 turns. Each turn starts by you rolling five fair 6-sided die. Then, you have $2$ rerolls. In each reroll, you pick a subset of dice to "lock". The dice that are not "lock" will be rerolled. After using some of your rerolls, you pick a category out of the following $11$ not yet chosen, and your score is described below.↵
↵
1. $1 \times \text{number of dice with 1}$↵
2. $2 \times \text{number of dice with 2}$↵
3. $3 \times \text{number of dice with 3}$↵
4. $4 \times \text{number of dice with 4}$↵
5. $5 \times \text{number of dice with 5}$↵
6. $6 \times \text{number of dice with 6}$↵
7. Sum of dice rolls if some number $x$ appears in at least $3$ die, $0$ otherwise.↵
8. Sum of dice rolls if some number $x$ appears in at least $4$ die, $0$ otherwise.↵
9. $25$ if some number $x$ appears in $3$ die and another number $y$ appears in $2$ die, $0$ otherwise.↵
10. $40$ if the die rolls are $1,2,3,4,5$ or $2,3,4,5,6$ in some order, $0$ otherwise.↵
11. $50$ if some number $x$ appears in all $5$ die, $0$ otherwise.↵
↵
The winner is the player with higher score.↵
↵
Since I wanted to all $0$ of my friends at it, I decided to write a program to find the maximum expected value.↵
↵
Note: Having the maximum expected value does not mean you win with maximum probability (a player who always gets a score of $2$ will beat a player with $99$ percent chance of having a score of $1$ and $1$ percent chance of having a score of $10^9$), but I believe trying to maximise the probability of winning is much harder.↵
↵
# Solution↵
↵
Simulating all turns is too slow. Instead, we note that to find the maximum score from a given position, we only need to consider these:↵
↵
- Which categories have not been chosen↵
- The current state of the dice↵
- The number of rerolls left↵
↵
The current score of the player is irrelevant, as we can simply add it to the expected value found. For example, if the expected score of a player with $0$ current score, categories $1$ to $6$ not yet chosen, and $3$ rerolls left is $59$, the expected score of a player with $10$ current score, categories $1$ to $6$ not yet chosen, and $3$ rerolls left is $69$.↵
↵
Therefore, this leads us to formulate a DP, where $dp[\text{mask}][\text{state}][\text{rerolls}]$ is the maximum expected score if the categories not chosen are represented by the bitmask $\text{mask}$, the state of the dice is represented by $\text{state}$, and $\text{rerolls}$ is the number of rerolls left.↵
↵
This DP gives us $2^{11} \times 6^5 \times 3 = 4.7 \times 10^7$ states. This seems somewhat reasonable until we realise that we have over $42$ transitions to consider, which are:↵
↵
- Picking $1$ of the $11$ categories↵
- Picking $1$ out of the $32$ subsets to lock, and rerolling↵
↵
In the second case, we have to consider all possible dice combinations we may get when rerolling, which takes too long.↵
↵
To speed up our DP, notice that there is essentially no difference between a dice combination of $62451$ and $12456$ (besides re-ordering). Thus, by stars and bars, the number of distinct dice combinations is $\binom{10}5 = 252$, giving us $2^{11} \times 252 \times 3 = 1.5 \times 10^6$ states, and a transition complexity of approximately $32 \times 252 = 8064$. At this point, I stopped optimising my code and wrote out my DP (which took 10min to run with the `O3` flag), only to realise that me doing this is the reason why I struggle to make friends. Anyways, the maximum expected score is $165.76$.↵
↵
<spoiler summary="Implementation">↵
The code below computes the DP. It outputs an encoded database containing optimal moves to `tablebase.txt`.↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
using ld = long double;↵
vector<array<int,6>> cnt;↵
int factorial[10];↵
template<typename F>↵
void init(int n, vector<int> cur, F callback) {↵
if(cur.size() == 6) {↵
callback(cur);↵
return;↵
}↵
int tot = accumulate(cur.begin(),cur.end(),0);↵
for(int i=(cur.size()==5?n-tot:0);i<=n-tot;i++) {↵
cur.push_back(i);↵
init(n,cur,callback);↵
cur.pop_back();↵
}↵
}↵
int diceTotal(int state) {↵
int total = 0;↵
for(int i=0;i<6;i++)↵
total += (i + 1) * cnt[state][i];↵
return total;↵
}↵
int score(int state, int act) {↵
if(act < 6)↵
return (act + 1) * cnt[state][act];↵
if(act == 6 || act == 7) { // please don't leave a comment just because of this line↵
int maxCnt = *max_element(cnt[state].begin(),cnt[state].end());↵
return (maxCnt >= (act - 3) ? diceTotal(state) : 0);↵
}↵
if(act == 8) {↵
int maxPos = max_element(cnt[state].begin(),cnt[state].end()) - cnt[state].begin();↵
if(cnt[state][maxPos] != 3)↵
return 0;↵
cnt[state][maxPos] -= 3;↵
int secondMaxCnt = *max_element(cnt[state].begin(),cnt[state].end());↵
cnt[state][maxPos] += 3;↵
if(secondMaxCnt != 2)↵
return 0;↵
return 25;↵
}↵
if(act == 9) {↵
int maxCnt = *max_element(cnt[state].begin(),cnt[state].end());↵
return (maxCnt == 1 && (cnt[state][0] == 0 || cnt[state][5] == 0) ? 40 : 0);↵
}↵
if(act == 10) {↵
int maxCnt = *max_element(cnt[state].begin(),cnt[state].end());↵
return (maxCnt >= 5 ? 50 : 0);↵
}↵
assert(0);↵
}↵
vector<int> stateToDice(int state) {↵
array<int,6> stateCnt = cnt[state];↵
vector<int> diceRoll;↵
for(int i=0;i<6;i++)↵
for(int j=0;j<stateCnt[i];j++)↵
diceRoll.push_back(i);↵
return diceRoll;↵
}↵
int countToState(array<int,6> stateCnt) {↵
return lower_bound(cnt.begin(),cnt.end(),stateCnt)-cnt.begin();↵
}↵
vector<pair<array<int,6>,ld>> diceCombinations(int n) {↵
vector<pair<array<int,6>,ld>> combinations;↵
init(n,{},[n,&combinations](vector<int> v) {↵
array<int,6> a;↵
long double probability = pow(1.0l/6,n);↵
probability *= factorial[n];↵
for(int i=0;i<6;i++) {↵
a[i] = v[i];↵
probability /= factorial[a[i]];↵
}↵
combinations.push_back({a,probability});↵
});↵
return combinations;↵
}↵
vector<pair<int,ld>> newStates(int state, int keep) {↵
vector<int> diceRoll = stateToDice(state);↵
array<int,6> diceCount;↵
for(int i=0;i<6;i++)↵
diceCount[i] = 0;↵
int reroll = 0;↵
for(int i=0;i<5;i++) {↵
if(keep & (1 << i))↵
diceCount[diceRoll[i]]++;↵
else↵
reroll++;↵
}↵
vector<pair<int,ld>> states;↵
for(auto [combination, probability]: diceCombinations(reroll)) {↵
for(int i=0;i<6;i++)↵
combination[i] += diceCount[i];↵
states.push_back({countToState(combination),probability});↵
}↵
return states;↵
}↵
string encode = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";↵
// dp[bt][i][j]: unused bitmask = bt, rolls left = i, dice display = j↵
pair<ld,int> dp[2048][3][252];↵
int main() {↵
factorial[0] = 1;↵
for(int i=1;i<10;i++)↵
factorial[i] = i * factorial[i-1];↵
init(5,{},[](vector<int> v) {↵
array<int,6> a;↵
for(int i=0;i<6;i++)↵
a[i] = v[i];↵
cnt.push_back(a);↵
});↵
// expval[bt]: expected value with unused bitmask = bt↵
ld expval[2048];↵
expval[0] = 0;↵
ofstream fout("tablebase.txt");↵
for(int bt=1;bt<2048;bt++) {↵
printf("bitmask %d\n",bt);↵
for(int i=0;i<3;i++)↵
for(int j=0;j<252;j++) {↵
dp[bt][i][j] = {-1,-1};↵
for(int act=0;act<11;act++)↵
if(bt&(1<<act))↵
dp[bt][i][j] = max(dp[bt][i][j],{expval[bt&(~(1<<act))]+score(j,act),act});↵
if(i > 0)↵
for(int keep=0;keep<31;keep++) {↵
long double newScore = 0;↵
for(auto [combination, probability]: newStates(j,keep))↵
newScore += dp[bt][i-1][combination].first * probability;↵
dp[bt][i][j] = max(dp[bt][i][j], {newScore,keep+11});↵
}↵
fout << encode[dp[bt][i][j].second];↵
}↵
fout << "\n";↵
expval[bt] = 0;↵
for(auto [combination, probability]: newStates(0,0))↵
expval[bt] += dp[bt][2][combination].first * probability;↵
cout << "Expected value: " << expval[bt] << "\n";↵
}↵
cout << expval[2047];↵
}↵
```↵
↵
The code below plays the game using the database computed above.↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
using ld = long double;↵
vector<array<int,6>> cnt;↵
int factorial[10];↵
template<typename F>↵
void init(int n, vector<int> cur, F callback) {↵
if(cur.size() == 6) {↵
callback(cur);↵
return;↵
}↵
int tot = accumulate(cur.begin(),cur.end(),0);↵
for(int i=(cur.size()==5?n-tot:0);i<=n-tot;i++) {↵
cur.push_back(i);↵
init(n,cur,callback);↵
cur.pop_back();↵
}↵
}↵
int countToState(array<int,6> stateCnt) {↵
return lower_bound(cnt.begin(),cnt.end(),stateCnt)-cnt.begin();↵
}↵
string encode = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";↵
string actions[11] = {"Count 1s", "Count 2s", "Count 3s", "Count 4s", "Count 5s", "Count 6s", "3 of a kind", "4 of a kind", "3 + 2", "Sequence of 5", "5 of a kind"};↵
int main() {↵
init(5,{},[](vector<int> v) {↵
array<int,6> a;↵
for(int i=0;i<6;i++)↵
a[i] = v[i];↵
cnt.push_back(a);↵
});↵
ifstream fin("tablebase.txt");↵
string tablebase[2048];↵
for(int i=1;i<2048;i++)↵
fin >> tablebase[i];↵
int bitmask = 2047;↵
for(int i=0;i<11;i++) {↵
for(int j=3;j--;) {↵
cout << "Input dice rolls, e.g. 26155: ";↵
string s;↵
cin >> s;↵
array<int,6> cnt;↵
for(int i=0;i<6;i++)↵
cnt[i] = 0;↵
for(int i=0;i<5;i++)↵
cnt[s[i]-'1']++;↵
int stateNumber = countToState(cnt);↵
int action = encode.find(tablebase[bitmask][j*252+stateNumber]);↵
if(action < 11) {↵
cout << actions[action] << "\n";↵
bitmask &= ~(1<<action);↵
break;↵
} else {↵
action -= 11;↵
vector<pair<int,int>> vec;↵
for(int i=0;i<5;i++)↵
vec.push_back({s[i]-'1',i});↵
sort(vec.begin(),vec.end());↵
vector<int> keep;↵
for(int i=0;i<5;i++)↵
if(action&(1<<i))↵
keep.push_back(vec[i].second + 1);↵
sort(keep.begin(),keep.end());↵
cout << "lock [";↵
for(int i=0;i<(int)keep.size();i++) {↵
if(i) cout<<",";↵
cout << keep[i];↵
}↵
cout << "] and reroll\n";↵
}↵
}↵
}↵
}↵
```↵
↵
</spoiler>↵
↵
