Under-doubling dice?
Bill Taylor
It seems a lot of folks might object somewhat to the great increase in variance
the doubling cube introduces to backgammon, but still very much like the idea
of something like a doubling cube. Or so it would appear from the willingness
of many money players to settle before the last move or two.
On the other hand, a great many other games might become more interesting
if played with something like a doubling cube. Even, chess, othello, etc,
could be interesting, if played for money, or as part of a long series. (The
world chess champs might be interesting if so played!) Indeed, poker played
with a pot-doubling limit is effectively nothing *but* show poker with a
doubling cube! A cute thought. As far as I know, it has never
seriously been suggested for games of pure skill that a doubling device might
be used, but I don't see why not. It still introduces an extra element of
skill, as in BG:- i.e. judgement on whether one is winning or not, as opposed
to merely playing on as best one may. This alone is worth a debate.
However, what I really want to discuss here is the doubling cube in BG.
In particular, a lot of doubles might be rejected with regret, not for
the fear of having made a wrong decision, but just for losing the fun of
playing out a fascinating (if poor) position. Similarly, a lot of money
might be lost by accepting for the same reason. This problem, and the
variance problem mentioned above, would both be ameliorated by the use
of a LESS-THAN-DOUBLING cube. The same idea exactly would be applied,
and so the same sort of probability calculations would obtain, but with
a factor of less than two.
My suggestion would be for a "one-and-a-halfing" cube; or, if you're a
classics scholar, a "sesqui-cube".
The sequi-cube could not always be perfectly exact, of course, but if the
basic stake were regarded as $4 (or $400 dollars, or 4 points in a match),
it could increase as follows:
4, 6, 9, 13, 20, 30, 45, 67, 100 etc.
Not a perfect 1.5 ratio, but near enough for money calculations to be
approximately independent of the current stake.
So; how would it be?
Would it be a good idea?
Would it have a beneficial effect on money play?
Would the average payout be different?
Would it have a beneficial effect on matches?
And would it be a good idea for games of skill?
-------------------------------------------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
-------------------------------------------------------------------------------
God does not play dice with the universe - god *is* the dice.
-------------------------------------------------------------------------------
Hank Youngerman
Nick Wedd
In article <626ipm$pno$1...@cantuc.canterbury.ac.nz>, Bill Taylor
<mat...@math.canterbury.ac.nz> writes
>It seems a lot of folks might object somewhat to the great increase in variance
>the doubling cube introduces to backgammon, but still very much like the idea
>of something like a doubling cube. Or so it would appear from the willingness
>of many money players to settle before the last move or two.
The ppurpose of the doubling cube is to get rid of the bit of the game
where the variance is low. An under-doubling cube would be less
effective at this, as well as less interesting in itself.
Something that novice backgammon players tend to forget: if you fold to
a double, you don't have to leave the room and go home, you are allowed
to start another game. This new game is likely to be more interesting.
Nick
--
Nick Wedd ni...@maproom.demon.co.uk
Nick Wedd
In article <626t1b$k...@camel15.mindspring.com>, Hank Youngerman
<flmas...@mindspring.com> writes
>Well - bridge DOES have doubles. And Redoubles.
Only two of them. And not backgammon-type ones, in which the doubled
party has the option of dropping, and paying the stake so far, without
play.
So here's another project: modify the rules of bridge, so as to have
unlimited doubles, with a drop option after every one. Remember that
after an accepted double, the cube gets turned and play continues.
William J. Hayes
The old rules (Auction Bridge not Contract Bridge) allowed unlimited
redoubles, however if your redouble took the trick score past 1000 then
your partner could force you to buy him out.
Nick Wedd (Ni...@maproom.demon.co.uk) wrote:
: In article <626t1b$k...@camel15.mindspring.com>, Hank Youngerman
Matthew Daly
mat...@math.canterbury.ac.nz (Bill Taylor), if that is your REAL name,
said:
>It seems a lot of folks might object somewhat to the great increase in variance
>the doubling cube introduces to backgammon, but still very much like the idea
>of something like a doubling cube. Or so it would appear from the willingness
>of many money players to settle before the last move or two.
>
>On the other hand, a great many other games might become more interesting
>if played with something like a doubling cube. Even, chess, othello, etc,
>could be interesting, if played for money, or as part of a long series.
To a degree, I see your point, but I think that backgammon has a feature
that chess and Othello don't have: the random element of rolling dice.
The "value" of a game of chess is a precise number, although it might be
one that is impractical to calculate, but virtually all backgammon
positions have fuzzy values. The doubling cube says, for all intents
and purposes, "By all rights, I should win this game, but there is
always a chance that the dice will turn in your favor. So you can
choose whether you want to take that chance at the cost of a greater
reward for me or resign now." (Cribbage is an example of a game that
would probably work well with a cube, though I've never heard of it
being tried.)
One informal device that exists in any game is the ability to say (here,
in a chess game), "Man, did I get off to a bad start. Maybe you'll get
a 1 point win, but maybe you'll only get a draw or perhaps even I'll
wind up winning. Tell you what, why don't you just settle for half a
point now and we'll start the next game quickly." And then your
opponent could either accept or argue that she deserves two-thirds of a
point, etc.
>In particular, a lot of doubles might be rejected with regret, not for
>the fear of having made a wrong decision, but just for losing the fun of
>playing out a fascinating (if poor) position. Similarly, a lot of money
>might be lost by accepting for the same reason. This problem, and the
>variance problem mentioned above, would both be ameliorated by the use
>of a LESS-THAN-DOUBLING cube. The same idea exactly would be applied,
>and so the same sort of probability calculations would obtain, but with
>a factor of less than two.
If all this was really important to you, you might try saying to your
opponent "I drop, so you win a point for this game, but I'd really enjoy
seeing the game through to its conclusion just for kicks." I doubt I
would grant you this wish if I were playing against you, but you'd be
welcome to copy down the position on a piece of paper so you could study
it later if you wanted to.
And if the decision to drop was an easy one, then your opponent didn't
choose the correct time to apply it. :-)
-Matthew
--
Matthew Daly I feel that if a person has problems communicating
mwd...@kodak.com the very least he can do is to shut up - Tom Lehrer
My opinions are not necessarily those of my employer, of course.
--- Support the anti-Spam amendment! Join at http://www.cauce.org ---
Chuck Messenger
mat...@math.canterbury.ac.nz (Bill Taylor) wrote:
>It seems a lot of folks might object somewhat to the great increase in variance
>the doubling cube introduces to backgammon, but still very much like the idea
>of something like a doubling cube. Or so it would appear from the willingness
>of many money players to settle before the last move or two.
>On the other hand, a great many other games might become more interesting
>if played with something like a doubling cube. Even, chess, othello, etc,
>could be interesting, if played for money, or as part of a long series. (The
>world chess champs might be interesting if so played!) Indeed, poker played
>with a pot-doubling limit is effectively nothing *but* show poker with a
>doubling cube! A cute thought. As far as I know, it has never
>seriously been suggested for games of pure skill that a doubling device might
>be used, but I don't see why not. It still introduces an extra element of
>skill, as in BG:- i.e. judgement on whether one is winning or not, as opposed
>to merely playing on as best one may. This alone is worth a debate.
>However, what I really want to discuss here is the doubling cube in BG.
>In particular, a lot of doubles might be rejected with regret, not for
>the fear of having made a wrong decision, but just for losing the fun of
>playing out a fascinating (if poor) position. Similarly, a lot of money
>might be lost by accepting for the same reason. This problem, and the
>variance problem mentioned above, would both be ameliorated by the use
>of a LESS-THAN-DOUBLING cube. The same idea exactly would be applied,
>and so the same sort of probability calculations would obtain, but with
>a factor of less than two.
>My suggestion would be for a "one-and-a-halfing" cube; or, if you're a
>classics scholar, a "sesqui-cube".
>The sequi-cube could not always be perfectly exact, of course, but if the
>basic stake were regarded as $4 (or $400 dollars, or 4 points in a match),
>it could increase as follows:
> 4, 6, 9, 13, 20, 30, 45, 67, 100 etc.
>Not a perfect 1.5 ratio, but near enough for money calculations to be
>approximately independent of the current stake.
>So; how would it be?
>Would it be a good idea?
>Would it have a beneficial effect on money play?
>Would the average payout be different?
>Would it have a beneficial effect on matches?
>And would it be a good idea for games of skill?
Yes -- I think you're on to something! On all counts. Firstly, there
is no reason at all that a doubling cube would make any less sense in
a game of 100% information (what you call a "game of skill") than it
does in other types of games. It merely adds a new element of skill --
the ability to determine when you're ahead/behind, and by how much.
As for the idea to change the doubling cube to a less-than-doubling
cube -- again, an interesting idea worth pursuing.
I've been thinking about the doubling mechanism, actually, and I
was about to write a program to calculate the correct time to
double (which I'm sure has been done endlessly before, but hey...)
I have heard that the optimal time to double is when you have a
66% chance to win, and I want to verify this. While I'm at it,
I could analyze your under-doubling scenario, and determine what
the optimal time to double would be. Seems logical that it would
be less than 66%, which would be a fine thing. This would mean
that doubling would occur more frequently in a game, making it a
more prominent part of the game.
- Chuck Messenger
Steve Mellen
>
> Yes -- I think you're on to something! On all counts. Firstly, there
> is no reason at all that a doubling cube would make any less sense in
> a game of 100% information (what you call a "game of skill") than it
> does in other types of games. It merely adds a new element of skill --
> the ability to determine when you're ahead/behind, and by how much.
>
If Kasparov doubles you after the first move, do you have a take?
Think about this before you conclude a doubling cube would make games of
skill more interesting.
Chuck Messenger
Well, I went ahead and wrote a simulation, to get some answers.
My simulation is based on a simplified game, whose purpose is to
analyze the doubling mechanism. Specifically, the question I'm
trying to answer is, at what % chance to win should you double?
I call the game I analyzed Tug-o-Dice. There is a track with 21
spaces, and a puck. Randomly decide who starts. Start the puck
2 spaces away from the the center, toward the non-starting player.
On your turn, you first get the option to double, just like
in backgammon. Then, you roll a 6-sided die, and move the puck
that many spaces toward your side. If the move would put the
puck past your end of the board, you win.
So, your chance to win is a simple function of where the puck
currently is, and your chance changes after each die roll, as
the puck moves. On average, Tug-o-Dice lasts about 35 turns
(assuming all doubles are accepted). This is similar, roughly,
to backgammon. So, Tug-o-Dice, arguably, provides a rough
simulation of the doubling mechanic in backgammon.
The following chart shows your chance to win (assuming you
sit on the left), as a function of where the puck is (top line
is space #, bottom line is win %):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
-- 98 95 92 89 84 78 73 68 64 59 54 49 44 39 34 29 24 19 15 10
Note: the center space is 11. If the player on the left
starts, the puck starts in space 13. Otherwise, it starts
in space 9. So, the starting player always begins the game
with a 49% chance to win.
The only decisions you have in Tug-o-Dice are when to double,
and when to accept a double. So, your strategy can be
summarized with 2 numbers: the maximum number of spaces away
the puck can be for you to double, and the maximum number of
spaces away it can to be for you to _accept_ a double.
After dozens of trials, with 1,000,000 samples per trial, I
established that the optimal answers are 8 and 15 (i.e. if
you're on the left, when the puck is at space 8 or lower, you
should double, and you should only accept a double if the puck
is at space 15 or lower). Looking at the chart above, these
correspond to a win % of 73% and 39%, respectively. So, you
should double if your chance to win is currently 73% or more,
and you should only accept a double if you have at least a 39%
chance to win. The average number of points per game is 2.4,
if both sides play optimally, and the game's avg duration is
30 turns (down from 35 with no doubling).
Just for an example, suppose that, rather than waiting for
our chance to win to be 73%, we instead impatiently double
as soon as our chance is over 50%. This means, for Tug-o-Dice,
that we double as soon as the puck is at space 12 or less
(vs. the optimal, which is space 8 or less). In a contest with
the optimal strategy, you'll get only 75% as many points, on
average, according to my simulation -- a severe penalty for
non-optimal play! (the avg points per game goes up to 4.7,
and game duration goes up to 32 turns)
OK, so the optimal double point is a win % somewhere near
70%+, and the optimal accept point is a win % somewhere near
40%. No big surprise, but it's nice to verify -- I had
heard the optimal win % was around 66%, which is supported
by my experiment.
So, now we're ready to answer the question: what if, rather
than doubling each time, we increase by some other factor,
like 1.5 -- as suggested by the originator of this thread.
My intuition had been that this change would increase the
frequency of doubles. However, my experiment with Tug-o-Dice
demonstrates otherwise. In this case, I found the optimal
double point had actually increased, to 7 from 8 (representing
a win % of 78%, up from 73%), while the accept point increased
from 15 to 16 (representing a minimum win % of 34%, down from
39%). So, the net effect of decreasing the "double" factor
to 1.5 from 2 was actually to _decrease_ the amount of
doubling -- it is optimal to wait even longer than before to
double, and conversely, to accept even more doubles than
before.
OK, well, what if we use tripling instead of doubling?
Does the trend reverse itself? Yes. With tripling, the
optimal double point goes back to 8 (win % of 73%), while
the optimal accept point goes up to 14 (minimum win % of
44%). So, with tripling instead of doubling, we should
become a notch less willing to accept a triple (over
accepting a double). Probably (although the simulation
doesn't show this, due to granularity limitations of the
model), we should also be a bit more willing to spring
a triple than we were to spring a double.
So, bottom line is, if you reduce the "doubling factor"
from 2 to 1.5, then there will be fewer doublings in a
game. Conversely, if you increase the doubling factor
to 3, there will be more doublings (assuming optimal
play, of course). These conclusions are certainly true
for Tug-o-Dice, and are doubtlessly true for backgammon,
too.
- Chuck Messenger
John S Mamoun
: mat...@math.canterbury.ac.nz (Bill Taylor) wrote:
: >On the other hand, a great many other games might become more interesting
: >if played with something like a doubling cube. Even, chess, othello, etc,
: >could be interesting, if played for money, or as part of a long series. (The
: >world chess champs might be interesting if so played!) Indeed, poker played
: >with a pot-doubling limit is effectively nothing *but* show poker with a
: >doubling cube! A cute thought. As far as I know, it has never
The problem with this idea is that, at least theoretically, there is
no luck factor in chess, othello, etc. Thus, mathematically, there is
an absolutely correct answer as to whether or not to take a double.
Consequently, there will theoretically be no motivation by one
winning the game to double, or for one losing to take. What makes the
doubling cube justifiable in Backgammon is the degree to which the
value of one's equity can evolve over the course of the game, despite
perfect checker skill by both players. This is due to the stochastic
factor of the game, without which the doubling cube is useless.
Of course, games like chess, othello, go, etc. are so far unsolved,
and contain countless more positions than Backgammon. BG has 10^20
positions roughly, while chess has 10^45, for example. For this
reason, there is in a way a stochastic factor in the game, in that
players will at times encounter positions for which they don't know
what decision is correct. In these positions, their decisions
will be made on whim, or on a decision-making impulse regulated by
chance. In a superficial way, this might justify use of a doubling
cube in these games (the same kind of whim also occurs in Backgammon).
But this superficial justification is over-ridden by the fact that
perfect players of the game cannot have any theoretical justification
for using a doubling cube.
Patrick Juola
In article <solon-23119...@ts011d12.chi-il.concentric.net> so...@concentric.net (Steve Mellen) writes:
>In article <347831...@servtech.com>, c...@servtech.com wrote:
>
>>
>> Yes -- I think you're on to something! On all counts. Firstly, there
>> is no reason at all that a doubling cube would make any less sense in
>> a game of 100% information (what you call a "game of skill") than it
>> does in other types of games. It merely adds a new element of skill --
>> the ability to determine when you're ahead/behind, and by how much.
>>
>
>If Kasparov doubles you after the first move, do you have a take?
I probably wouldn't accept the double. Kasparov also knows this. It
more or less gives him the ability to force a win more quickly than he
otherwise could have, so he can win thirty games in an hour instead
of only six.
I'd also not accept the double from the world backgrammon champion
after the first move. This is because I know that I'm behind from
the start on skill level alone.
-kitten
Chuck Messenger
John S Mamoun wrote:
>
> : mat...@math.canterbury.ac.nz (Bill Taylor) wrote:
> : >On the other hand, a great many other games might become more interesting
> : >if played with something like a doubling cube. Even, chess, othello, etc,
> : >could be interesting, if played for money, or as part of a long series. (The
> : >world chess champs might be interesting if so played!) Indeed, poker played
> : >with a pot-doubling limit is effectively nothing *but* show poker with a
> : >doubling cube! A cute thought. As far as I know, it has never
>
> The problem with this idea is that, at least theoretically, there is
> no luck factor in chess, othello, etc.
Not true. In all interesting games, there is a luck factor,
because you cannot foresee all of the consequences of your move.
It's like choosing from a box of chocolates. This is as much
a luck element as throwing a dice.
> Thus, mathematically, there is
> an absolutely correct answer as to whether or not to take a double.
True. However, this doesn't matter. Take Big Blue, for example.
The way it chooses it's move is by calculating how good it
thinks its position would be after making each possible move.
So, in principle, it could refine this algorithm to come up with
a measure of how much better it's position was than it's opponent's
(it may well already do this). Then, it's just a matter of setting
a threshold and doubling at the choice moment (when it figures it's
chance of winning is about 70%).
> Consequently, there will theoretically be no motivation by one
> winning the game to double, or for one losing to take.
Only if you're playing against a "perfect computer", which can
always choose the absolute best move. However, it wouldn't be
very interesting to play such a computer, I wouldn't think.
Besides, this computer could simply double at the point where
it realised it had a 100% chance to win. You would know your
goose was cooked when you got doubled by this baby...
> What makes the
> doubling cube justifiable in Backgammon is the degree to which the
> value of one's equity can evolve over the course of the game, despite
> perfect checker skill by both players. This is due to the stochastic
> factor of the game, without which the doubling cube is useless.
In all "interesting" games (i.e. discounting games like Tic Tac
Toe), the value of one's equity evolves over the course of the
game.
> Of course, games like chess, othello, go, etc. are so far unsolved,
> and contain countless more positions than Backgammon. BG has 10^20
> positions roughly, while chess has 10^45, for example. For this
> reason, there is in a way a stochastic factor in the game, in that
> players will at times encounter positions for which they don't know
> what decision is correct.
Not just at time, but constantly. In fact, on almost every
move, except some specialized cases in the endgame (which
only beginners even bother to play out, since their outcome
is a foregone conclusion).
> In these positions, their decisions
> will be made on whim, or on a decision-making impulse regulated by
> chance. In a superficial way, this might justify use of a doubling
> cube in these games (the same kind of whim also occurs in Backgammon).
>
> But this superficial justification is over-ridden by the fact that
> perfect players of the game cannot have any theoretical justification
> for using a doubling cube.
As stated before, if you're a perfect player, then just double
when you know you're going to win -- that's a good theoretical
justification!
- Chuck Messenger
Matthew Daly
pat...@gryphon.psych.ox.ac.uk (Patrick Juola), if that is your REAL
name, said:
>I'd also not accept the double from the world backgrammon champion
>after the first move. This is because I know that I'm behind from
>the start on skill level alone.
Unless the first move was something really gross her starting with a 6-1
and me rolling a 5-2, I'd take the double with glee. The difference
between the world chess champion and the world backgammon champion is
that a beginner can beat a grandmaster backgammon player.
How the dice will affect the development of the board is anyone's guess,
but it's hard to figure that the pro has a 75% of beating me with no
board even after giving me the leverage of owning the cube. If it were,
why did I agree play a game that I expected to drop after the first
move?
John S Mamoun
Chuck Messenger (c...@servtech.com) wrote:
: John S Mamoun wrote:
: > The problem with this idea is that, at least theoretically, there is
: > no luck factor in chess, othello, etc.
: Not true. In all interesting games, there is a luck factor,
: because you cannot foresee all of the consequences of your move.
: It's like choosing from a box of chocolates. This is as much
: a luck element as throwing a dice.
Ok, fine, that's exactly what I said in my post anyway. Your point?
: > Thus, mathematically, there is
: > an absolutely correct answer as to whether or not to take a double.
: True. However, this doesn't matter. Take Big Blue, for example.
: The way it chooses it's move is by calculating how good it
: thinks its position would be after making each possible move.
: So, in principle, it could refine this algorithm to come up with
: a measure of how much better it's position was than it's opponent's
: (it may well already do this). Then, it's just a matter of setting
: a threshold and doubling at the choice moment (when it figures it's
: chance of winning is about 70%).
Well, this is irrelevent. I'm assuming that players evaluate
positions perfectly. If they do so, there is no 70% of anything.
A position is either a draw, a win or a loss.
: > Consequently, there will theoretically be no motivation by one
: > winning the game to double, or for one losing to take.
: Only if you're playing against a "perfect computer", which can
: always choose the absolute best move. However, it wouldn't be
: very interesting to play such a computer, I wouldn't think.
: Besides, this computer could simply double at the point where
: it realised it had a 100% chance to win. You would know your
: goose was cooked when you got doubled by this baby...
This is besides the point. My point is that there is no justification
for using a doubling cube in theoretically pure-skill games because
there is no chance of the equity of a game evolving after the point
of the double when the game is played by perfect players.
: > What makes the
: > doubling cube justifiable in Backgammon is the degree to which the
: > value of one's equity can evolve over the course of the game, despite
: > perfect checker skill by both players. This is due to the stochastic
: > factor of the game, without which the doubling cube is useless.
: In all "interesting" games (i.e. discounting games like Tic Tac
: Toe), the value of one's equity evolves over the course of the
: game.
Not if the game is played by perfect players. Once a position
is a win, loss or draw, it will remain that way until the game
plays out to the end outcome. In fact, in a perfectly played
game, there is only one outcome (except for multiple draw
outcomes) decided, in fact, by the initial position of the game.
:
: > Of course, games like chess, othello, go, etc. are so far unsolved,
: > and contain countless more positions than Backgammon. BG has 10^20
: > positions roughly, while chess has 10^45, for example. For this
: > reason, there is in a way a stochastic factor in the game, in that
: > players will at times encounter positions for which they don't know
: > what decision is correct.
: Not just at time, but constantly. In fact, on almost every
: move, except some specialized cases in the endgame (which
: only beginners even bother to play out, since their outcome
: is a foregone conclusion).
That's besides the point. The point is that since perfect play
leads to absolutely predisposed equity values, there is no
justification for doubling. Just because humans are foolish
mortals who don't have perfect game-playing vision, doesn't
mean that use of the doubling cube is justifiable.
: > In these positions, their decisions
: > will be made on whim, or on a decision-making impulse regulated by
: > chance. In a superficial way, this might justify use of a doubling
: > cube in these games (the same kind of whim also occurs in Backgammon).
: >
: > But this superficial justification is over-ridden by the fact that
: > perfect players of the game cannot have any theoretical justification
: > for using a doubling cube.
: As stated before, if you're a perfect player, then just double
: when you know you're going to win -- that's a good theoretical
: justification!
No it isn't, because I'm assuming that the opponent is also a
perfect player, in which case he will instantly drop. There is
thus no possibility of a perfect player playing another perfect
player to increase his equity by using the doubling cube, compared
to not using it. So why use it in pure skill games?
--John
Gary Wong
(Followups to rec.games.backgammon; this isn't very abstract any more.)
pat...@gryphon.psych.ox.ac.uk (Patrick Juola) writes:
> In article <solon-23119...@ts011d12.chi-il.concentric.net>
> so...@concentric.net (Steve Mellen) writes:
> I'd also not accept the double from the world backgrammon champion
> after the first move. This is because I know that I'm behind from
> the start on skill level alone.
That reasoning can't be right. For a start, are you playing a match or for
money? I know if I was playing the world champ for money, I'd be considering
what kind of psychiatric treatment to apply for, not whether to accept his/her
cube :-)
But seriously, assuming your take point in a money game is 25% cubeless
winning chances, then even plenty of beginners would have that much equity
against a world champion -- a 75/25 advantage is equivalent to over 950
FIBS rating points in terms of cubeless winning probability (though admittedly
gammons and the cube make it somewhat uncertain). If the world champ is rated
at 2000, then you only need to be about a 1000 class player to take the cube.
Depending what your goals are (do you want to lose as little money as possible
in a fixed amount of time? lose as little money as possible in a fixed number
of games? maximise your probability of winning?), your take point could
arguably go lower than normal if you are the underdog: if you have
sufficiently low winning chances, then dropping at the opening minimises your
losses in a fixed number of games, but does not minimise the loss for fixed
time or maximise your winning probability. So no matter how bad you are, the
world champ would be foolish to cube you at the opening: if he/she is not
overwhelmingly better than you, then you have an easy take; if he/she is,
then your take point is correspondingly lower and the opening position isn't
nearly volatile enough to justify a double. In fact they would be giving
you a considerable advantage by passing you the cube -- they're sacrificing
the opportunity to cube you out later, without any risk of you dropping the
initial double.
In match play, the take becomes even clearer. No matter how much of an
underdog you are, your match equity is always higher at 5-away, 5-away
holding a 2 cube than it is trailing 4-away, 5-away for the same board
position (because in either case a loss will occur with the same probability,
taking you to trailing 3-away, 5-away; but a win for you holding a 2 cube
is considerably better -- not to mention that you increase your winning
probability somewhat just by owning the cube). So again, the world champ
would actually be making an error by turning the cube at the start of the
game.
The above reasoning is of course simplified somewhat because it's based on an
(illegal) double before the game begins. But I suspect the result still holds,
even for a double by the champion at the earliest opportunity. If you start,
the best you can do is 31 (assuming you're competent enough to play it
8/5, 6/5) which between equally able players might give you a 7% advantage
(67/53). The champion would definitely be wrong to cube you after you open
with a 31, and you'd have a very easy take. Assuming it went the other way
(the world champ rolls 31; you roll junk; the champion doubles), then
admittedly you might have a drop then if you were enough of an underdog. But
I still maintain that if the opening roll(s) go sufficiently well for you,
then you ALWAYS have a take in match play if the world champ doubles you at
the earliest opportunity, no matter who you are or how likely you are to lose.
The same goes for money if you are playing to win or minimising your losses
over fixed time; players who expect to lose over a point a game against the
world champion (who would have a FIBS rating of under 1000) can minimise their
losses for money in a fixed game by dropping the cube at the earliest
opportunity (though you have to wonder what the point of playing is).
Cheers,
Gary (GaryW on FIBS).
PS: sorry if none of the above makes any sense, it's past my bedtime and I'm
going home now and am too tired and irritable to proofread it :-)
--
Gary Wong, Computer Science Department, University of Auckland, New Zealand
ga...@cs.auckland.ac.nz http://www.cs.auckland.ac.nz/~gary/
Gary Wong
Chuck Messenger <c...@servtech.com> writes:
> John S Mamoun wrote:
> > The problem with this idea is that, at least theoretically, there is
> > no luck factor in chess, othello, etc.
>
> Not true. In all interesting games, there is a luck factor,
> because you cannot foresee all of the consequences of your move.
> It's like choosing from a box of chocolates. This is as much
> a luck element as throwing a dice.
John is right (given that he says "at least theoretically"). In perfect
information games, there is theoretically no luck -- the terminal game
states can only be (using chess as an example) "black wins", "white wins",
or "stalemate". The board state immediately before the ultimate move would
have been "black can force a win", "white can force a win", or "neither player
can force a win" respectively. With perfect play on both sides (which is
why the "at least theoretically" restriction is necessary), this state will
_never change_ between positions -- if the state before a move is "white can
force a win", it is impossible for black to change the state, and white
will not change the state either without an error. The same situation
applies in reverse; ie. if black has just moved and the current state is
"white can force a win", then the state must have been "white can force a
win" _before_ the move too (otherwise, black just made an error). Carrying
on the reasoning all the way back to the beginning of the game, you can see
that the initial position must be either a win for white, win for black, or
draw (I believe the initial position in chess is not a win for black, without
considering proof or disproof -- that is, either white can always win, or
black can always draw).
Humans can already categorise some positions (eg. "white to mate in 3"); the
starting position might also (theoretically) turn out to be "white to mate
in 72", for instance.
> > What makes the
> > doubling cube justifiable in Backgammon is the degree to which the
> > value of one's equity can evolve over the course of the game, despite
> > perfect checker skill by both players. This is due to the stochastic
> > factor of the game, without which the doubling cube is useless.
>
> In all "interesting" games (i.e. discounting games like Tic Tac
> Toe), the value of one's equity evolves over the course of the
> game.
Not true. The way humans _estimate_ their equity may vary (as a result of
our limited analysis of the position) over the course of the game, but in a
perfect information game, the true equity is well defined (in absolute terms,
not probabilistic as in backgammon), whether it is known to the players or not.
Not only that, but the equity _does not change_ from move to move, unless a
player makes a mistake.
Another related issue is that the use of the cube depends on volatility, and
volatility only exists in imperfect information games. A very simple rule
in backgammon for considering when to double is: "if the opponent will always
take the cube should you double next turn instead, then it is incorrect to
double now", ie. you NEED market-losing rolls to make it a correct double.
But market-losing rolls only exist because of the volatility in the game;
in a perfect information game (without volatility) you should never double!
In backgammon, there are 6 possibilities for the correct cube strategy for
any position: the player on roll should either 1) neither double nor redouble,
2) double but not redouble, or 3) double or redouble; and the opponent should
either a) take or b) drop. Each of the 6 combinations are valid in various
positions (there is a 7th possibility; double/beaver with the Jacoby rule
in effect, but that's another story). However, in a perfect information
game this will not be the case: there are only two correct cube behaviours:
double/drop, or no double/take. It is NEVER correct to double/take in
(for instance) chess, which makes the cube action pretty much farcial.
> > But this superficial justification is over-ridden by the fact that
> > perfect players of the game cannot have any theoretical justification
> > for using a doubling cube.
>
> As stated before, if you're a perfect player, then just double
> when you know you're going to win -- that's a good theoretical
> justification!
No it's not; it may be a shaky practical justification but it's not a
theoretical justification at all. In a chess game, if you know you are
going to win then the correct behaviour is for your opponent to resign,
or failing that you might demonstrate "mate in 3". In either case, your
opponent has a clear drop, so the cube can't be seen as adding anything
to the game.
Cheers,
Gary (GaryW on FIBS).
Patrick Juola
In article <65ctot$avf$1...@netnews.upenn.edu> js...@mail2.sas.upenn.edu (John S Mamoun) writes:
>: Only if you're playing against a "perfect computer", which can
>: always choose the absolute best move. However, it wouldn't be
>: very interesting to play such a computer, I wouldn't think.
>: Besides, this computer could simply double at the point where
>: it realised it had a 100% chance to win. You would know your
>: goose was cooked when you got doubled by this baby...
>
>This is besides the point. My point is that there is no justification
>for using a doubling cube in theoretically pure-skill games because
>there is no chance of the equity of a game evolving after the point
>of the double when the game is played by perfect players.
There's no point in *playing* a pure-skill game with perfect players.
-kitten
Carl Tait
In article <65ctot$avf$1...@netnews.upenn.edu>,
John S Mamoun <js...@mail2.sas.upenn.edu> wrote:
>
>No it isn't, because I'm assuming that the opponent is also a
>perfect player, in which case he will instantly drop. There is
>thus no possibility of a perfect player playing another perfect
>player to increase his equity by using the doubling cube, compared
>to not using it. So why use it in pure skill games?
By this argument, why should we play pure skill games at all?
Assuming perfect players, the outcome of the game can be predicted
with certainty before any moves are made. Connect Four, for example,
is known to be a win for the first player.
The obvious answer is that humans are so far from perfect players
that they can find such games interesting. A similar argument applies
to the use of a doubling cube in these games. The existence of an
absolutely correct decision says nothing about the difficulty --
or potential interest -- of finding it.
--
Carl Tait IBM T. J. Watson Research Center
cdt...@us.ibm.com Yorktown Heights, NY 10598
Don Woods
Chuck Messenger <c...@servtech.com> writes:
[description of Tug-o-Dice game omitted]
> The only decisions you have in Tug-o-Dice are when to double,
> and when to accept a double.
> After dozens of trials, with 1,000,000 samples per trial, I
> should double if your chance to win is currently 73% or more,
> and you should only accept a double if you have at least a 39%
> chance to win.
Tug-o-Dice looks like a reasonable game for empirical analysis of
doubling, but I don't believe your results.
For starters, the "accept" threshhold is easy to determine
mathematically. It's 25%. If you accept a double when you
hvae a 25% chance, then 75% of the time you lose a doubled
stack (-1.5), and 25% of the time you win the doubled stake
(+0.5), for a net of -1, which is exactly the same net as
if you decline the double. If your chances are 26%, you
lose 0.74x2 and win 0.26x2 = net -0.96, which means you lose
less by accepting.
Part of your problem is that you're interpreting your own
results wrong:
> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
> -- 98 95 92 89 84 78 73 68 64 59 54 49 44 39 34 29 24 19 15 10
>
> if you're on the left, when the puck is at space 8 or lower, you
> should double, and you should only accept a double if the puck
> is at space 15 or lower
The latter result does NOT mean you should accept only at 39% or
lower. Remember, if you're thinking of accepting a double it must
be the OTHER player's turn. So really you should be looking at it
from the righthand player's point of view: the puck is at 7 and a
double has been offered. His chances are 22% so he should drop.
But this is at least a lot closer to 25%, so it's within the bounds
of empirical error.
The other big oversight in your analysis is that there are THREE
relevant numbers: when to accept, when to double, and when to
REDOUBLE. As any good backgammon player knows, having the cube is
a big advantage. Actually, it's two advantages: you can double
whenever you think it's good for you to do so, AND your opponent
CAN'T. The latter means that, no matter how bad your position gets,
you can play it to the end at no additional risk.
In _The Backgammon Book_ by Jacoby & Crawford, they discuss when to
double/redouble/accept, and start out "by considering only cases
in which there is no possibility of a gammon" (an automatically
doubled stake that is not received if the game ends due to a double
being declined). They suggest you "consider a first double" if
your chances are 7-to-5 or better, and "definitely make a first double"
at 9-to-5 or better. That's a range of about 58-64%. But if you have
already accepted a double, their suggested range for the redouble is
to consider it at 3-to-2, and definitely redouble at 2-to-1 (60-67%).
It may well be that Tug-o-Dice doesn't have a fine enough breakdown
of probabilities to make this distinction matter, but you should try
it to see.
Meanwhile, your later result (a 1.5-times die means you wait longer
to double, and accept at worse odds) is far from surprising. By the
same analysis that gives 25% as the take point on a doubling cube, a
1.5ing cube would have a take point of 5/6 (83%). If you accept the
cube at 5/6, you lose 5/6 times 1.5 and win 1/6 times 1.5, which is
a net loss of 2/3 times 1.5 = -1, the same as if you declined. The
tripling cube would have a take point of 2/3 (67%). This should even
be intuitively obvious: if you're playing for $1 and you're behind,
and the other player wants to up the stakes to $1.50, it's not as big
a deal as if he wants to raise the stakes to $3. For $3 you'd want
to have a lot better chance of the game turning around!
-- Don.
-------------------------------------------------------------------------------
--
-- Don Woods (d...@clari.net) ClariNet provides on-line news.
-- http://www.clari.net/~don I provide personal opinions.
--
Alexander Nitschke
Don Woods wrote:
>
> Chuck Messenger <c...@servtech.com> writes:
> [description of Tug-o-Dice game omitted]
> > and when to accept a double.
> > After dozens of trials, with 1,000,000 samples per trial, I
> > should double if your chance to win is currently 73% or more,
> > and you should only accept a double if you have at least a 39%
> > chance to win.
>
> doubling, but I don't believe your results.
>
> For starters, the "accept" threshhold is easy to determine
> mathematically. It's 25%. If you accept a double when you
> hvae a 25% chance, then 75% of the time you lose a doubled
> stack (-1.5), and 25% of the time you win the doubled stake
> (+0.5), for a net of -1, which is exactly the same net as
> if you decline the double. If your chances are 26%, you
> lose 0.74x2 and win 0.26x2 = net -0.96, which means you lose
> less by accepting.
>
> Part of your problem is that you're interpreting your own
> results wrong:
>
> > -- 98 95 92 89 84 78 73 68 64 59 54 49 44 39 34 29 24 19 15 10
> >
> > should double, and you should only accept a double if the puck
>
> The latter result does NOT mean you should accept only at 39% or
> lower. Remember, if you're thinking of accepting a double it must
> be the OTHER player's turn. So really you should be looking at it
> from the righthand player's point of view: the puck is at 7 and a
> double has been offered. His chances are 22% so he should drop.
> But this is at least a lot closer to 25%, so it's within the bounds
> of empirical error.
His chances are 22% CUBELESS (so I assume with some certainty), this
doesn't mean it is a drop. He can gain additional equity with redoubles,
which puts his equity WITH CUBE above 25%.
I think Tug-o-Dice is a good object for studying doubling, but there
should be two refinements:
Firstly the scale is much too rough because 21 fields are too few, the
playing field should be extended to at least 100 fields.
Secondly the volatility could be studied as an important factor for
doubling decisions. This could be introduced with dice with more or less
than six sides. If a die is used with only 4 sides (ie numbers 1 to 4),
the volatility would be lower, a die with 8 sides would introduce higher
volatility.
--
Alexander (acey_deucey@FIBS)
Chuck Messenger
Don Woods wrote:
>
> Chuck Messenger <c...@servtech.com> writes:
> [description of Tug-o-Dice game omitted]
> > and when to accept a double.
> > After dozens of trials, with 1,000,000 samples per trial, I
> > should double if your chance to win is currently 73% or more,
> > and you should only accept a double if you have at least a 39%
> > chance to win.
>
> doubling, but I don't believe your results.
>
> For starters, the "accept" threshhold is easy to determine
> mathematically. It's 25%. If you accept a double when you
> hvae a 25% chance, then 75% of the time you lose a doubled
> stack (-1.5), and 25% of the time you win the doubled stake
> (+0.5), for a net of -1, which is exactly the same net as
> if you decline the double. If your chances are 26%, you
> lose 0.74x2 and win 0.26x2 = net -0.96, which means you lose
> less by accepting.
>
> Part of your problem is that you're interpreting your own
> results wrong:
>
> > -- 98 95 92 89 84 78 73 68 64 59 54 49 44 39 34 29 24 19 15 10
> >
> > should double, and you should only accept a double if the puck
>
> The latter result does NOT mean you should accept only at 39% or
> lower. Remember, if you're thinking of accepting a double it must
> be the OTHER player's turn. So really you should be looking at it
> from the righthand player's point of view: the puck is at 7 and a
> double has been offered. His chances are 22% so he should drop.
> But this is at least a lot closer to 25%, so it's within the bounds
> of empirical error.
Yes -- thanks for straightening me out -- I hadn't seen that
there was a simple analytical answer to when you should accept
a double. And yes, as you say, I was misinterpreting my own
results. The results are right, by my interpretation was wrong,
then -- my results show to accept at 22% or better, which is
within the margin of accuracy of the Tug-o-Dice model.
Actually, that simplifies things for me nicely -- there's no
point it simulating when to accept a double -- the answer is
obvious. So, that reduces the problem to 2 variables rather
than 4 (the 2 variables being the double point for each
player).
> The other big oversight in your analysis is that there are THREE
> relevant numbers: when to accept, when to double, and when to
> REDOUBLE. As any good backgammon player knows, having the cube is
> a big advantage. Actually, it's two advantages: you can double
> whenever you think it's good for you to do so, AND your opponent
> CAN'T. The latter means that, no matter how bad your position gets,
> you can play it to the end at no additional risk.
Yes, well, I purposely avoided the subject of redoubling,
since I already had 4 variables, which was as many as I could
manage. Since you've eliminated two of my variables (they're
really constants), I could now manage the analysis of
redoubling, too.
> In _The Backgammon Book_ by Jacoby & Crawford, they discuss when to
> double/redouble/accept, and start out "by considering only cases
> in which there is no possibility of a gammon" (an automatically
> doubled stake that is not received if the game ends due to a double
> being declined). They suggest you "consider a first double" if
> your chances are 7-to-5 or better, and "definitely make a first double"
> at 9-to-5 or better. That's a range of about 58-64%. But if you have
> already accepted a double, their suggested range for the redouble is
> to consider it at 3-to-2, and definitely redouble at 2-to-1 (60-67%).
>
> It may well be that Tug-o-Dice doesn't have a fine enough breakdown
> of probabilities to make this distinction matter, but you should try
> it to see.
Interesting! Perhaps my Tug-o-Dice model is useful, after all.
According to my model, it is distinctly non-optimal to double
at 5-to-7. Let's say player A doubles at bin 11 or less (59%
win chance), and player at doubles at the optimal bin 8 (73%
win chance). My simulation shows player B winning 55% of the
total points. The average points/game is 4.0, and the avg.
turns/game is 32.
What about 9-to-5? That's a 64% win chance, which corresponds
to bin 10. Pitted against the optimal bin 8, simulation
shows the optimal strategy winning 53% of the points (avg.
points/game 3.5, avg. turns/game 32).
So, does this show that your book's advice is bad? At least
in Tug-o-Dice, you shouldn't double until you have about 73%
win chance, which is about 13-to-5.
- Chuck Messenger
Chuck Messenger
Alexander Nitschke wrote:
>
> Don Woods wrote:
> >
> > Chuck Messenger <c...@servtech.com> writes:
> > [description of Tug-o-Dice game omitted]
> > > and when to accept a double.
> > > After dozens of trials, with 1,000,000 samples per trial, I
> > > should double if your chance to win is currently 73% or more,
> > > and you should only accept a double if you have at least a 39%
> > > chance to win.
> >
> > doubling, but I don't believe your results.
> >
> > For starters, the "accept" threshhold is easy to determine
> > mathematically. It's 25%. If you accept a double when you
> > hvae a 25% chance, then 75% of the time you lose a doubled
> > stack (-1.5), and 25% of the time you win the doubled stake
> > (+0.5), for a net of -1, which is exactly the same net as
> > if you decline the double. If your chances are 26%, you
> > lose 0.74x2 and win 0.26x2 = net -0.96, which means you lose
> > less by accepting.
> >
> > Part of your problem is that you're interpreting your own
> > results wrong:
> >
> > > -- 98 95 92 89 84 78 73 68 64 59 54 49 44 39 34 29 24 19 15 10
> > >
> > > should double, and you should only accept a double if the puck
> >
> > The latter result does NOT mean you should accept only at 39% or
> > lower. Remember, if you're thinking of accepting a double it must
> > be the OTHER player's turn. So really you should be looking at it
> > from the righthand player's point of view: the puck is at 7 and a
> > double has been offered. His chances are 22% so he should drop.
> > But this is at least a lot closer to 25%, so it's within the bounds
> > of empirical error.
>
> doesn't mean it is a drop. He can gain additional equity with redoubles,
> which puts his equity WITH CUBE above 25%.
Well, this brings up an issue, then: perhaps I _can't_ leave
out the accept-the-double decision from the model, after
all, if there is redoubling. That would mean there were
6 variables (each player with 3 decisions: when to double,
when to accept, and when to redouble). Could still be
done, but searching for a global optimum would take alot
more doing...
> I think Tug-o-Dice is a good object for studying doubling, but there
> should be two refinements:
> Firstly the scale is much too rough because 21 fields are too few, the
> playing field should be extended to at least 100 fields.
> Secondly the volatility could be studied as an important factor for
> doubling decisions. This could be introduced with dice with more or less
> than six sides. If a die is used with only 4 sides (ie numbers 1 to 4),
> the volatility would be lower, a die with 8 sides would introduce higher
> volatility.
Yes, I've considered other scales, for the reasons you've
mentioned. I've been assuming it's important to keep the
average number of turns in the range of what it would be
for a game of backgammon. This means that if you use a
larger die, you need a longer board.
One quick simulation later, I find that a 101 square
board with a 20-sided die yields an average game length
of 30 turns. The accuracy of this model would be close
to 1% per bin, vs. more like 5% per bin with the current
model.
So, you're right -- a 101-long board with a d20 would
give more accurate results. The reason I didn't do this
is it would take alot more work to find the local
optimum point, and I just wanted some rough answers
to start the process off. I think the best way to go
would be to hone in on the right answer with the
d6/21-spaces model, then switch to the d20/101-spaces
model to fine tune the results.
- Chuck Messenger
Chuck Messenger
Alexander Nitschke wrote:
> His chances are 22% CUBELESS (so I assume with some certainty), this
> doesn't mean it is a drop. He can gain additional equity with redoubles,
> which puts his equity WITH CUBE above 25%.
After some reflection, I now see what you're saying -- even
without considering the effects of redoubling, we can't simply
say that 25% is the analytical answer for when we should accept
a double, because after accepting, we have the benefit of the
cube. So, I guess my original simulation was fine. The only
mistake was that I attributed an acceptance of doubling at
bin 15 as corresponding to a 39% win chance, when in reality
it corresponded to a 22% win chance. (with about a 2-3% margin
of error).
When I get a chance (post Turkey day), I'll re-run the
simulation on the 101 step model, to get a finer granularity
on my results.
- Chuck
Gary Wong
Chuck Messenger <c...@servtech.com> writes:
> Yes -- thanks for straightening me out -- I hadn't seen that
> there was a simple analytical answer to when you should accept
> a double. And yes, as you say, I was misinterpreting my own
> results. The results are right, by my interpretation was wrong,
> then -- my results show to accept at 22% or better, which is
> within the margin of accuracy of the Tug-o-Dice model.
>
> Actually, that simplifies things for me nicely -- there's no
> point it simulating when to accept a double -- the answer is
> obvious. So, that reduces the problem to 2 variables rather
> than 4 (the 2 variables being the double point for each
> player).
The 25% drop point is convenient, but it's not the end of the story. It
doesn't take into account match score, recube vig, gammons and the Jacoby
rule, volatility, relative skill... even if you could quantify all of those,
you'd be way beyond just 2 or 4 variables! Understanding which factors are
important and how they should influence your decision is far better IMHO than
being able to (analytically or empirically) derive the take/drop point for
a single artificial position without being able to extrapolate from there
for any practical use. On the other hand, there's a lot to be said for a
simple approximation if it gives you more insight. So here's what I think:
- Dropping at 25% for money is reasonable, but ignores the recube vig you'd
gain if you took the cube. A slightly better analysis by E. Keeler and
J. Spencer ("Optimal Doubling in Backgammon", Operations Research, Vol. 23,
No. 6) which takes redoubles but not volatility into account, shows that
the theoretical break-even point under those conditions is 20%.
Tug-o-Dice is a somewhat better model to backgammon than theirs because
it's a discrete stochastic game instead of their imaginary smooth
continuous game. But applying Tug-o-Dice results to backgammon should
still be taken with a grain of salt, unless you take care to ensure that
the volatility between the games and positions is comparable.
- When to double (as opposed to when to drop) is more interesting, because
the volatility of the position comes into play. Although the 20% money
drop point is superficially equivalent for any position, in any game
(backgammon, Tug-o-Dice, or whatever), the optimal point at which to
double will vary. The important things to understand are the disadvantages
of doubling early vs. late: if you wait too long before doubling (ie. you
lose your market), then you'll only win a single game instead of having
good chances of winning a doubled game. If your opponent's drop point is
20%, then doubling at 79% winning chances gives you an expected gain of
1.16 points; doubling at 81% and having them drop gives you only 1 point.
That's the cost of doubling late. On the other hand, if you double early,
you run more risk of the game going your opponent's way and them using it
against you (wishing you hadn't doubled after all), and lose the ability
to cube later. If you _re_double early, it's even worse, because you give
your opponent the opportunity to double which they wouldn't have had
otherwise (which is why positions exist that are initial doubles, but not
redoubles).
So here are two rules of thumb:
+ it's better to double slightly early than slightly late (79% is better
than 81%)
+ it's better not to double early if you can help it; the only reason you
should double this turn (as opposed to next turn) is if there's a chance
that your opponent might take the cube this turn, but drop it next turn.
Can we derive a theoretical doubling point from what we know, in the same
way we derived the 20% take point? Unfortunately it doesn't look like it;
it's hard to quantify a position's volatility against the early/late
costs. I'll argue that the cost of losing your market (doubling late)
ranges linearly from zero at your opponent's take point to 1 point (at
the current cube value) at 100% winning chances. On the other hand, the
cost of doubling early is 1 point for every game your opponent wins that
they WOULDN'T have won if you'd waited until their drop point; ie. if you
double 5% early, then the cost is 0.05 points. (Note that I haven't
considered the extra cost of _re_doubling early here -- the recube vig
would then come into consideration).
So, if the chance of losing your market over the next 2 plies (your roll,
then your opponent's roll) is greater than the cost of doubling early, then
it is correct to double now. After all this waffle, it's probably time for
an example:
+13-14-15-16-17-18-------19-20-21-22-23-24-+
| O X | | X X X X X X |
| X | | X X X X X X |
| | | |
| | | |
| | | |
v| |BAR| | O on roll, 1 cube, money game.
| | | |
| | | |
| | | |
| | | O O O O O O |
| X O O | | O O O O O O |
+12-11-10--9--8--7--------6--5--4--3--2--1-+
Let's assume that if O hits, she has 95% winning chances and no chance of
winning or losing a gammon; if she misses, the the race after this move will
be essentially even and the game will be 50/50.
O has 11 rolls that hit and lose her market, and 25 rolls that miss for an
even race, which gives her 63.7% winning chances. X has 36.3% chances which
make it an easy take on our 20% theoretical criteria. Is this a double?
The cost of O losing her market is 11/36 x 0.75 (because 95% winning chances
are 3/4 of the way past X's take point) = 0.229 points; the cost of her
doubling early is 25/36 x 0.3 (because if she misses she's 30% short of her
opponent's take point) = 0.208 points, so by the criteria above it's
a narrow double/clear take. If O only had 40% chances in the race, then her
winning chances would be 56.8%; the cost of doubling late would remain at
0.229; but the cost of her doubling early would be 25/36 x 0.4 = 0.278, and it
would be a no double/take.
Note that we saw here a position with 63.7% winning chances that was a
double, and another with 56.8% chances that was not. Does that imply that
there's some magic figure between 56.8 and 63.7 that separates doubles from
no-doubles? No. In a fairly non-volatile position (eg. a long race),
63.7% is not generally good enough to double. On the other hand, the most
volatile position you can get is the last roll of the game: if I have one
chequer on each of my 5 and 2 points, and you have one on each of your 2
and 1 points, then this is a double/take even though I only have 52.7%
winning chances. There is no imaginary doubling point in the same sense
that there is a take point; it depends on the volatility of the position.
So the conclusion is: all other things being equal, the take point in a money
game is 20%. There is no fixed double point; it depends not only on the
winning chances but the volatility. The closest you can get is to calculate
the cost of doubling late vs. the cost of doubling early; if the cost of
doubling late is higher, then it is correct to double now.
All of this discussion has glossed over several important issues (which are
complicated enough that people have written entire books about them). For
instance: how good does your position to be to play on for a gammon,
instead of claiming with the cube? Answer: you need to expect twice as
many gammons as losses (proof is an exercise for the reader). How does the
match score affect cube handling? Tom Keith has written an excellent
article at http://www.bkgm.com/articles/mpd.html ("Match Play Doubling
Strategy") that explains what factors influence the game. How does the
relative skill of the players affect the cube? Read "Can A Fish Taste
Twice As Good" (Jake Jacobs and Walter Trice).
Cheers,
Gary (GaryW on FIBS).
(Follow-ups to rec.games.backgammon.)
Chuck Bower
In article <q4vhxgw...@clari.net>, Don Woods <d...@clari.net> wrote:
(snip)
>In _The Backgammon Book_ by Jacoby & Crawford, they discuss when to
>double/redouble/accept, and start out "by considering only cases
>in which there is no possibility of a gammon" (an automatically
>doubled stake that is not received if the game ends due to a double
>being declined). They suggest you "consider a first double" if
>your chances are 7-to-5 or better, and "definitely make a first double"
>at 9-to-5 or better. That's a range of about 58-64%. But if you have
>already accepted a double, their suggested range for the redouble is
>to consider it at 3-to-2, and definitely redouble at 2-to-1 (60-67%).
This thread has gotten rather involved, but I can see that there
are several previously published works which are being overlooked. First,
though:
I believe Jacoby/Crawford was the SECOND book published in the
modern era of backgammon. First was Obelinsky (sp?) and James around
1969. As such, although probably the best book ever written on BG at
the time of its release, it is today no more than an introduction.
The above quoted doubling points are, in general, way too low, IMHO.
I suggest the interested readers seek out the following studies:
1) Articles published in Management Science and also in Operations
Research (two scholarly journals) by Keeler and Spencer and by
Kobliska (and a co-author whose name I can't recall at the moment).
Both of these articles refer to GAMMONLESS games. Initially they
treat "continous" games (perfect cube efficiency) but then go on to
simulations of volatile, discontinuous cases--more like real BG.
2) Work by Danny Kleinman, starting with "Vision Laughs at Counting,
with Advice to the Dicelorn" (two volumes, esp. volume II, both
available from Carol Cole...@flint.org).
3) by far the most complete coverage of the money cube that I know
of has been done by Rick Janowski. His results--formulas for double,
redouble, beaver, drop/take, play on, etc. for Jacoby, non-Jacoby AND
all outcomes (simple games, gammons, and backgammons) were published in
three issues of Hoosier Backgammon Newsletter in 1993. Write Butch
Meese ( me...@worldnet.att.net ) if interested in obtaining those back
issues. As an example, the following is just one of the formulas (and
the only one I happen to have memorized) which applies to the money take
point (in percentage of wins):
L - 0.5
T = ---------------
W + L + 0.5x
where W = (s + 2g + 3b)/(s + g + b)
and s,g,b are simple, gammon, and backgammon win chances for the person
considering whether to drop/take. L is the similar expression for losses.
x is a cube efficiency factory which varies from 0 (dead cube) to 1
(perfectly efficient cube) and is typically set to somewhere between
0.6 and 0.7.
You should be able to quickly see that gammonless cubeless is 25% and
gammonless cubeful is 20%, both numbers being bandied about in this thread.
Janowski doesn't include the derivations (but it took 3 issues just to
describe and list the results!). I recommend his work to anyone serious
in delving into this complex topic.
Chuck
bo...@bigbang.astro.indiana.edu
c_ray on FIBS
Bruce McIntyre
Chuck Messenger wrote in message <347831...@servtech.com>...
>mat...@math.canterbury.ac.nz (Bill Taylor) wrote:
>
>>It seems a lot of folks might object somewhat to the great increase in
variance
>>the doubling cube introduces to backgammon, but still very much like the
idea
>>of something like a doubling cube. Or so it would appear from the
willingness
>>of many money players to settle before the last move or two.
>
>>On the other hand, a great many other games might become more interesting
>>if played with something like a doubling cube. Even, chess, othello,
etc,
>>could be interesting, if played for money, or as part of a long series.
(The
>>world chess champs might be interesting if so played!) Indeed, poker
played
>>with a pot-doubling limit is effectively nothing *but* show poker with a
>>doubling cube! A cute thought. As far as I know, it has never
>>seriously been suggested for games of pure skill that a doubling device
might
>>be used, but I don't see why not. It still introduces an extra element of
>>skill, as in BG:- i.e. judgement on whether one is winning or not, as
opposed
>>to merely playing on as best one may. This alone is worth a debate.
Off the topic a bit, but I would love to see a doubling cube in professional
snooker. You could call a frame a "gammon" if one player scores 100 or
more, and a "backgammon" if a player shuts out his opponent. Allow a player
to double at the beginning of his turn but not on the break-off. Use the
Crawford and Jacoby rules. Currently in a televised snooker-match
highlights package there are several "century" breaks which are impressive,
but a little boring to watch. The doubling cube and Jacoby rule would end
many of these before they had a chance to begin, and repeated doubles and
redoubles in close frames where defensive play is highlighted would occur
more often and be rewarded more richly. Right now if it's an hour long
program and one guy's up 8 frames to 3 in a match to 11 with fifteen minutes
to go, the result is known. But if you can win an unlimited number of
points in a frame...who knows!
On another off-topic line, a friend and I used a doubling cube-like rule in
an NFL football bet several years ago. We'd pick teams against the point
spread for a dollar a game, but instead of picking a team, you had the
option of doubling the stake in all of the games where you had picked teams,
plus any of the other guys teams you wanted. The non-doubler could then
redouble instead of picking a team later on and would have to double or
redouble all of the teams he had picked, plus any of the other guys teams
that had been doubled his way. We found that this usually created several
games worth $1-2, and a few $4, and occasionally an $8 or $16 game. Oddly
enough, we discovered that the first doubler usually lost, but we were
uncertain as to whether this was coincidence or not. (I was up over $100
before the last week but lost big in the last week to be down about $10. We
haven't tried this since.)
--Bruce McIntyre
Don Woods
Chuck Messenger <c...@servtech.com> writes:
> > His chances are 22% CUBELESS (so I assume with some certainty), this
> > doesn't mean it is a drop. He can gain additional equity with redoubles,
> > which puts his equity WITH CUBE above 25%.
>
> out the accept-the-double decision from the model, after
> all, if there is redoubling. That would mean there were
> 6 variables (each player with 3 decisions: when to double,
> when to accept, and when to redouble). Could still be
> done, but searching for a global optimum would take alot
> more doing...
>
> One quick simulation later, I find that a 101 square
> board with a 20-sided die yields an average game length
> of 30 turns. The accuracy of this model would be close
> to 1% per bin, vs. more like 5% per bin with the current
> model.
I'm not sure I see the point of requiring that the game be about
30 turns (your estimate of the length of a backgammon game). If
the idea is that a game has about "30 turns worth" of opportunities
for the lead to swing back and forth, you still aren't anywhere
close to modelling what's really happening in backgammon. For
starters, in tug-o-dice there's only one position where the first
player is 49% to win (cubeless), i.e. position 13. And from that
position there is ALWAYS an average of 30-35 turns left in the game.
Whereas in backgammon (or most other board games where positions
evolve over time) there are lots of different positions where the
player on roll is N% to win for any given N. And -- to get back on
topic -- the question of whether he should double, AND whether the
other player should accept, depends a lot on "how much game is left".
I.e., if the current roll is guaranteed to decide the game (a so-called
dead cube), then it is right to double even at (say) 52% odds, and it
is wrong to accept at worse than 25%. But earlier in the game it's
wrong to double at 52% because the other player gains too much by
having the cube for an extended period.
This doesn't mean that tug-o-dice isn't a useful model to study, but
it'll be hard to generalise from the results unless someone can give
a way of measuring "how dead the cube is" at the various positions.
From other posts in this thread, it sounds like there are lengthy
papers or even books on the topic. I saw one formula posted that
included a variable for "cube liveness", ranging from 0 to 1, but I
haven't really seen a way of evaluating that factor from a position.
(Well, other than computing the double/take points and using the
formula to backwards evaluate to obtain the cube-life factor!)
Incidentally, you might be able to generate results more efficiently
if you do it in closed form rather than running millions of trial
games. E.g., 21-position cubeless tug-o-dice solves exactly to the
following winning chances for the lefthand player when he is on roll:
1.00000000000000
0.982589078078851
0.958273788065857
0.92637604048044
0.886410327324467
0.838111010122393
0.781446566766625
0.734031826772428
0.68530531545864
0.635929279940424
0.586400581664826
0.536966468589429
0.487642698621792
0.438250807960698
0.388953971492077
0.339986660134605
0.289795903212444
0.239794278935837
0.191386485512501
0.145891740077965
0.104465531526895
These were obtained by generating equations giving the chance of winning
as a function of the position resulting after each possible roll. E.g.,
from position 8 you can reach positions 2-7 with probability 1/6 each,
and the left player's chances from those positions are 1 minus the right
player's chances from 15-20. Set up 21 equations in 21 unknowns and
solve!
Adding double/redouble/take strategies would up the number of variables
by adding the state of the cube, but it's still tractible. Plus there's
enough structure to the problem that I'm sure it can be analysed by more
sophisticated means, too.
Wei-Hwa Huang
Uh, of course there is. One does it so that one can emulate that
perfect player.
There's no point in playing a pure-skill game with a perfect player if
that's the only player you'll ever play that game with.
--
Wei-Hwa Huang, whu...@ugcs.caltech.edu, http://www.ugcs.caltech.edu/~whuang/
---------------------------------------------------------------------------
"[Lucy's eyes] look like little round dots of India ink..." -- Charlie Brown
Chuck Messenger
Gary Wong wrote:
> The 25% drop point is convenient, but it's not the end of the story. It
> doesn't take into account match score, recube vig, gammons and the Jacoby
> rule, volatility, relative skill... even if you could quantify all of those,
> you'd be way beyond just 2 or 4 variables! Understanding which factors are
> important and how they should influence your decision is far better IMHO than
> being able to (analytically or empirically) derive the take/drop point for
> a single artificial position without being able to extrapolate from there
> for any practical use. On the other hand, there's a lot to be said for a
> simple approximation if it gives you more insight. So here's what I think:
>
> - Dropping at 25% for money is reasonable, but ignores the recube vig you'd
> gain if you took the cube. A slightly better analysis by E. Keeler and
> J. Spencer ("Optimal Doubling in Backgammon", Operations Research, Vol. 23,
> No. 6) which takes redoubles but not volatility into account, shows that
> the theoretical break-even point under those conditions is 20%.
> Tug-o-Dice is a somewhat better model to backgammon than theirs because
> it's a discrete stochastic game instead of their imaginary smooth
> continuous game. But applying Tug-o-Dice results to backgammon should
> still be taken with a grain of salt, unless you take care to ensure that
> the volatility between the games and positions is comparable.
Gary: Thanks for the incredibly in-depth post on doubling theory in
backgammon -- very interesting reading!
Just for a bit of background on Tug-o-Dice, my goal is really to
understand the doubling mechanism, not specifically for backgammon,
but as applied in general to any game. Of course, the only game
I'm aware of in which the doubling mechanism is conventionally
used is backgammon (which I'm only a beginner at, so please excuse
my ignorance in backgammon terminology). It seems to me that most
of what has been learned about doubling in backgammon is generally
applicable, though -- the only thing which is backgammon-specific
is the gammon factor (and this could be made to be a factor in
other games, too).
When you say "recube vig", I assume you mean the added advantage
you get in holding the cube.
I wonder how redoubling affects the percentages? How important
is redoubling in backgammon? On the face of it, it seems that
it shouldn't be a big factor during optimal play -- why would
one side ever double in a case where a redouble would be a
possibility? Is the value of holding the cube (the recube vig)
so great that it can account for a swing from a 20-30% win
chance (which is what you'll have if you're doubled), up to a
70-80% win chance (which is what you want in order to double)?
Or perhaps, all that's needed in the case of redoubling is to
bring your win chance up to > 50%. Perhaps the recube vig can
sometimes be enough to make up a swing from 30% to 50%...
> - When to double (as opposed to when to drop) is more interesting, because
> the volatility of the position comes into play. Although the 20% money
> drop point is superficially equivalent for any position, in any game
> (backgammon, Tug-o-Dice, or whatever), the optimal point at which to
> double will vary. The important things to understand are the disadvantages
> of doubling early vs. late: if you wait too long before doubling (ie. you
> lose your market), then you'll only win a single game instead of having
> good chances of winning a doubled game. If your opponent's drop point is
> 20%, then doubling at 79% winning chances gives you an expected gain of
> 1.16 points; doubling at 81% and having them drop gives you only 1 point.
> That's the cost of doubling late. On the other hand, if you double early,
> you run more risk of the game going your opponent's way and them using it
> against you (wishing you hadn't doubled after all), and lose the ability
> to cube later. If you _re_double early, it's even worse, because you give
> your opponent the opportunity to double which they wouldn't have had
> otherwise (which is why positions exist that are initial doubles, but not
> redoubles).
The doubling logic all makes good sense, but I'm a bit confused
about redoubling. I thought that you can only redouble at the
point where you accept the double, and that after the redouble,
you keep doubling privilege. If so, what does it mean to redouble
early? Sorry about my ignorance...
> So here are two rules of thumb:
>
> + it's better to double slightly early than slightly late (79% is better
> than 81%)
> + it's better not to double early if you can help it; the only reason you
> should double this turn (as opposed to next turn) is if there's a chance
> that your opponent might take the cube this turn, but drop it next turn.
And, I suppose, in backgammon, you're particularly shy of
doubling, because you always have the hope of a gammon.
> Can we derive a theoretical doubling point from what we know, in the same
> way we derived the 20% take point? Unfortunately it doesn't look like it;
> it's hard to quantify a position's volatility against the early/late
> costs. I'll argue that the cost of losing your market (doubling late)
> ranges linearly from zero at your opponent's take point to 1 point (at
> the current cube value) at 100% winning chances.
Except that this cost is mitigated somewhat by the chance that
you'll get a gammon.
> On the other hand, the
> cost of doubling early is 1 point for every game your opponent wins that
> they WOULDN'T have won if you'd waited until their drop point; ie. if you
> double 5% early, then the cost is 0.05 points. (Note that I haven't
> considered the extra cost of _re_doubling early here -- the recube vig
> would then come into consideration).
The cost would really be TWICE that, right? After all, say
the cube is at 1, and you double 5% early. That means the
point value has gone up to 2, and you're going to lose 5%
more of those doubled games than you would have if you
waited.
It seems to me its a bit more complicated than this. The
reason is we need to account for the recube vig (I hope
I'm using this expression right). Let's say, for the sake
of argument, that the recube vig is worth 5% win chances.
Then the very act of doubling reduces our chances of
winning by 5%. Also, even if we miss, our win % is higher
than 50%, since we have the doubling privilege -- it's
more like 55%. It all gets very complicated, but I do
see your basic point. I'll have to think about it some
more...
> Note that we saw here a position with 63.7% winning chances that was a
> double, and another with 56.8% chances that was not. Does that imply that
> there's some magic figure between 56.8 and 63.7 that separates doubles from
> no-doubles? No. In a fairly non-volatile position (eg. a long race),
> 63.7% is not generally good enough to double. On the other hand, the most
> volatile position you can get is the last roll of the game: if I have one
> chequer on each of my 5 and 2 points, and you have one on each of your 2
> and 1 points, then this is a double/take even though I only have 52.7%
> winning chances. There is no imaginary doubling point in the same sense
> that there is a take point; it depends on the volatility of the position.
Indeed, just as the optimal double point drops as the game
nears the end (higher volatility), the optimal take point
increases, from 20% toward 25%. Basically, this behavior
is based on the value of the doubling privilege, which is
high when the game has a long way to go, and is zero at the
end of the game.
> So the conclusion is: all other things being equal, the take point in a money
> game is 20%. There is no fixed double point; it depends not only on the
> winning chances but the volatility. The closest you can get is to calculate
> the cost of doubling late vs. the cost of doubling early; if the cost of
> doubling late is higher, then it is correct to double now.
I'd ammend that a bit, to say that, generally, the optimal double
point in any "long" game is around 75%, while the optimal take
point is around 20% (the exact numbers are debatable, but can be
analyzed reasonably with Tug-o-Dice; whatever they are, they're
generally applicable to any game. Also, the numbers are modified
by specifics of a particular game, like gammon in backgammon).
However, as the game nears the end, or nears a particular crisis
point where the win %'s might change dramatically, the value of
having the doubling privilege is reduced, which means the optimal
double point is reduced (toward a limit of 50%), while the optimal
take point is increased (toward a limit of 25%).
Actually, I see right away that this isn't right. Here's an
experiment I can do with Tug-o-Dice: test to see what happens
if we eliminate the recube vig -- in other words, there can
only be a single double during the course of the game (it's
decided randomly at the start who gets the double privilege).
This would then give us the optimal cubeless double point.
> All of this discussion has glossed over several important issues (which are
> complicated enough that people have written entire books about them). For
> instance: how good does your position to be to play on for a gammon,
> instead of claiming with the cube? Answer: you need to expect twice as
> many gammons as losses (proof is an exercise for the reader). How does the
> match score affect cube handling? Tom Keith has written an excellent
> article at http://www.bkgm.com/articles/mpd.html ("Match Play Doubling
> Strategy") that explains what factors influence the game. How does the
> relative skill of the players affect the cube? Read "Can A Fish Taste
> Twice As Good" (Jake Jacobs and Walter Trice).
Well, you've given me some good food for thought. If I do
more Tug-o-Dice stuff, perhaps I'll analyze the cubeless
situation, to get a rough answer to the question -- how many
win % points is the cube worth? Then I might analyze the
effects of expected game length (the shorter the game, the
lower the optimal double point, no doubt).
- Chuck Messenger
Gerry Quinn
>
>That's besides the point. The point is that since perfect play
>leads to absolutely predisposed equity values, there is no
>justification for doubling. Just because humans are foolish
>mortals who don't have perfect game-playing vision, doesn't
>mean that use of the doubling cube is justifiable.
[snip]
>
>No it isn't, because I'm assuming that the opponent is also a
>perfect player, in which case he will instantly drop. There is
>thus no possibility of a perfect player playing another perfect
>player to increase his equity by using the doubling cube, compared
>to not using it. So why use it in pure skill games?
>
Because they are not played by perfect players.
- Gerry
===========================================================
ger...@indigo.ie (Gerry Quinn)
http://indigo.ie/~gerryq
Original puzzlers for PC, Amiga, and Java
===========================================================
Gary Wong
Chuck Messenger <c...@servtech.com> writes:
> Just for a bit of background on Tug-o-Dice, my goal is really to
> understand the doubling mechanism, not specifically for backgammon,
> but as applied in general to any game. Of course, the only game
> I'm aware of in which the doubling mechanism is conventionally
> used is backgammon (which I'm only a beginner at, so please excuse
> my ignorance in backgammon terminology). It seems to me that most
> of what has been learned about doubling in backgammon is generally
> applicable, though -- the only thing which is backgammon-specific
> is the gammon factor (and this could be made to be a factor in
> other games, too).
>
> When you say "recube vig", I assume you mean the added advantage
> you get in holding the cube.
Yes, that's right. To be a bit more precise you could define recube
vigorish in terms of points, which would be "the difference in the points
this player expects to win with and without access to the cube". If you're
right on the take/drop point with 80% winning chances, you expect to lose
0.8 - 0.2 = 0.6 points with no cube, but assuming perfectly efficient
redoubles we're saying you break even (against dropping) here and so only
lose 0.5 points holding the cube. Your recube vig is the difference: 0.1
points (which is basically the same equity as 5% winning chances without
gammons).
> Is the value of holding the cube (the recube vig)
> so great that it can account for a swing from a 20-30% win
> chance (which is what you'll have if you're doubled), up to a
> 70-80% win chance (which is what you want in order to double)?
> Or perhaps, all that's needed in the case of redoubling is to
> bring your win chance up to > 50%. Perhaps the recube vig can
> sometimes be enough to make up a swing from 30% to 50%...
>
> The doubling logic all makes good sense, but I'm a bit confused
> about redoubling. I thought that you can only redouble at the
> point where you accept the double, and that after the redouble,
> you keep doubling privilege. If so, what does it mean to redouble
> early? Sorry about my ignorance...
I think we're just not quite talking about the same thing. By "redouble", I
mean doubling when the cube has already been turned (ie. the second or
subsequent double in a game). I would call a "redouble at the point where
you accept the double" a `beaver' to make the distinction clear, but
admittedly `redouble' could conceivably mean either, depending on the context.
So to clarify: no, the recube vig should never be enough to account for
enormous swings in equity -- generally no position is a correct double and
a correct beaver (except for complications with gammons and the Jacoby rule).
You're also right that in the case of redoubling (in the beaver sense), you
only need 50% winning chances holding the cube -- in which case your opponent
was wrong to double.
> > So here are two rules of thumb:
> >
> > + it's better to double slightly early than slightly late (79% is better
> > than 81%)
> > + it's better not to double early if you can help it; the only reason you
> > should double this turn (as opposed to next turn) is if there's a chance
> > that your opponent might take the cube this turn, but drop it next turn.
>
> And, I suppose, in backgammon, you're particularly shy of
> doubling, because you always have the hope of a gammon.
Quite right, though typically you need fairly strong gammon chances to play on
instead of claiming immediately. If I have 50% chances of winning a single
game, 30% chances of winning a gammon, and 20% chances of losing a single game,
then it would be a clear drop for my opponent, but still correct for me to
claim now: with a double/drop, I win 1 point immediately; if I play to
conclusion I only expect to win 0.9 points. And in many positions (high
anchor holding games and races) the gammon chances are small to negligible.
> > On the other hand, the
> > cost of doubling early is 1 point for every game your opponent wins that
> > they WOULDN'T have won if you'd waited until their drop point; ie. if you
> > double 5% early, then the cost is 0.05 points. (Note that I haven't
> > considered the extra cost of _re_doubling early here -- the recube vig
> > would then come into consideration).
>
> The cost would really be TWICE that, right? After all, say
> the cube is at 1, and you double 5% early. That means the
> point value has gone up to 2, and you're going to lose 5%
> more of those doubled games than you would have if you
> waited.
Hmmm. In the terms of my original post I would argue that the cost is not
twice that (they would win that proportion of games with a 1 cube regardless;
but having doubled, you've let them win with a 2 cube for a difference of 1
point -- the _old_ cube value). But it's not entirely clear whether the
winning chances should be doubled to convert to points (losing 5% more games
means you lose 0.05 points because you're missing out on the wins, and the
opponent gains 0.05 points for a total difference of 0.1). So I think you're
right that the cost should be doubled -- whichever reason you prefer is six
of one, half a dozen of the other (there's 2 factors of 2 and one of 1/2 in
there :-) But since then I've thought of an explanation I prefer anyway:
Consider the benefit of having access to the cube for various winning chances.
Let's neglect gammons and assume a perfectly live cube (hence 20% take/drop
point) for simplicity. At 0% or 100% winning chances, the cube is obviously
worthless to both players (they could either double/drop for a win/loss of the
cube value, or play the game to conclusion for the same thing). But at 80%
winning chances (which we've assumed to be the break-even take/drop point),
the cube is worth 0.4 points to the leading player, and 0.1 to the trailer.
How can we show this? Well, without cube access, the player at 80% would
expect to win 0.6 points (0.8 for 80% wins, less 0.2 for 20% losses). But
with the cube, they could claim 1.0 points since it's a borderline drop. The
difference (1.0 - 0.6 = 0.4) is the value of the cube to them.
If the trailing player takes the cube, we're assuming they end up expecting
to lose 1.0 points with the new cube, ie. 0.5 at the old. However, before
taking the cube, we demonstrated that they expected to lose 0.6 points
(0.8 - 0.2). So the value of owning the cube to the trailing player is 0.1
points.
So the value of owning the cube is 0 points at 0%; 0.1 at 20%; up to a maximum
of 0.4 at 80%; down to 0 again at 100%. It's fairly easy to see that you can
interpolate linearly between 80% and 100% (your opponent has a drop in every
case; so the value of the cube is simply the difference between your equity
without it and 1.0) and I assert that you can similarly interpolate between
0% and 80%. So the value looks like this:
VALUE OF ACCESS TO THE CUBE FOR VARIOUS WINNING CHANCES
assuming a perfectly live cube in a gammonless game
Cube owning
equity
0.5 +
|
0.4 + - - - - - - - - - - - - - - - - - - -,* - - - - -
| _,-`~ |\
0.3 + _,-`~ `,
| _,-`~ | \
0.2 + _,-`~ \
| _,-`~ | \
0.1 + _,*`~ `,
| _,-`~ | \
0.0 *----+----+----+----+----+----+----+----+----+----*
| | | | |
0 10 20 30 40 50 60 70 80 90 100% Winning chances
| | | | |
-1 -0.6 0 0.6 1 Cubeless equity
NB: below your take point, the cube is worth nothing to you if your opponent
also has cube access, because you can expect to be cubed out immediately.
You want to maximise the sum of the cubeless equity + cube owning equity.
As examples of how to calculate these: at the start of the game, you have
50/50 winning chances for 0 cubeless equity; and the centred cube is worth
0.25 points to you minus 0.25 points to your opponent (since you both have
access) for a total sum of 0 (as you would expect). If you own a 2-cube with
30% winning chances, your cubeless equity in the game is 0.3 - 0.7 = -0.4;
your opponent has no cube owning equity at all and you have 0.15, for a total
equity of -0.25 -- which, at a 2-cube, leaves you expecting to lose on average
half a point per game.
So, how does this help you to decide whether a position is a double or not?
Calculate the total equities after the next exchange, once assuming you double
now, and once assuming you don't. If your equity assuming you double is
higher than your equity assuming you don't, you should double now. Fair
enough?
Take the example position from my last post (tweaked slightly to give the same
answer as before now we're raising the cost of doubling early :-) -- O is on
roll, and has 14 market losers that take her to 95% winning chances, and 22
misses that give an race with 55% chances. The cube is centred. Since X
can expect pretty efficient recubes (the game is likely to be a long race),
we assume his take point is 20%, and given that X has only 67.5% winning
chances, it's a clear take. The question is: is it a double?
+13-14-15-16-17-18-------19-20-21-22-23-24-+
| O X | | X X X X X X |
| X | | X X X X X X |
| | | |
| | | |
| | | |
v| |BAR| | O on roll, 1 cube, money game.
| | | |
| | | |
| | | O |
| | | O O O O O O |
| X O | | O O O O O O |
+12-11-10--9--8--7--------6--5--4--3--2--1-+
If O does not double, her equity after this exchange is:
hits 14/36 of the time for 95% winning chances
= 0.9 cubeless equity; the cube is centred and
worth 0.1 points to her and nothing to X
(see note above) for total equity of 1.0.
1.0 x 14/36 = 0.389
misses 22/36 of the time for 55% winning chances
= 0.1 cubeless equity; the cube is still centred
and worth 0.275 points to O and 0.225 to X for
0.05 overall; total equity 0.15.
0.15 x 22/36 = 0.092
-----
0.481
which is worth 0.481 cubeless equity at a 1-cube for 0.481 points.
If O doubles now:
hits 14/36 of the time for 95% winning chances
= 0.9 cubeless equity; X owns the cube which
is worth 0.05 points to him for total equity of
0.85.
0.85 x 14/36 = 0.331
misses 25/36 of the time for 55% winning chances
= 0.1 cubeless equity; X owns the cube which
is worth 0.225 points to him for total equity of
-0.125.
-0.125 x 22/36 = -0.076
------
0.255
and 0.255 cubeless equity at a 2-cube is 0.510 points.
0.510 is more than 0.481, so it is correct to double now. By comparison, if
O was holding the cube (as opposed to it being centred), her equity holding
on to it would be:
hits 14/36 of the time for 95% winning chances
= 0.9 cubeless equity; the cube is worth 0.1 points
to her for total equity of 1.0.
1.0 x 14/36 = 0.389
misses 22/36 of the time for 55% winning chances
= 0.1 cubeless equity; she owns the cube which is
worth 0.275 points to her for total equity 0.375.
0.375 x 22/36 = 0.229
-----
0.618
This is more equity than she has with X holding the cube at twice its
current value; so she should hold on to the cube if she owns it. The
position is therefore an initial double, but not a redouble.
> > O has 11 rolls that hit and lose her market, and 25 rolls that miss for an
> > even race, which gives her 63.7% winning chances. X has 36.3% chances which
> > make it an easy take on our 20% theoretical criteria. Is this a double?
> > The cost of O losing her market is 11/36 x 0.75 (because 95% winning chances
> > are 3/4 of the way past X's take point) = 0.229 points; the cost of her
> > doubling early is 25/36 x 0.3 (because if she misses she's 30% short of her
> > opponent's take point) = 0.208 points, so by the criteria above it's
> > a narrow double/clear take. If O only had 40% chances in the race, then her
> > winning chances would be 56.8%; the cost of doubling late would remain at
> > 0.229; but the cost of her doubling early would be 25/36 x 0.4 = 0.278, and it
> > would be a no double/take.
>
> It seems to me its a bit more complicated than this. The
> reason is we need to account for the recube vig (I hope
> I'm using this expression right). Let's say, for the sake
> of argument, that the recube vig is worth 5% win chances.
> Then the very act of doubling reduces our chances of
> winning by 5%. Also, even if we miss, our win % is higher
> than 50%, since we have the doubling privilege -- it's
> more like 55%. It all gets very complicated, but I do
> see your basic point. I'll have to think about it some
> more...
Yes, that's quite true. The cost of doubling early should really be increased
a little to account for the fact that X's winning chances are higher owning
the cube. The recube vig was considered in the second attempt above, if that's
any consolation :-)
> Well, you've given me some good food for thought. If I do
> more Tug-o-Dice stuff, perhaps I'll analyze the cubeless
> situation, to get a rough answer to the question -- how many
> win % points is the cube worth? Then I might analyze the
> effects of expected game length (the shorter the game, the
> lower the optimal double point, no doubt).
I would argue that at the start of the game (ie. 50/50 chances), the player
owning the cube would expect to win 0.25 points (see the graph above). This
is the same number of points they'd expect to win in a cubeless game with
62.5% winning chances, but that doesn't necessarily mean they win 62.5% of the
games; part of the equity comes from the fact that more of their wins will
be doubled than their opponent's. It would be very interesting to see how
this theoretical figure compares to empirical data (whether backgammon or
Tug-o-Dice). In practice I would expect the cube owning equity to be a
little lower to reflect the fact that the player will not always be able to
make efficient doubles.
Cheers,
Gary.
n...@usa.0
I just lately reviewed the thread on doubling theory, and wanted to
add a few words to the discussion. I, too, have thought about
doubling strategy, not necessarily related to backgammon (I have
heard that it has become popular playing golf for money - either
player can double the wager on a hole at any time, after which
only the other player can make the second double, and so on).
I have used an even simpler example than dice to extract some of
the basic principles. I wanted an example where the probabilities
remain obvious to the players, at all times, something easily
accomplished with just a single coin. Start with a score of 50,
and flip a coin. If the coin comes up heads, add one to the score,
and subtract one if the coin lands tails. Player A wins if the
score reaches 100 (before 0), and player B wins if the score
reaches 0 (before 100). The current score (divided by 100) exactly
represents the probability of A winning the game. Obviously we can
make the probability function as fine as necessary (start with a
score of 500, and proceed to 1000 or 0, and so on).
A few observations:
1. If you double before you become a 2/3 favorite (for example,
you double once your score reaches 66), your expected loss, even
for a single game (assuming optimal play by your opponent), is
infinite (don't talk to me about collecting from your opponent if
he adopts this strategy). To convince yourself of this, compare
the distance from 66 to 100 to the distance from 66 to 33 (where
your opponent should redouble), and realize that you will more
likely encounter the redouble than win the game. Thus the series
of payouts for concluded games never converges.
2. As a direct corollary, your optimum strategy depends upon your
opponent. I will leave the computation of the exact results to the
math professors (or Dave Dejardins), but assuming you have a
consistent opponent (it would seem bizarre and irrational, though
not impossible, to double at different probabilities, perhaps
using some random function), and excluding the degenerate case
described above, you maximize your gain by doubling at a slightly
higher probability than your opponent (if he has the same, or
sufficiently close, double and take points - otherwise, with a
much higher take point than double point, you wait until reaching
his take point to double).
As a quick example, if your opponent has decided on .75/.78
strategy (double when his winning chances reach 75% and take
if your winning chances don't exceed 78%), you maximize by
doubling just BEYOND .78, winning .0924 versus .0822 by doubling
at .78. On the other hand, if your opponent chooses .75/.79, now
you double AT .79 (you do better by having him take - winning
.1046 versus .0687 by cubing him out at .790001).
To belabor this point one more time, if your opponent has set his
drop point too low, you want to double just beyond it so that he
drops, and facing a drop point above the ideal level, you want him
to accept your doubles, and therefore double at the last possible
take condition. Clearly, the optimal drop point should equate the
expected value of accepting with the expected value of dropping.
3. Don't ask me how to apply any of this at the table, except that
if both players pursue the optimum strategy (this assumes, of
course, volatility as small as necessary for cube efficiency,
ignoring gammons, backgammons, match scores, and other realities),
then as stated previously in other posts, both players will double
as soon as they become 80% favorites, equating the expected value
of the take/drop decision for their opponents.
I have attached a spreadsheet (old style .wk1 - which any program
can read) that computes the expected gains given two different
doubling and take points, so interested readers can actually
analyze the inferiority of suboptimal strategies. It only sums
results from the first hundred doubles (if both players double at
or below each others take point - otherwise you will never see
more than two doubles), so the cases that converge slowly or don't
converge will not produce meaningful answers (you can always add
lines if you desire additional accuracy in those situations).
Tom
Chuck Bower
In article <675372$9...@bgtnsc01.worldnet.att.net>, <net@usa.0> wrote:
>...if your opponent has set his
>drop point too low, you want to double just beyond it so that he
>drops, and facing a drop point above the ideal level, you want him
>to accept your doubles, and therefore double at the last possible
>take condition. Clearly, the optimal drop point should equate the
>expected value of accepting with the expected value of dropping.
One of my (many?) theories about backgammon writing is: Whenever
I feel I've come up with something clever or worthwhile, I find that
Danny Kleinman already had the idea (and wrote it up) ten or more
years previously. And now I see I'm not the only person cursed by
this. The above (and a lot more) can be found in "Vision Laughs at
Counting, With Advice to the Dicelorn".
Tom
Chuck Bower wrote:
>
> One of my (many?) theories about backgammon writing is: Whenever
> I feel I've come up with something clever or worthwhile, I find that
> Danny Kleinman already had the idea (and wrote it up) ten or more
> years previously. And now I see I'm not the only person cursed by
> this. The above (and a lot more) can be found in "Vision Laughs at
> Counting, With Advice to the Dicelorn".
Actually, I didn't consider that either new or clever. The main points,
observable here, but relevant (and known) to backgammon:
1. Not having the ability to double at the optimal time lowers your
take point.
2. Try to learn your opponents' weaknesses and exploit them (this
applies everywhere).
3. The optimal take point equates the value of accepting and dropping
(I thought everyone learned this as a basic principle of backgammon).
I felt it worthwhile to actually attach numbers to some of these
principles. The fact that you can earn about .1 per game if you can
double at .78 or .79 while your opponent doubles at .75 seems quite
striking to me.
Tom
Bill Taylor
OK then, having started it, it's my turn to contribute to this thread.
About the matter of using a doubling cube with other games, I'm sure
it's a goer, for money games or long-match games. The arguments against,
for complete-info games of no chance, (chess etc), struck me as very weak.
Incidentally, I agree that for CI-NC games that are actually *played*,
i.e. for which perfect strategies are as yet unknown, there IS luck in
them, in any reasonable sense of the term. A chess master pal of mine
from long ago, summed it up well, even profoundly - "In chess there is no
such thing as BAD luck, but there IS good luck". Rather neat, I thought.
I was particularly struck by the suggestion that a doubling cube be used
for snooker matches, especially on telly - that it would reduce those long
boring near-certain results, and also keep the likely outcome secret
from the program-time-aware viewer. :) Also, snooker is quite a high
volatility game, which would make it a natural for a doubling cube.
-----------
However, all that aside, what I really want to talk about here is the
UNDER-doubling part of the thread, for backgammon-style games.
Underdoubling OR OVER-doubling, of course! A tripling cube might
well be an amusement, especially for the keen gambler.
There's not much in here except a pretty picture, (pretty crumby picture?),
except that I look at the general M-multiplying cube. So standardly, M=2.
Like others, I *only* look at the very sub-backgammon-like situation
where there is ZERO VOLATILITY. This is like the tug-o-dice game, only
more so. We model the game as a diffusion, with a variable moving between
0 and 1, this being the cubeless P(WIN) for one player. This variable
starts at 0.5, and drifts continuously to and fro on the [0,1] interval,
with equal chances of drifting left or right, until an end-point is hit,
or a cube is dropped. So in effect, moves are infinitesimally small
increments in a 2-way race. This continuous movement, or zero volatility,
is a very poor model indeed of real backgammon, as it removes most of the
key everyday cubely problems. But we have to start somewhere.
With a doubling cube, it is well-known that one should double, and also
either-take-or-drop, when your P(WIN) gets to 0.8
Now we look at the M-cube situation.
Here are two graphs of the player's game equity, as a function of that
cubeless win-probability variable; WITH the cube, (above, graph "f"),
and AGAINST the cube, (below, graph "e").
It is 180-symmetric about the (.5 , 0) point, of course.
| :
| :
1 |- - - - - - -:- -*- -
| /. /:
| f / . / :
| / ./ :
| / / :
| / /. :
| b / / . :
0 -+------/-+-/--:---:--- x = P(player wins) [cubeless]
| / / K :
| / / :
| / / :
| / / :
| / / e :
|/ / :
-1 *.../....:........:...
| : :
| :
0 0.5 1
K is the precise cubing point - and by non-volatility, the take point also.
If the cuber waits just a tad longer, it's a drop;
if he cubes just a tad sooner, it's a take.
"b" is the beaver point, incidentally - the moment you get positive
equity, with the cube. Note one might always beaver soundly even (!) with
P(cubeless win) < .5 .
It is a standard result following from the linearity of expectation,
that the graphs are straight lines; by symmetry between players they
must be 180-symmetric as stated; and the (0,-1) point is obvious.
That just leaves the slope (and/or intercepts) to calculate.
Clearly we have f(x) = 2x/K - 1 ; and e(x) = - f(1-x).
For K to be the cubing point we must have M.e(K) = 1 .
Thus 1/M = e(K) = - f(1-K) = 1 - 2(1-K)/K = 3 - 2/K . Therefore...
K = 2M/(3M - 1) .
~~~~~~~~~~~~~~~
Thus for the usual cube where M = 2, we get K = 0.8 , as stated.
For an under-doubling cube like a sesqui-cube, M = 1.5 , we get K = 6/7.
I found this somewhat counter-intuitive; I would have expected a cheaper
cube to give rise to a lot *more* cubing, not less! But the key is,
that *taking* is a lot cheaper, so more cubes will be taken, and thus
there is no need to make early cubes, as no "market losing" will apply
until much later. Strictly, the continuous game doesn't have market
losers, of course, but similar reasoning applies.
On the other hand, with an OVER-doubling cube, drops come much earlier,
so market losing is a real issue, and cubing must thus be done earlier.
For a tripling cube, M = 3, K = 0.75 ; not so very big a difference.
There is an even more intriguing matter though. Without analysing the
exact discrete probability process for a game of many tiny increments,
let us assume that both players play a tactic of cubing just BEFORE the
point K, rather than just after. [Just after, would be very boring - it
means there will only ever be one cube turn, always dropped, no game never
gets fully played out! Bunny stuff! ;-) ] But with market-loss
anxiety, as it were, the cube will always be turned just before the K
point, and thus always taken.
What now? The game is more interesting - it flows to and fro between
the K and (1-K) points, being recubed (and taken) at each swing, till
it eventualy goes well on past one, and ends the game at 0 or 1.
What is the expected number of cubings till the game finishes?
P(hit on cube point | hit at other)
= P(reach K before 0 | a diffusion on [0,K] starting at (1-K) )
= (1-K)/K (a standard result from Markov chain theory, easily
proved using constant expectation from zero drift)
= (M-1)/(2M)
= p say.
Then the number of cubings is a geometric random variable with
p_1 = (1-p) (p_0 = 0 as it must get to one of the K-points first),
p_2 = (1-p)p
p_3 = (1-p)p^2 etc. So the expected number of cubings is 1/(1-p).
For the standard M = 2; K = 0.8 , p = 1/4, E[#] = 4/3.
Even with a tripling cube we get E[#] = 1.5 . Not very exciting?
HOWEVER! There is a BIIIIIIG surprise!
The key thing is, not the expected number of cubings, but the expected
size of the final stake. For this we get...
# cubings: 1 2 3 4 ... . .
probability: (1-p) (1-p)p (1-p)p^2 (1-p)p^3 ... . .
final stake: M M^2 M^3 M^4 ... . .
So E[final_stake] = sum[0:inf] {M(1-p)(Mp)^k}
= M(1-p)/(1-Mp)
= (M+1)/(3-M)
For the usual M = 2, E[f_s] = 3; moderate.
For the tame M = 1.5 E[f_s] = 1.67, tame indeed, (as 1.5 = min payout!)
But for the mild-seeming TRIPLING cube, E[f_s] = infinite !!
~~~~~~~~~~~~~~~~~
With a tripling cube, you are already, unbeknownst, playing a StPetersburg
style game of infinite expectation, (though "only just").
And with a QUADRUPLING cube, ("automatic compulsory beavers"),
you're completely in outer space!!
Food for thought!
-------------------------------------------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
-------------------------------------------------------------------------------
LOSE MONEY FAST !
===============
Buy our sub-annuity. Send $1000 to the above address,
and for a little while you will receive $10 every week in the post!
-------------------------------------------------------------------------------
Chuck Messenger
Bill Taylor wrote:
> Thus for the usual cube where M = 2, we get K = 0.8 , as stated.
>
> For an under-doubling cube like a sesqui-cube, M = 1.5 , we get K = 6/7.
>
> I found this somewhat counter-intuitive; I would have expected a cheaper
> cube to give rise to a lot *more* cubing, not less! But the key is,
> that *taking* is a lot cheaper, so more cubes will be taken, and thus
> there is no need to make early cubes, as no "market losing" will apply
> until much later. Strictly, the continuous game doesn't have market
> losers, of course, but similar reasoning applies.
>
> On the other hand, with an OVER-doubling cube, drops come much earlier,
> so market losing is a real issue, and cubing must thus be done earlier.
>
> For a tripling cube, M = 3, K = 0.75 ; not so very big a difference.
I, too, had expected more doubling as a benefit of an under-doubling
cube. However, my Tug-o-Dice simulations set me straight.
An interesting question, then, becomes: can we design a doubling-
like mechanism which yields more frequent actions, and yet (unlike
the tripling mechanism) maintains a reasonable average per-game
point value?
In effect, I'm thinking of something like a stock market mechanism,
where the point value somehow provides a continuous "meter" of
the players' expectations of their win chances.
Just thinking out loud...
- Chuck Messenger
David Ullrich
Bill Taylor wrote:
[...]
> With a doubling cube, it is well-known that one should double, and also
> either-take-or-drop, when your P(WIN) gets to 0.8
It's "well-known" in some circles. What one "should" or
should not do depends on what one is trying to accomplish.
Presumably you mean that if one is trying to maximize one's
expected gain then one should use this strategy.
But before that makes any sense one needs to define
what this "expected gain" thing is. Precisely what is the
"expected gain" in a backgammon position?
What bothers me is that there's no a priori upper
bound on the length of the game. So if you try to define
the expected gain in a position by summing over all possible
futures, assuming the opponent makes the best play at each
point (and assuming that we can resolve the circularity
inherent in assuming that while we're still trying to
show that there _is_ a "best strategy") it's not at all
clear that the sums you get are convergent. At least it's
not clear to me. (If there were no cube it would be clear
the sums converge...)
--
David Ullrich
sig.txt not found
Ilias Kastanas
In article <349AC2...@math.okstate.edu>,
David Ullrich <ull...@math.okstate.edu> wrote:
>Bill Taylor wrote:
>[...]
>> With a doubling cube, it is well-known that one should double, and also
>> either-take-or-drop, when your P(WIN) gets to 0.8
>
>should not do depends on what one is trying to accomplish.
>Presumably you mean that if one is trying to maximize one's
>expected gain then one should use this strategy.
> But before that makes any sense one needs to define
>what this "expected gain" thing is. Precisely what is the
>"expected gain" in a backgammon position?
>
> What bothers me is that there's no a priori upper
>bound on the length of the game. So if you try to define
>the expected gain in a position by summing over all possible
>futures, assuming the opponent makes the best play at each
>point (and assuming that we can resolve the circularity
>inherent in assuming that while we're still trying to
>show that there _is_ a "best strategy") it's not at all
>clear that the sums you get are convergent. At least it's
>not clear to me. (If there were no cube it would be clear
>the sums converge...)
The symmetry argument itself for "least x in [0,1]: opponent might as
well resign when doubled" is simple. After doubling, "win" is still at 1
while "loss" is not at 0 but at 1-x... since the opponent will double
there. P(hit 1 before 1-x) / P(hit 1-x before 1) is thus x-(1-x) / 1-x;
and the outcome, 2*stakes*( 2x-1 /x - 1-x /x), should be = stakes,
the "resign" outcome. So 3x-2 = x/2, x = 4/5.
We are just _maintaining_ our expected gain (which is 0, of course).
Doubling at x - epsilon does not; the opponent would accept and come out
ahead. Not doubling at x + epsilon leaves the opponent in the game, again
to enjoy a windfall, the few runs that dip back to 0.
Well, is this simple approach justified? In backgammon circles
people usually don't mutter about sigma-fields or the strong Markov property.
But following Bill, an "idealized" model is a Wiener-Levy process B_t (Brow-
nian motion) starting at 1/2 and running until it hits 0 or 1. Then, hitting
times T_c = inf{t: B_t = c} for any c (or for any open or closed set) are
stopping times; s.M.p. holds; B_t is a martingale; and P_x( T_c < T_d) /
/ P_x( T_d < T_c) = d-x / x-c (c < x < d), the fact used above. Let my
doubling strategy be z (1/2 < z < 1), let hers be 1-z'; even if we accept
all doubles there is no convergence problem with expected values. Runs that
e.g. oscillate between z and 1-z' never hitting 0 or 1 are a set of
measure zero. They don't matter.
It can happen in real backgammon -- in theory; a never-ending game,
the advantage alternating back and forth. For that matter, a game can even
stall... the players keep on rolling the dice but neither one gets to move
a stone, ever. Again, it doesn't matter (unless if you are one of them).
A variant would be a 1-time doubling cube... for that, x_1 = 3/4.
The 2-time cube has x_2 = 13/16. (Warning, this is spur-of-the-moment).
It seems that for a k-time M_ing cube, x_i+1 = 1 - x_i(M-1 /2M), x_0 = 1.
As k -> inf this does yield x = 2M/ 3M-1.
Ilias
series. As usual,
Bill Taylor
Well David, if this had been any other author I'd'a just ignored it; but DU
always deserves a reply, and one of us seems to be missing something vital.
David Ullrich <ull...@math.okstate.edu> writes:
|> > With a doubling cube, it is well-known that one should double, and also
|> > either-take-or-drop, when your P(WIN) gets to 0.8
|>
|> It's "well-known" in some circles. What one "should" or
|> should not do depends on what one is trying to accomplish.
Natch.
|> Presumably you mean that if one is trying to maximize one's
|> expected gain then one should use this strategy.
Exactly.
|> But before that makes any sense one needs to define
|> what this "expected gain" thing is. Precisely what is the
|> "expected gain" in a backgammon position?
The expected payout to yourself, given that each adopts the strategy
mentioned in the context under inspection.
|> What bothers me is that there's no a priori upper
|> bound on the length of the game. So if you try to define
|> the expected gain in a position by summing over all possible
|> futures, assuming the opponent makes the best play at each
|> point (and assuming that we can resolve the circularity
|> inherent in assuming that while we're still trying to
|> show that there _is_ a "best strategy") it's not at all
|> clear that the sums you get are convergent.
OUCH! I'd hoped it was clear that that's what my post went to prove!
That is, for a less-than-tripling cube, that they were, & for a tripling or
more cube, they weren't. I seem to be missing something in your question.
|> So if you try to define
|> the expected gain in a position by summing over all possible
|> futures, assuming the opponent makes the best play at each
|> point (and assuming that we can resolve the circularity
|> inherent in assuming that while we're still trying to
|> show that there _is_ a "best strategy")
Quite, there is a circularity present, but that is true for all 2-player
zero-sum ganmes, almost by definition. The possibility of unbounded
payouts, as here, doesn't substantially interact with this, I think, in
spite of appearances. Whether or not the expectation exists, is the key.
|> it's not at all clear that the sums you get are convergent.
Again; I thought that was what had just been proved. Would anyone else
care to comment on this dilemma of communication between us?
-------------------------------------------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
-------------------------------------------------------------------------------
The most disturbing game-theoretic paradox isn't
"The Prisoner's Dilemma" but "The Double Payment Auction"!
-------------------------------------------------------------------------------
ull...@math.okstate.edu
Ilias Kastanas wrote:
>
> In article <349AC2...@math.okstate.edu>,
> David Ullrich <ull...@math.okstate.edu> wrote:
> >Bill Taylor wrote:
> >[...]
> >> either-take-or-drop, when your P(WIN) gets to 0.8
> >
> >should not do depends on what one is trying to accomplish.
> >expected gain then one should use this strategy.
> >what this "expected gain" thing is. Precisely what is the
> >"expected gain" in a backgammon position?
> >
> >bound on the length of the game. So if you try to define
> >the expected gain in a position by summing over all possible
> >futures, assuming the opponent makes the best play at each
> >point (and assuming that we can resolve the circularity
> >inherent in assuming that while we're still trying to
> >show that there _is_ a "best strategy") it's not at all
> >not clear to me. (If there were no cube it would be clear
> >the sums converge...)
>
assuming that there _is_ such a thing as the expected gain deleted]
>
> Well, is this simple approach justified? In backgammon circles
> people usually don't mutter about sigma-fields or the strong Markov property.
> But following Bill, an "idealized" model is a Wiener-Levy process B_t (Brow-
> nian motion) starting at 1/2 and running until it hits 0 or 1. Then, hitting
> times T_c = inf{t: B_t = c} for any c (or for any open or closed set) are
> stopping times; s.M.p. holds; B_t is a martingale; and P_x( T_c < T_d) /
> / P_x( T_d < T_c) = d-x / x-c (c < x < d), the fact used above. Let my
> doubling strategy be z (1/2 < z < 1), let hers be 1-z'; even if we accept
> all doubles there is no convergence problem with expected values. Runs that
> e.g. oscillate between z and 1-z' never hitting 0 or 1 are a set of
> measure zero. They don't matter.
I don't follow the "no convergence problem" bit. Yes, the runs
that oscilate infinitely often are a set of measure zero and hence don't
matter. So almost surely the game terminates, fine. No exactly how do we
define the expected gain? The fact that the game almost surely terminates
does not give a bound on the length of the game - exactly _how_ do you
know that the series is summable? The random variable WhoWins is defined
as, and the random variable HowMuch is defined as, fine. _How_ does it
follow that HowMuch has a well-defined expected value?
And for that matter when you say "let her [strategy] be 1-z'"
it seems like you're assuming that the opponent is playing in a
manner that makes sense to you and me. Suppose her strategy is to
accept all doubles, and to double any time she can legally do so.
Now of course we need to replace this brownian-motion model with
a discrete-time analog or the cube goes to infinity the first time
I feel it's right to double. No big deal, we change the model.
But how do you know that with a bizarre strategy like this the
expected value in the discrete model does not become infinty - infinity?
(Actually this strategy is more widely used than you might expect -
regardless, it seems that if our expected gain deserves to be called
that we need a law of large numbers to the effect that regardless of
what the opponent does we will as not do worse than so and so.
Non-integrable random variables don't satisfy laws of large numbers...)
Don't misunderstand, you may well be right, here "I don't
follow" means I don't follow. But the fact that all the terms in a
series are finite does not imply that the series converges...
Suppose we change the game: the n-th time the cube is turned
the stakes are multiplied by m_n instead of by 2. It's clear that if
m_n blows up fast enough then the series analogous to the one I'm
worried about here _does_ diverge (well I think it's clear - I suppose
that with a dynamic cube like this the "optimal strategy" will not
be so simple either. It's clear that if both sides are using a fixed
z (1 - z') sort of strategy then the series is not absolutely convergent
if m_n blows up fast enough. Could be that it's obvious that those are
not optimal strategies in the new version of the game; so what? It looks
to me like this shows that there's something to be shown.)
> It can happen in real backgammon -- in theory; a never-ending game,
> the advantage alternating back and forth. For that matter, a game can even
> stall... the players keep on rolling the dice but neither one gets to move
> a stone, ever. Again, it doesn't matter (unless if you are one of them).
Hmm. We could go around in circles regarding what doesn't matter -
there are a few things that you're saying don't matter that I never said
did matter. I didn't say anything about infinitely long games. Exactly
_how_ do you define the expected gain in a position? Even in the
Weiner-Levy model above?
I _can_ show that there exists a map from the set of backgammon
positions to the positive reals that has the properties you'd want of the
"equity" that backgammon players talk about. (It's never larger than
three times the value of the cube, at the end of the game it equals the
outcome, if you're about to roll the dice it equals the appropriate
average over possible rolls, if you're about to make a decision it equals
the max over your possible choices (min if you're the other side), etc.)
I don't know how to do so by calculating expected values in a
probabilistic model as above (if you do great, I'm not convinced yet.)
The existence of the "equity" function follows from Brower's fixed point
theorem. But this thing I know how to do doesn't answer my question
either: Presumably if you know the equity associated with any given
position then the optimal strategy is always to make the decision that
maximizes the equity. But I don't know that this strategy "assures" that
you will not lose money (to first order, in a law-of-large-numbers
sense). Whether it does so depends on whether a certain random variable
is integrable - whether this is integrable depends on the details of the
rules in a way that the existence of the equity function does not. (And
if there is no law of large numbers available then the "optimal strategy"
seems pretty useless.)
I didn't make up the problem. Well, I did in some sense,
then I discovered that the problem had already been noticed.
There's a paper on optimal doubling strategy in some math journal
somewhere - at the end the author appends a section titled
"Great Expectations" where he points out that he just realized
a certain series may diverge, in which case he's hosed. (It's
stated a little differently in the actual paper.)
> A variant would be a 1-time doubling cube... for that, x_1 = 3/4.
> The 2-time cube has x_2 = 13/16. (Warning, this is spur-of-the-moment).
> It seems that for a k-time M_ing cube, x_i+1 = 1 - x_i(M-1 /2M), x_0 = 1.
> As k -> inf this does yield x = 2M/ 3M-1.
>
> Ilias
>
> series. As usual,
typically,
--
David Ullrich
sig.txt not found
-------------------==== Posted via Deja News ====-----------------------
http://www.dejanews.com/ Search, Read, Post to Usenet
Fred Galvin
On Fri, 19 Dec 1997, David Ullrich wrote:
> Bill Taylor wrote:
> [...]
> > With a doubling cube, it is well-known that one should double, and also
> > either-take-or-drop, when your P(WIN) gets to 0.8
>
> It's "well-known" in some circles. [...]
Do you guys mean to imply that the 0.8 rule is *folklore* or something? If
you have a citation showing that it was known prior to the 1975 paper of
Keeler & Spencer, I'd like to see it.
Fred Galvin
On 18 Dec 1997, Bill Taylor wrote:
> [...]
> About the matter of using a doubling cube with other games, I'm sure
> it's a goer, for money games or long-match games. The arguments against,
> for complete-info games of no chance, (chess etc), struck me as very weak.
Doubling in blitz chess (contra! recontra! supcontra! mortcontra!) has
been common for a long time, although chessplayers somehow manage to keep
track of doubles without a cube. The math will be different because of the
rule that the last player to double is giving the odds of the draw. Has
anyone figured this out?
David Ullrich
Sorry if this apears twice - seems like it should have appeared
already but I don't see it:
Ilias Kastanas wrote:
>
> In article <349AC2...@math.okstate.edu>,
> David Ullrich <ull...@math.okstate.edu> wrote:
> >Bill Taylor wrote:
> >[...]
> >> With a doubling cube, it is well-known that one should double, and also
> >> either-take-or-drop, when your P(WIN) gets to 0.8
> >
ull...@math.okstate.edu
In article <Pine.SOL.3.96.971222165819.8762B-100000@titania>,
Fred Galvin <gal...@math.ukans.edu> wrote:
>
> On Fri, 19 Dec 1997, David Ullrich wrote:
>
> > Bill Taylor wrote:
> > [...]
> > > either-take-or-drop, when your P(WIN) gets to 0.8
> >
>
> Do you guys mean to imply that the 0.8 rule is *folklore* or something? If
> you have a citation showing that it was known prior to the 1975 paper of
> Keeler & Spencer, I'd like to see it.
Well, what _I_ meant to imply is that the 0.8 rule applies in
situations where you can say exactly what P(WIN) _is_, but in general
(in backgammon. in situations where there's still contact) it's not at
all clear to me that there _is_ such a thing as P(WIN). In any case I
don't know how to calculuate my probability of winning in a given
situation. I'm not talking about the calculation being too hard or
taking too long, I don't know what the _definition_ of P(WIN) is - I
don't know what P(WIN) is, even theoretically.
(If that sounds stupid by all means say so, but only if you also
include a precise definition of P(WIN).)
My probability of winning depends on the strategy I'm using
as well as the strategy the opponent is using. Presumably when people
talk about the probability of winning they mean assuming both sides
play optimally. The optimal strategy is presumably that which
maximizes one's "equity". But I don't know how to define my equity
in a given position. If there were no cube I could write down
definitions of all these things as certain infinite series which
I would know converged, but with the cube the convergence is not
at all clear to me.
So P(WIN) depends on what strategy we're using - if there's
a "real" P(WIN) we assume we're using the optimal strategy. The
optimal strategy is to maximize our equity. The _definition_ of the
equity is a sum involving P(WIN). I'm confused.
Ilias posted something that was supposed to reassure me,
but it seemed to me he was just avoiding the point, simply taking
for granted the things I was concerned about. (Based on his record
it certainly seems possible that I'm just missing something he
said. But... for example he points out that there are (almost
surely) no infinitely long games. I never said there were - the
problem is that there's no bound on the length of a game. He
understands the difference very well.)
Let's play a stupid game. We toss a coin until a T appears.
Say there were N H's before the first T. Then I pay you (-2)^N dollars.
(Ie if the number of heads is even I pay you 2^N dollars, while if
the number of heads was odd you pay me 2^N dollars.) What's the value
of this game to me? Looks like
-1/2 + 1/2 - 1/2 + 1/2 ... .
It's even worse if I pay you (-4)^N dollars if there are N heads before
the first tail. Then the value is
-1/2 + 2 - 4 ...
or some such. These series diverge, the second worse than the first -
there simply is no such thing as the "value" of the game as far as I
can see.
I don't see how we know that a similar problem doesn't come up in
backgammon - it's much more complicated, but it seems to me there's
something that we need to verify converges before we can make sense
of a lot of the things that a lot of people say. (And if we _do_ need
to worry about all this then it seems clear that simplified models
are going to be useless - we need to know what the actual numbers
are in the actual game.)
"Keeler & Spencer" - so that's where that paper was. Aha...
Note the Appendix titled "Great Expectations":
"There is a theoretical flaw in our treatment of backgammon
doubling points. We have tacitly assumed that the expected value of
the game, given doubling strategies for A and B[,] exists. It need
not."
Then they go on to give an example as above where certain
series diverge. They then give some ad hoc replies to the objection,
but it's very ad hoc - having demonstrated that there are cases in
which their model gives nonsense they don't really fix anything
or explain any of the defintions I request above, they just agree
to ignore the cases where it makes all no sense. The trouble is
an "optimal strategy" is supposed to guarantee that you won't on
average do worse than even no matter what your opponent does - it's
not supposed to depend on your opponent using one of the strategies
in a paper by Keeler and Spencer.
To be fair, they point out that in real life assets are finite.
But of course this changes everything, including the validity of all
those models. (There's no rule in the _real_ game that requires you
to drop if you can't afford to pay if you take and lose. That would
change things considerably...)
David C. Ullrich
Bill Daly
David Ullrich wrote in message <349FF8...@math.okstate.edu>...
[I omitted the bulk of your message, as it is fairly long and has already
been repeated more than once.]
I didn't know you were interested in backgammon. Hmm...
There is a position (I wouldn't call it well-known, but it has been
discussed before) in which both players have a checker on the bar, whoever
enters first will almost certainly win, and the probability of entering on
any given roll is significantly less than 50%. If you work this out, you
will get a divergent series for the expectation (i.e. equity) of either
player. The position is legal, and for all I know may have actually arisen
in play, since it is not particularly weird. Essentially, each player covers
all but the 6-point on his own board, each player has a checker on his
opponent's 6-point, each player has a checker on the bar, and the remaining
6 checkers (3 for each side) are scattered about more or less symmetrically.
For this to be legal, it must be the case that whichever player was first on
the bar must have had two checkers on the bar, and he must have just entered
with one of them on his opponent's 6-point, hitting the opponent's checker
which is now on the bar.
In my view, expectation is always defined and never divergent, simply
because for one reason or another the cube becomes irrelevant to the
outcome. One way for this to happen (somewhat obviously) is in match play,
when after a certain point, it no longer matters how high the cube is, since
the result of the game will decide the match. At this point, there is
nothing to be gained (or lost for that matter) by doubling. Real life money
play can always be regarded as a long match, since as a practical matter,
there is a finite limit to what each player can afford to pay if he loses,
and once this limit is exceeded for both players, the cube becomes
irrelevant.
What this means to me is: the money game can never be precisely analyzed,
because it is too difficult to predetermine what each player is prepared to
lose. On the other hand, the match game can always be precisely analyzed,
even in the face of bizarre situations of the type that I described above,
because the state of the match limits the power of the cube. It is almost
certainly the case that the correct move or the correct cube action, at
least in some circumstances, depends on the state of the match, but as long
as this can be quantified, the proper strategy can be determined
mathematically, in principle.
Regards,
Bill
Bill Taylor
David Ullrich <ull...@math.okstate.edu> writes:
|> Suppose her strategy is to
|> accept all doubles, and to double any time she can legally do so.
Heheh! Nice example! (But I wonder if the current politically correct
practice of mixing pronoun genders might backfire here - suggesting to
outraged feminists that only a *woman* would consider such an emotional
and lame-brained cube strategy! Ah well... ;-) )
|> Now of course we need to replace this brownian-motion model with
|> a discrete-time analog or the cube goes to infinity the first time
|> I feel it's right to double. No big deal, we change the model.
Yes, good point; the problem here is that this strategy leads to
"continuous doubling"! But as you say - no big deal to discretize.
|> (Actually this strategy is more widely used than you might expect -
Heheheh! Yes - but the proponents don't tend to accumulate too many rating
points in backgammon! It seems to be used a lot in politics, though.
|> But how do you know that with a bizarre strategy like this the
|> expected value in the discrete model does not become infinty - infinity?
OK then, let's see if I can hand-wave glibly enough to avoid any actual work.
Bill Daly has already made a response involving upper limits on the
doubling, either from fixed-length matches, or by invoking (in effect) the
non-linearity of the utility of money. Nice response, Bill, (after all, we
Bills gotta stick together!), but maybe it misses the target a little.
But we can do the same, strictly mathematically.
Let's suppose we are playing against the "emotional" strategy above;
or any other non-optimal one. We can adopt our own (allegedly) optimal
strategy, but truncate it so as to never double in our favorable zone
where we-double-and-she-should-drop, after we have already made one such
favorable (and taken) double there. Then this strategy will do at least
as well for us as if the opponent had played sensibly, (obvious, I hope),
and will not lead to infinite expectations, (by my former calculation).
Then we can consider the same, but where we are prepared to do TWO of these
super-favorable doubles. The calculation will show that we still have
finite, but LARGER expectation to us. Then do THREE, and so on. Now by
waving our hands and muttering "dominated convergence theorem" or perhaps
better "monotone convergence theorem", we outline a proof that our limiting
strategy of always doubling when in the doubling zone, tends to expectations
of plus infinity for us, with no minus infinity part anywhere. I'll play!!
Detailed proof is left as an exercise to the reader; but I'm fully convinced
by the neatness of this uncannily persuasive argument. :) :) Please write
in with more objections though - it's a good learning experience (for me).
|> I _can_ show that there exists a map from the set of backgammon
|> positions to the positive reals that has the properties you'd want of
|> the "equity" that backgammon players talk about. (It's never larger than
|> three times the value of the cube, at the end of the game it equals the
|> outcome, if you're about to roll the dice it equals the appropriate
|> average over possible rolls, if you're about to make a decision it
|> equals the max over your possible choices (min if you're the other
|> side), etc.)
Sounds good!
|> The existence of the "equity" function follows from Brower's fixed point
|> theorem.
Sounds very neat indeed. But I don't get it yet - could you please
elaborate on the use of fixed-point in this matter?
-------------------------------------------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
-------------------------------------------------------------------------------
Every problem has at least one solution which is elegant, neat - and wrong.
-------------------------------------------------------------------------------
Gerry Quinn
>There is a position (I wouldn't call it well-known, but it has been
>discussed before) in which both players have a checker on the bar, whoever
>enters first will almost certainly win, and the probability of entering on
>any given roll is significantly less than 50%. If you work this out, you
>will get a divergent series for the expectation (i.e. equity) of either
>player. The position is legal, and for all I know may have actually arisen
>in play, since it is not particularly weird. Essentially, each player covers
>all but the 6-point on his own board, each player has a checker on his
>opponent's 6-point, each player has a checker on the bar, and the remaining
>6 checkers (3 for each side) are scattered about more or less symmetrically.
>For this to be legal, it must be the case that whichever player was first on
>the bar must have had two checkers on the bar, and he must have just entered
>with one of them on his opponent's 6-point, hitting the opponent's checker
>which is now on the bar.
>
Surely this is easy to analyse? The player to move has a 6/11 chance
to win, and the other has a 5/11 chance. Either would be mad to
double before they enter.
NATHANIEL SILVER
This has nothing to do with math. Important aspects of doubling are that:
Even if you are a 3-1 favorite:
1. You have released the cube which gives your opponent extra winning
chances, if he accepts. He may be able to double later (whenever he wants
to) and you may be unable to accept. This may affect your play. And he can
beaver (redouble immediately) if he is in a "gambling mood" and, of course,
he still holds the cube. And there is more pressure on you, especially if
you have a small bankroll.
2. Significant psychological factors are at play, involving the opponent's
knowledge of the position, the opponent's knowledge of your knowledge of
the position, and whether you can intimidate (bluff) him into giving up.
Natty
Ilias Kastanas
In article <349FF8...@math.okstate.edu>,
Right; T, the time to hit 0 or 1, is not bounded. We do have
E(T) = 1/4, E(T^2) = 5/48.
>that the series is summable? The random variable WhoWins is defined
>as, and the random variable HowMuch is defined as, fine. _How_ does
>it follow that HowMuch has a well-defined expected value?
>
> And for that matter when you say "let her [strategy] be 1-z'"
>it seems like you're assuming that the opponent is playing in a
>manner that makes sense to you and me. Suppose her strategy is to
>accept all doubles, and to double any time she can legally do so.
>Now of course we need to replace this brownian-motion model with
>a discrete-time analog or the cube goes to infinity the first time
>I feel it's right to double. No big deal, we change the model.
Sure. Actually, even with one-double-per-instance, there would
still be a problem; B_t has a countable infinity of local maxima.
>But how do you know that with a bizarre strategy like this the
>expected value in the discrete model does not become infinty - infinity?
>(Actually this strategy is more widely used than you might expect -
>regardless, it seems that if our expected gain deserves to be called
>that we need a law of large numbers to the effect that regardless of
>what the opponent does we will as not do worse than so and so.
>Non-integrable random variables don't satisfy laws of large numbers...)
>
> Don't misunderstand, you may well be right, here "I don't
>follow" means I don't follow. But the fact that all the terms in a
>series are finite does not imply that the series converges...
You have the best of reasons not to follow; see below!
And, uh, agreed; even a_n -> 0 doesn't guarantee convergence --
since we chose R and not Q_p!...
> Suppose we change the game: the n-th time the cube is turned
>the stakes are multiplied by m_n instead of by 2. It's clear that if
>m_n blows up fast enough then the series analogous to the one I'm
>worried about here _does_ diverge (well I think it's clear - I suppose
>that with a dynamic cube like this the "optimal strategy" will not
>be so simple either. It's clear that if both sides are using a fixed
>z (1 - z') sort of strategy then the series is not absolutely convergent
>if m_n blows up fast enough. Could be that it's obvious that those are
>not optimal strategies in the new version of the game; so what? It looks
>to me like this shows that there's something to be shown.)
>
>
>> It can happen in real backgammon -- in theory; a never-ending game,
>> the advantage alternating back and forth. For that matter, a game can even
>> stall... the players keep on rolling the dice but neither one gets to move
>> a stone, ever. Again, it doesn't matter (unless if you are one of them).
>
> Hmm. We could go around in circles regarding what doesn't matter -
>there are a few things that you're saying don't matter that I never said
>did matter. I didn't say anything about infinitely long games. Exactly
>_how_ do you define the expected gain in a position? Even in the
>Weiner-Levy model above?
I don't mean to include problematic "wild" strategies; they are not
interesting anyway. Unfortunately I only gave the "sanity" requirement,
z > 1/2, instead of the "logic" one, z > 2/3 (i.e. "better than" the w with
equal distance to 1 and to 1-w).
At z, the probability of hitting 1 before 1-z' is p = z+z'-1 /z'.
The expected gain (all doubles accepted) is p*2 + (1-p)[p'*(-4) + (1-p'){p*8 +
... ...}]) For z, z' > 2/3 this is easily convergent (to 2(2z-1)/2-z if
z = z', so at z=4/5 it is 1). At z = z' = 2/3 it becomes 1-1+1-1..., and
then it gets worse!
What if my opponent _does_ use a wild strategy, say z' = 0 --
always doubling? After I double and she doubles back, I may elect not to
double again -- I'm already better off. Or I might double once more, or
twice, or whatever... limited only by greed; I can get as close to "infinity"
as desired. This is just "infinity"... no infinity-infinity problem.
> I _can_ show that there exists a map from the set of backgammon
>positions to the positive reals that has the properties you'd want of
>the "equity" that backgammon players talk about. (It's never larger than
>three times the value of the cube, at the end of the game it equals the
>outcome, if you're about to roll the dice it equals the appropriate
>average over possible rolls, if you're about to make a decision it
>equals the max over your possible choices (min if you're the other
>side), etc.) I don't know how to do so by calculating expected values
>in a probabilistic model as above (if you do great, I'm not convinced yet.)
>The existence of the "equity" function follows from Brower's fixed point
>theorem. But this thing I know how to do doesn't answer my question
>either: Presumably if you know the equity associated with any given
>position then the optimal strategy is always to make the decision
>that maximizes the equity. But I don't know that this strategy
>"assures" that you will not lose money (to first order, in a
>law-of-large-numbers sense). Whether it does so depends on whether
>a certain random variable is integrable - whether this is integrable
>depends on the details of the rules in a way that the existence
>of the equity function does not. (And if there is no law of large
>numbers available then the "optimal strategy" seems pretty useless.)
That's interesting... Brouwer as is, or Tychonoff's version
(Schauder in the case of Banach spaces)?
> I didn't make up the problem. Well, I did in some sense,
>then I discovered that the problem had already been noticed.
>There's a paper on optimal doubling strategy in some math journal
>somewhere - at the end the author appends a section titled
>"Great Expectations" where he points out that he just realized
>a certain series may diverge, in which case he's hosed. (It's
>stated a little differently in the actual paper.)
Eh, I guess it is!
>> A variant would be a 1-time doubling cube... for that, x_1 = 3/4.
>> The 2-time cube has x_2 = 13/16. (Warning, this is spur-of-the-moment).
>> It seems that for a k-time M_ing cube, x_i+1 = 1 - x_i(M-1 /2M), x_0 = 1.
>> As k -> inf this does yield x = 2M/ 3M-1.
>>
>> Ilias
Ilias
David Ullrich
Ilias Kastanas wrote:
>
> In article <349FF8...@math.okstate.edu>,
> David Ullrich <ull...@math.okstate.edu> wrote:
> >Ilias Kastanas wrote:
> >>
> >> In article <349AC2...@math.okstate.edu>,
> >> David Ullrich <ull...@math.okstate.edu> wrote:
> >> >Bill Taylor wrote:
>
> I don't mean to include problematic "wild" strategies; they are not
> interesting anyway. Unfortunately I only gave the "sanity" requirement,
> z > 1/2, instead of the "logic" one, z > 2/3 (i.e. "better than" the w with
> equal distance to 1 and to 1-w).
>
> At z, the probability of hitting 1 before 1-z' is p = z+z'-1 /z'.
> The expected gain (all doubles accepted) is p*2 + (1-p)[p'*(-4) + (1-p'){p*8 +
> ... ...}]) For z, z' > 2/3 this is easily convergent (to 2(2z-1)/2-z if
> z = z', so at z=4/5 it is 1). At z = z' = 2/3 it becomes 1-1+1-1..., and
> then it gets worse!
>
> What if my opponent _does_ use a wild strategy, say z' = 0 --
> always doubling? After I double and she doubles back, I may elect not to
> double again -- I'm already better off. Or I might double once more, or
> twice, or whatever... limited only by greed; I can get as close to "infinity"
> as desired. This is just "infinity"... no infinity-infinity problem.
Yeah. But saying that you didn't mean to include certain strategies
by your opponent, and that if he does this you can just do that really
doesn't answer any of my questions, does it? Seems like there are some
definitions missing, and just saying that in one particular case you could
so such and so doesn't say anything about what the definition is. (Nor
does it say anything about the validity of this model to a person who's
worried about not knowing what "P(WIN)" is in the real game.)
If a bizarre strategy means that my "optimal" strategy doesn't
work any more then it's interesting. If my optimal strategy requires
reading the opponent's mind it's sort of useless. And if there _is_
such a thing as an optimal strategy I simply can't believe it can
really depend on the _level_ (as opposed to the position) of the cube.
> > I _can_ show that there exists a map from the set of backgammon
> >positions to the positive reals that has the properties you'd want of
> >the "equity" that backgammon players talk about. (It's never larger than
> >three times the value of the cube, at the end of the game it equals the
> >outcome, if you're about to roll the dice it equals the appropriate
> >average over possible rolls, if you're about to make a decision it
> >equals the max over your possible choices (min if you're the other
> >side), etc.) I don't know how to do so by calculating expected values
> >in a probabilistic model as above (if you do great, I'm not convinced yet.)
> >The existence of the "equity" function follows from Brower's fixed point
> >theorem. But this thing I know how to do doesn't answer my question
> >either: Presumably if you know the equity associated with any given
> >position then the optimal strategy is always to make the decision
> >that maximizes the equity. But I don't know that this strategy
> >"assures" that you will not lose money (to first order, in a
> >law-of-large-numbers sense). Whether it does so depends on whether
> >a certain random variable is integrable - whether this is integrable
> >depends on the details of the rules in a way that the existence
> >of the equity function does not. (And if there is no law of large
> >numbers available then the "optimal strategy" seems pretty useless.)
>
> That's interesting... Brouwer as is, or Tychonoff's version
> (Schauder in the case of Banach spaces)?
I dunno whose theorem it is, I made it up (non-mathematicians
should note I'm allowed to do that as long as I include a proof):
Any continuous map from an infinite product of compact intervals to
itself has a fixed point (follows trivially from the version for finite
products.)
"Positions" are defined by the position of the pieces, the cube,
the dice, etc. So if I'm deciding whether to double that's a "position",
then after I roll, when I'm deciding what play to make, that's
another "position". You consider X, the class of all maps E from positions
to reals, such that
(*) |E(Pos)| <= 3*Cube
for each position. The inequality
says that E is an element of a certain product as in the previous
paragraph. (Where Cube = the current value of the cube. I forget the
definition of Cube in the position where one side has doubled and
the other is deciding whether to take - it's whatever's needed to make
the following work. In fact maybe in that case the inequality is replaced
by -3*OldCube <= E(Pos) <= 3*NewCube or some such.)
You define T: X -> X by saying that T(E) is what E would have
to be if E were a real "equity" function. This gives a bunch of rules:
If Pos is a position where I'm making a choice between alternatives
Pos_1, ... Pos_N then T(E)(Pos) = max(E(Pos_1), ... E(Pos_N)).
If Pos is a position where I'm about to roll the dice then
T(E)(Pos) = (1/36)*E(Pos(1,1)) + ... + (1/36)*E(Pos(6,6)) ,
where Pos(j,k) is the same position after I roll a (j,k). Etc. For
each position Pos there's a natural rule saying what T(E)(Pos) should
be. You verify that if E satisfies the inequality (*) for all Pos
(possibly amended in those situations where "value of the cube"
is ambiguous) then it follows that T(E) satisfies the same
inequality for all Pos (you use this to figure out what inequality
(*) should be in the problematic Pos "deciding whether to take".)
It's easy to see that T is continuous, hence T has a fixed point E0.
There are a few details left out here, but one can easily fill them
all in (and note that there are _no_ simplifying assumptions
required - it's exactly _backgammon_ that we're talking about!)
So there's the "value" of the game - it's E0(Pos). Now
if I'm about to roll the dice then E0(CurrentPos) is the approprate
average of E0(PosAfterPossibleRolls), if I'm about to make a choice
then E0(Pos) = max(E0(PossibleChoices)), etc, as it should. Presumably
the "optimal" strategy is to always make the choice that maximizes
E0. And in, say, situations where there's no contact left one can
show that this _is_ optimal - if one does this then regardless of
what your opponent does you will win on average E0(CurrentPos).
But in general some martingale needs to be L1-bounded or there is
_no_ such guarantee (and in fact I believe that if the relevant
gizmo is not L1-bounded then it's not just that we can't prove
the optimal strategy is ok, I believe in that case it can be proved
that there _is_ no guarantee available...). The argument so far is
very soft, but to determine the L1-boundedness we need a much more
careful analysis. (And if the actual details of the actual numbers
are important I tend not to see how models of random walks
on [0,1] can help - there for example it's easy to see what
P(WIN) is, here it's not. At least I don't see it, and I haven't
seen any definitions offered yet (although this is the first of
today's replies that I've read.))
Or so it seems to me.
> > I didn't make up the problem. Well, I did in some sense,
> >then I discovered that the problem had already been noticed.
> >There's a paper on optimal doubling strategy in some math journal
> >somewhere - at the end the author appends a section titled
> >"Great Expectations" where he points out that he just realized
> >a certain series may diverge, in which case he's hosed. (It's
> >stated a little differently in the actual paper.)
>
> Eh, I guess it is!
--
David Ullrich
Bill Daly wrote:
>
> David Ullrich wrote in message <349FF8...@math.okstate.edu>...
>
> [I omitted the bulk of your message, as it is fairly long and has already
> been repeated more than once.]
>
> I didn't know you were interested in backgammon. Hmm...
>
> discussed before) in which both players have a checker on the bar, whoever
> enters first will almost certainly win, and the probability of entering on
> any given roll is significantly less than 50%. If you work this out, you
> will get a divergent series for the expectation (i.e. equity) of either
> player. The position is legal, and for all I know may have actually arisen
> in play, since it is not particularly weird. Essentially, each player covers
> all but the 6-point on his own board, each player has a checker on his
> opponent's 6-point, each player has a checker on the bar, and the remaining
> 6 checkers (3 for each side) are scattered about more or less symmetrically.
> For this to be legal, it must be the case that whichever player was first on
> the bar must have had two checkers on the bar, and he must have just entered
> with one of them on his opponent's 6-point, hitting the opponent's checker
> which is now on the bar.
>
> because for one reason or another the cube becomes irrelevant to the
> outcome. One way for this to happen (somewhat obviously) is in match play,
> when after a certain point, it no longer matters how high the cube is, since
> the result of the game will decide the match. At this point, there is
> nothing to be gained (or lost for that matter) by doubling. Real life money
> play can always be regarded as a long match, since as a practical matter,
> there is a finite limit to what each player can afford to pay if he loses,
> and once this limit is exceeded for both players, the cube becomes
> irrelevant.
Match play is a totally different story - this is why I was careful
to point out at the start that what one "should" do depends on one's objectives.
In a match one attempts to maximize P(Winning the match), which is not
at all the same thing as maximizing one's expected gain in a "money game".
There's effectively a bound on the level of the cube and all the problems
I've been worried about go away.
In the mathematical model I was objecting to there's no limit
specified on the amount either side can afford to pay. If we start
considering that in the real game things are very different. But of
course:
> What this means to me is: the money game can never be precisely analyzed,
> because it is too difficult to predetermine what each player is prepared to
> lose.
Also we never defined whether it's for example _legal_ to take
a double although you cannot afford to pay. Which is not just an
academic question - the fact that people are allowed to take doubles
they can't afford affects the outcome of plenty of actual games.
There's the notion of "table stakes" in poker: You're not
allowed to bet more than what you have on the table, otoh you're
not required to see bets for more than that either (if someone makes
a bet and you're out of chips the hand splits into two pots, one of
which is frozen, and which you win if you have the high hand, and
one of which everybody else puts money into, which you're not
allowed to win.) The point being that although the guy with the
most money still has an obvious advantage he can't use his large
wallet to force you to fold any given hand.
> On the other hand, the match game can always be precisely analyzed,
> even in the face of bizarre situations of the type that I described above,
> because the state of the match limits the power of the cube. It is almost
> certainly the case that the correct move or the correct cube action, at
> least in some circumstances, depends on the state of the match, but as long
> as this can be quantified, the proper strategy can be determined
> mathematically, in principle.
Yup. (From this point of view) a match is much simpler.
David Ullrich
Bill Taylor wrote:
>
> David Ullrich <ull...@math.okstate.edu> writes:
>
> |> Suppose her strategy is to
> |> accept all doubles, and to double any time she can legally do so.
>
> practice of mixing pronoun genders might backfire here - suggesting to
> outraged feminists that only a *woman* would consider such an emotional
> and lame-brained cube strategy! Ah well... ;-) )
I was referring to Ilias' "she".
> |> Now of course we need to replace this brownian-motion model with
> |> a discrete-time analog or the cube goes to infinity the first time
> |> I feel it's right to double. No big deal, we change the model.
>
> Yes, good point; the problem here is that this strategy leads to
> "continuous doubling"! But as you say - no big deal to discretize.
>
> |> (Actually this strategy is more widely used than you might expect -
>
> Heheheh! Yes - but the proponents don't tend to accumulate too many rating
> points in backgammon! It seems to be used a lot in politics, though.
>
> |> But how do you know that with a bizarre strategy like this the
> |> expected value in the discrete model does not become infinty - infinity?
>
> OK then, let's see if I can hand-wave glibly enough to avoid any actual work.
>
> Bill Daly has already made a response involving upper limits on the
> doubling, either from fixed-length matches,
A match is totally different. Remember I _started_ by asking what we
were trying to accomplish and conjecturing that our goal was "maximize expected
gain", leading to the question of what that was? In a match our goal is to
maximize the chance of winning the match. If it's a 7-point match then winning
7-6 is the same as 24-0. A completely different topic.
> or by invoking (in effect) the
> non-linearity of the utility of money. Nice response, Bill, (after all, we
> Bills gotta stick together!), but maybe it misses the target a little.
>
> But we can do the same, strictly mathematically.
>
> Let's suppose we are playing against the "emotional" strategy above;
> or any other non-optimal one. We can adopt our own (allegedly) optimal
> strategy, but truncate it so as to never double in our favorable zone
> where we-double-and-she-should-drop, after we have already made one such
> favorable (and taken) double there. Then this strategy will do at least
> as well for us as if the opponent had played sensibly, (obvious, I hope),
> and will not lead to infinite expectations, (by my former calculation).
> Then we can consider the same, but where we are prepared to do TWO of these
> super-favorable doubles. The calculation will show that we still have
> finite, but LARGER expectation to us. Then do THREE, and so on. Now by
> waving our hands and muttering "dominated convergence theorem" or perhaps
> better "monotone convergence theorem", we outline a proof that our limiting
> strategy of always doubling when in the doubling zone, tends to expectations
> of plus infinity for us, with no minus infinity part anywhere. I'll play!!
Pshaw. Your optimal strategy consists of playing optimally
except when you happen to notice the opponent doing something funny? You
_mutter_ about the DCT instead of verifying the hypotheses?
If one is claiming an _optimal_ strategy one should first be able
to state _exactly_ what one means in calling it "optimal", and then
one should be able to _prove_ that it has this property. Presumably
there's some sort of "no matter _what_ the opponent does" in the
definition of "optimal strategy" being used (what _is_ the definition
you're using?). Then we need to prove something happens _no_ _matter_
_what_ _the_ _opponent_ _does_. You're answering a "but what if the
opponent does _this_?" with a "then do _that_" - no what are you
going to do if the oppponent does something else?
Reminds me of a lot of proofs of Fermat's last theorem.
Someone points out a gap - a revision appears, plugging that one
gap...
> Detailed proof is left as an exercise to the reader; but I'm fully convinced
> by the neatness of this uncannily persuasive argument. :) :) Please write
> in with more objections though - it's a good learning experience (for me).
If you've proved something this sort of request doesn't come up.
> |> I _can_ show that there exists a map from the set of backgammon
> |> positions to the positive reals that has the properties you'd want of
> |> the "equity" that backgammon players talk about. (It's never larger than
> |> three times the value of the cube, at the end of the game it equals the
> |> outcome, if you're about to roll the dice it equals the appropriate
> |> average over possible rolls, if you're about to make a decision it
> |> equals the max over your possible choices (min if you're the other
> |> side), etc.)
>
> Sounds good!
>
> |> The existence of the "equity" function follows from Brower's fixed point
> |> theorem.
>
> Sounds very neat indeed. But I don't get it yet - could you please
> elaborate on the use of fixed-point in this matter?
There are some hints in my reply to Ilias. There _does_ exist a
function E(Pos) with these properties, I know because I can prove it.
And if there is an "expected value" in the usual sense then it seems it
must agree with this E. But I don't see how it helps, since I can't show
that the strategy "always maximize E" guarantees any sort of almost-surely
-you-won't-do-worse-than-this outcome.
David Ullrich
PS regarding what the constraint should be:
E(Pos) is supposed to represent the value of the game to
me. Say the value of the cube is Cube. Then in most situations
we require |E(Pos)| <= 3*Cube.
If Pos is such that I've just doubled and the opponent
is deciding whether to take let's say that the former value of
the cube is Cube. Then the position cannot be worth more than
Cube to me, since the opponent could drop. Otoh it could
happen that the opponent can take and win a backgammon, in fact
it could be certain. (Not that I'm likely to double in a
position where the opponent is certain to win a backgammon -
that's not the point.) So in this position the constraint is
(1) -6*Cube <= E(Pos) <= Cube ,
with a similar constraint in the dual position where I'm deciding
whether to take.
Note that the above is not an argument, just a heuristic
telling us what the definition of the interval I(Pos) "should"
be. In most cases I(Pos) = [-3*Cube, 3*Cube]. In the case considered
above we define I(Pos) as above: I(Pos) = [-6*Cube, Cube] .
Now we let X be the set of all mappings E from the set
of all positions to the reals, such that E(Pos) is an element
of I(Pos) for all Pos. We verify that the T defined previously
maps X to X (we need to define X before we can prove this,
hance the current PS), we verify that T is continuous, and
hence T has a fixed point.
Gary Wong
ger...@indigo.ie (Gerry Quinn) writes:
> In article <67pgud$eff$1...@broadway.interport.net>, "Bill Daly"
<bill...@interport.net> wrote:
> >discussed before) in which both players have a checker on the bar, whoever
> >enters first will almost certainly win, and the probability of entering on
> >any given roll is significantly less than 50%. If you work this out, you
> >will get a divergent series for the expectation (i.e. equity) of either
> >player. The position is legal, and for all I know may have actually arisen
> >in play, since it is not particularly weird. Essentially, each player covers
> >all but the 6-point on his own board, each player has a checker on his
> >opponent's 6-point, each player has a checker on the bar, and the remaining
> >6 checkers (3 for each side) are scattered about more or less symmetrically.
> >For this to be legal, it must be the case that whichever player was first on
> >the bar must have had two checkers on the bar, and he must have just entered
> >with one of them on his opponent's 6-point, hitting the opponent's checker
> >which is now on the bar.
>
> to win, and the other has a 5/11 chance. Either would be mad to
> double before they enter.
The player to move has a 6/11 chance to win? If so, bring a tournament
official over, I want these dice checked :-) It's getting late at night so
treat my maths as suspect, but IMHO the probability of the player on roll
winning is 11/36 for this roll, plus 25/36 x 25/36 x 11/36 for entering after
both players dance once, etc. etc. for a sum to infinity of 396/671 ~= 0.59.
A bit more than 6/11.
41% winning chances makes it an obvious take for money, but is it a double?
Assuming no gammon chances and crediting whoever rolls a 6 first with a single
win gives them 11 huge market losers. That's enough to make me take a good
hard look at the cube (no comment on whether I'm mad or not :-). Is it
correct to turn it here? Let's take the case where the cube is initially
centred first. The cube is worthless to you if you enter (you'd win a single
game regardless of whether you have access to the cube or not), so it's
"now or never" with the double. Since the cube is centred, your opponent
can already double so you're not giving them any additional recube vig by
doubling them now. Therefore, you have nothing to lose by doubling; you also
have something to gain because you are a slight favourite with cubeless equity
0.18. So I believe it _is_ correct to double (and take) here.
Is the situation any different for a redouble? In this case you might be a
little more reluctant to give your opponent the cube because you're giving
them the chance to double they wouldn't otherwise have had. However, I don't
believe this makes any difference; the cube will still die if you don't double
now. Since it was a correct initial double, we know we'd prefer to have our
opponent holding a live doubled cube than a dead one in any position; so I
think it is a correct redouble as well. Each player should double when they
are on roll; the opponent should take (but not beaver). The cube will go
arbitrarily high if both players dance indefinitely; the exponential cube
values are sufficiently large to outweigh the diminishing probabilities of
the game lasting that long which makes the total equity truly undefined.
To get back to the point of this thread ("this is a song about Alice.
Remember Alice?") -- note that none of the above discussion about whether it
was correct to double relied on the "rate" of the cube (by that I mean whether
it's a doubling cube, tripling, 1.5, or whatever) -- the same perpetual
doubling behaviour would be correct for any kind of cube that increases the
stakes. However, since the probability of the game continuing another roll
is only 25/36, the cube has to be at least a 36/25 for the equity to be
undefined. For values less than that, the expectation of points scored in
short games dominate the equity and the infinite series converges.
Cheers,
Gary (GaryW on FIBS).
Gary Wong
ull...@math.okstate.edu writes:
> In article <Pine.SOL.3.96.971222165819.8762B-100000@titania>,
> Fred Galvin <gal...@math.ukans.edu> wrote:
> > Do you guys mean to imply that the 0.8 rule is *folklore* or something? If
> > you have a citation showing that it was known prior to the 1975 paper of
> > Keeler & Spencer, I'd like to see it.
>
> Well, what _I_ meant to imply is that the 0.8 rule applies in
> situations where you can say exactly what P(WIN) _is_, but in general
> (in backgammon. in situations where there's still contact) it's not at
> all clear to me that there _is_ such a thing as P(WIN). In any case I
> don't know how to calculuate my probability of winning in a given
> situation. I'm not talking about the calculation being too hard or
> taking too long, I don't know what the _definition_ of P(WIN) is - I
> don't know what P(WIN) is, even theoretically.
>
> (If that sounds stupid by all means say so, but only if you also
> include a precise definition of P(WIN).)
I wouldn't go so far as to say that sounds stupid, but it seems to me that
we should be able to agree fairly readily on a reasonable definition. What's
wrong with assuming the current players repeatedly play the position out to
completion, and take P(WIN) = the limit of (games won)/(games played) as the
number of games played approaches infinity? This (cubeless) quantity will
always be well defined, for any position, by any players, using any strategies.
> My probability of winning depends on the strategy I'm using
> as well as the strategy the opponent is using.
Quite true.
> Presumably when people
> talk about the probability of winning they mean assuming both sides
> play optimally.
I'm not sure, I think when many people talk about the probability of winning,
they often gloss over exactly what they mean :-) Sometimes people post
Jellyfish evaluations of a position and implicitly assume that the evaluations
are an accurate representation of their own probability of winning from that
position, or even the probability of winning given optimal play. In practice
the values are likely to be reasonably close, but it certainly seems to me
that the quantity of interest is the one given the current players -- there's
something to be said for seeking a position I'm more familiar with than my
opponent, for instance, or deliberately seeking complication against a weaker
player or avoiding it against a stronger one.
> The optimal strategy is presumably that which
> maximizes one's "equity". But I don't know how to define my equity
> in a given position. If there were no cube I could write down
> definitions of all these things as certain infinite series which
> I would know converged, but with the cube the convergence is not
> at all clear to me.
That's true too (although we know the convergence exists in match play, or
money play for limited stakes).
> So P(WIN) depends on what strategy we're using - if there's
> a "real" P(WIN) we assume we're using the optimal strategy. The
> optimal strategy is to maximize our equity. The _definition_ of the
> equity is a sum involving P(WIN). I'm confused.
I don't think there's any problem. The key is that you can express P(WIN)
in terms of the P(WIN) for _other_ (subsequent) positions, and P(WIN) for some
positions are deducible from the positions themselves. It's certainly possible
to calculate both P(WIN) and the equity of a position, given neither -- it's
like two equations and two unknowns.
However, P(WIN) is really only a useful measure in cubeless and gammonless
games -- the optimal strategy is to maximise the equity, not P(WIN). There
are plenty of situations where the optimal play results in less wins than
another -- eg. hitting loose in your home board to attempt a blitz could well
risk more losses than playing safe, but may be worth it because of the extra
gammons. Every time you double, you almost certainly reduce P(WIN) (because
your opponent then has cube access and you don't) but if the double was correct
then your equity has increased along with the stakes. P(WIN) by itself really
is not a practically useful quantity.
> Ilias posted something that was supposed to reassure me,
> but it seemed to me he was just avoiding the point, simply taking
> for granted the things I was concerned about. (Based on his record
> it certainly seems possible that I'm just missing something he
> said. But... for example he points out that there are (almost
> surely) no infinitely long games. I never said there were - the
> problem is that there's no bound on the length of a game. He
> understands the difference very well.)
I don't think the possibility of infinitely long games represents a fundamental
problem. (The possibility of the cube going infinitely high in a money game
and having an arbitrarily large influence on the equity quite possibly could
be, but that's another story entirely...) There are a finite number of
possible positions in the game, and for each position P(WIN) is well defined --
and can be expressed in terms of the P(WIN) for all possible resultant
positions later on in the game. This causes no problems, even if some of
the resultant positions repeat the current or earlier positions in the same
game (which is the only way a game can last infinitely long).
> I don't see how we know that a similar problem doesn't come up in
> backgammon - it's much more complicated, but it seems to me there's
> something that we need to verify converges before we can make sense
> of a lot of the things that a lot of people say. (And if we _do_ need
> to worry about all this then it seems clear that simplified models
> are going to be useless - we need to know what the actual numbers
> are in the actual game.)
I agree that there exist some backgammon positions where the equity is
undefined (for money play with unlimited stakes only). But it seems to me
that there's a world of difference between admitting our model which relies
on the expectation existing is "incomplete" against "useless". I'm typing
this article on a deterministic computer. There exist models for computability
that can classify problems that can and cannot be solved by deterministic
computers, deduced from the properties of Turing machines. However, my
computer cannot duplicate a Turing machine (it has finite storage, but the
theoretical machine has an infinitely long tape). Does that mean the
computability model is useless? Not at all, it happens to be incomplete, but
that doesn't need to cause any practical problems as long as we are aware of
the limitations.
In the same way, we claim to have a model for determining the optimal play
in a backgammon position based on the expectation of the outcome for various
possibilities. As long as the expectation exists, we are happy. If it
doesn't, we have to deduce the correct play by some means that does not rely
on the equity (see my previous article where I attempt to establish that a
position with undefined equity is a correct double/take). But the fact remains
that for the vast majority of backgammon positions, there is an exceedingly
high probability that the game will proceed to completion without reaching
any stage where both players are likely to double so often that the equity
becomes undefined. So for all of these billions and billions of positions,
why not stick to the simple (and arguably incomplete) equity-based model
and only resort to alternative approaches when the probability of reaching
a difficult position given the players' doubling strategies is significant?
The situation seems to me something like accepting Newtonian mechanics as
a simple (if incomplete) model of motion to be applied where possible,
resorting to relativistic and/or quantum theory where necessary.
If it still bothers you, then why not stick to match play where our model
is complete?
> "Keeler & Spencer" - so that's where that paper was. Aha...
> Note the Appendix titled "Great Expectations":
>
> "There is a theoretical flaw in our treatment of backgammon
> doubling points. We have tacitly assumed that the expected value of
> the game, given doubling strategies for A and B[,] exists. It need
> not."
>
> Then they go on to give an example as above where certain
> series diverge. They then give some ad hoc replies to the objection,
> but it's very ad hoc - having demonstrated that there are cases in
> which their model gives nonsense they don't really fix anything
> or explain any of the defintions I request above, they just agree
> to ignore the cases where it makes all no sense. The trouble is
> an "optimal strategy" is supposed to guarantee that you won't on
> average do worse than even no matter what your opponent does - it's
> not supposed to depend on your opponent using one of the strategies
> in a paper by Keeler and Spencer.
I suspect we can still derive an "optimal strategy" regardless. If your
opponent doubles when according to K&S he shouldn't, then you can either
hold the cube and claim more equity, or redouble if you decide it is
correct and on average do better than even. If you both continue redoubling
when it is correct for you and not for your opponent, then your equity may
even increase without bounds (subject to the length of the game) -- but it
is still defined. Similar arguments hold if your opponent does not double,
even though it would be appropriate to under a K&S strategy.
The only other case is when it is correct for both players to continue
redoubling, and they do so. In this case the equity does become undefined,
but even so I suspect on average you won't do worse than even, since it's
a symmetrical zero-sum game. If you double and your opponent doesn't, then
you definitely do better than even. So it is quite possible for an
"optimal strategy" to exist, independent of equity, and regardless of strategy.
Ilias Kastanas
In article <34A407...@math.okstate.edu>,
If I play z = 4/5 and my opponent adopts a wild strategy,
it may be that E, as we know it, is undefined, in the sense of being
"infinity". I cannot win an infinite amount, just arbitrarily large
finite ones; so in that case there is no single optimal strategy, but a
sequence, say, of increasingly good ones.
Why is it wrong to "truncate" per cube level? Why kill the goose
that lays the golden eggs by insisting on the original strategy if it
makes the game never end? It's not mind-reading; after seeing the
opponent make some damaging doubles, I elect to stop the doubling process
forgoing some extra gain, and take my profit as is.
Eh, in case anyone is _worried_, the Hilbert cube has the f.p.
property, and so do its absolute retracts...
OK, I'll think about this!
> So there's the "value" of the game - it's E0(Pos). Now
>if I'm about to roll the dice then E0(CurrentPos) is the approprate
>average of E0(PosAfterPossibleRolls), if I'm about to make a choice
>then E0(Pos) = max(E0(PossibleChoices)), etc, as it should. Presumably
>the "optimal" strategy is to always make the choice that maximizes
>E0. And in, say, situations where there's no contact left one can
>show that this _is_ optimal - if one does this then regardless of
>what your opponent does you will win on average E0(CurrentPos).
>But in general some martingale needs to be L1-bounded or there is
>_no_ such guarantee (and in fact I believe that if the relevant
>gizmo is not L1-bounded then it's not just that we can't prove
>the optimal strategy is ok, I believe in that case it can be proved
>that there _is_ no guarantee available...). The argument so far is
>very soft, but to determine the L1-boundedness we need a much more
>careful analysis. (And if the actual details of the actual numbers
>are important I tend not to see how models of random walks
>on [0,1] can help - there for example it's easy to see what
>P(WIN) is, here it's not. At least I don't see it, and I haven't
>seen any definitions offered yet (although this is the first of
>today's replies that I've read.))
>
> Or so it seems to me.
Ilias
David Ullrich
Ilias Kastanas wrote:
> [...]
> If I play z = 4/5 and my opponent adopts a wild strategy,
> it may be that E, as we know it, is undefined, in the sense of being
> "infinity". I cannot win an infinite amount, just arbitrarily large
> finite ones; so in that case there is no single optimal strategy, but a
> sequence, say, of increasingly good ones.
>
> Why is it wrong to "truncate" per cube level? Why kill the goose
> that lays the golden eggs by insisting on the original strategy if it
> makes the game never end? It's not mind-reading; after seeing the
> opponent make some damaging doubles, I elect to stop the doubling process
> forgoing some extra gain, and take my profit as is.
Well then you're no longer attempting to maximize your
expected gain, which I thought we decided at the start was
what we were trying to do. Never mind. Start here:
I've been thinking about the great debate while things were
offline here - I decided maybe I haven't been entirely clear. People say
[something}, I complain that that doesn't answer the question, people
repeat modified versions of [something]... Could be I never clarified
what "the question" (ie the question that interests me here<g>) is. So:
A _strategy_ for backgammon is a "procedure" that specifies how
we make choices when we have a choice to make. Could be that it involves
flipping a coin, for example correct poker strategy requires some sort
of randomization. My guess is that in fact this is not necessary in
backgammon because there's no hidden information - I conjecture that
if we defined a strategy to be a mapping from the class of all positions
where we have a decision to make to the class of all positions (with
the property that AStrategy(APosition) is one of the positions we can
legally move to from APosition) that would suffice. I think.
Whether the notion of "strategy" in backgammon requires random
choices as in poker or not, a strategy tells us what to do in _every_
position in which we have a choice to make, ok? The notion of abandoning
the optimal strategy when the opponent does something else sort of
doesn't come up - if that's what we're doing then the "optimal" strategy
in question is not the strategy we're following; the strategy we're
following includes _all_ those rules "if the opponent does this then
do that".
There's a question that strikes me as "the interesting question".
It's a precisely defined mathematical question - it's a precisely defined
mathematical question about backgammon itself, not about some mathematical
model. And it's a question that as far as I can see is not addressed by
anything anyone's said, including lots of remarks that sound as though
I'm supposed to think that they answer the question. The question is:
Does there _exist_ an optimal strategy in backgammon?
Now, a lot of people have been talking about optimal strategies
without giving a definition. I'd say that a strategy S0 is optimal if
it has the following property: Suppose you play the game using strategy
S0. Suppose your opponent plays using strategy S. Having fixed both
strategies we now have well-defined random variables X_n , n = 1, 2, ...,
where X_n is the amount you win in the n-th game. (There's a technical
detail left out here, addressed below). I would call the strategy S0
_optimal_ if it is the case that no matter what strategy S the
opponent uses, it is almost surely true that
(*) lim inf (X_1 + ... + X_N) / N >= 0 .
(That's math speak for "almost surely, _on average_ you break
even or better, more or less, eventually".)
That's what an optimal strategy does, it seems to me. It's
easy to see that such a strategy exists in poker, or in backgammon
with a bound on the length of the game or a bound on the size of
the cube. But the existence of an optimal strategy in backgammon
per se is not at all obvious to me.
Why not? For example: Let's suppose for the sake of argument
that S0 _is_ an optimal strategy. Let's suppose that we and the
opponent are both using strategy S0, and let's define X_n as above.
Then E(X_n) = 0, by symettry. And so if E(|X_1|) is finite then a
version of the law of large numbers says that (*) holds, in fact
almost surely the quantity in (*) actually tends to 0. But if
otoh E(|X_1|) = infinity, then another result (cf. Chung "A Course
in Probabilty Theory" Thm 5.4.2) states explicitly that (*) will
_not_ hold. Supposing that there is an "optimal" strategy and
supposing that E(|X_1|) is infinite then the averages in (*) do
_not_ tend to 0, they are unbounded. Even if both players are
using the optimal srategy.
All the comments about how to modify the strategy in this
or that situation say nothing whatever about any of this - "the"
question (the question I've been getting at anyway) is whether
there _exists_ an optimal strategy. If in this case you should
do this instead of that fine, but that just says that some
particular strategy is better than another. Nothing you've said
about martingales, and nothing Bill Taylor's said about convergence
theorems says anything as far as I can see about whether
E(|X_1|) is finite in the real game - I don't see how an
analysis of a model like the one you're talking about
_could_ say that E(|X_1|) is finite. (Otoh it doesn't strike
me as impossible that Bill Daly's comment actually says something
about E(|X_1|) being infinite. But don't quote me on that...)
And the point is that a lot of the "OK, if that happens
then do this" don't help at all. If in fact E(|X_1|) is infinite
for any strategy then there is _no_ collection of extra
sub-stretegies that's going to solve the problem - in that case
no matter _how_ you play the game you cannot be assured of
success (in the sense of (*), an "assurance" that _is_
available in poker and most games.) I suspect some people may
be annoyed at the way I appear to have been ignoring some of
the details of what they've had to say about all this; this
may explain why: Saying how a strategy should be modified in
spoe situation (in a simplified model of the game) doesn't
say anything about the question I've been wondering about.
It seems not impossible that one could show that "always
optimize E0" (where E0 is that fixed-point thing defined below,
unfortunate notation, since whether E0 is the same as the
expected vaue is sort of part of the question) is an optimal strategy
if anything is. If one knew that then one would "simply" need to check
whether the expected value of |X_1| was finite given that
both players are optimizing E0...
(Technical detail: I said that once we've fixed both
players' strategies then X_n is well-defined. This depends on
the fact that the length of the game is almost certainly
finite, _regardless_ of the strategy being used (like even
if both players are trying to extend the game instead of
trying to win.) I suspect that that's true. It would suffice
to show
Lemma In _any_ position there exists a sequence of
dice rolls that will suffice to terminate the game, regardless
of the players' strategies.
Which sounds right, although proving it for the
real game might be tedious.)
Well that's a relief<g>. (So that means I'm using Tychonoff's
theorem or someone else's?)
OK. (Note the addendum elsewhere clarifying what the relevant
constraint is in a position where one side is deciding whether to
accept a double. Also note I'm not sure I got that bit right, although
I think I did. I wrote all this down in detail years ago and now
I can't find it.)
Bill Taylor
This has been a very interesting and worthwhile thread! Long may it continue.
I haven't read the latest lot of follow-ups yet, but I'll post anyway.
Although the existence of somewhat backgammon-like games with
doubling cubes and undefined (i.e. infinite-infinite) expectations was
vaguely known to me, I'd not realized that such things could actually
appear in a real backgammon game! Indeed, I never even knew till just
now that it was possible for both players to simultaneously have checkers
on the bar; though the mechanism is obvious enough once mentioned.
BTW, have any players here ever had this situation arise in a real game?
The mere existence of such a nasty does indeed put the unmodified
concept of game expectation (= game value = equity) beyond definition.
It isn't enough to say "ignoring such cases", or whatever, as even a
tiny probability of this happening makes all expectation calculations
worthless, as David Ulrich has been insisting. (Though I think my
diffusion-style no-volatility game is still safe, as explained before.)
So then, if unmodified expected value is worthless, let us modify it.
The usual thing, is EITHER to observe that there is an effective limit
to the doubling sequence somewhere, either by being embedded in a match,
or by having a cap on (one or both) player's willingness to double beyond
a certain personal limit; OR, by invoking the non-linearity of the
utility of money, which is a mess, and for most people amounts to the
same thing anyway. Some of these effects may well be asymmetric between
the two players, but that can be handled similarly to below.
So let us formally assume there *is* a cap on the amount they can play for,
i.e. a limit on the stake, beyond which no doubles may be made.
Now let us suppose we're in this weird but legal situation where both
players are trying to roll that elusive entry combo, and (possibly)
doubling every time they have the bones. Let us assume symmetry of rolls,
& put
p = P(player about to roll hits winning combo) ; q = 1-p.
(We adopt the simplification that the miracle roll makes a win certain.)
Usually p = 11/36, but we can keep it general.
A simple conditional-prob calculation shows that (if neither drops a cube)
P(player on roll wins) = p/(p+qp) ,
P(player off roll wins) = qp/(p+qp) .
Suppose the stake gets to where we *can* double, but it would be the
last double allowed. Should we do so? (Assume unit current stake.)
E[ winnings | no double ] = (p - qp)/(p + qp) > 0 , and
E[ winnings | double ] = 2.(above) , which is bigger:- therefore double!
Obvious enough. Now suppose we are on roll, and we can double, but if
the opponent redoubles that would be the last one. If we double and
don't hit the magic roll, he should double for sure next time (by above),
so we get...
E[ winnings | no double ] = (p - qp)/(p + qp) , and
E[ winnings | double ] = 2p - 4q(p - qp)/(p + qp) .
So it is better to double if 2p - 4q(p - qp)/(p + qp) > (p - qp)/(p + qp)
which reduces to p > 1/2 .
In the case where p > 1/2 the expected values converge anyway, so we
can ignore that; and in the alternate case, it is better NOT TO DOUBLE.
Again, a highly believable result. So if two doubles remain, it is
better NOT TO double. And by a simple backward induction, if ANY even
number of doubles remain, it is better not to. Interesting, and not
quite trivial.
And of course, this tames the backgammon situation so that expected
value is defined and all the usual equity calculations apply.
No doubt there is a lot more to be said about this; which I await keenly.
-------------------------------------------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
-------------------------------------------------------------------------------
microtome: an instrument that cuts thin slices for microscopic examination
tome: a million of these
-------------------------------------------------------------------------------
David Ullrich
Bill Taylor wrote:
>
> This has been a very interesting and worthwhile thread! Long may it continue.
> I haven't read the latest lot of follow-ups yet, but I'll post anyway.
>
> Although the existence of somewhat backgammon-like games with
> doubling cubes and undefined (i.e. infinite-infinite) expectations was
> vaguely known to me, I'd not realized that such things could actually
> appear in a real backgammon game! Indeed, I never even knew till just
> now that it was possible for both players to simultaneously have checkers
> on the bar; though the mechanism is obvious enough once mentioned.
> BTW, have any players here ever had this situation arise in a real game?
Yes, it happens all the time that both players are on the bar.
Well, not all the time, but it certainly happens. (What never happens
is that both players are closed out.) Not that I see what this has
to do with "the" question (where "the" question is by definition the
one I find interesting<g> - see my recent reply to Ilias.) Does there
exist an optimal strategy?
> The mere existence of such a nasty does indeed put the unmodified
> concept of game expectation (= game value = equity) beyond definition.
> It isn't enough to say "ignoring such cases", or whatever, as even a
> tiny probability of this happening makes all expectation calculations
> worthless, as David Ulrich has been insisting. (Though I think my
> diffusion-style no-volatility game is still safe, as explained before.)
>
> So then, if unmodified expected value is worthless, let us modify it.
It still seems to me like you're focussing on the details, and
on the details in a simplified model of the game at that. Unless you
can explain to me how this shows that E(|X_1|) is finite, where
X_1 is defined in that post to Ilias.
> The usual thing, is EITHER to observe that there is an effective limit
> to the doubling sequence somewhere, either by being embedded in a match,
> or by having a cap on (one or both) player's willingness to double beyond
> a certain personal limit; OR, by invoking the non-linearity of the
> utility of money, which is a mess, and for most people amounts to the
> same thing anyway. Some of these effects may well be asymmetric between
> the two players, but that can be handled similarly to below.
>
> So let us formally assume there *is* a cap on the amount they can play for,
> i.e. a limit on the stake, beyond which no doubles may be made.
If the cap is agreed on in advance and is the same for both
players then the problems that concern me go away. But this game is
very different from actual backgammon. (And if one thinks that this
game is more like actual backgammon in the actual real world that's
mot so either. In an actual game an honest man cannot take a double
if he cannot afford to pay but a scoundrel can (and do!) - ths means
different rules apply and an actual analysis would be complicated.
It's clear it gives an advantage to the scoudrel, and in any case
this is not backgammon.)
> Now let us suppose we're in this weird but legal situation where both
> players are trying to roll that elusive entry combo,
What does this one position have to do with the general
question?
> and (possibly)
> doubling every time they have the bones. Let us assume symmetry of rolls,
> & put
> p = P(player about to roll hits winning combo) ; q = 1-p.
>
> (We adopt the simplification that the miracle roll makes a win certain.)
> Usually p = 11/36, but we can keep it general.
>
> A simple conditional-prob calculation shows that (if neither drops a cube)
>
> P(player on roll wins) = p/(p+qp) ,
> P(player off roll wins) = qp/(p+qp) .
>
> Suppose the stake gets to where we *can* double, but it would be the
> last double allowed. Should we do so? (Assume unit current stake.)
>
> E[ winnings | no double ] = (p - qp)/(p + qp) > 0 , and
> E[ winnings | double ] = 2.(above) , which is bigger:- therefore double!
>
> Obvious enough. Now suppose we are on roll, and we can double, but if
> the opponent redoubles that would be the last one. If we double and
> don't hit the magic roll, he should double for sure next time (by above),
> so we get...
>
> E[ winnings | no double ] = (p - qp)/(p + qp) , and
> E[ winnings | double ] = 2p - 4q(p - qp)/(p + qp) .
>
> So it is better to double if 2p - 4q(p - qp)/(p + qp) > (p - qp)/(p + qp)
>
> which reduces to p > 1/2 .
>
> In the case where p > 1/2 the expected values converge anyway, so we
> can ignore that;
Aha. _Why_ can we ignore that case? (Could be I'm misunderstanding
what you mean when you say "the expected values converge" - I'm assuming
that we're analyzing this simplified game with a cap on the number of
doubles, then letting the number of allowable doubles tend to infinity,
and you're saying the expected values converge when that happens.)
You never gave a precise
definition of exactly what you were trying to prove, so I can't be
certain whether we "can" ignore this or not. But if we're trying to
demonstrate something like what I guess we're trying to demonstrate
I don't see why this is ignorable: (i) suppose that Y_n is a random
variable, Y_n -> Y in some sense, and E(Y_n) -> v. It does not
follow that E(Y) = v. (ii) even if E(Y) = v it does not follow that
v is the "expected" value of Y in the sense in which non-mathematicians
understand the term: the law of large numbers need not hold (and
in fact _does_ not unless we know something.)
> and in the alternate case, it is better NOT TO DOUBLE.
Is "better" in what sense? I can imagine various things that
"it is better" could mean, which are not equivalent (and some of
which may or may not make sense here).
You seem to continue to claim that you've proved something.
Could you state exactly what it is that you're proving? If you use
words like "should", "is better to", you need to include precise
definitions of those words. (I _can_ prove, that, say, there
exists an optimal strategy in poker (not that this is due to me).
And I can define _exactly_ what I mean by this. And I do _not_
see how to prove that there exists an optimal strategy in
backgammon in the same sense. DO you mean to be claiming that
you've shown there exists an optimal strategy in this sense
(I gave a precise definiton in that post to Ilias yesterday)?
My guess is that this is not what you're claiming. But if not
you should say what you _are_ claiming to have proved, _including_
a precise statement of what you mean when you say it is "better"
to do one thing than another. A person has a better chance of
deciding whether he believes a proof is correct if the statement
of the theorem is included.))
> Again, a highly believable result. So if two doubles remain, it is
> better NOT TO double. And by a simple backward induction, if ANY even
> number of doubles remain, it is better not to. Interesting, and not
> quite trivial.
>
> And of course, this tames the backgammon situation so that expected
> value is defined and all the usual equity calculations apply.
What does this mean, exactly?
> No doubt there is a lot more to be said about this; which I await keenly.
Yes, there's more to be said. Like you could explain the things
I keep asking you to explain. This really _is_ remininding me of the
perennial "proofs" that 0.999... = 1 where the author omits the
definition of exactly what is _meant_ by the statement "0.999... = 1",
thinking we can prove it's true before saying what it means.
I may be missing something, but it looks to me like I keep
asking what these calculations actually mean and you keep replying
with more calculations, not answering the question. As far as I'm
concerned "the" question is whether there exists an optimal strategy.
Nobody's said why there does exist such a thing. People give reasons
why this might be doubtful and you change the game to avoid the
particular objection, or you revise the calculations so it comes
out right in that case. But all you ever do is talk about this
or that particular situation - whether your fix is valid or not
in any particular case doesn't say anything about how you know
that there exists an optimal strategy, what you mean by "better",
etc.
In order that an optimal strategy exist in the sense of
the definition I gave yesterday it is necessary that E(|X_1|) be
finite. That's a theorem, regardless of what you say about what
a person should do when both players are on the bar.
(The last time I thought about this was years ago, which
explains why some of what I have to say about this is a little
more clearly formulated than a week or so ago. Also I was more
of a sissy back then - the idea of actually showing E(|X_1|)
is finite, using, say, E0 to define X_1, doesn't strike me as
nearly as impossible as it seemed way back then. But it has to
be done - if E(|X_1|) is always infinite then there is no
optimal strategy, and that _does_ say something about whether
one can expect to win on average, in the long run, by playing
"perfectly".)
steve_harris
In article , ger...@indigo.ie says...
>E = (11/36)(1) - (11/36)(25/36)(2) + (11/36)(25/36)^2(4) - ...
>
>E = A( 1 - 2R + 4R^2 - 8R^3 + ... )
> (where A=11/36, R=25/36)
>
>E = A.G = A.Sigma[i=0 to Inf.](-2R)^i
>
>G = 1 - 2RG
>
>Where R = 25/36, G=36/86 we get E = 11/86
>
Do I need a scientific calculator to play this game?
(Just a joke, guys. Happy New Year!)
Gerry Quinn
Yes, I don't play much Backgammon, and I forgot there are two dice!!
However, the non-convergent expectation is what interests me. I
hadn't realised that was possible.
I know that the result of a divergent series cannot safely be defined,
but what about this:
Extra points expected after doubling (cube currently at 1); it is
assumed that both players will always double when it is their move:
E = (11/36)(1) - (11/36)(25/36)(2) + (11/36)(25/36)^2(4) - ...
E = A( 1 - 2R + 4R^2 - 8R^3 + ... )
(where A=11/36, R=25/36)
E = A.G = A.Sigma[i=0 to Inf.](-2R)^i
G = 1 - 2RG
Where R = 25/36, G=36/86 we get E = 11/86
Could this be correct? It seems like a sensible figure...
Also, perhaps some of you senior wranglers could comment on whether
the uncharacteristic behaviour occurs because the possible outcomes
are not a continuum, so the 0.8 'winning probability' criterion for
doubling does not apply. There are only four possible 'winning
probabilities' with limited transitions between them:
0.00 --> 0.41 <--> 0.59 --> 100
Gary Wong
mat...@math.canterbury.ac.nz (Bill Taylor) writes:
> Although the existence of somewhat backgammon-like games with
> doubling cubes and undefined (i.e. infinite-infinite) expectations was
> vaguely known to me, I'd not realized that such things could actually
> appear in a real backgammon game! Indeed, I never even knew till just
> now that it was possible for both players to simultaneously have checkers
> on the bar; though the mechanism is obvious enough once mentioned.
> BTW, have any players here ever had this situation arise in a real game?
Not I :-) The first I heard of it was in Paul Tanenbaum's article here
("Subject: Extremely theoretical") and it was apparently independently
discovered earlier by Bob Floyd.
> The mere existence of such a nasty does indeed put the unmodified
> concept of game expectation (= game value = equity) beyond definition.
> It isn't enough to say "ignoring such cases", or whatever, as even a
> tiny probability of this happening makes all expectation calculations
> worthless, as David Ulrich has been insisting. (Though I think my
> diffusion-style no-volatility game is still safe, as explained before.)
Hrmmm... I agree that the possibility of many contact positions leading
to one where the equity is undefined can be used to argue that any of those
contact positions also have undefined equity. However, even in Tanenbaum's
position, which must be among the most exotic of badly behaved equities, the
random variable X (points won by the player on roll) follows a nice simple
distribution: P(X=1) = 11/36, P(X=-2) = 25/36 x 11/36, P(X=4) = 25/36 x
25/36 x 11/36, etc. etc. E(X) is not defined, but virtually any other
property of X we care to inspect (eg. P(X>0)) is.
David Ullrich questions whether the lack of E(X) implies that no "optimal
strategy" can exist for backgammon (for suitable definition of "optimal
strategy"). I assert that optimal strategies still do exist: let us call a
strategy "optimal" if and only if there exists no opponent's strategy that
dominates it. To define domination: let the random value X follow the
distribution (points won by player using strategy S after n games) -
(points won by player using strategy O after n games). It has already been
established that there exist strategies S and O such that X's distribution
is well defined, but E(X) is not. Therefore our definition of dominance
may not include E(X) if it is to include those strategies. Instead, let's
define strategy S as dominating strategy O if and only if the limit P(X>0)
is greater than 0.5 as n increases without bound. (As an aside: it is
quite possible that for a "poor" strategy S against a "better" strategy O,
P(X>0) is indeed > 0.5 for small n, but < 0.5 for large n. For instance, a
strong back game strategy might win more than 50% of games against some
players, but those that are won are typically single games and those that
are lost are gammons. The random distribution is skewed with the mode
favouring the back game player, but with a longer tail (more points)
favouring the other player, which means the other player's strategy
dominates overall. A strategy that does well at double match point does
not necessarily dominate others in money play).
Anyway, with this definition of an optimal strategy, does the lack of E(X)
mean optimal strategies cannot exist? Let us partition the class of all
games into two sets: those that contained troublesome positions T, and
those that did not T'. We classify a position P as "troublesome" if and
only if the probability of the game reaching the same position P in the
future (which is the only way a game can last indefinitely) with the cube
doubled by a factor of F is at least 1/F. This is clearly true for Paul
and Bob's position because F = 4 (two doubles) and it repeats with
probability P = 25/36 x 25/36 for P > 1/4. Note that this definition
depends on the strategies of the players; if either player does not double,
then they'll end up holding the cube and F = 1, so the position will not be
troublesome. The point is that T and T' partition the set, so X can be
expressed as X|T + X|T', the sum of the distributions of troublesome and
non-troublesome games. E(X_P|T'), the equity of a position P given that
the game completes without encountering a troublesome position is well
defined and classical backgammon theory applies; E(X_P|T) is not defined.
For an optimal strategy, E(X|T') >= 0 for all i and P(X|T' >0) >= 0.5. For
the set of troublesome positions we can't rely on E(X_i|T), but note that
there are only 4 strategies in a troublesome position, namely: a) always
double, always take; b) always double, always drop; c) never double, always
take; d) never double, always drop. We know that the position is an easy
take for money so strategies a) and c) dominate b) and d); it is also a
disadvantage to hold the cube (because then the other player gains leverage
from the cube and you don't) and so a) also dominates c). (See my earlier
article for more rigorous investigation of whether to double/redouble).
Any other strategy (eg. one that sometimes takes, sometimes drops) can be
considered a "weighted average" of two or more of the above strategies.
Notice that no possible strategy dominates a), and therefore a) alone is
optimal for this partition. An optimal strategy therefore incorporates a)
in troublesome positions. P(X|T >0) >= 0.5 against all four possible
strategies (and their combinations). Note that P(X|T >0) >= 0.5 and P(X|T'
>0) >= 0.5; since T and T' are disjoint, P(X|T >0) and P(X|T' >0) represent
two (upper and lower) bounds on P(X>0) and therefore P(X>0) >= 0.5. And so
a strategy that was optimal for classical backgammon and uses a) in
troublesome positions is still optimal overall.
> So then, if unmodified expected value is worthless, let us modify it.
>
> The usual thing, is EITHER to observe that there is an effective limit
> to the doubling sequence somewhere, either by being embedded in a match,
> or by having a cap on (one or both) player's willingness to double beyond
> a certain personal limit; OR, by invoking the non-linearity of the
> utility of money, which is a mess, and for most people amounts to the
> same thing anyway. Some of these effects may well be asymmetric between
> the two players, but that can be handled similarly to below.
>
> So let us formally assume there *is* a cap on the amount they can play for,
> i.e. a limit on the stake, beyond which no doubles may be made.
>
[maths deleted]
>
> Again, a highly believable result. So if two doubles remain, it is
> better NOT TO double. And by a simple backward induction, if ANY even
> number of doubles remain, it is better not to. Interesting, and not
> quite trivial.
That analysis is quite true, but applies only when the number of points
remaining is a power of 2 (eg. it is correct to turn a 1 cube in this position
at 8-away, 8-away; but not 16-away, 16-away). It is not clear whether it
is clear to turn a 4 cube to 8 at 12-away, 12-away for instance (because the
other player will have some recube vig, unlike -8, -8; but not as much as
-16, -16 because of the 4 wasted points). At uneven match scores, the
cube handling becomes even trickier (at 100-away, 5-away, the trailer is
very eager to turn a 4 cube to 8; does this mean that the leader should hold
the cube at 2?)
When the position was originally presented, I posted a list of the sums to
infinity with various limits on the cube value (for various integers, not just
powers of 2) representing the equity of the player on roll in a match where
both players needed that many points to win. I had a hunt with Deja News
just now but can't find a thing... no doubt our news server propagation is
to blame again :-\ I don't have the figures any more but they verify your
argument that odd powers of 2 are doubles and even powers of 2 are not;
they represent local maxima and minima in the equity against match score
assuming doubles are taken whenever possible. The position is always a
take if the match is even; but not necessarily in other cases (eg. I suspect
the trailer holding a 32 cube at 66-away, 34-away has a double/drop).
What all the arguments so far have neglected is that the player that enters
first has excellent chances of winning a gammon, so there's every possibility
that the cube handling should really be the _other_ way around (double
odd powers of 2 away, hold evens) to reflect the fact that the equity of the
player who enters may be closer to twice the cube value.
Yet another assumption that that argument makes is that the value of a point
is constant -- it is not, in general (not in match play, anyway). Some number
of points giving you a lead in the match are far more valuable than extending
your lead by that many points: suppose I've made it to the final round of a
tournament and am now playing the world champion (hey, it's a hypothetical
situation, I'm allowed to dream :-) in a 101 point match to win $1000.
Naturally the champion is a significantly better player than me so in the
long match I'm a massive underdog. But the tournament director is crooked
and has a proposition to me: "psst... slip me $500 and I'll give you 50 points"
ie. I'll be leading the match 51-away, 101-away. Assuming I was sufficiently
dishonest, I'd be insane to turn the offer down. But now consider the case
where I somehow managed to win 51 points against the odds, so I was leading
the match 50-away, 101-away before the offer of $500 for 50 points was made.
Superficially it looks like 50 points here would be very valuable to me,
winning the match outright, but considering it for a moment you realise that
I'm far better off playing on from here; I have very little match equity to
make up to win the match and am better off doing it myself than paying $500
for it (unless of course I'm sufficiently bad that the world champion is still
a favourite trailing 101-away). What I'm trying to say about this position
here is that as the cube goes higher, its relative worth dwindles. If we're
playing in a long match and are even at 71-away, 71-away, then turning the
cube from 32 to 64 really doesn't affect the match equity nearly as much as
the big numbers might suggest. The fact is that winning 32 points (bringing
you to lead 39-away, 71-away) is nearly as good as winning 64 (leading
7-away, 71-away) -- you will be a massive favourite to win the match,
either way. So the cube shouldn't be seen so much doubling the stakes, as
raising the match equity on the line from 99.9% to 99.99% to 99.999% -- ie.
sod all.
> And of course, this tames the backgammon situation so that expected
> value is defined and all the usual equity calculations apply.
Quite right :-) Kill the dragons ;-)
Ilias Kastanas
In article <34A97C...@math.okstate.edu>,
David Ullrich <ull...@math.okstate.edu> wrote:
>Ilias Kastanas wrote:
>> [...]
>> If I play z = 4/5 and my opponent adopts a wild strategy,
>> it may be that E, as we know it, is undefined, in the sense of being
>> "infinity". I cannot win an infinite amount, just arbitrarily large
>> finite ones; so in that case there is no single optimal strategy, but a
>> sequence, say, of increasingly good ones.
>>
>> Why is it wrong to "truncate" per cube level? Why kill the goose
>> that lays the golden eggs by insisting on the original strategy if it
>> makes the game never end? It's not mind-reading; after seeing the
>> opponent make some damaging doubles, I elect to stop the doubling process
>> forgoing some extra gain, and take my profit as is.
> Well then you're no longer attempting to maximize your
>expected gain, which I thought we decided at the start was
>what we were trying to do. Never mind. Start here:
How could I get the maximum, if it is infinity?... For every m
there being a strategy that achieves at least m...?!
> I've been thinking about the great debate while things were
>offline here - I decided maybe I haven't been entirely clear. People say
>[something}, I complain that that doesn't answer the question, people
>repeat modified versions of [something]... Could be I never clarified
>what "the question" (ie the question that interests me here<g>) is. So:
Good, let's try to clarify.
> A _strategy_ for backgammon is a "procedure" that specifies how
>we make choices when we have a choice to make. Could be that it involves
>flipping a coin, for example correct poker strategy requires some sort
>of randomization. My guess is that in fact this is not necessary in
>backgammon because there's no hidden information - I conjecture that
>if we defined a strategy to be a mapping from the class of all positions
>where we have a decision to make to the class of all positions (with
>the property that AStrategy(APosition) is one of the positions we can
>legally move to from APosition) that would suffice. I think.
>
> Whether the notion of "strategy" in backgammon requires random
>choices as in poker or not, a strategy tells us what to do in _every_
>position in which we have a choice to make, ok? The notion of abandoning
>the optimal strategy when the opponent does something else sort of
>doesn't come up - if that's what we're doing then the "optimal" strategy
>in question is not the strategy we're following; the strategy we're
>following includes _all_ those rules "if the opponent does this then
>do that".
I agree. I wasn't "abandoning" it, though; I was describing good
strategies in a situation lacking a single optimal one.
> There's a question that strikes me as "the interesting question".
>It's a precisely defined mathematical question - it's a precisely defined
>mathematical question about backgammon itself, not about some mathematical
>model. And it's a question that as far as I can see is not addressed by
>anything anyone's said, including lots of remarks that sound as though
>I'm supposed to think that they answer the question. The question is:
>
> Does there _exist_ an optimal strategy in backgammon?
>
> Now, a lot of people have been talking about optimal strategies
>without giving a definition. I'd say that a strategy S0 is optimal if
>it has the following property: Suppose you play the game using strategy
>S0. Suppose your opponent plays using strategy S. Having fixed both
>strategies we now have well-defined random variables X_n , n = 1, 2, ...,
>where X_n is the amount you win in the n-th game. (There's a technical
>detail left out here, addressed below). I would call the strategy S0
>_optimal_ if it is the case that no matter what strategy S the
>opponent uses, it is almost surely true that
>
>(*) lim inf (X_1 + ... + X_N) / N >= 0 .
>
> (That's math speak for "almost surely, _on average_ you break
>even or better, more or less, eventually".)
And, I suppose, with " >= a" (a > 0) not achievable -- automatic
for our symmetric game.
> That's what an optimal strategy does, it seems to me. It's
>easy to see that such a strategy exists in poker, or in backgammon
>with a bound on the length of the game or a bound on the size of
>the cube. But the existence of an optimal strategy in backgammon
>per se is not at all obvious to me.
>
> Why not? For example: Let's suppose for the sake of argument
>that S0 _is_ an optimal strategy. Let's suppose that we and the
>opponent are both using strategy S0, and let's define X_n as above.
>Then E(X_n) = 0, by symettry. And so if E(|X_1|) is finite then a
>version of the law of large numbers says that (*) holds, in fact
Yes; the weak law says "in probability", the strong adds "a.s."
>almost surely the quantity in (*) actually tends to 0. But if
>otoh E(|X_1|) = infinity, then another result (cf. Chung "A Course
>in Probabilty Theory" Thm 5.4.2) states explicitly that (*) will
Is that the book where Chung invites us to speculate on whether
Levy's 0-1 law is "obvious!" or "incredible!" ? I have to read it some day.
>_not_ hold. Supposing that there is an "optimal" strategy and
>supposing that E(|X_1|) is infinite then the averages in (*) do
>_not_ tend to 0, they are unbounded. Even if both players are
>using the optimal srategy.
I suppose you mean results about its finiteness being necessary for
the strong law; E(|X_1|) = inf implies P("S_n/n has a finite limit") =0,
and in fact that for any sequence c_n, lim_sup |S_n/n - c_n| = inf.
Sure. Actually, if E(X_1+) = inf and E(X_1-) < inf we do have
the limit S_n/n -> inf, a.s. And anyway, if b_m/m is increasing then
lim_sup |S_n|/b_n is = 0, [= inf], as Sum P(|X_1| >= b_n) is < inf, [= inf].
No quarrel here. Eh, if this happens when both are using the optimal strategy,
then the _definition_ of the latter is violated...
Okay, the "point" about (sub)martingales is that if sup E(X_n+) < inf
they converge a.s. ("bounded => convergent"), true... to a limit X with E(|X|)
< inf. And the basic martingale fact, E(X_N) = E(X_0), holds for _bounded_
stopping times N. But of course we do have results about L_p convergence,
including L_1... and also extensions of the "fact" to unbounded N.
> It seems not impossible that one could show that "always
>optimize E0" (where E0 is that fixed-point thing defined below,
>unfortunate notation, since whether E0 is the same as the
>expected vaue is sort of part of the question) is an optimal strategy
>if anything is. If one knew that then one would "simply" need to check
>whether the expected value of |X_1| was finite given that
>both players are optimizing E0...
>
> (Technical detail: I said that once we've fixed both
>players' strategies then X_n is well-defined. This depends on
>the fact that the length of the game is almost certainly
>finite, _regardless_ of the strategy being used (like even
>if both players are trying to extend the game instead of
>trying to win.) I suspect that that's true. It would suffice
>to show
> Lemma In _any_ position there exists a sequence of
>dice rolls that will suffice to terminate the game, regardless
>of the players' strategies.
> Which sounds right, although proving it for the
>real game might be tedious.)
Eh... for random walks already, if E(|X_1|) < inf and E(N) < inf
then E(S_N) = E(X_1) E(N). For submartingales we can replace the first
condition by E(|X_n+1 - X_n|) bounded a.s., and conclude E(X_N) >= E(X_0).
We go on to theorems valid for N < inf _and_ N = inf (notation:
X_inf is lim X_n). For (uniformly integrable) submartingales, we have
E(X_0) <= E(X_N) <= E(X_inf). And for (nonnegative) supermartingales,
E(X_0) >= E(X_N), including N = inf.
Now the point I want to make is about types of convergence.
Example: Start a symmetric random walk at S_0 = 1; let N = inf{i: S_i =0},
and define X_n = S_(N cap n). Then X_n -> X_inf a.s., and X_inf = 0;
but E(X_n) = 1 for all n, so this a.s. convergence cannot occur in L_1.
(By the way, this shows that the "basic fact" doesn't always hold for
N = inf; we need the theorems as stated above).
Example: Let X_0 = 0. If X_n-1 = 0, then X_n = 1 or -1 with probability
1/2n each; else = 0. If X_n-1 != 0, then X_n = nX_n-1 with probability
1/n; else = 0. We then have P(X_n = 0) >= 1 - 1/n, while P( X_n = 0 for
n >= B) = 0. So X_n -> 0 in probability, but not a.s.
(I skip an example where expected values converge in L_1 but not a.s.)
Of course these are elementary facts of Real Analysis; I couched
them in probabilistic terms to ask, do we _have_ to go by a.s. or L_1?
Why not "in probability"? Each has its idiosyncracies. Say, X_n/n -> 0
happens a.s. iff E(|X_1|) < inf; it happens in probability iff
nP(|X_1| > n) -> 0. Is the latter chopped liver?
Consider something even more familiar:
Example: (St. Petersburg) Each X_n is = 2^k with probability 1/2^k; so
E(X_1) = inf. We have (**) S_n /n*log(n) -> 1 in probability; I posted
a proof some time ago. Again, this convergence is not a.s., since we have
lim_sup S_n /n*log(n) = inf a.s.
What I'm suggesting is: (**) will do as a "law of large numbers".
Never mind a.s.! Yes, (**) does have operational content: it looks behind
E(X_1) = inf, "fixed fair-price per game is inf (?!)", and tells me: after n
games I can expect n*log(n), so fair-price is log(n). "Inf" really "is"
log(n). If I play n = 1000 times (OK, 1024), an entry fee log(n) = 10
is break-even. If I can play longer than that, it's a good proposition;
if I can only play a couple of hundred times, I should stay away. Or, if
I'm offering the game and I find a taker at that fee, I should limit the
number of games accordingly. Yes, things do depend on fee level!
One can easily modify the example and make it hold not for n*log(n)
but for n*log(log(n)), or n/log(n) ... and so on. Nothing unique about it.
In other words, E(|X|) = inf and the attendant lack of a strong
law does not necessarily preclude analyzing the situation and coming up with
an indicated course of action!
...
>> >> That's interesting... Brouwer as is, or Tychonoff's version
>> >> (Schauder in the case of Banach spaces)?
>> >
>> > I dunno whose theorem it is, I made it up (non-mathematicians
>> >should note I'm allowed to do that as long as I include a proof):
>> >Any continuous map from an infinite product of compact intervals to
>> >itself has a fixed point (follows trivially from the version for finite
>> >products.)
>>
>> Eh, in case anyone is _worried_, the Hilbert cube has the f.p.
>> property, and so do its absolute retracts...
>
> Well that's a relief<g>. (So that means I'm using Tychonoff's
>theorem or someone else's?)
Hmm, it's a safe bet that if anybody _was_ worried, it wasn't you!...
Tychonoff is about locally convex topological vector spaces -- pro-
bably not needed here.
In any case, to focus the issue, here is a trivial discretized
version: a +/-1 random walk from 0, -2 being loss and +2 win. At +1, no
doubling, my E is 1/2. With doubling allowed, if I do so at +1 then
a) opponent (accepts and) never doubles: E = 1 (same with opponent resigning)
b) opponent doubles at -1: easily, E = 4/5; better for her than (a).
c) opponent doubles at 0: E = inf. If I truncate my strategy at n = 0
(stop doubling after her first one), E_0 = 1. If I do so at n = 1,
E_1 = 5/3. Generally, E_n = 2(4/3)^n -1; it gets better and better. And
I don't _have_ to truncate; I can enjoy the monotonicity all the way.
d) opponent doubles at +1(!): (no, without "keeping the cube"). If we
both persist, this is ill-defined, the cube never settling! I can drive
the cube as high as I want and then truncate; much better for me than (c).
Do you feel there is a problem with (c), as to the (untruncated)
strategy being optimal? What about (d), no "optimal" strategy but ever-
better ones since the opponent is "giving it all away"?
Ilias
David Ullrich
Ilias Kastanas wrote:
>
> In article <34A97C...@math.okstate.edu>,
> David Ullrich <ull...@math.okstate.edu> wrote:
> >Ilias Kastanas wrote:[...]
> >expected gain, which I thought we decided at the start was
> >what we were trying to do. Never mind. Start here:
>
> How could I get the maximum, if it is infinity?... For every m
> there being a strategy that achieves at least m...?!
Um, right. I think we're just running into the problems that
arise when we talk about things that we don't know exist.
Yes it is. I never said that there _was_ an optimal strategy -
the existence of such a thing is exactly what I'm wondering about.
Right. But I don't see the point to the point. Hmm, first, your
X_n is not the same as the X_n's I defined above - those X_n's are not
a martingale, they're iid random variables, X_n being the outcome of
the n'th game. So maybe you should say what X_n you're talking about
(maybe this becomes clear below). Exactly what is X_n here (and whatever
it is, how do you know that sup E(X_n+) is finite?)
It appears that you're talking about a single game, and
X_n has something to do with the state of that game after n moves.(???)
I'm not certain exactly what X_n is here - it's certainly not the
same thing as the expected outcome of the n-th game.
> > It seems not impossible that one could show that "always
> >optimize E0" (where E0 is that fixed-point thing defined below,
> >unfortunate notation, since whether E0 is the same as the
> >expected vaue is sort of part of the question) is an optimal strategy
> >if anything is. If one knew that then one would "simply" need to check
> >whether the expected value of |X_1| was finite given that
> >both players are optimizing E0...
> >
> > (Technical detail: I said that once we've fixed both
> >players' strategies then X_n is well-defined. This depends on
> >the fact that the length of the game is almost certainly
> >finite, _regardless_ of the strategy being used (like even
> >if both players are trying to extend the game instead of
> >trying to win.) I suspect that that's true. It would suffice
> >to show
> > Lemma In _any_ position there exists a sequence of
> >dice rolls that will suffice to terminate the game, regardless
> >of the players' strategies.
> > Which sounds right, although proving it for the
> >real game might be tedious.)
>
> Eh... for random walks already, if E(|X_1|) < inf and E(N) < inf
> then E(S_N) = E(X_1) E(N).
Um. I defined X_1 to be the outcome of the first game. We need to
know that the first game terminates before this makes any sense. In
particular X_1 needs to be defined a.s. before it _has_ an expected
value, hence before we can deduce anything from the properties of
its expected value. The point to the "technical detail"/Lemma is
to suggest that a person could actually _prove_ that an _actual_
game of actual backgammon must a.s. terminate. Was talking about
backgammon, not that brownian motion thing. Seems clear that the
game must terminate a.s., but one might want to actually prove this.
??? I would've said E(S_N) = E(X_1 * N) - maybe that's wrong, maybe
the two are obviously the same, dunno much probability.
> For submartingales we can replace the first
> condition by E(|X_n+1 - X_n|) bounded a.s., and conclude E(X_N) >= E(X_0).
Right. The question (ok, _a_ question) is whether it's any consolation
to the guy to know that his expected gain is positive, if its also almost
certain that at some point he will lose his shirt.
> We go on to theorems valid for N < inf _and_ N = inf (notation:
> X_inf is lim X_n). For (uniformly integrable) submartingales, we have
> E(X_0) <= E(X_N) <= E(X_inf). And for (nonnegative) supermartingales,
> E(X_0) >= E(X_N), including N = inf.
>
> Now the point I want to make is about types of convergence.
>
> Example: Start a symmetric random walk at S_0 = 1; let N = inf{i: S_i =0},
> and define X_n = S_(N cap n). Then X_n -> X_inf a.s., and X_inf = 0;
> but E(X_n) = 1 for all n, so this a.s. convergence cannot occur in L_1.
Precisely. And if you took a slightly modified example you get
inf(X_n) = -infinity a.s., in spite of the fact that E(X_n) = 1. Hence
my skepticism about why E(X_n) = 1 is really what we should be worried
about.
> (By the way, this shows that the "basic fact" doesn't always hold for
> N = inf; we need the theorems as stated above).
Couldn't find "basic fact" above - which basic fact were you referring
to? Sorry.
Depends on what you mean by "indicated". Presumably taking the
"indicated" action is better than taking some contraindicated action.
Better how? I don't see how it can be that much "better", since
E(|X_1|) = infinity _does_ imply that inf(S_n/n) = - infinity.
A perfect poker player can play forever and know that unless he
gets unreasonably unlucky he will not do much worse than break even on
average, and will come closer to at least breaking even the longer he
plays. If E(|X_1|) is infinite (not that I'm saying it is) then
backgammon simply does not have this property - a player who always
makes the "indicated" move _will_ eventually find that he's
lost an average of $1000000 per game even though he was playing for
nickels (unless he gets unreasonably lucky). Don't see what good
it does to know what action is "indicated", given this.
(No, of course this has very little to do with the actual
game in the actual world. One could say the same about a lot of
models of a lot of things. It _does_ it seems to me say something
about the validity of models of backgammon where we just assume
that there is a thing which deserves to be called "P(WIN)".
P(WIN) depends on what strategy the players are using - if we're
talking about P(WIN) independent of this we must be assuming
perfect play, on our side at least. And if there's no such thing
as "perfect play" then we don't know what P(WIN) is anymore.
Hence my original objection to statements about how we
should double when P(WIN) > this or that.)
> ...
> >> >> That's interesting... Brouwer as is, or Tychonoff's version
> >> >> (Schauder in the case of Banach spaces)?
> >> >
> >> > I dunno whose theorem it is, I made it up (non-mathematicians
> >> >should note I'm allowed to do that as long as I include a proof):
> >> >Any continuous map from an infinite product of compact intervals to
> >> >itself has a fixed point (follows trivially from the version for finite
> >> >products.)
> >>
> >> Eh, in case anyone is _worried_, the Hilbert cube has the f.p.
> >> property, and so do its absolute retracts...
> >
> > Well that's a relief<g>. (So that means I'm using Tychonoff's
> >theorem or someone else's?)
>
> Hmm, it's a safe bet that if anybody _was_ worried, it wasn't you!...
Um, yes, I actually do know the difference between a proof and a
non-proof, in a context where we know what the words mean.
> Tychonoff is about locally convex topological vector spaces -- pro-
> bably not needed here.
>
> In any case, to focus the issue, here is a trivial discretized
> version: a +/-1 random walk from 0, -2 being loss and +2 win. At +1, no
> doubling, my E is 1/2. With doubling allowed, if I do so at +1 then
Focussing on an understandable version seems like a good idea.
But I don't understand the rules of the game yet. You said "discretized" -
presumably you're not talking about contniuous time? What I don't understand
is who has the right to double when, whether there is more than one "turn"
between succesive dice rolls, etc. Possibly I could figure out the rules by
seeing what rules give the numbers you cite, or you could just explain the
game.
> a) opponent (accepts and) never doubles: E = 1 (same with opponent resigning)
> b) opponent doubles at -1: easily, E = 4/5; better for her than (a).
> c) opponent doubles at 0: E = inf. If I truncate my strategy at n = 0
> (stop doubling after her first one), E_0 = 1. If I do so at n = 1,
> E_1 = 5/3. Generally, E_n = 2(4/3)^n -1; it gets better and better. And
> I don't _have_ to truncate; I can enjoy the monotonicity all the way.
> d) opponent doubles at +1(!): (no, without "keeping the cube"). If we
> both persist, this is ill-defined, the cube never settling! I can drive
> the cube as high as I want and then truncate; much better for me than (c).
>
> Do you feel there is a problem with (c), as to the (untruncated)
> strategy being optimal? What about (d), no "optimal" strategy but ever-
> better ones since the opponent is "giving it all away"?
The definition I gave for "optimal strategy" involved a few
quantifiers. I defined S0 to be optimal if it has the property that
if I use S0 then no matter _what_ strategy S the opponent uses, I
will have
(*) lim inf (X_1 + ... + X_n) / n >= 0 .
(Note that the _definition_ of X_n depends on S0 and S.) It can certainly
happen that if the opponent uses a bad strategy then the lim inf in
(*) is +infinity. This would not be a bad thing - it's also perfectly
consistent with my definition of "optimal strategy".
The bit about "if E(|X_1|) = infinity then (*) fails and that's
a bad thing was assuming that _both_ players are using the _same_ strategy
S0 - if they're using the same strategy and E(|X_1|) = infinty then
the lim inf in (*) is - infinity, which is bad. But my saying this does not
imply that I think (c) would be bad, because in (c) the players are not
using the same strategy.
(But if E(|X_1|) = infinity for _any_ S0, assuming both players
are using S0, then that _does_ say that backgammon's hopeless. Supposing
this, then (c) doesn't come up: in (c) we have the opponent using a bad
strategy, and the fact that we can win if the opponent plays poorly proves
nothing. If E(|X_1|) = infinity for _any_ S0, assuming both players
are using S0, then no matter what I do there is a strategy available to
the opponent that will make things very bad for me.
Hence the earlier bit about "mindreading": When you say
"assuming you do this and the opponent does that" I don't see what
it proves, since you don't know what the opponent _is_ going to
do in an actual game. If you start making suboptimal plays in
response to bad plays by the opponent you're in trouble if he
notices this... Seems what really matters is a minimax "if you
do this the worst that could happen is this, no matter what the
opponent does".)
David Ullrich
Gary Wong wrote:
>
> mat...@math.canterbury.ac.nz (Bill Taylor) writes:
> > Although the existence of somewhat backgammon-like games with
> > doubling cubes and undefined (i.e. infinite-infinite) expectations was
> > vaguely known to me, I'd not realized that such things could actually
> > appear in a real backgammon game! Indeed, I never even knew till just
> > now that it was possible for both players to simultaneously have checkers
> > on the bar; though the mechanism is obvious enough once mentioned.
> > BTW, have any players here ever had this situation arise in a real game?
>
> Not I :-)
Not that I see what it matters, but I've played plenty of games
where both players were on the bar at some point.
[...]
> David Ullrich questions whether the lack of E(X) implies that no "optimal
> strategy" can exist for backgammon (for suitable definition of "optimal
> strategy"). I assert that optimal strategies still do exist: let us call a
> strategy "optimal" if and only if there exists no opponent's strategy that
> dominates it. To define domination: let the random value X follow the
> distribution (points won by player using strategy S after n games) -
> (points won by player using strategy O after n games). It has already been
> established that there exist strategies S and O such that X's distribution
> is well defined, but E(X) is not. Therefore our definition of dominance
> may not include E(X) if it is to include those strategies. Instead, let's
> define strategy S as dominating strategy O if and only if the limit P(X>0)
> is greater than 0.5 as n increases without bound.[...]
>
> Anyway, with this definition of an optimal strategy, does the lack of E(X)
> mean optimal strategies cannot exist?
I never claimed that this implied that with _this_ definition
of "optimal strategy". Definitions are definitions, but I don't feel
this is the "right" definition of "optimal strategy". Let's say
this is a Wong-optimal strategy. It can happen that a strategy S is
Wong-optimal, but nonetheless if you play an infinite sequence of
games using strategy S there is almost surely a point where your
average winnings are - 1,000,000 . (_Not_ because of an unlucky
streak, it can happen that a strategy is Wong-optimal but you're
still "assured" of being this far behind at some point, assuming
perfectly "random" dice.) A strategy that lets you lose this
much does not strike me as all that great.
(Um, note that when I say that one could have a Wong-optimal
strategy with this unfortunate property I'm not insisting there is
such a thing in actual backgammon, just that there could exist
"bad" Wong-optimal strategies in some simpler games. The point being
to wonder whether it's the right definition of "optimal".)
I suspect that there _do_ exist Wong-optimal strategies,
in particular I suspect that "Always play to maximize E0" is such
a strategy (where E0 is the "equity" function that we know _does_
exist, cf a few posts to Ilias.) But a Wong-optimal strategy does
not "assure" results the way I feel an "optimal" strategy should.
Otoh if "Ullrich-optimal" is as defined a few posts ago
then a player using an Ullrich-optimal strategy _cannot_ on average
lose this much (in the long run, assuming random dice). Seems like
a more optimal version of "optimal". But it's a theorem that if
certain numbers come out a certain way then there is no
Ullrich-optimal strategy.
(I don't know that "Always maximize E0" is not an
Ullrich-optimal strategy; never said it wasn't. All I've asserted
is that it's not clear to me that it is.)
Ilias Kastanas
In article <34ABD6...@math.okstate.edu>,
David Ullrich <ull...@math.okstate.edu> wrote:
>Ilias Kastanas wrote:
>>
>> In article <34A97C...@math.okstate.edu>,
>> David Ullrich <ull...@math.okstate.edu> wrote:
>> >Ilias Kastanas wrote:[...]
>> > Well then you're no longer attempting to maximize your
>> >expected gain, which I thought we decided at the start was
>> >what we were trying to do. Never mind. Start here:
>>
>> How could I get the maximum, if it is infinity?... For every m
>> there being a strategy that achieves at least m...?!
>
> Um, right. I think we're just running into the problems that
>arise when we talk about things that we don't know exist.
This sort of nonexistence I can live with. If I can play such
strategies, never mind optimality!
...
I was talking about martingales in general; sorry about the confusion.
The X_n are just that.
That's another can of worms, the actual game. I do have the
B_t in mind; I'm not claiming proofs about the real thing -- to any other
extent than modulo usual modeling assumptions. It _is_ different.
> ??? I would've said E(S_N) = E(X_1 * N) - maybe that's wrong, maybe
>the two are obviously the same, dunno much probability.
Eh... how would we know in general that X_1, N are independent --
or at least uncorrelated? All we have assumed about N is that it's a
stopping time... {N=k} is in the level-k sigma field. E.g. let T =
inf{t: B_t not in (-a, b)}. If b = a, T is independent of (B_T)^2 and
we can use a simple martingale trick to compute E(T^2). If b != a, T
isn't independent and we can't.
>> For submartingales we can replace the first
>> condition by E(|X_n+1 - X_n|) bounded a.s., and conclude E(X_N) >= E(X_0).
>
> Right. The question (ok, _a_ question) is whether it's any consolation
>to the guy to know that his expected gain is positive, if its also almost
>certain that at some point he will lose his shirt.
Ah, you cannot lose money betting on a submartingale... even if
you want to.
>> We go on to theorems valid for N < inf _and_ N = inf (notation:
>> X_inf is lim X_n). For (uniformly integrable) submartingales, we have
>> E(X_0) <= E(X_N) <= E(X_inf). And for (nonnegative) supermartingales,
>> E(X_0) >= E(X_N), including N = inf.
>>
>> Now the point I want to make is about types of convergence.
>>
>> Example: Start a symmetric random walk at S_0 = 1; let N = inf{i: S_i =0},
>> and define X_n = S_(N cap n). Then X_n -> X_inf a.s., and X_inf = 0;
>> but E(X_n) = 1 for all n, so this a.s. convergence cannot occur in L_1.
> Precisely. And if you took a slightly modified example you get
>inf(X_n) = -infinity a.s., in spite of the fact that E(X_n) = 1. Hence
>my skepticism about why E(X_n) = 1 is really what we should be worried
>about.
>
>> (By the way, this shows that the "basic fact" doesn't always hold for
>> N = inf; we need the theorems as stated above).
>
> Couldn't find "basic fact" above - which basic fact were you referring
>to? Sorry.
Sorry, it was a way back; here it is again:
@@ And the basic martingale fact, E(X_N) = E(X_0), holds for _bounded_
I don't dare use the "O" word... due to your definition...
>"indicated" action is better than taking some contraindicated action.
>Better how? I don't see how it can be that much "better", since
>E(|X_1|) = infinity _does_ imply that inf(S_n/n) = - infinity.
In St. Petersburg we had E(|X|) = inf, and the lim_sup was inf
too, so the house was facing a lim_inf of -inf. In fact, we even had
lim_sup S_n/n*log(n) = +inf, a.s. Yet the game was being offered at a
finite fee; and the indicated action, non-obvious, comes from
S_n/n*log(n) -> 1 in probability.
Knowing that P(|S_n/n*log(n) - 1| > epsilon) goes to 0 (and often
knowing at what rate) is the kind of thing focusing on what is realistic and
likely. Don't you think? What is your view of the St.P. analysis above?
Or take the variant with the 1/2^k modified to 1/k(k+1)2^k, and
counterbalanced by a -1 value so that E(X) = 0 and E(|X|) < inf. Is
it a fair game? Again, the story is told by S_n/(n/log(n)) -> -1, in
probability. It's not E per se, it's the law-of-large-numbers behavior
that matters... right? Well, isn't _this_ the l.l.m. here?
If someone offered you a 1-in-a-million chance of winning a billion
dollars, would you pay $500 for it? Just one ticket to buy, take it or
leave it. Or maybe $200?
> A perfect poker player can play forever and know that unless he
>gets unreasonably unlucky he will not do much worse than break even on
>average, and will come closer to at least breaking even the longer he
>plays. If E(|X_1|) is infinite (not that I'm saying it is) then
>backgammon simply does not have this property - a player who always
>makes the "indicated" move _will_ eventually find that he's
>lost an average of $1000000 per game even though he was playing for
>nickels (unless he gets unreasonably lucky). Don't see what good
>it does to know what action is "indicated", given this.
Hmm, is this to happen once in a 1000 years? The rest being good?
Especially the one when he finds he has _won_ $1000000 per game!
> (No, of course this has very little to do with the actual
>game in the actual world. One could say the same about a lot of
>models of a lot of things. It _does_ it seems to me say something
>about the validity of models of backgammon where we just assume
>that there is a thing which deserves to be called "P(WIN)".
>P(WIN) depends on what strategy the players are using - if we're
>talking about P(WIN) independent of this we must be assuming
>perfect play, on our side at least. And if there's no such thing
>as "perfect play" then we don't know what P(WIN) is anymore.
> Hence my original objection to statements about how we
>should double when P(WIN) > this or that.)
The practical game includes knowing the opponent's level of skill,
strengths and weaknesses, inducing errors, using psychology, etc etc.
Leaving out the cube, I should think there is P(win); finitely many
positions/transitions, and one can condition on strategies or not. But one
must be precise. Maximum chance of any win? Of points won (gammon vs simple
win)? Minimize chance of being gammoned? Combinations?
...
>> In any case, to focus the issue, here is a trivial discretized
>> version: a +/-1 random walk from 0, -2 being loss and +2 win. At +1, no
>> doubling, my E is 1/2. With doubling allowed, if I do so at +1 then
>
> Focussing on an understandable version seems like a good idea.
>But I don't understand the rules of the game yet. You said "discretized" -
>presumably you're not talking about contniuous time? What I don't understand
>is who has the right to double when, whether there is more than one "turn"
>between succesive dice rolls, etc. Possibly I could figure out the rules by
>seeing what rules give the numbers you cite, or you could just explain the
>game.
All I mean is p = 1/2 transitions to +/-1, and then +/-2. At
+1 I have the advantage; at +2 I win -- game over. After each transition
the cube owner may double. Obviously at -1, 0 or 1. I'm using the stra-
tegy "double at +1; always accept". Since it creates a (formal at least)
problem in (d) we change it: "if a double is immediately doubled, and this
happens k times, stop doubling". Or so.
One might also make a rule: only one double allowed per transition.
>a) opponent (accepts and) never doubles: E = 1 (same with opponent resigning)
>> b) opponent doubles at -1: easily, E = 4/5; better for her than (a).
>> c) opponent doubles at 0: E = inf. If I truncate my strategy at n = 0
>> (stop doubling after her first one), E_0 = 1. If I do so at n = 1,
>> E_1 = 5/3. Generally, E_n = 2(4/3)^n -1; it gets better and better. And
>> I don't _have_ to truncate; I can enjoy the monotonicity all the way.
>> d) opponent doubles at +1(!): (no, without "keeping the cube"). If we
>> both persist, this is ill-defined, the cube never settling! I can drive
>> the cube as high as I want and then truncate; much better for me than (c).
>>
>> Do you feel there is a problem with (c), as to the (untruncated)
>> strategy being optimal? What about (d), no "optimal" strategy but ever-
>> better ones since the opponent is "giving it all away"?
> The definition I gave for "optimal strategy" involved a few
>quantifiers. I defined S0 to be optimal if it has the property that
>if I use S0 then no matter _what_ strategy S the opponent uses, I
>will have
>
>(*) lim inf (X_1 + ... + X_n) / n >= 0 .
>
>(Note that the _definition_ of X_n depends on S0 and S.) It can certainly
>happen that if the opponent uses a bad strategy then the lim inf in
>(*) is +infinity. This would not be a bad thing - it's also perfectly
>consistent with my definition of "optimal strategy".
So there could be many optimal strategies after all.
In particular, you are not asking for maximum gain. The various
truncations at (d) presumably improve with increasing k... but maybe all
are optimal!
> The bit about "if E(|X_1|) = infinity then (*) fails and that's
>a bad thing was assuming that _both_ players are using the _same_ strategy
>S0 - if they're using the same strategy and E(|X_1|) = infinty then
>the lim inf in (*) is - infinity, which is bad. But my saying this does not
>imply that I think (c) would be bad, because in (c) the players are not
>using the same strategy.
If both play S' = "double (once per transition) wherever", E(|X|) =
1/2 * 4 + 1/4 * 16 + ... = inf, as P(game ends in 2m transitions) = 1/2^m.
Of course the expected # of transitions is = 4.
> (But if E(|X_1|) = infinity for _any_ S0, assuming both players
>are using S0, then that _does_ say that backgammon's hopeless. Supposing
>this, then (c) doesn't come up: in (c) we have the opponent using a bad
>strategy, and the fact that we can win if the opponent plays poorly proves
>nothing. If E(|X_1|) = infinity for _any_ S0, assuming both players
>are using S0, then no matter what I do there is a strategy available to
>the opponent that will make things very bad for me.
But S' doesn't matter. It's just a silly strategy; _I_ am
not going to play it. I'll stick to my "double at +1". If the opponent
then plays S', that's tantamount to "double at 0" (still assuming once
per transition), discussed under (c).
> Hence the earlier bit about "mindreading": When you say
>"assuming you do this and the opponent does that" I don't see what
>it proves, since you don't know what the opponent _is_ going to
>do in an actual game. If you start making suboptimal plays in
>response to bad plays by the opponent you're in trouble if he
>notices this... Seems what really matters is a minimax "if you
>do this the worst that could happen is this, no matter what the
>opponent does".)
Of course. It's not what the opponent will do; it is what she has
done. Phrasing it as "following S" is for convenience. Typically, one
picks Ss so that non-Ss are demonstrably worse.
Ilias
Glen Barnett
In article <34A97C...@math.okstate.edu>,
David Ullrich <ull...@math.okstate.edu> wrote:
> Now, a lot of people have been talking about optimal strategies
>without giving a definition. I'd say that a strategy S0 is optimal if
>it has the following property: Suppose you play the game using strategy
>S0. Suppose your opponent plays using strategy S. Having fixed both
>strategies we now have well-defined random variables X_n , n = 1, 2, ...,
>where X_n is the amount you win in the n-th game. (There's a technical
>detail left out here, addressed below). I would call the strategy S0
>_optimal_ if it is the case that no matter what strategy S the
>opponent uses, it is almost surely true that
>
>(*) lim inf (X_1 + ... + X_N) / N >= 0 .
>
> (That's math speak for "almost surely, _on average_ you break
>even or better, more or less, eventually".)
>
> Why not? For example: Let's suppose for the sake of argument
>that S0 _is_ an optimal strategy. Let's suppose that we and the
>opponent are both using strategy S0, and let's define X_n as above.
>Then E(X_n) = 0, by symettry.
I've only half been reading this thread, so doubtless I missed
something, but for a random variable symmetry about zero alone
is not sufficient to establish that its expectation is zero.
That establishes that the Cauchy principal value is zero, but
for the expectation to be zero, the integral (well, ok, in this
case it's a sum) must converge in both limits independently.
Since it's symmetric, I think you can just say that if |X_n|
has finite expectation, X_n has zero expectation by symmetry.
There may be some obvious property of X_n you know but haven't stated
that means that E(X_n) is zero, though (or have stated, but I missed).
Glen
Gary Wong
David Ullrich <ull...@math.okstate.edu> writes:
> Gary Wong wrote:
> > mat...@math.canterbury.ac.nz (Bill Taylor) writes:
> > > Although the existence of somewhat backgammon-like games with
> > > doubling cubes and undefined (i.e. infinite-infinite) expectations was
> > > vaguely known to me, I'd not realized that such things could actually
> > > appear in a real backgammon game! Indeed, I never even knew till just
> > > now that it was possible for both players to simultaneously have checkers
> > > on the bar; though the mechanism is obvious enough once mentioned.
> > > BTW, have any players here ever had this situation arise in a real game?
> >
> > Not I :-)
>
> where both players were on the bar at some point.
So have I, but none of them have been troublesome because the probability
of reaching the same state with a higher cube value was very small. Both
players being on the bar is relatively common; a position being troublesome
must be extremely rare.
> [...]
> > David Ullrich questions whether the lack of E(X) implies that no "optimal
> > strategy" can exist for backgammon (for suitable definition of "optimal
> > strategy"). I assert that optimal strategies still do exist: let us call a
> > strategy "optimal" if and only if there exists no opponent's strategy that
> > dominates it. To define domination: let the random value X follow the
> > distribution (points won by player using strategy S after n games) -
> > (points won by player using strategy O after n games). It has already been
> > established that there exist strategies S and O such that X's distribution
> > is well defined, but E(X) is not. Therefore our definition of dominance
> > may not include E(X) if it is to include those strategies. Instead, let's
> > define strategy S as dominating strategy O if and only if the limit P(X>0)
> > is greater than 0.5 as n increases without bound.[...]
> >
> > Anyway, with this definition of an optimal strategy, does the lack of E(X)
> > mean optimal strategies cannot exist?
>
> I never claimed that this implied that with _this_ definition
> of "optimal strategy". Definitions are definitions, but I don't feel
> this is the "right" definition of "optimal strategy". Let's say
> this is a Wong-optimal strategy. It can happen that a strategy S is
> Wong-optimal, but nonetheless if you play an infinite sequence of
> games using strategy S there is almost surely a point where your
> average winnings are - 1,000,000 . (_Not_ because of an unlucky
> streak, it can happen that a strategy is Wong-optimal but you're
> still "assured" of being this far behind at some point, assuming
> perfectly "random" dice.) A strategy that lets you lose this
> much does not strike me as all that great.
Ah, that's true. But I suspect you can only get a distribution like that
if the games are not independent -- I have thought about it a bit and the
only cases I can think of with E(X) < 0 but P(X>0) > 0.5 for unbounded n
are eg. roulette where the house has a slight advantage, but you start your
bets at 1 for the initial game or immediately following a win, and double
your previous bet immediately following a loss. I suspect the same
difficulty cannot occur in backgammon, because in general the cube can only
reach twice the value at which the previous player lost with the
co-operation of both players, and if the doubling decisions of an optimal
strategy are independent of previous games, then X as n increases without
bound becomes the sum of a large number of independent random variables and
tends to a normal distribution.
So, can we agree on some other definition of optimality then? Perhaps
optimality isn't such a good term for it; what would be nice is a
definition sufficient to show that the following strategies are
"unbeatable":
- the house is unbeatable at roulette even if the stakes are unlimited and
one adopts the doubling strategy above -- the player is also unbeatable if
there are no zeroes on the wheel;
- both players are unbeatable (loosely defined as that they expect to at
least break even, though what "expectation" is is somewhat unclear) in the
P(X=(-4)^y) = 1/2^y (for all y >= 1) game?
If a definition is general enough to satisfy both of those cases, then I
believe I can demonstrate that optimal strategies exist in the same sense
for backgammon.
Anon
I would like to bring this discussion back down to earth
by noting that neither player has an infinite credit
limit, which makes the possibility of a infinite number of doubles
impossible (well, if a player did have an infinite credit limit I
wonder why he would need such things as optimal strategies).
"Highlights" of the aforementioned discussion follow:
Gary Wong <ga...@cs.auckland.ac.nz> wrote in article
<ieybtxs...@cs20.cs.auckland.ac.nz>...
> David Ullrich <ull...@math.okstate.edu> writes:
> > Gary Wong wrote:
<snip>
> > > David Ullrich questions whether the lack of E(X) implies that no
"optimal
> > > strategy" can exist for backgammon (for suitable definition of
"optimal
> > > strategy"). I assert that optimal strategies still do exist: let us
call a
snip
> > I never claimed that this implied that with _this_ definition
> > of "optimal strategy". Definitions are definitions, but I don't feel
> > this is the "right" definition of "optimal strategy". Let's say
> > this is a Wong-optimal strategy. It can happen that a strategy S is
> > Wong-optimal, but nonetheless if you play an infinite sequence of
> > games using strategy S there is almost surely a point where your
> > average winnings are - 1,000,000 . (_Not_ because of an unlucky
> > streak, it can happen that a strategy is Wong-optimal but you're
> > still "assured" of being this far behind at some point, assuming
> > perfectly "random" dice.) A strategy that lets you lose this
> > much does not strike me as all that great.
>
snip
> - the house is unbeatable at roulette even if the stakes are unlimited
and
> one adopts the doubling strategy above -- the player is also unbeatable
if
> there are no zeroes on the wheel;
>
snip
Bill Taylor
David Ullrich <ull...@math.okstate.edu> writes:
|> A _strategy_ for backgammon is a "procedure" that specifies how
|> we make choices when we have a choice to make.
Quite so. It is a function from the set of positions union positions+rolls,
to the set of moves union drop/accept/double.
|> Could be that it involves flipping a coin,
Well... that's not the usual thing. The above are called "pure strategies",
and you are then allowed to randomize over these. The sort of things you're
talking about, (where randomization is done after the choice of a single
strategy), are called "behavioural strategies", and are seen more in
decision theory than game theory. It is a non-trivial theorem that the
two approaches are equivalent.
|> My guess is that in fact this is not necessary in
|> backgammon because there's no hidden information
Correct. It is another theorem that games of complete information need
never have randomized strategies as their solutions. Both of these theorems,
though quite non-trivial, are somewhat "intuitively obvious".
|> Does there _exist_ an optimal strategy in backgammon?
"Optimal strategy" is usually defined as one which achieves the (mini-)maximum
expected payoff-value. If the game is non-compact in an appropriate sense,
there may be no optimum strategy. e.g. "Secretly choose a number, and the
largest number wins." However, finite games always do. However, backgammon
is not finite. Furthermore, it appears as though (due to these freak
positions) it probably has undefined expected value; therefore no optimal
strategy would exist, by definition. I think we have all agreed to this,
though you keep on asking about it!
However we have also kept making the point that, for all practical purposes,
for one reason or another, it does have optimal strategies. You apparently
do not want to know this, even though your main question has been answered.
|> I would call the strategy S0
|> _optimal_ if it is the case that no matter what strategy S the
|> opponent uses, it is almost surely true that
|>
|> (*) lim inf (X_1 + ... + X_N) / N >= 0 .
That is a nice looking property, which is equivalent to optimal, for
compact games, (provided the RHS is replaced by v, in general). That is
the content of von Mises' SLLN.
But it is NOT the standard definition of "optimal", in game thoery. Ilias'
post about StPetersburg and log(n), gives a much more satisfactory approach
for non-compact games than the above, which turns out to be rather feeble.
|> no matter _how_ you play the game you cannot be assured of
|> success (in the sense of (*), an "assurance" that _is_
|> available in poker and most games.)
Actually, NOT, in poker! Unless, (as you gave said you don't like doing!),
you modify it in some way by capping the stakes. But in "pure" poker, i.e.
unlimited betting, your point fails. It is ironic that you have fallen into
the same trap for poker, (which you seeem to regard with some affection),
that you have accused the rest of us about backgammon! Very ironic.
But it's pretty clear you CANNOT expect to guarantee a long-term average
winning in unlimited poker, with any "proper strategy". To defeat you, all
one needs to do is always bet more than the accumulated losses/gains so far,
and quit when ahead. With unlimited betting, this can always be done, we
can make you play double-or-quits all the time. (Treble-or-quits, for
safety.) This is MUCH worse than any backgammon situation!
|> I suspect some people may
|> be annoyed at the way I appear to have been ignoring some of
|> the details of what they've had to say about all this;
Yes and no. Of course it's important to explain oneself properly, and insist
on sticking to one's main point of inquiry. But it can get tedious when
that point has been answered early on! One begins to see why your battle
with Pertti Lounesto went on so long and tediously!
-------------------------------------------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
-------------------------------------------------------------------------------
Life is complex. It has both real and imaginary parts.
-------------------------------------------------------------------------------
Bill Taylor
David Ullrich <ull...@math.okstate.edu> writes:
|> about the validity of models of backgammon where we just assume
|> that there is a thing which deserves to be called "P(WIN)".
|> P(WIN) depends on what strategy the players are using - if we're
|> talking about P(WIN) independent of this we must be assuming
|> perfect play, on our side at least.
This is an easily resolved point, I think. Someone else noted that in
backgammon calculations, it is standard use P(WIN) as the probability
of winning a CUBELESS game, assuming both play perfect strategies.
Similarly with P(Gammon) and P(BGmn). (There is the technical point that
the same optimal strategy may not (almost certainly does not) suffice to
maximize all three, but this is usually ignored as being largely
irrelevant to most questions here.)
In the case of my diffusion-based game, I actually *defined* P(WIN) that way,
as a part of defining the game; so it's odd that you keep raising this
minor point.
-------------------------------------------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
-------------------------------------------------------------------------------
God does not play dice with the universe - god *is* the dice.
-------------------------------------------------------------------------------
David Ullrich
> > > > Although the existence of somewhat backgammon-like games with
> > > > doubling cubes and undefined (i.e. infinite-infinite) expectations was
> > > > vaguely known to me, I'd not realized that such things could actually
> > > > appear in a real backgammon game! Indeed, I never even knew till just
> > > > now that it was possible for both players to simultaneously have checkers
> > > > on the bar; though the mechanism is obvious enough once mentioned.
> > > > BTW, have any players here ever had this situation arise in a real game?
> > >
> > > Not I :-)
> >
> > where both players were on the bar at some point.
>
> So have I, but none of them have been troublesome because the probability
> of reaching the same state with a higher cube value was very small. Both
> players being on the bar is relatively common; a position being troublesome
> must be extremely rare.
>
> > [...]
> > > strategy" can exist for backgammon (for suitable definition of "optimal
> > > strategy"). I assert that optimal strategies still do exist: let us call a
> > > strategy "optimal" if and only if there exists no opponent's strategy that
> > > dominates it. To define domination: let the random value X follow the
> > > distribution (points won by player using strategy S after n games) -
> > > (points won by player using strategy O after n games). It has already been
> > > established that there exist strategies S and O such that X's distribution
> > > is well defined, but E(X) is not. Therefore our definition of dominance
> > > may not include E(X) if it is to include those strategies. Instead, let's
> > > define strategy S as dominating strategy O if and only if the limit P(X>0)
> > >
> > > Anyway, with this definition of an optimal strategy, does the lack of E(X)
> > > mean optimal strategies cannot exist?
> >
> > of "optimal strategy". Definitions are definitions, but I don't feel
> > this is the "right" definition of "optimal strategy". Let's say
> > this is a Wong-optimal strategy. It can happen that a strategy S is
> > Wong-optimal, but nonetheless if you play an infinite sequence of
> > games using strategy S there is almost surely a point where your
> > average winnings are - 1,000,000 . (_Not_ because of an unlucky
> > streak, it can happen that a strategy is Wong-optimal but you're
> > still "assured" of being this far behind at some point, assuming
> > perfectly "random" dice.) A strategy that lets you lose this
> > much does not strike me as all that great.
>
> if the games are not independent --
Why is that?
> I have thought about it a bit and the
> only cases I can think of with E(X) < 0 but P(X>0) > 0.5 for unbounded n
> are eg. roulette where the house has a slight advantage, but you start your
> bets at 1 for the initial game or immediately following a win, and double
> your previous bet immediately following a loss. I suspect the same
> difficulty cannot occur in backgammon, because in general the cube can only
> reach twice the value at which the previous player lost with the
> co-operation of both players, and if the doubling decisions of an optimal
> strategy are independent of previous games, then X as n increases without
> bound becomes the sum of a large number of independent random variables and
> tends to a normal distribution.
>
> So, can we agree on some other definition of optimality then? Perhaps
> optimality isn't such a good term for it; what would be nice is a
> definition sufficient to show that the following strategies are
> "unbeatable":
>
> - the house is unbeatable at roulette even if the stakes are unlimited and
> one adopts the doubling strategy above -- the player is also unbeatable if
> there are no zeroes on the wheel;
>
> - both players are unbeatable (loosely defined as that they expect to at
> least break even, though what "expectation" is is somewhat unclear) in the
> P(X=(-4)^y) = 1/2^y (for all y >= 1) game?
>
> If a definition is general enough to satisfy both of those cases, then I
> believe I can demonstrate that optimal strategies exist in the same sense
> for backgammon.
Well, you can make any definition you want. The definition I
gave _does_ seem to me to be the "right" one. It seems like you're
deciding what you want to prove and then deciding how you need to
define your terms in order to prove it.
Not that it matters, because if I start with infinitely much
money then when I win a dollar I don't have any more money than I had
before, but if we consider roulette with no limit on the sice of
the bet (and if we assume that I have infinitely much money, so there's
_really_ no limit on the size of the bet) then the house is simply
_not_ "unbeatable" at roulette. If I simply repeatedly bet 1 + the amount
I've lost so far (sparing us those nasty geometric series) then eventually
I will win a game, and then I will be a dollar ahead. Given this, why do
you want a definition of "optimal" that makes the house "unbeatable"
in no-limit roulette?
I mean, if I wanted to disprove the fact that every natural
number has a unique prime factorization I could look for a definition
of "prime" such that 2 and 4 are both primes. Why would I do that?
David Ullrich
Ilias Kastanas wrote:
>
> In article <34ABD6...@math.okstate.edu>,
> David Ullrich <ull...@math.okstate.edu> wrote:
> >Ilias Kastanas wrote:
> >>
> >> In article <34A97C...@math.okstate.edu>,
> >> David Ullrich <ull...@math.okstate.edu> wrote:
> >> Okay, the "point" about (sub)martingales is that if sup E(X_n+) < inf
> >they converge a.s. ("bounded => convergent"), true... to a limit X with E(|X|)
> >> < inf. And the basic martingale fact, E(X_N) = E(X_0), holds for _bounded_
> >> stopping times N. But of course we do have results about L_p convergence,
> >> including L_1... and also extensions of the "fact" to unbounded N.
>
> > Right. But I don't see the point to the point. Hmm, first, your
> >X_n is not the same as the X_n's I defined above - those X_n's are not
> >a martingale, they're iid random variables, X_n being the outcome of
> >the n'th game. So maybe you should say what X_n you're talking about
> >(maybe this becomes clear below). Exactly what is X_n here (and whatever
> >it is, how do you know that sup E(X_n+) is finite?)
> >
> > It appears that you're talking about a single game, and
> >X_n has something to do with the state of that game after n moves.(???)
> >I'm not certain exactly what X_n is here - it's certainly not the
> >same thing as the expected outcome of the n-th game.
>
> I was talking about martingales in general; sorry about the confusion.
> The X_n are just that.
"Just that" meaning just a martingale in general, nothing to do with
the questions about backgammon here? Then what does this have to do with
what we've been talking about?
Yup.
> > ??? I would've said E(S_N) = E(X_1 * N) - maybe that's wrong, maybe
> >the two are obviously the same, dunno much probability.
>
> Eh... how would we know in general that X_1, N are independent --
> or at least uncorrelated? All we have assumed about N is that it's a
> stopping time... {N=k} is in the level-k sigma field. E.g. let T =
> inf{t: B_t not in (-a, b)}. If b = a, T is independent of (B_T)^2 and
> we can use a simple martingale trick to compute E(T^2). If b != a, T
> isn't independent and we can't.
I didn't mean to assert (nor did I assert) that E(X_1 * N) = E(X_1) * E(N);
that was just an offhand/thoughtless conjecture attempting to explain how
we could both be right. In fact of course you were right, E(S_N) = E(X_1) * E(N) .
> >> For submartingales we can replace the first
> >> condition by E(|X_n+1 - X_n|) bounded a.s., and conclude E(X_N) >= E(X_0).
> >
> > Right. The question (ok, _a_ question) is whether it's any consolation
> >to the guy to know that his expected gain is positive, if its also almost
> >certain that at some point he will lose his shirt.
>
> Ah, you cannot lose money betting on a submartingale... even if
> you want to.
Come now. "You cannot lose money betting on a submartingale" is a
colloquialism. Substitute an actual theorem here and then explain how it
contradicts what I said. It doesn't. If you're betting on a submartingale
then your expected gain is non-negative (or non-decreasing, or some such,
depending on exactly what we're referring to). That does not have any
"almost surely" consequences _unless_ you add some sort of (L1)
boundedness conditions. I mean, you've given examples here where a
person _can_ lose money betting on a submartingale.
My point in all of this (ok, one of my points) has been that
we mathematicians say a lot about the "expected value" of various things.
But our "expected value" is not exactly the same as what it seems to
me the typical man in the street regards as "expected value". In a
naive context where we've "defined" (ie attempted to define, not noticing
the circularity) probability in terms of (a.s.) relative frequency in
a large number of trials people tend to interpret "expected value" in
terms of the average value in a large number of trials. When you say
you can't lose money betting on a submartingale you're colloquializing
some statement about expected values. That statement is true of our
mathematical measure-theortic "expected value", but the corresponding
statement is _not_ true for the naive "average in a large number of
tries" expected value, except under some hypotheses.
In poker or in cubeless backgammon one could show that they're
the same, but in actual backgammon they're not (or at least they may
not be - whether they are or not depdends on whether a certain quantity
is finite or infinite.)
I'm surprised you'd feel that "you cannot lose money betting
on a submartingale" was precise enough to prove something, without
clarification of exactly what's meant. (This is how you show that
God exists starting from Godel's theorem, isn't it?)
[...]
> >> In other words, E(|X|) = inf and the attendant lack of a strong
> >> law does not necessarily preclude analyzing the situation and coming up with
> >> an indicated course of action!
>
> > Depends on what you mean by "indicated". Presumably taking the
>
> I don't dare use the "O" word... due to your definition...
Again, come now. You say something about the "indicated" action,
I ask exactly what you mean, and this is how you clarify what you said?
If you're going to talk about the "indicated" action then presumably you
mena that the "indicated" action is a better idea than other actions.
So you should tell me in what sense it's better. I'm _really_ surprised
at the "don't dare use the "O" word... due to your definition". I didn't
claim it was the _right_ definition, it was just the definition I was
using, because it was what seemed to me to be the appropriate
definiton. You can redefine the word any way you like, a long as you
tell me what definition you're using.
Again, do tell me in precisely what sense your "indicated" action
is "indicated".
Um: I'm not certain whether the last two paragraphs need revision
in the light of what you say below.
> >"indicated" action is better than taking some contraindicated action.
> >Better how? I don't see how it can be that much "better", since
> >E(|X_1|) = infinity _does_ imply that inf(S_n/n) = - infinity.
>
> In St. Petersburg we had E(|X|) = inf, and the lim_sup was inf
> too, so the house was facing a lim_inf of -inf. In fact, we even had
> lim_sup S_n/n*log(n) = +inf, a.s. Yet the game was being offered at a
> finite fee; and the indicated action, non-obvious, comes from
> S_n/n*log(n) -> 1 in probability.
>
> Knowing that P(|S_n/n*log(n) - 1| > epsilon) goes to 0 (and often
> knowing at what rate) is the kind of thing focusing on what is realistic and
> likely. Don't you think? What is your view of the St.P. analysis above?
I don't recall what the "indicated" action was here, sorry. (My
recollection is that the thing was introduced here as an example illustrating
various modes of convergence - already knowing what convergence in
probability was I may have skimmed it a little fast and missed a detail.)
If you take the time to remind me of what the "indicated" action is
please also include an explanation of what the statement that it's
"indicated" indicates. "Focussing on what's realistic and likely" sounds
like a good thing in general but it's a little vague.
> Or take the variant with the 1/2^k modified to 1/k(k+1)2^k, and
> counterbalanced by a -1 value so that E(X) = 0 and E(|X|) < inf. Is
> it a fair game? Again, the story is told by S_n/(n/log(n)) -> -1, in
> probability. It's not E per se, it's the law-of-large-numbers behavior
> that matters... right? Well, isn't _this_ the l.l.m. here?
>
> If someone offered you a 1-in-a-million chance of winning a billion
> dollars, would you pay $500 for it? Just one ticket to buy, take it or
> leave it. Or maybe $200?
Oh. Maybe you _are_ indicating what "indicated" was supposed to
mean - I got thrown off by the text from me in between the beginning of
your reply and the rest of it.
Why don't you actually offer me, say, a 1-in-100 chance to
win $1000, for a $1 ticket. Then we could find out what I'd do...
> > A perfect poker player can play forever and know that unless he
> >gets unreasonably unlucky he will not do much worse than break even on
> >average, and will come closer to at least breaking even the longer he
> >plays. If E(|X_1|) is infinite (not that I'm saying it is) then
> >backgammon simply does not have this property - a player who always
> >makes the "indicated" move _will_ eventually find that he's
> >lost an average of $1000000 per game even though he was playing for
> >nickels (unless he gets unreasonably lucky). Don't see what good
> >it does to know what action is "indicated", given this.
>
> Hmm, is this to happen once in a 1000 years? The rest being good?
> Especially the one when he finds he has _won_ $1000000 per game!
As I said once before: I thought this was sci.math when I
jumped in. (Tried to redirect followups once didn't work. Maybe I
did it wrong - interwhat.) The question of whether there exists an
optimal strategy in backgammon in the sense defined "above" seems
like a perfectly legitimate question.
> > (No, of course this has very little to do with the actual
> >game in the actual world. One could say the same about a lot of
> >models of a lot of things. It _does_ it seems to me say something
> >about the validity of models of backgammon where we just assume
> >that there is a thing which deserves to be called "P(WIN)".
> >P(WIN) depends on what strategy the players are using - if we're
> >talking about P(WIN) independent of this we must be assuming
> >perfect play, on our side at least. And if there's no such thing
> >as "perfect play" then we don't know what P(WIN) is anymore.
> > Hence my original objection to statements about how we
> >should double when P(WIN) > this or that.)
>
> The practical game includes knowing the opponent's level of skill,
> strengths and weaknesses, inducing errors, using psychology, etc etc.
IN, say, cubeless backgammon or poker, where there certainly
is an optimal strategy even by my stringent definition, one can
include all these things. And if one's estimates of the opponent's
skill, etc, is correct it may help. Otoh this allows an opponent
even clever than you to gain an advantage - simply following the
optimal strategy guarantees success regardless. (Where the meaning
of "guarantees success" has been expounded on previously.)
Seriously: It happens all the time that you have two plays.
Play A is really the right play, but play B is better against a
beginner who doesn't know the right response to play B. I can't
tell you how many times I've lost making play B when it turned
out the guy knew what to do about it after all (pisses me off,
given that he didn't know how to respond the week before.)
> Leaving out the cube, I should think there is P(win); finitely many
> positions/transitions, and one can condition on strategies or not. But one
> must be precise. Maximum chance of any win? Of points won (gammon vs simple
> win)? Minimize chance of being gammoned? Combinations?
For the seventh time, yes, if there's no cube then all the issues
I'm worried about go away.
Yes, one needs to define these things. The typical definition of
P(WIN) is "probability that you win, assuming perfect play on both sides".
(In fact here probably P(WIN) is not really relevant to anything, what
we'd really want to know is P(LoseGammon), P(Lose), P(Win), P(WinGammon).
But never mind that.)
And hence my problem with P(WIN) in backgammon, before we've
established that there _is_ such a thing as perfect play. But in another
game where we know there is an optimal strategy: Given two strategies,
there is such a thing as the probability that I win if I follow this
strategy and you follow that one. And then P(WIN) is the probability
that I win, assuming we both use an optimal strategy.
Yes.
> In particular, you are not asking for maximum gain.
No, but in a game where various expectations are finite so
everything makes sense that would presumably follow: a strategy that
did not seek to maximize "equity" with each decision could presumably
be defeated by another strategy that did attempt to do so, and hence
would be non-optimal.
I move we introduce the word "equity", btw. Years ago I thought
backgammon players used the word "equity" because they didn't realize
it was a synonym for "expected value". But the two are really not
synonymous: random variables have expected values, and here all our
probailities depend on the strategies used by both players, as well
as on the position.
Ie, if Pos is a position, S1 and S2 are strategies, then
there is such a thing as
E(Pos, S1, S2) = ExpectedValue(what I win starting at Pos,
if I use S1 and you use S2) .
Seems like the _equity_ in a position is
Eqity(Pos) = sup inf E(Pos, S1, S2)
S1 S2
.
Well we're agreed on that, anyway. (Neither here nor there, but
it _is_ funny how you can talk about what "she" has done with impunity,
while if I simply use the same pronoun in my reply I get cracks about
PC this and that. Never mind...)
Gary Wong
> > > I never claimed that this implied that with _this_ definition
> > > of "optimal strategy". Definitions are definitions, but I don't feel
> > > this is the "right" definition of "optimal strategy". Let's say
> > > this is a Wong-optimal strategy. It can happen that a strategy S is
> > > Wong-optimal, but nonetheless if you play an infinite sequence of
> > > games using strategy S there is almost surely a point where your
> > > average winnings are - 1,000,000 . (_Not_ because of an unlucky
> > > streak, it can happen that a strategy is Wong-optimal but you're
> > > still "assured" of being this far behind at some point, assuming
> > > perfectly "random" dice.) A strategy that lets you lose this
> > > much does not strike me as all that great.
> >
> > Ah, that's true. But I suspect you can only get a distribution like that
> > if the games are not independent --
>
> Why is that?
What's the result that says that the sum of independent random variables tends
to a normal distribution for large n? I forget what it depends on, perhaps
it needs defined means and/or variances. If you have proof or disproof,
please enlighten me :-)
> > So, can we agree on some other definition of optimality then? Perhaps
> > optimality isn't such a good term for it; what would be nice is a
> > definition sufficient to show that the following strategies are
> > "unbeatable":
> >
> > - the house is unbeatable at roulette even if the stakes are unlimited and
> > one adopts the doubling strategy above -- the player is also unbeatable if
> > there are no zeroes on the wheel;
> >
> > - both players are unbeatable (loosely defined as that they expect to at
> > least break even, though what "expectation" is is somewhat unclear) in the
> > P(X=(-4)^y) = 1/2^y (for all y >= 1) game?
> >
> > If a definition is general enough to satisfy both of those cases, then I
> > believe I can demonstrate that optimal strategies exist in the same sense
> > for backgammon.
>
> Well, you can make any definition you want. The definition I
> gave _does_ seem to me to be the "right" one.
I agree that your definition appears to be "right", except that it's overly
strict because it requires the expectation to exist. Claiming E(X)=0 from
symmetry, whether justified or not, isn't enough, because I could invent an
asymmetric game: how about we give X a continuous uniform distribution in
the range (0,q], and in each game I pay you sin(1/X)/X. For what values of
q (if any) is my strategy optimal? Yours? Both? Neither? If we could
come up with a generalised version of your definition that simplified to
the same result for defined E(X) or symmetry, then I think we'd be on to
something. That was what I was attempting to do with my definition based
on P(X>0), which made assumptions about the limit of the mode as n
increased without bound, which may or may not be true depending on the
distribution and if we can claim independence between games. If it _is_
true, then Wong-optimal strategies are a superset of Ullrich-optimal
strategies and one implies the other for defined E(X).
> Not that it matters, because if I start with infinitely much
> money then when I win a dollar I don't have any more money than I had
> before, but if we consider roulette with no limit on the sice of
> the bet (and if we assume that I have infinitely much money, so there's
> _really_ no limit on the size of the bet) then the house is simply
> _not_ "unbeatable" at roulette. If I simply repeatedly bet 1 + the amount
> I've lost so far (sparing us those nasty geometric series) then eventually
> I will win a game, and then I will be a dollar ahead. Given this, why do
> you want a definition of "optimal" that makes the house "unbeatable"
> in no-limit roulette?
I think I asked the question the wrong way. What I want to know is: what
property is it of the roulette game that makes the house's strategy
"optimal"? I know you can show it with the expectation, but is there
anything more fundamental there that would relax the requirement for
expectation? (As for why P(X>0)>0 doesn't imply the house isn't unbeatable
at roulette, terminating the series early is cheating. Otherwise, I could
claim I'm better than any backgammon player in the world, simply because if
we both lived infinitely long and played for money, I'd be ahead at some
point _eventually_, even if it took me centuries or millenia. But I haven't
given up my day job quite yet :-)
What it all boils down to is that I am willing to believe that non-negative
expectation implies the optimality/unbeatablity property we're trying to
establish. I'm not convinced that optimality/unbeatability implies
non-negative expectation, though (or any expectation at all). Therefore I
don't see that they're necessarily equivalant, and we haven't got sufficient
justification to define one in terms of the other.
Cheers,
Gary (GaryW on FIBS).
PS: Follow-ups to rec.games.abstract. Let's stop annoying the poor
backgammon players :-)
David Ullrich
> |> that there is a thing which deserves to be called "P(WIN)".
> |> P(WIN) depends on what strategy the players are using - if we're
> |> talking about P(WIN) independent of this we must be assuming
> |> perfect play, on our side at least.
>
> backgammon calculations, it is standard use P(WIN) as the probability
> of winning a CUBELESS game, assuming both play perfect strategies.
> Similarly with P(Gammon) and P(BGmn). (There is the technical point that
> the same optimal strategy may not (almost certainly does not) suffice to
> maximize all three,
This is a little silly - the rational thing is not to try to
maximize any of these probabilities, the rational thing is to try
to maximize your expected gain. Not at all the same thing.
> but this is usually ignored as being largely
> irrelevant to most questions here.)
> Not as odd as thinking that that definition of P(WIN) actually has
something to do with finding the best strategy in the real game. In fact
we really care about how much we're gonna win, not whether we win, so that
we need all three probabilities to figure out anything interesting. But that's
a minor point.
The major point here: There _is_ a cube in the real game. It affects
what "perfect play" is - even assuming there _is_ such a thing, the right
play in a cubeless game can be very different from the right play in a
game with the cube. Since the plays being made by our hypothetical perfect
players in actual backgammon are _not_ the same as those made in a
cubeless game (yes, talking about what move to make, not just cube-related
issues) I don't see what "P(WIN, assuming perfect play in a cubeless
game" has to do with anything. The fact that this is usually ignored does
not prove it's a minor "technical" point.
> In the case of my diffusion-based game, I actually *defined* P(WIN) that way,
> as a part of defining the game; so it's odd that you keep raising this
> minor point.
Sorry. I've been thinking about backgammon instead of "your"
diffusion-based game.
David Ullrich
Bill Taylor wrote:
>
> David Ullrich <ull...@math.okstate.edu> writes:[...]
> |> Does there _exist_ an optimal strategy in backgammon?
>
> expected payoff-value. If the game is non-compact in an appropriate sense,
> there may be no optimum strategy. e.g. "Secretly choose a number, and the
> largest number wins." However, finite games always do. However, backgammon
> is not finite. Furthermore, it appears as though (due to these freak
> positions) it probably has undefined expected value; therefore no optimal
> strategy would exist, by definition. I think we have all agreed to this,
> though you keep on asking about it!
Sorry, I don't recall us all agreeing to this. For that matter
I've never asserted that there is no optimal strategy - this is not
at all clear to me.
> However we have also kept making the point that, for all practical purposes,
> for one reason or another, it does have optimal strategies. You apparently
> do not want to know this, even though your main question has been answered.
Um. The fact that you say something doesn't mean I necessarily
believe it. The fact that I don't believe something you say does not
imply that I don't want to know the answer to whatever you're trying
to explain, it implies only that I don't think you're omniscient or
infallible.
Take the game you meantion as an example of a game with no
optimal strategy: "Secretly choose a number, the larger number wins".
The reason that there's no optimal strategy is because there are
infinitely many numbers, most of which are larger than any given one.
Now I play devil's advocate: The reasons people tell me that
there _is_ an optimal strategy in backgammon, "for all practical
purposes", might map to something like the following in the
choose-a-number game: "Presumably we're required to write the number
in some standard notation. But of course there are not really infinitely
many numbers that one can actually write down, for example to specify
all the digits of a number larger than [insert a large number here]
would take more than 1000000 years. So there's actually a bound on
the size of the number you can choose, and hence there _is_ an
optimal strategy."
Instead of telling me that my questions have all been
answered and I apparently don't want to hear the answers why don't
you do one of the following:
(i) tell me what the optimal strategy in the pick-a-number game
actually is.
(ii) tell me with a straight face that you actually believe there
is an optimal strategy for all practical purposes in the
pick-a-number game, although you can't say exactly what it is
due to limits on computation time
(iii) explain how you know that "for all practical purposes" there
is in fact an optimal strategy in backgammon.
Please try to avoid simply telling me that (iii)'s been done. I recall
a lot of people attempting (iii), but I don't recall any attempts
that don't remind me of my devil's-advocate proof of the "fact" that
"for all practical purposes" there's an optimal strategy in the
pick-a-number game. If the two don't strike you as similar then
explain to me how (iii) actually goes.
(See, I don't believe there actually is an optimal strategy
in the pick-a-number game. The point being there's a little fuzziness:
while it's true that there's a limit to the size of a number you can
write down it's also true that for any number you can write down
someone else could write down a larger one. I'm aware that the
previous sentence is logically inconsistent - I'm confused about
this. The explanations of why there's an optimal strategy in
backgammon "for all practical purposes" lead to the same sort
of confusion, as far as I can see.)
> |> I would call the strategy S0
> |> _optimal_ if it is the case that no matter what strategy S the
> |> opponent uses, it is almost surely true that
> |>
> |> (*) lim inf (X_1 + ... + X_N) / N >= 0 .
>
> That is a nice looking property, which is equivalent to optimal, for
> compact games, (provided the RHS is replaced by v, in general). That is
> the content of von Mises' SLLN.
>
> But it is NOT the standard definition of "optimal", in game thoery. Ilias'
> post about StPetersburg and log(n), gives a much more satisfactory approach
> for non-compact games than the above, which turns out to be rather feeble.
I didn't see a definition of "optimal strategy" there. What is the
standard definition of "optimal" in a situation like the present? And what
in what sense does the definition make sense - exactly what is "optimized"
by an "optimal" strategy?
> |> no matter _how_ you play the game you cannot be assured of
> |> success (in the sense of (*), an "assurance" that _is_
> |> available in poker and most games.)
>
> Actually, NOT, in poker! Unless, (as you gave said you don't like doing!),
> you modify it in some way by capping the stakes. But in "pure" poker, i.e.
> unlimited betting, your point fails. It is ironic that you have fallen into
> the same trap for poker, (which you seeem to regard with some affection),
> that you have accused the rest of us about backgammon! Very ironic.
Gimme a break. This might be "ironic", or it could just be that
I was assuming that a limit on the bet was part of the standard definition
of the word "poker".
It's not a question of what I like to do or don't like to do.
I've been attempting to discuss the actual games as actually played,
instead of diffusion models. I've played a few poker games - they all
included limits on the size of a bet. I've played a few backgammon
games - they did not include any limit on the level of the cube.
[...]
> |> I suspect some people may
> |> be annoyed at the way I appear to have been ignoring some of
> |> the details of what they've had to say about all this;
>
> Yes and no. Of course it's important to explain oneself properly, and insist
> on sticking to one's main point of inquiry. But it can get tedious when
> that point has been answered early on! One begins to see why your battle
> with Pertti Lounesto went on so long and tediously!
This is a little offensive. The battle with PL went on so long
because (although he denies this at present) he insisted that "my"
definition of a complex number as an ordered pair of reals was _wrong_.
Here I've not been getting any answers to the questions I've
asked. With apologies to Ilias if I missed it in the details, but
I've been asking exactly what an "optimal" strategy is, if not what
I suggested, and I don't recall anyone giving a definition. People
have suggested various explicit strategies for various explicit
games, but I don't recall a definition of "optimal strategy" among
them. (Except for Wong. But I simply don't see what's so
optimal about a Wong-optimal strategy.)
Ilias Kastanas
In article <34B11F...@math.okstate.edu>,
>> The X_n are just that.
> "Just that" meaning just a martingale in general, nothing to do with
>the questions about backgammon here? Then what does this have to do with
>what we've been talking about?
You had made a comment about my bringing up martingales; I was
replying along the line "on their face, they are good just for A; but there
are extensions good for B". (Or I thought I was!)
We _are_ discussing more than one game, by the way. (1) the B_t,
brownian-motion version; (2) backgammon, the math version -- no bound on
cube values; (3) real-world version, for money. And (3) is not (2);
nobody has ever played (2), or ever will, as there are payoffs exceeding any
real-world bound.
>> Ah, you cannot lose money betting on a submartingale... even if
>> you want to.
>
> Come now. "You cannot lose money betting on a submartingale" is a
>colloquialism. Substitute an actual theorem here and then explain how it
It was a joke... but there is a theorem too, the Upcrossing ine-
quality. Let T_1 = least m with X_m <= a, T_2 = least m after that
with X_m >= b, etc... and U_k = (# of upcrossings by time k) =
sup {i: T_2i <= k} (buy low, <= a, sell high, >= b). If X_m is a
submartingale,
(b-a) E(U_k) <= E( (X_k - a)+) - E( (X_0 - a)+).
>contradicts what I said. It doesn't. If you're betting on a submartingale
>then your expected gain is non-negative (or non-decreasing, or some such,
>depending on exactly what we're referring to). That does not have any
>"almost surely" consequences _unless_ you add some sort of (L1)
>boundedness conditions. I mean, you've given examples here where a
>person _can_ lose money betting on a submartingale.
I mentioned some results (by the way, uniform integrability is
equivalent to convergence in L_1)... but the point I'm trying to make
is different anyway (see below).
> My point in all of this (ok, one of my points) has been that
>we mathematicians say a lot about the "expected value" of various things.
>But our "expected value" is not exactly the same as what it seems to
>me the typical man in the street regards as "expected value". In a
>naive context where we've "defined" (ie attempted to define, not noticing
>the circularity) probability in terms of (a.s.) relative frequency in
>a large number of trials people tend to interpret "expected value" in
>terms of the average value in a large number of trials. When you say
>you can't lose money betting on a submartingale you're colloquializing
>some statement about expected values. That statement is true of our
>mathematical measure-theortic "expected value", but the corresponding
>statement is _not_ true for the naive "average in a large number of
>tries" expected value, except under some hypotheses.
Yes, there are surprises when the variance is infinite... and
more when E itself is!
> I'm surprised you'd feel that "you cannot lose money betting
>on a submartingale" was precise enough to prove something, without
>clarification of exactly what's meant. (This is how you show that
>God exists starting from Godel's theorem, isn't it?)
Ah, that lemma, "nonexistence of God is inconsistent". It goes
back to Euler, right?!
>[...]
>> >> In other words, E(|X|) = inf and the attendant lack of a strong
>> law does not necessarily preclude analyzing the situation and coming up with
>> >> an indicated course of action!
>>
>> > Depends on what you mean by "indicated". Presumably taking the
>>
>> I don't dare use the "O" word... due to your definition...
>
> Again, come now. You say something about the "indicated" action,
>I ask exactly what you mean, and this is how you clarify what you said?
>If you're going to talk about the "indicated" action then presumably you
>mena that the "indicated" action is a better idea than other actions.
>So you should tell me in what sense it's better. I'm _really_ surprised
>at the "don't dare use the "O" word... due to your definition". I didn't
Just kidding! (I thought you _had_ read what I had already written.)
>claim it was the _right_ definition, it was just the definition I was
>using, because it was what seemed to me to be the appropriate
>definiton. You can redefine the word any way you like, a long as you
>tell me what definition you're using.
>
> Again, do tell me in precisely what sense your "indicated" action
>is "indicated".
>
> Um: I'm not certain whether the last two paragraphs need revision
>in the light of what you say below.
...
> I don't recall what the "indicated" action was here, sorry. (My
>recollection is that the thing was introduced here as an example illustrating
>various modes of convergence - already knowing what convergence in
>probability was I may have skimmed it a little fast and missed a detail.)
>If you take the time to remind me of what the "indicated" action is
>please also include an explanation of what the statement that it's
>"indicated" indicates. "Focussing on what's realistic and likely" sounds
>like a good thing in general but it's a little vague.
Okay, here is a look back.
*****************************
>> Now the point I want to make is about types of convergence.
>>
>> Example: Start a symmetric random walk at S_0 = 1; let N = inf{i: S_i =0},
>> and define X_n = S_(N cap n). Then X_n -> X_inf a.s., and X_inf = 0;
>> but E(X_n) = 1 for all n, so this a.s. convergence cannot occur in L_1.
> Precisely. And if you took a slightly modified example you get
>inf(X_n) = -infinity a.s., in spite of the fact that E(X_n) = 1. Hence
>my skepticism about why E(X_n) = 1 is really what we should be worried
>about.
I agree; even in the finite E case there is more to be said.
>> Example: Let X_0 = 0. If X_n-1 = 0, then X_n = 1 or -1 with probability
>> 1/2n each; else = 0. If X_n-1 != 0, then X_n = nX_n-1 with probability
>> 1/n; else = 0. We then have P(X_n = 0) >= 1 - 1/n, while P( X_n = 0 for
>> n >= B) = 0. So X_n -> 0 in probability, but not a.s.
>>
>> (I skip an example where expected values converge in L_1 but not a.s.)
>>
>> Of course these are elementary facts of Real Analysis; I couched
>> them in probabilistic terms to ask, do we _have_ to go by a.s. or L_1?
>> Why not "in probability"? Each has its idiosyncracies. Say, X_n/n -> 0
>> happens a.s. iff E(|X_1|) < inf; it happens in probability iff
>> nP(|X_1| > n) -> 0. Is the latter chopped liver?
I'm suggesting generalized _weak_ laws of l.n. are relevant.
For E infinite as well as finite.
>> Consider something even more familiar:
>>
>> Example: (St. Petersburg) Each X_n is = 2^k with probability 1/2^k; so
>> E(X_1) = inf. We have (**) S_n /n*log(n) -> 1 in probability; I posted
>> a proof some time ago. Again, this convergence is not a.s., since we have
>> lim_sup S_n /n*log(n) = inf a.s.
>>
>> What I'm suggesting is: (**) will do as a "law of large numbers".
>> Never mind a.s.! Yes, (**) does have operational content: it looks behind
>> E(X_1) = inf, "fixed fair-price per game is inf (?!)", and tells me: after n
>> games I can expect n*log(n), so fair-price is log(n). "Inf" really "is"
>> log(n). If I play n = 1000 times (OK, 1024), an entry fee log(n) = 10
>> is break-even. If I can play longer than that, it's a good proposition;
>> if I can only play a couple of hundred times, I should stay away. Or, if
>> I'm offering the game and I find a taker at that fee, I should limit the
>> number of games accordingly. Yes, things do depend on fee level!
Here, (**) is the weak law. Indicated action: play the game if
entry fee < log(n).
>> One can easily modify the example and make it hold not for n*log(n)
> but for n*log(log(n)), or n/log(n) ... and so on. Nothing unique about it.
>>
>> In other words, E(|X|) = inf and the attendant lack of a strong
>> law does not necessarily preclude analyzing the situation and coming up with
>> an indicated course of action!
...
>Better how? I don't see how it can be that much "better", since
>E(|X_1|) = infinity _does_ imply that inf(S_n/n) = - infinity.
: In St. Petersburg we had E(|X|) = inf, and the lim_sup was inf
:too, so the house was facing a lim_inf of -inf. In fact, we even had
:lim_sup S_n/n*log(n) = +inf, a.s. Yet the game was being offered at a
:finite fee; and the indicated action, non-obvious, comes from
:S_n/n*log(n) -> 1 in probability.
So, it is not the lim_sup/inf behavior of S_n/n*log(n) [much
less S_n/n] that matters here. Yes, we get +inf a.s.; but the key fact
is, in probability, the lim exists and is 1.
: Knowing that P(|S_n/n*log(n) - 1| > epsilon) goes to 0 (and often
:knowing at what rate) is the kind of thing focusing on what is realistic and
:likely. Don't you think? What is your view of the St.P. analysis above?
:
:
: Or take the variant with the 1/2^k modified to 1/k(k+1)2^k, and
:counterbalanced by a -1 value so that E(X) = 0 and E(|X|) < inf. Is
:it a fair game? Again, the story is told by (@) S_n/(n/log(n)) -> -1, in
:probability. It's not E per se, it's the law-of-large-numbers behavior
:that matters... right? Well, isn't (@) the l.l.n. here?
Again, the weak law (@) tells the story. Never mind that S_n/n
-> 0 a.s.; (@) warns me "stay away!".
********************
It seems to me _this_, rather than a.s. and L_1, is what is
crucial.
Note that when applying "n -> inf" approximation theorems an implicit
assumption is that "n is n", i.e. no optional stopping. If one can "quit
while ahead", l.l.n.'s and c.l.t.'s go out the window; in that case it's
the law of the Iterated Logarithm that matters.
>> If someone offered you a 1-in-a-million chance of winning a billion
>> dollars, would you pay $500 for it? Just one ticket to buy, take it or
>> leave it. Or maybe $200?
>
> Oh. Maybe you _are_ indicating what "indicated" was supposed to
>mean - I got thrown off by the text from me in between the beginning of
>your reply and the rest of it.
>
> Why don't you actually offer me, say, a 1-in-100 chance to
>win $1000, for a $1 ticket. Then we could find out what I'd do...
Eh, does this mean "no"?!...
>> > A perfect poker player can play forever and know that unless he
>> >gets unreasonably unlucky he will not do much worse than break even on
>> >average, and will come closer to at least breaking even the longer he
>> >plays. If E(|X_1|) is infinite (not that I'm saying it is) then
>> >backgammon simply does not have this property - a player who always
>> >makes the "indicated" move _will_ eventually find that he's
>> >lost an average of $1000000 per game even though he was playing for
>> >nickels (unless he gets unreasonably lucky). Don't see what good
>> >it does to know what action is "indicated", given this.
>>
>> Hmm, is this to happen once in a 1000 years? The rest being good?
>> Especially the one when he finds he has _won_ $1000000 per game!
>
> As I said once before: I thought this was sci.math when I
>jumped in. (Tried to redirect followups once didn't work. Maybe I
Well, this being sci.math, would you accept that $500 deal
after all?!
>did it wrong - interwhat.) The question of whether there exists an
>optimal strategy in backgammon in the sense defined "above" seems
>like a perfectly legitimate question.
I agree. What I'm saying is that there may be cases where the
a.s., lim_inf definition is not _appropriate_. And that a weak-law
based one may be the way to go.
> Seriously: It happens all the time that you have two plays.
>Play A is really the right play, but play B is better against a
>beginner who doesn't know the right response to play B. I can't
>tell you how many times I've lost making play B when it turned
>out the guy knew what to do about it after all (pisses me off,
>given that he didn't know how to respond the week before.)
Oh, yes. It even happens in chess.
...
> I move we introduce the word "equity", btw. Years ago I thought
>backgammon players used the word "equity" because they didn't realize
>it was a synonym for "expected value". But the two are really not
>synonymous: random variables have expected values, and here all our
>probailities depend on the strategies used by both players, as well
>as on the position.
> Ie, if Pos is a position, S1 and S2 are strategies, then
>there is such a thing as
>
>E(Pos, S1, S2) = ExpectedValue(what I win starting at Pos,
> if I use S1 and you use S2) .
>
>Seems like the _equity_ in a position is
>
>Eqity(Pos) = sup inf E(Pos, S1, S2)
> S1 S2
Sounds reasonable.
>> Of course. It's not what the opponent will do; it is what she has
>> done. Phrasing it as "following S" is for convenience. Typically, one
>> picks Ss so that non-Ss are demonstrably worse.
>
> Well we're agreed on that, anyway. (Neither here nor there, but
>it _is_ funny how you can talk about what "she" has done with impunity,
>while if I simply use the same pronoun in my reply I get cracks about
>PC this and that. Never mind...)
Hmm... yes, a funny strategy...
Ilias
David Ullrich
Ilias Kastanas wrote something four days ago that I just saw:
>
> In article <34B11F...@math.okstate.edu>,
> David Ullrich <ull...@math.okstate.edu> wrote:
> >> >> >Ilias Kastanas wrote:[...][...]
> >>
> >> I was talking about martingales in general; sorry about the confusion.
> >> The X_n are just that.
>
> > "Just that" meaning just a martingale in general, nothing to do with
> >the questions about backgammon here? Then what does this have to do with
> >what we've been talking about?
>
> You had made a comment about my bringing up martingales; I was
> replying along the line "on their face, they are good just for A; but there
> are extensions good for B". (Or I thought I was!)
>
> We _are_ discussing more than one game, by the way. (1) the B_t,
> brownian-motion version; (2) backgammon, the math version -- no bound on
> cube values; (3) real-world version, for money. And (3) is not (2);
> nobody has ever played (2), or ever will, as there are payoffs exceeding any
> real-world bound.
True. But it's been asserted here that the fact that we're playing
(3) instead of (2) means that all this other stuff doesn't matter, and I
don't think it's that simple. Cf my admittedly confused devil's-advocate
comments to Bill regarding the "pick a number, the one who picks the
largest number wins" game:
There's "theoretically" no optimal strategy there. Otoh surely the
players are required to write down the number in standard notation (if
they're allowed to specify a number any way at all then there's no algorithm
to decide who won.) And they cannot write down arbitrarily large numbers
before the Sun burns out. So there must be an optimal strategy after all...
(???)
>
> >> Ah, you cannot lose money betting on a submartingale... even if
> >> you want to.
> >
> > Come now. "You cannot lose money betting on a submartingale" is a
> >colloquialism. Substitute an actual theorem here and then explain how it
>
> It was a joke...
Never mind then.
> but there is a theorem too, the Upcrossing inequality.
Yes of course, but
> Let T_1 = least m with X_m <= a, T_2 = least m after that
> with X_m >= b, etc... and U_k = (# of upcrossings by time k) =
> sup {i: T_2i <= k} (buy low, <= a, sell high, >= b). If X_m is a
> submartingale,
>
> (b-a) E(U_k) <= E( (X_k - a)+) - E( (X_0 - a)+).
the question is whether this really says "you can't lose money".
I thought I was making a joke but it turns out it's not so funny:
Yesterday I saw an ad for a new pop-math book, or maybe it's an
old book, by a guy named Pickover. The ad mentions the fascinating
ramge of topics, "from Godel's proof of the existence of God to...".
>
> >[...]
> >> >> In other words, E(|X|) = inf and the attendant lack of a strong
> >> law does not necessarily preclude analyzing the situation and coming up with
> >> >> an indicated course of action!
> >>
> >> > Depends on what you mean by "indicated". Presumably taking the
> >>
> >> I don't dare use the "O" word... due to your definition...
> >
> > Again, come now. You say something about the "indicated" action,
> >I ask exactly what you mean, and this is how you clarify what you said?
> >If you're going to talk about the "indicated" action then presumably you
> >mena that the "indicated" action is a better idea than other actions.
> >So you should tell me in what sense it's better. I'm _really_ surprised
> >at the "don't dare use the "O" word... due to your definition". I didn't
>
> Just kidding! (I thought you _had_ read what I had already written.)
Sorry, I tended to skip some of the clearly irrelevant details, although
they weren't, quite.
Right. What I hadn't noticed about this was that you were talking
about a situation where there was a limit on the number of games. Doesn't
seem like the way real games work.
Various things go out the window when you realize that a "strategy"
can include consideration of how the previous games came out - things that
I've been taking to be independent are not.
> >> If someone offered you a 1-in-a-million chance of winning a billion
> >> dollars, would you pay $500 for it? Just one ticket to buy, take it or
> >> leave it. Or maybe $200?
> >
> > Oh. Maybe you _are_ indicating what "indicated" was supposed to
> >mean - I got thrown off by the text from me in between the beginning of
> >your reply and the rest of it.
> >
> > Why don't you actually offer me, say, a 1-in-100 chance to
> >win $1000, for a $1 ticket. Then we could find out what I'd do...
>
> Eh, does this mean "no"?!...
Does _that_ mean no? People have complained that all these issues don't
come up in the "real" game. It's never happened in the real world that
someone's actually offered me a bet of the form you describe and I
expect it never will. Otoh you _could_ offer me a 1% chance to win
$1000 for a $1 bet. I could tell you what I would do if you made such
an offer but that would only indicate what I _say_ I would do -
there _is_ a way you can find out what I'd _actually_ do. Let me know;
we could easily work out the details (third party to hold the cash,
some "random" publicly available number to determine the result, etc.)
>
> >> > A perfect poker player can play forever and know that unless he
> >> >gets unreasonably unlucky he will not do much worse than break even on
> >> >average, and will come closer to at least breaking even the longer he
> >> >plays. If E(|X_1|) is infinite (not that I'm saying it is) then
> >> >backgammon simply does not have this property - a player who always
> >> >makes the "indicated" move _will_ eventually find that he's
> >> >lost an average of $1000000 per game even though he was playing for
> >> >nickels (unless he gets unreasonably lucky). Don't see what good
> >> >it does to know what action is "indicated", given this.
> >>
> >> Hmm, is this to happen once in a 1000 years? The rest being good?
> >> Especially the one when he finds he has _won_ $1000000 per game!
> >
> > As I said once before: I thought this was sci.math when I
> >jumped in. (Tried to redirect followups once didn't work. Maybe I
>
> Well, this being sci.math, would you accept that $500 deal
> after all?!
Offer me the other deal, the one you can actually cover if
you lose, and find out.
> >did it wrong - interwhat.) The question of whether there exists an
> >optimal strategy in backgammon in the sense defined "above" seems
> >like a perfectly legitimate question.
>
> I agree. What I'm saying is that there may be cases where the
> a.s., lim_inf definition is not _appropriate_. And that a weak-law
> based one may be the way to go.
Could be.
> > Seriously: It happens all the time that you have two plays.
> >Play A is really the right play, but play B is better against a
> >beginner who doesn't know the right response to play B. I can't
> >tell you how many times I've lost making play B when it turned
> >out the guy knew what to do about it after all (pisses me off,
> >given that he didn't know how to respond the week before.)
>
> Oh, yes. It even happens in chess.
How could that be? Chess is trivial...
Ilias Kastanas
In article <34B929...@math.okstate.edu>,
David Ullrich <ull...@math.okstate.edu> wrote:
>Ilias Kastanas wrote something four days ago that I just saw:
>> brownian-motion version; (2) backgammon, the math version -- no bound on
>> cube values; (3) real-world version, for money. And (3) is not (2);
>> nobody has ever played (2), or ever will, as there are payoffs exceeding any
>> real-world bound.
>
> True. But it's been asserted here that the fact that we're playing
>(3) instead of (2) means that all this other stuff doesn't matter, and I
An "honest" approach to (3) might be: the players agree at the start
on the amount each has at risk, and during each game doubling cannot exceed
the amount available to the player who is behind.
>don't think it's that simple. Cf my admittedly confused devil's-advocate
>comments to Bill regarding the "pick a number, the one who picks the
>largest number wins" game:
> There's "theoretically" no optimal strategy there. Otoh surely the
>players are required to write down the number in standard notation (if
>they're allowed to specify a number any way at all then there's no algorithm
>to decide who won.) And they cannot write down arbitrarily large numbers
>before the Sun burns out. So there must be an optimal strategy after all...
>(???)
If the rules specify paper size, digit size etc, there is a maximum
number... I guess I don't see the conundrum here.
...
>> Yes, there are surprises when the variance is infinite... and
>> more when E itself is!
>>
>> > I'm surprised you'd feel that "you cannot lose money betting
>> >on a submartingale" was precise enough to prove something, without
>> >clarification of exactly what's meant. (This is how you show that
>> >God exists starting from Godel's theorem, isn't it?)
>>
>> Ah, that lemma, "nonexistence of God is inconsistent". It goes
>> back to Euler, right?!
>
> I thought I was making a joke but it turns out it's not so funny:
> Yesterday I saw an ad for a new pop-math book, or maybe it's an
>old book, by a guy named Pickover. The ad mentions the fascinating
>ramge of topics, "from Godel's proof of the existence of God to...".
Hmm... Goedel, God, Godot... who knows...
>> >[...]
>> Okay, here is a look back.
>>
>> *****************************
Well, is there a guarantee your backgammon opponent will keep on
playing, game after game, as long as you wish?!... Even a Vegas slot machine
is only available "as is" until they come to empty it -- since at that point
they can change its settings.
In St.P. you want to make sure you _can_ play more than 2^fee times.
Technically, I said "someone"...!
I did "offer" a game once. I had written that in a run of, say,
500 coin flips, with probability 1/2 the player ahead at the midpoint of
the run will remain ahead until the end. Someone replied that he would
lose 3 if so and win 1 if not, and challenged me to play. I told him I
would gladly play a thousand runs, but invited him to think it over first.
He did, and changed his mind.
>> >> > A perfect poker player can play forever and know that unless he
>> >> >gets unreasonably unlucky he will not do much worse than break even on
>> >> >average, and will come closer to at least breaking even the longer he
>> >> >plays. If E(|X_1|) is infinite (not that I'm saying it is) then
>> >> >backgammon simply does not have this property - a player who always
>> >> >makes the "indicated" move _will_ eventually find that he's
>> >> >lost an average of $1000000 per game even though he was playing for
>> >> >nickels (unless he gets unreasonably lucky). Don't see what good
>> >> >it does to know what action is "indicated", given this.
>> >>
>> Hmm, is this to happen once in a 1000 years? The rest being good?
>> >> Especially the one when he finds he has _won_ $1000000 per game!
>> >
>> > As I said once before: I thought this was sci.math when I
>> >jumped in. (Tried to redirect followups once didn't work. Maybe I
>>
>> Well, this being sci.math, would you accept that $500 deal
>> after all?!
>
> Offer me the other deal, the one you can actually cover if
>you lose, and find out.
Is "covering" the issue? Suppose Bill Gates were to read this
and decided to make you the offer, put the billion $ in escrow and all.
Would you accept?
This crude example has E(X) = 1000, yet "in probability" (99.9...% !)
X = -500. Isn't the latter what informs one's decision?
Expanding on this: You mentioned theorems, and I'm not disputing
them; they are theorems. I'm asking instead, to what extent do they apply?
They say "as n -> inf"... do we get thereabouts? In St.P. we have that
lim_sup S_n/n*log(n) = +inf, a.s. ... should I go by that? Yes, it will
achieve the huge value H, by n = 10^10^10... On the other hand, we also
have that, in probability, lim S_n/n*log(n) = 1. It's the latter that
tells me what I'm most _likely_ to encounter.
Mathematically one may adopt this or that criterion and study the
corresponding notion. What I'm saying is that if we want relevance in
practice, I think we should opt for in-probability, weak-law definitions.
Which ones is a matter to study.
>> >did it wrong - interwhat.) The question of whether there exists an
>> >optimal strategy in backgammon in the sense defined "above" seems
>> >like a perfectly legitimate question.
>>
>> I agree. What I'm saying is that there may be cases where the
>> a.s., lim_inf definition is not _appropriate_. And that a weak-law
>> based one may be the way to go.
>
> Could be.
You know, E. Borel wrote somewhere that as far as a single person
is concerned, an event of probability 1/1,000,000 is to be ignored!
Ilias