Author |
Topic: Calculator Game (Read 1234 times) |
|
Ulkesh
Junior Member
Posts: 147
|
 |
Calculator Game
« on: Sep 9th, 2003, 4:15pm » |
 Quote  Modify
|
A few years back when I was being bored to tears in maths classes, a friend and I came up with an interesting game (interesting relative to the maths lesson!) that could be played using a scientific calculator with a 'random number' function. When the random number function is used, the calculator displays a 3dp number between zero and 0.999 inclusive. The algorithm that the calculator uses to produce one of these 1000 possibilities can be considered truly random for the purposes of this game.
The game works like this:
Each player (of the two playing the game) has a calculator the screen of which he keeps to himself, so the other player can't see.
Each player then uses the calculator to produce a maximum of 10 random numbers, the point of which is to have a higher random number visible on your calculator screen than your opponent after this process is finished. For example, one player may obtain 0.924 on his first attempt and decide that it is likely that this will not be bettered in any of his 9 possible future attempts, and therefore stop. The other player may obtain a number on his first attempt that is too low to justify not continuing, and therefore keep producing random numbers until he gets a good number, or until he has had 10 attempts, at which point he must stop.
The players then compare calculator screens and the player with the higher number wins.
A couple of points that may need clearing up:
-To remove the possibility of mind games and the like, assume niether player knows at which random number their opponent stopped.
-Just to make it clear, each random number obtained is completely independent of the last, ie, they are not cumulative etc.
The question is this: What is the optimal strategy for this game? What about if N attempts at calling a random number are allowed?
---
After this game got boring (which was very quickly), I started playing mammoth games of 4-D Noughts and Crosses (Tic Tac Toe to Americans, I think) on a 5x5x5x5 grid, which often lasted weeks at a time. Needless to say, this didn't help my maths at all...
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Calculator Game
« Reply #1 on: Sep 10th, 2003, 12:38am » |
Quote Modify
|
interesting problem..
The optimal strategy probably depends on the strategy of your opponent..
At first glance I'd say to try a new number if the chance you'll get a higher number in the remaining tries is higher than the number you have..
I think maybe a genetic algorithm could be tried to solve this.. (approximately)
|
| « Last Edit: Sep 10th, 2003, 12:39am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Calculator Game
« Reply #2 on: Sep 10th, 2003, 6:24am » |
Quote Modify
|
ok i have some strategy in my head that might help me out in such situations.
Since the distribution is random,i can safely assume that anything above .500 gives me a good chance to win and that anything above .8 has a high probability of me winning.
An algorithm that i would follow,
1>Press random button
2>if value < 0.500 ignore the value and goto step 1
else goto step 3
3>if value > .8 accept value and goto step 6
else goto step 4
4>Note down the value in a paper.
5>Take the ratio of this current value with previous value(if any else goto step 1),
if the ratio is >= 1 accept value and goto step 6
if the .7<ratio<1 and attempt>5 accept value and goto step 6
if ratio <.7 goto step 1.
6>Stop
I cannot prove or disprove that this approach is optimum but i can say that my motto here is " go for the best or let the 10th attempt decide your fate "
|
| « Last Edit: Sep 10th, 2003, 6:25am by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
visitor
Guest
|
If you're looking for an exact optimum strategy, then this one definitely is not easy. Suppose it was just 2 rolls. Simple strategy says if my first roll is above .5 I keep it. But that means there's a .75 chance that the other player's roll will be above .5. So if my first roll was .51, it will probably lose, and I should roll again, even tho the odds of improving it are against me. The decision point for two rolls might be .55 or .6. But as you add more rolls, the decision point for the second last roll will change as the odds of victory change. (and complicated by the fact that changing decision points after each roll will make it very difficult to calculate what the reall probabilities are at this point)
In the end the answer will have to take into consideration
1) the likelihood that you'll get a higher number at some point in the rolls remaining
2) the likelihood that you'll roll that many times to give yourself the full probability of number 1
3) the likelihood that you could win with the number you've got.
4) the likelihood that any improvement you're likely to make will change a loss into victory (or any decline could change a victory into loss)
5) the likelihood that your opponent will reach his tenth spin and have a number that is totally random so you can forget all that strategy and just try to beat .5.
In the end you (and your opponent will have a probability curve of possible outcomes that is very indiscrete, but your strategy depends on that curve from the start, and changing your strategy will change the curve will change your strategy.
|
|
IP Logged |
|
|
|
Ulkesh
Junior Member
Posts: 147
|
|
Re: Calculator Game
« Reply #4 on: Sep 10th, 2003, 10:09am » |
Quote Modify
|
Interesting points made by towr and visitor. When I posted this puzzle, I was under the impression that optimal strategy did not depend on the strategy of your opponent, which is why I put the puzzle in 'easy' (I happen to still believe this, I'll explain why in a minute). To avoid confusion and to justify the 'easy' rating, I believe the game can be thought of as a single-player game with the same rules, with the objective being to achieve as high a random number as possible. This makes it a simple exercise in calculating probabilities.
However, I do not believe that a second player being involved in the game has any effect on either player's strategy. The game is symmetric, in that both players play by identical rules, and neither player affects the other at any point in the game by what he does. So either player may play by any strategy he or she wishes of the same set of strategies. Some strategies may have advantages over the single-player optimal strategy when pitted against certain other strategies, but players have equal choice over which strategy to adopt. Therefore two intelligent players will surely choose the same strategy, and two intelligent players will know this, so will base their strategy solely on achieving the highest random number for themselves. Namely, the optimal single-player strategy. This applies to any number of players as well, not just two. And I'm willing to bet that in any game where players play independently of one another, as in this game, single-player optimal strategy is always optimal for each player. Second-guessing your opponents' thoughts won't pay off in the long run.
If I'm wrong about this (which is very possible), and the game is more complicated than I originally thought, moderators feel free to move this to the medium/hard forums at their discretion.
|
|
IP Logged |
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Calculator Game
« Reply #5 on: Sep 10th, 2003, 12:09pm » |
Quote Modify
|
First lets solve the easy problem of getting the best possible result. In each case you wish to take another turn if the probability that you will get a higher number on one of your following turns is greater than 50%. I do not believe that visitor's thought to include the consideration of whether you are likely to use all the remaining turns has validity, though his other points are all critical.
Using my own notation (as I do not know standard probablility notations), P(x,n) is the probability of getting better than x with n more turns. Simply solving for x when P=.5 tells you when you need to bet again.
P(x,n)=1-x + x*P(x,n-1)
P(x,1)=1-x
P(x,2)=1-x + x*(1-x)=1-x2
P(x,3)=1-x + x*(1-x2)=1-x3
...
P(x,n)=1-xn
x=.5(1/n)
Thus, you want to take another turn if you have equal to or worse than the following on the previous turn (.001 has been subtracted from all terms to take into account that we go from 0 to .999 not .001 to 1)
1).924
2).916
3).904
4).889
5).869
6).839
7).792
8).706
9).499
When you consider that the other person is playing I think it does actually affect your ideal strategy, but I am not going to try that one right now.
|
| « Last Edit: Sep 10th, 2003, 12:21pm by aero_guy » |
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Calculator Game
« Reply #6 on: Sep 10th, 2003, 12:11pm » |
Quote Modify
|
I will demonstrate that the "naive" strategy where you just try to maximize your return fails against a smarter strategy.
The naive strategy must be of the following form:
If, on turn t, I get more than q[t], then I stop.
q[t] is fixed before the competition, although it may not be easy to calculate what the values of q[t] are.
Now what happens if you are playing against an opponent? You and your opponent generate your first random number. Your number is less than q[1], so you generate your second number. Your opponent does not generate a second number, indicating that his number is larger than q[1]. Suppose your second number is larger than q[2] but smaller than q[1]. Should you stop?
The naive strategy says yes, but it should be obvious that if you opponent has really stopped (and is not bluffing), then you cannot hope to win. Therefore you have better odds if you keep going.
But I think the game is even more complicated than that! Suppose you generate your third number, and it is just barely higher than q[1]. Is it worth stopping? How much higher must it be?
Now suppose you generate a number sufficiently higher than q[1] that it's worth stopping. Your opponent sees you stop. Is it worth your opponent starting up again?
Add to that the complexity of bluffing, and I'd say you have a reasonably difficult game going on.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Calculator Game
« Reply #7 on: Sep 10th, 2003, 12:15pm » |
Quote Modify
|
James, the game you describe has now become poker. It has far more to do with reading an opponent than probability. Ulkesh did, however, remove that consideration by saying you do not know at which number your opponent stopped.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Calculator Game
« Reply #8 on: Sep 10th, 2003, 1:35pm » |
Quote Modify
|
Oh. I guess I should have read the question 
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
visitor
Guest
|
The way the second player's game play affects the first is that the number he presents is not evenly distributed between 0 and 1.
I don't know how to calculate any but the simplest probabilities, but I put together a simple basic simulation of the game. I found that 57% of the time, the number you have to beat is > .9. Only 6.5% is it less than one half. So if you get a .5 on your ninth try, does it really make sense to keep an almost sure loser?
I also simulated a simple 2 turn game and found that repicking on a .6 beats repicking on a .5 about 50.5% of the time.
|
|
IP Logged |
|
|
|
visitor
Guest
|
Pitting Ulkesh's strategy against one that raises his last few numbers (I just guessed at .85, .81, .75 and .625 for the last four rounds; I left the first rounds the same) I was able to beat his strategy 50.5% of the time.
|
|
IP Logged |
|
|
|
Ulkesh
Junior Member
Posts: 147
|
|
Re: Calculator Game
« Reply #11 on: Sep 10th, 2003, 4:02pm » |
Quote Modify
|
Ok, I concede the point, visitor. The 2-player version of the game doesn't have the same optimal strategy as the single-player version. I don't think I was looking at things the right way. It's obvious now you've put it that way.
How about this: Calculate the average value obtained using single-player optimal strategy. Have this number be the threshold number on the last round rather than 0.499. Obviously this modified strategy will be better than the original. Then calculate the average for this new strategy and repeat the process until you have an optimal threshold number for the last round.
Of course this ignores the previous 8 rounds, but I'm sure it's not much of an intellectual leap to expand this iteration to involve all rounds (and perhaps N rounds?).
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Calculator Game
« Reply #12 on: Sep 11th, 2003, 5:18am » |
Quote Modify
|
aero_guy,
I don't think your numbers are correct. Here is a different way of calculating it, getting different numbers:
Define a(n) as the expected payback with n rolls left. Define p(n) as the cutoff after you have generated your nth last number. a(1) is obviously 0.5 and p(1) is obviously 0 (since you have to accept the last number).
To calculate a(2), we use the following recursion definition:
a(n+1) = p(n+1)a(n) + (1 - p(n+1))(1 + p(n+1))/2
This is simple: below the cutoff, you expect to get a(n) (because you'll keep going), and above the cutoff, you can expect something between the cutoff and 1 (uniformly distributed).
To be rigorous, I'll maximize the expectation:
a(n+1) = p(n+1)a(n) + (1 - p2(n+1))/2
a(n+1) = (1 + 2p(n+1)a(n) - p2(n+1))/2
da(n+1)/dp(n+1) = 1/2(2a(n) - 2p(n+1))
This is obviously zero when a(n) = p(n+1), matching our intuition. If we expect we can do better on the remaining n numbers, we won't keep the current number. So what is a(n+1) in terms of a(n)?
a(n+1) = a2(n) + (1 - a2(n))/2
= (1 + a2(n))/2
This gives the following cutoffs:
n cutoff
1 0.500
2 0.625
3 0.695
4 0.742
5 0.775
6 0.800
7 0.820
8 0.836
9 0.849
expected return: 0.860
This maximizes the expected return for the whole game. Whether or not this is the optimal strategy, I still don't know.
But it doesn't explain visitor's observation about the game with only two rerolls.
|
| « Last Edit: Sep 11th, 2003, 5:21am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Calculator Game
« Reply #13 on: Sep 11th, 2003, 7:10am » |
Quote Modify
|
Good job James, while my method calculates probabilities based upon the idea that you WILL reroll all the rest of your turns, yours takes into account the possibility that the other turns will not be necessary, a concept originally introduced by visitor that I had poo-pooed earlier.
Though your strategy may give the highest expected return, a strategy of retrying anything less than or equal to .88 beats it. The idea is that you need to beat James's mean. Though the mean of this method is significantly lower than James's, it wins 54% of the time. Of course you need to know the method your opponent is using for this to work. Here we have a kind of arms race where the optimal strategy depends on what your opponent thinks the optimal strategy is.
|
| « Last Edit: Sep 11th, 2003, 7:11am by aero_guy » |
IP Logged |
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Calculator Game
« Reply #14 on: Sep 11th, 2003, 7:47am » |
Quote Modify
|
So I ran a brute force style optimization and, at least for using a single number, around .885 comes up best for beating the James solution. Of course, a method that depends upon round number would probably work better.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Calculator Game
« Reply #15 on: Sep 11th, 2003, 8:01am » |
Quote Modify
|
aero_guy,
Confirming your results, I also found the naive maximize-your-return strategy is not optimal for winning the game. If you know your opponent is using such a strategy, then you can win 54.9% of the time, using the following cutoffs:
0, 0.775, 0.822, 0.844, 0.857, 0.867, 0.876, 0.884, 0.89, 0.896
This gives an expectation of only 0.824, versus an expectation of 0.861 for the expectation-maximization strategy. I believe that it is the very best you can do versus the naive approach.
I wonder what strategy would beat this one optimally?
[edit]okay, I found out. You can beat this one 50.6% of the time[/edit]
|
| « Last Edit: Sep 11th, 2003, 8:14am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Calculator Game
« Reply #16 on: Sep 11th, 2003, 8:14am » |
Quote Modify
|
Would it be fun to make a site where we can pit our strategies against each other?
I'm sure I could whip something up in PHP.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Calculator Game
« Reply #17 on: Sep 11th, 2003, 9:05am » |
Quote Modify
|
Unfortunately, you're a little late. I have already made a spreadsheet that will run two strategies against each other, and used it to find the single un-beatable strategy:
0.000, 0.704, 0.806, 0.851, 0.876, 0.892, 0.902, 0.910, 0.915, 0.919
[edit] Doh! Sorry, I should have attached the spreadsheet. If you want me to, I'll attach it to a new post... [/edit]
|
| « Last Edit: Sep 11th, 2003, 9:09am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Calculator Game
« Reply #18 on: Sep 11th, 2003, 10:25am » |
Quote Modify
|
Unfortunately I can't do anything with a spreadsheet, I simply lack the software, and the room for the software.
Any proof your new strategy is unbeatable?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Ulkesh
Junior Member
Posts: 147
|
|
Re: Calculator Game
« Reply #19 on: Sep 11th, 2003, 10:42am » |
Quote Modify
|
on Sep 11th, 2003, 9:05am, James Fingas wrote:| [edit] Doh! Sorry, I should have attached the spreadsheet. If you want me to, I'll attach it to a new post... [/edit] |
|
That'd be great, if you don't mind...
So did you obtain this strategy simply by trial and improvement, or have you found some kind of mathematical explanation?
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Calculator Game  calculator.xls (attachment deleted)
« Reply #20 on: Sep 11th, 2003, 12:38pm » |
Quote Modify
|
Well, ummm, I don't exactly have ... proof. I just sort of have this idea and it seems to be backed up by the existing information.
I came across the solution I give by finding out the optimal strategy to beat the naive maximization strategy, then finding the optimal strategy to beat that strategy, then finding the optimal strategy to beat that one, and so on. The strategies converge to give the strategy I've listed above. It might be possible to prove that it's the optimal strategy (maybe induction on the number of rerolls allowed), but I haven't started thinking about that.
But I brute-forced it ... after I accidentally deleted the spreadsheet I got fed up and just used the built-in solver to find the optimal cutoffs. I was only finding them through a manual brute-force search anyways.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Calculator Game calculator_game.gif (attachment deleted)
« Reply #22 on: Sep 15th, 2003, 8:24am » |
Quote Modify
|
But my strategy is unbeatable! How dare you!
When flipping a coin 1000 times, the standard deviation is about 1.9%, so your test (if you are only doing 1000 trials) may not be accurate enough to prove the results shown. Besides, if you're doing a tournament, the top contender will be the one the beats the worst contenders by the highest margin--not the single unbeatable strategy. Maybe I'll design a strategy to beat the currently-listed strategies by the highest margin!
My spreadsheet predicts that my method wins an average of 50.5% of the time against the top listed method "greedy" (which seems a little simplistic).
I've done the math for the 2-roll case, and the optimal cutoff is [phi], which cannot be beaten. The math gets quite hairy the way I did it though, so I'm not going to try the three-roll case.
I think we could mathematically show the optimal response to any given strategy, though. I'll take a shot at it below:
Given a probability distribution p.d.f. p(y), which shows the probability that the outcome y will occur in an opponents strategy, we will come up with the optimal cutoff for the very last reroll of our strategy.
The probability that a given result x will win against the strategy p(y) is the area under the curve p(y) less than x. To simplify things, we will calculate the cumulative density function P(y), which is the integral of p(y). This is a monotonically increasing function on the interval [0,1], with P(0)=0 and P(1)=1. The chance that a given x will beat the strategy p(y) is therefore P(x).
Given a probability distribution q(x), which gives the probability of us getting each value of x, the overall likelihood of beating p(y) is therefore the following integral:
[int]P(x)q(x)dx, from x=0 to x=1.
The probability that the last roll will beat p(y) is this integral with q(x) replaced by the constant 1. This is numerically equal to the average value of P(x) over the interval [0,1].
Now we have to consider what happens when we create a cutoff for the second-last roll. In the interest of choosing the cutoff that gives the maximum likelihood of winning, we will consider what happens when we change the cutoff by small amounts.
The probability distribution created by choosing a single cutoff is a step function (see the diagram below). When we increase the cutoff by a small amount, we decrease the pdf at the bottom of the step, and increase it uniformly along the side of the step. This ceases to be profitable at the point where P(x) = Pbar(x) (the average value of P(x)).
To choose the next cutoff, we reapply this method, but substitute P(x)q(x) (the step function for the last two rolls) for P(x) in the integral. You can see that this should result in higher and higher cutoffs.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Calculator Game
« Reply #23 on: Sep 15th, 2003, 8:34am » |
Quote Modify
|
umm please someone give me the greedy method algorithm .. i would like to see it!!!! (it seems to work pretty nicely)
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Calculator Game
« Reply #24 on: Sep 15th, 2003, 9:09am » |
Quote Modify
|
on Sep 15th, 2003, 8:24am, James Fingas wrote:| When flipping a coin 1000 times, the standard deviation is about 1.9%, so your test (if you are only doing 1000 trials) may not be accurate enough to prove the results shown. |
|
true of course. I thought 1000 would be pretty good, but we're dealing with very small win margins.
Quote:| Besides, if you're doing a tournament, the top contender will be the one the beats the worst contenders by the highest margin--not the single unbeatable strategy. |
|
Well, you should beat the worst contenders by a high margin. Ideally you'll look at the pdf your opponent has, deduce what strategy he uses and adapt your strategy to beat him (though of course this can't be done by a series of threshold, you'll need a real program).
In any case I think it should even out when more quality contenders get submitted (which is currently a problem since the server is acting poorly and won't let any submitted data be processed at the moment).
|
| « Last Edit: Sep 15th, 2003, 9:11am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove