№	Пользователь	Рейтинг
1	Benq	3792
2	VivaciousAubergine	3647
3	jiangly	3631
4	Kevin114514	3574
5	maroonrk	3521
6	strapple	3515
7	Radewoosh	3461
8	tourist	3428
9	turmax	3378
10	Um_nik	3376

№	Пользователь	Вклад
1	Qingyu	162
2	adamant	148
3	Um_nik	146
4	Dominater069	143
5	errorgorn	141
6	cry	138
7	Proof_by_QED	136
8	YuukiS	135
9	chromate00	134
10	soullless	133

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 \times \text{number of dice with 1}$$$
$$$2 \times \text{number of dice with 2}$$$
$$$3 \times \text{number of dice with 3}$$$
$$$4 \times \text{number of dice with 4}$$$
$$$5 \times \text{number of dice with 5}$$$
$$$6 \times \text{number of dice with 6}$$$
Sum of dice rolls if some number $$$x$$$ appears in at least $$$3$$$ die, $$$0$$$ otherwise.
Sum of dice rolls if some number $$$x$$$ appears in at least $$$4$$$ die, $$$0$$$ otherwise.
$$$25$$$ if some number $$$x$$$ appears in $$$3$$$ die and another number $$$y$$$ appears in $$$2$$$ die, $$$0$$$ otherwise.
$$$40$$$ if the die rolls are $$$1,2,3,4,5$$$ or $$$2,3,4,5,6$$$ in some order, $$$0$$$ otherwise.
$$$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$$$.

Implementation

The code below computes the DP. It outputs an encoded database containing optimal moves to tablebase.txt.

#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.

#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";
			}
		}
	}
}

Комментарии (9)

Написать комментарий?

literalchild

3 месяца назад, скрыть # |

Auto comment: topic has been updated by literalchild (previous revision, new revision, compare).

→ Ответить

MAbuBakrShahid

Here is web version.

DenimFlame12

Yes, I too have played that game a lot...interesting take of cp irl, maybe now i can use my problem solving skills to win games too :XD

wery0

+22

Wow, what a coincidence! I've implemented exactly the DP you described for a similar version of this game about a year ago for a Geometry Dash level:
— Implementation: Link
— Level itself: https://gdbrowser.com/search/121259975
I wanted to get the highest score and felt like my CP skills we finally usefull somewhere :D

And you can find 5 more programs I've implemented for 5 other GD levels in the repository. Below is an explanation for 3 of the most interesting of them.

Spoiler

Guess I need to go touch some grass.

ATSTNG

Great job.

I enjoy doing similar things for different games. This reminds me of my Strange applications: League of Legends ARAM champion selection math & statistics

SamS_99

Shouldn't number of dice combinations be 11C6?

3 месяца назад, скрыть # ^ |

You can think of it as arranging $$$5$$$ os and $$$5$$$ |s in a row, which has $$$\binom{10}{5}$$$ ways.

os before the first | correspond to $$$1$$$.

os between the first and second | correspond to $$$2$$$. (and so on)

os after the last | correspond to $$$6$$$.

Kognition

← Rev. 2 →

This problem is nice, but in a contest it is pretty frustrating to implement. It was on the set for ECNA 2018 https://ecna18.kattis.com/contests/ecna18/problems/sequentialyahtzee

lrvideckis

here's my impl of this

https://github.com/lrvideckis/yahtzee-max-expected-score

Блог пользователя literalchild

Statement

Solution