I just thought of an interesting little game theory exercise, curious if anyone has heard of anything similar, or has any thoughts on it.
So the game has two players. One player is “active”. That player secretly rolls a certain number of dice… let’s say, 6 20sided dice. He looks down and sees 6 numbers, say “2, 2, 7, 8, 11, 15”. He then rearranges them in an order of his choice and starts revealing them to his opponent. At any point, the opponent can stop that revealing and take the most recently revealed number. Then the first player scores a number of points equal to the sum of his remaining dice, and the second player scores a number of points equal to the die he took. Both players are trying to maximize their score. (Presumably you aren’t comparing the scores directly, as the active player will almost always win, you’re just trying to maximize your own score and minimize your opponent’s score).
Any thoughts as to an optimal strategy? 100% certainly the nonactive player should always take a 20. This also means that 100% certainly the active player should always choose an order with any 20s last. And it certainly does seem reasonable to have a general policy for the non-active player to always take sufficiently high numbers. If you always take a 19 if you see one you’re only going to have played non-optimally in very rare circumstances, and the moment you start turning down 19s hoping for 20s the active player is going to be able to exploit the heck out of you.
Seems like this would make an interesting algorithm challenge, not sure if it would actually be interesting to play in real life.
Well, you can certainly compare directly by doing, say, 10 sets as each role and then switch. I think it’s worth trying out as an interesting bluffing game.
By the way, I intend “Then the first player scores a number of points equal to the sum of his remaining dice” to mean “the other 5 dice”, not only the non-revealed dice or the already-revealed dice or anything.
A related problem is the Suitor’s problem. That’d give at least a first approximation to Player 2’s strategy, though it’d doubtless have to be modified to account for Player 1 choosing the order, rather than it being random, and for the values of the dice being discrete and capped.
Yeah, if the active player just randomizes the dice, then the other player should use that strategy. But of course the fact that both players KNOW that makes it different entirely.
There are lots of semi-reasonable strategies that either player can employ, but once either player has figured out the other player’s strategy (if it’s a fixed and immutable one) they can easily exploit that. I feel like any truly “optimal” strategy is first of all going to focus on trying to deduce your opponent’s strategy over multiple playings, and is also going to involve a bunch of weighted probabilities to avoid having your own strategy exploited.
It would seem to me to be a more equal game if the active player could only keep one of his remaining dice rather than all five of them. In that game, the nonactive player (the guesser) would be trying to guess which number called was the highest and the active player (the caller) would be trying to bluff the guesser into taking a lower die.
In the “take five” version, the numbers are heavily weighed in favor of the active player - he’s going to score higher virtually all of the time. Even if you alternate the players in the active and inactive roles, the higher totals they get when they are active will drown out any differences in their guessing strategies.
No, because Player 1’s score is affected by Player 2’s decisions by the same amount that Player 2’s score is. There will be random noise, of course, but that’s easily taken care of just by having enough rounds of play.
But in the “take-five” game the majority of points will be scored by the active player. So active strategy is going to be five times as important as inactive strategy. I think the two areas should ideally have equal weight in determining who wins.
Crudely, best strategy for Picker is “wait for a big number.”
Starting with a very simple case, suppose three 3-sided die with the three sides’ values being 0, K, and 1, with K an intermediate value, 0 < K < 1. Picker’s best strategy in that case seems to be as follows:
[ul] [li] If K < 5/8, take only 1 when it comes.[/li][li] If 5/8 < K < 3/4, always take 1, but flip a coin and take K in ONLY 1st or 2nd position depending on coin toss.[/li][li] If 3/4 < K, take K or 1 whenever either comes.[/li][/ul]
Setter’s optimal mixed strategy is somewhat more complicated.
That the distribution in Sultan’s Dowry is unknown makes a very big difference. In the Dowry game a random ordering is assumed; and the payoff schedule is quite different than in Max’s game. Other than these differences the games are quite similar.
Pinochle is another game which is quite similar, though it’s played with cards instead of dice. The rules aren’t the same but are written with the same 26-letter alphabet.
Where the points are scored doesn’t matter, only where the variance in the score comes from. For comparison, consider a game where Player 1 gets 500 points for free, and then Player 1 and Player 2 compete symmetrically for 10 points.
And septimus, I did say that doubtless the strategy would have to be modified.
I played with this for a while. Nothing definitive yet but a few thoughts.
One key factor is whether or not the active player rolls a twenty. If reveals a twenty to the guesser, then obviously the guesser will take it - there’s no option for getting a better number. So if the guesser has a twenty, the best strategy is to reveal it last and hope that the guesser picks another number before the twenty is reached.
I’m thinking that if the active player doesn’t have a twenty, his best strategy is to put his lowest number last and then reveal his second lowest number first, then his third lowest, and so on with his highest number being the penultimate one. The reason for this is that if the guesser has a number he’ll settle for, then he’ll obviously also settle for any number higher than that. If, for example, he’s willing to settle for a eighteen then he’d also be willing to take a nineteen or a twenty if they were revealed before an eighteen. So if the active player had an eighteen and a nineteen, he’d want to reveal the eighteen first.
Of course, the guesser may be waiting for a number that wasn’t rolled. If he’s waiting until a nineteen is revealed and the highest number the active player rolled is an eighteen, then the guesser will refuse every number as it’s revealed until he reaches the last number. This is the reason the active player wants to put his lowest number last if it isn’t a twenty - the last number is the “booby prize”.
So what happens if the guesser knows the active player is following this strategy? He’ll know to reject the first four numbers. The moment of truth comes when the fifth number is revealed. He has to decide what he thinks the sixth number will be: a twenty or a booby prize?
At this point, I should probably be analyzing the probabilities of the die rolls but I haven’t decided if I’m that committed yet. I also need to consider the effect of multiple occurrences of the same number. And there’s the issue of whether bluffing is a sound strategy. My guess is that both sides are going to end up with mixed strategies.
Here are possible strategies for Setter and Picker given six 20-sided dice.
Setter:
First place all dice between 5 and 18 inclusive, in ascending order. Then place any 19’s or dice 4 or less in random order. Finally place any 20’s.
Picker:
Pick the first die 15 or larger if there is one, else the last die.
Average pick is now 15.13.
I certainly do not claim that these strategies are optimal. But they might be optimal among strategies constrained to the simple parametric form implied, and thus (assuming those forms are not unreasonable) might give a hint to optimal strategies. The game value changes very little for neighbors of the Setter strategy; and Picker thresholds of 14 or 16 give results close to those of 15.
(“Might” is an operative word in the above paragraph, as these results were obtained by an unverified hastily-written simulation. Maybe I overlooked a move. )
Fairly sure that can’t possibly actually be optimal. Because if you adopt that strategy, and your opponent deduces it, you’re 100% guaranteeing yourself to never get a 1 (well, unless the roll is 1, 1, 1). I think any actual “optimal” strategy would have to involve attempting to deduce your opponent’s strategy and respond to it.
In standard game theory, players don’t care about anyone’s score but their own. You need to specify a payoff function that captures this goal in order to have an actual model, and once you do, finding the optimal strategy is just a matter of solving a fairly large linear program.
Edit: The linear programming formulation only applies if the game is zero sum (i.e., the first player’s payoff is always the negative of the second player’s payoff), but there are algorithms for any non-repeated game.
I’ve now convinced myself otherwise. However, I think that the case with only 3 values is remarkably less interesting than any other case, assuming they’re worth 0, 1, and some fixed value in between. In particular, it renders meaningless all decisions that the active player makes. The inactive player will NEVER take a 0, no matter what, and will ALWAYS take a 1, no matter what. This also means that in addition to the well known put-all-your-1s-last rule, there’s a “never end in 0k instead of k0” rule. In fact, I have a suspicion that it’s always optimal to put all your ks first, then all your 0s, then all your 1s, no matter what, although I can’t entirely convince myself that that’s 100% true.
That can’t be right. If you use that premise, you’re going to come up with some very unrealistic results.
For example, according to that logic, there’s no point in a baseball team developing its pitching or fielding - neither of these increase the team’s score, they only reduce the other team’s score. An “only worry about our own score” plan would concentrate strictly on hitting.
A team that actually played on this basis might score two or three more home runs each game. But their opponents would be scoring five or ten more runs per game.
For accurate game modeling, you have to look at the game as a whole and not just focus on high scoring. You can win a game keeping your opponent’s score lower than yours. A strategy that gives you a 1-0 victory is better than one that gives you a 10-12 defeat.
I think “score” was used in the sense of “net payoff.” In baseball the net payoff is either +1 or -1 (win or lose) regardless of total runs scored.
I heartily agree that the case is least interesting, but wanted to tackle the simplest non-trivial case first. And it appears I muffed even it. :smack:
And I agree with your suspicion about optimal Setter strategy, though in some cases some other strategies may be equally as good.
Sorry for my confused earlier post about even this simple case. The idea that Setter’s best strategy was mixed arose from applying a general simplex-type solver (2 or more equally good strategies may appear to be mixed). It now seems to me that Picker should
[ul][li] Wait for 1 when K < 1/2[/li][li] Take first K that presents when 3/4 < K[/li][li] Skip initial K but take 2nd K when 1/2 < K < 3/4[/li][/ul]
OK, let’s simplify this. Player 1’s score is the sum of all unpicked dice minus the picked die. Player 2’s score is the picked die minus the sum of all unpicked dice. There, now both players are just straightforwardly trying to maximize their own score.
I’m not sure I trust those Goofspiel results, incidentally, since the strategies described there throw away a huge amount of information available to the player, namely, what cards the opponent has played so far, and which prizes have already been won and by whom.
)