"Game theory" perfect play possible?
Thomas Conner Annandale
non-negative expectation (never loses in the long run) against ANY
possible opponent WITHOUT paying any attention to the way that opponent
plays?
Say you have a function that only takes in the state of a game of
hold-em up to a point. Like, the number of players, the actor's hole
cards, the cards that have fallen, and the sequence of bets/raises/folds
up to the point of action. The function then returns a tuple of
probabilities for raising, calling, and folding that are its
recommendations for these actions. These probabilities might be saved in
a huge table, or (more realisticaly) be embedded in some kind of neural
net. Does there exist a theoretically "perfect" such function that
absolutely cannot be beaten, even if you know exactly how it will play in
any given situation?
I have a vague recollection of Sklansky mentioning idly in one of his
books that it would indeed be possible, but maybe that's a false memory or
bad interpretation.
I've been toying with the idea of trying to use this approach to produce
a program that plays heads up (where there are much fewer variables to
consider). I was going to use a genetic algorithm to train it, since I
can't see how any other AI method might be applicable, but before I start,
I want to know if there might be a fundamental limit to how far paying
attention only to the current game can take you in the goal of producing
an unbeatable algorithm. I know "Know your opponent" and "It all depends"
have become so ingrained in the collective poker mind that most people
will probably just instinctively say something along those lines, if at
all. But if anyone has any serious thoughts on the matter, I'd be
interested.
--
Thomas
www.boredatheist.com
Randy Hudson
Thomas Conner Annandale <gte...@prism.gatech.edu> wrote:
> Is it theoretically possible to construct an algorithm that achieves
> non-negative expectation (never loses in the long run) against ANY
> possible opponent WITHOUT paying any attention to the way that opponent
> plays?
Heads-up (without a rake), yes. At ring games, no, as "collusion" in the
game-theory sense (which may or may not be collusion in the poker-cheating
sense) can make even a perfect non-colluding program into a loser.
I don't recall if Mike Caro claims ORAC (his heads-up no-limit holdem
program) is game-theroetically perfect. If he were still around, he might
answer :-).
--
Randy Hudson <i...@panix.com>
ben morris
wouldn't be famous) that works against single-player deviations, but it's
not possible to develop a strategy that will work against multiple
non-rational opponents (i.e. the conditions at all full ring games). It
doesn't even matter that the other players aren't colluding, if they are all
far from the equilibrium, your strategy is useless.
An example of this kind of behavior is the 1st day game theory "pick a
number" game, in which 100 people are asked to choose a number between 1 and
100, where a prize is given to the person (or divided among the persons) who
chooses the number closest to 1/2 the average of everyone else's choices.
The nash equilibrium in this game is for everyone to choose 0, and if that
were the default state, any single player deviating from 0 loses payoff
(1/100th of the prize) and the rest of the players gain his share. But, as
is the case when this game is played in real life with real people, almost
no-one plays the equilibrium, and if you want to win, you shouldn't either!
(in an average group of 100, the winning # is usually around 14)
Of course, it would be possible heads-up, or if you could get your algorithm
to play 9 of the ten players on the table.
As a side note, I've often wondered how much poker play at the higher levels
(i.e., more skilled, not just more money) approaches the N.E. solution to
the game. If the top players were ever to get so good as to approximate the
equilibrium, none of them could ever profit from each other. This could put
a dent in the quest to make Poker a televised sport, as there will never be
superstars as long as the e.v. for all the top players is equal. (And even
though football, tennis, baseball, etc theoretically also have n.e.
strategies, it's not the only component of games that come down to who is
the strongest, most talented etc. In poker, "talented" generally comes down
to "who plays the best strategies")
just my thoughts,
ben
"Thomas Conner Annandale" <gte...@prism.gatech.edu> wrote in message
news:advq3u$8qh$1...@news-int.gatech.edu...
Seth Peck
game x), when passed to a function g (f, y) where y is an index of time
and g returns a value of profit, g approaches zero as y approaches
infinity.
Poker (in its cleanest form) is a game that requires a lot more than
statistics to be successful.
Michael de la Maza
Michael Bodell
> On Sun, 9 Jun 2002 14:52:46 +0000 (UTC), Thomas Conner Annandale <gte...@prism.gatech.edu> wrote:
> > Is it theoretically possible to construct an algorithm that achieves
> > non-negative expectation (never loses in the long run) against ANY
> > possible opponent WITHOUT paying any attention to the way that opponent
> > plays?
>
> There is no such strategy. The proof begins: "Suppose that every player is using the positive expectation strategy...."
There is a difference between "non-negative" and "positive". If
everyone was using the perfect strategy than EV = 0. If some people are
using non-perfect strategy than EV may still be 0 or it may be +ve.
I suspect the only reasonable perfect non-negative strategy is to not
play.
Alix Martin
Heads up, the existence of an optimal strategy (of ev 0) can be
proven. Proof involves stating that poker is a matrix game and
applying the minimax theorem. With more than 2 players, an isolated
individual has negative ev because of the "fundamental theorem of
scamming" : any Nash equilibrium in a poker game involves exactly two
coalitions.
Alix Martin
Keith Ellul
But, it is more likely that for any given strategy which does NOT take
into account the play of your opponents (ie, it takes no information
from past hands), there is a counter-strategy (or a combination of
counter-strategies if you are not playing heads up) which will give
your fixed strategy a long-term negative expectation.
But, then again, this is just my intuition. Good luck proving it...
Keith
Keith Ellul
> In article <advq3u$8qh$1...@news-int.gatech.edu>,
> Thomas Conner Annandale <gte...@prism.gatech.edu> wrote:
>
> > Is it theoretically possible to construct an algorithm that achieves
> > non-negative expectation (never loses in the long run) against ANY
> > possible opponent WITHOUT paying any attention to the way that opponent
> > plays?
>
> Heads-up (without a rake), yes.
Can you prove this or are you guessing? It seems counter-intuitive to
me...
Keith
Randy Hudson
Keith Ellul <kbe...@fe02.math.uwaterloo.ca> wrote:
It seems automatic to me. Heads-up means two-person game; no rake means
zero-sum. There must exist a strategy that is unexploitable, probably a
mixed strategy. That is not necessarily a good choice for a real-world
strategy, as it will probably fail to take advantage of significant opponent
errors (the only ones it will take advantage of, and then sort of by
accident, are the times the opponent makes a "dominated" move).
I am not qualified, however, to discuss game theory beyond a very
superficial understanding of some broad concepts. You could probably get as
thorough an answer as you'd care for on rec.games.abstract, where some real
game theorists have been known to hang out. (Darse is a Real Game Theorist
who has participated in r.g.p discussions in the past; he might contribute
to the thread here.)
--
Randy Hudson <i...@panix.com>
Michael Bodell
Well let us start with a simpler game. Player A and B have 100 units.
A is forced to bet 2 unit to start then B puts in 4 units (forced) and
then it is A's turn to act. Each player gets either 0 or 1 with 50%
probability (independent of the other players result). If a player has
a 1 and their opponent has a 0 they win. If both players have the same
number they tie and split the money. Assume if A calls the 2 unit extra
B can act (I.e., both blinds are live). Assume we have a no-limit
situation where the players can raise by any integer amount. What's the
optimum strategy?
With a 1, you clearly want to raise as much as will get a call, unless
no raise will get a call, in which case you raise and take the pot.
With a 0, you clearly want to make any raise that will cause your
opponent to fold, and you want to call versus another 0 but fold versus
a 1.
You want to be able to not lose money regardless of if you are facing:
1. Call every bet.
2. Raise every bet.
3. Call iff you have a 1.
4. Raise iff you have a 1.
5. Randomly raise regardless of cards with probability p, call with a 1
in cases of 1-p, fold with 0 in the cases of 1-p.
6. A strategy made knowing your strategy.
What is the correct strategy? How do the blinds effect the equilibrium?
Dave Wagner
It is easy to see that no such strategy can exist. (One that has positive
EV headsup against any other strategy.) If it existed, it would have to
have positive EV headsup against itself. Who wins in the long run, then?
Cheers,
Dave
Dave Wagner
In article <ae6dtb$ioq$1...@tabloid.uwaterloo.ca>,
Dave Wagner <dgwa...@math.uwaterloo.ca> wrote:
>In article <ae6882$pc1$1...@reader3.panix.com>,
>Randy Hudson <i...@netcom.com> wrote:
>>It seems automatic to me. Heads-up means two-person game; no rake means
>>zero-sum. There must exist a strategy that is unexploitable, probably a
>>mixed strategy. That is not necessarily a good choice for a real-world
>>strategy, as it will probably fail to take advantage of significant opponent
>>errors (the only ones it will take advantage of, and then sort of by
>>accident, are the times the opponent makes a "dominated" move).
>It is easy to see that no such strategy can exist. (One that has positive
>EV headsup against any other strategy.) If it existed, it would have to
>have positive EV headsup against itself. Who wins in the long run, then?
My bad. Randy was only asking for *nonnegative* EV against any other
strategy. This is a bit trickier, but such strategies can exist
only in really boring games. E.g. not in poker....
We're talking symmetric two-player zero-sum games of imperfect information.
Let's say the players are Alice and Bob. Alice's pure strategies are
A_1,...,A_m and Bob's pure strategies are the same B_1,...,B_m. If
Alice picks A_i and Bob picks B_j, then there is a distribution of
payouts P_ij from which the result is chosen randomly -- whatever Alice
wins, Bob loses. Since we're only considering EV, we can replace the
distribution P_ij by its EV, and we have a symmetric two-player zero-sum
game of *perfect* information which is equivalent to the original one for
our purposes.
The hypotheses above really are general enough to cover any form of
headsup *limit* poker, at least. Nolimit, too, I think -- as long as
the table stakes are FINITE. ;-p
Now suppose that Alice has a mixed strategy
PA = p_1.A_1 + p_2.A_2 + ... + p_m.A_m
(where the p_i are nonnegative numbers adding up to 1) which has
nonnegative EV for her against any strategy Bob chooses. That is,
p_i is the probability that Alice will employ strategy A_i on any
given hand. (The four rounds of action in hold'em make this analysis
look suspect, but really it's okay. There can be billions of pure
strategies according to all betting patterns, flops, turns, et cetera.)
Here are three mild assumptions:
1. PA is not a pure strategy (so p_i < 1 for all i).
2. There are no dominated pure strategies (so 0 < p_i for all i).
3. Bob has a strategy QB against which PA has strictly positive
expectation E > 0 for Alice.
(If either 1. or 3. fails, the game is extremely boring -- under optimal
play the EV is zero and the VARIANCE is zero! We can assume 2. becuase
no one would play a dominated strategy under optimal play, anyway.)
I will show that under these assumptions, the "guaranteed non-losing"
strategy PA does not exist.
Since the game is symmetric, Bob can apply the same strategy PB as
Alice. By symmetry of the game, the EV for Alice of PA versus PB
is zero.
Since 0 < p_i < 1 for all i, there is a teeny tiny number c > 0
such that the combination SB = (1+c).PB - c.QB is a valid strategy.
(which just means that it combines the pure strategies B_j with
coefficients which are nonnegative and add up to one).
Now, the EV for Alice of the strategy PA versus SB is -c.E < 0.
So PA isn't the "guaranteed non-loser" it was cracked up to be.
The moral of the story, I guess, is to get a read on your opponent and
look for an edge. But you didn't need the hard math to tell you that!
Cheers,
Dave
Chuck Kincy
"Dave Wagner" <dgwa...@math.uwaterloo.ca> wrote in message
news:ae6dtb$ioq$1...@tabloid.uwaterloo.ca...
> It is easy to see that no such strategy can exist. (One that has positive
> EV headsup against any other strategy.) If it existed, it would have to
> have positive EV headsup against itself. Who wins in the long run, then?
>
This X strategy would have +EV against ANY other strategy, and 0 EV against
itself. Were such a strategy to exist.
Remember ORAC?
Keith Ellul
> There is no such strategy. The proof begins: "Suppose that every
> player is using the positive expectation strategy...."
"Non-negative" and "positive" aren't the same thing. For example, look
at my bankroll ;-).
Anyway, I made some posts earlier where I said that I didn't think that
such a strategy exists, but, after reading some posts, and doing some
quick "research" on the subject (that is, I fired up google) it has
become clear that I didn't know what I was talking about. Actually, I
always knew that I didn't know anything about game theory... I just
figured, hey, how hard can it be? ;-)
Keith
Rick McGrath
> [Regarding guaranteed non-losing strategies...]
>
> In article <ae6dtb$ioq$1...@tabloid.uwaterloo.ca>,
> Dave Wagner <dgwa...@math.uwaterloo.ca> wrote:
> >In article <ae6882$pc1$1...@reader3.panix.com>,
> >Randy Hudson <i...@netcom.com> wrote:
>
> >>It seems automatic to me. Heads-up means two-person game; no rake means
> >>zero-sum. There must exist a strategy that is unexploitable, probably a
> >>mixed strategy. That is not necessarily a good choice for a real-world
> >>strategy, as it will probably fail to take advantage of significant
opponent
> >>errors (the only ones it will take advantage of, and then sort of by
> >>accident, are the times the opponent makes a "dominated" move).
Opponent errors will create pure strategies. (corner solutions)
>
> >It is easy to see that no such strategy can exist. (One that has
positive
> >EV headsup against any other strategy.) If it existed, it would have to
> >have positive EV headsup against itself. Who wins in the long run, then?
>
> My bad. Randy was only asking for *nonnegative* EV against any other
> strategy. This is a bit trickier, but such strategies can exist
> only in really boring games. E.g. not in poker....
Playing "perfect poker" probably is boring, but this suggests that you break
even in the long run against perfect players and win money against everyone
else. I'm thinking that this might be something a few folks around here
aspire to.
>
> We're talking symmetric two-player zero-sum games of imperfect
information.
>
> Let's say the players are Alice and Bob. Alice's pure strategies are
> A_1,...,A_m and Bob's pure strategies are the same B_1,...,B_m. If
> Alice picks A_i and Bob picks B_j, then there is a distribution of
> payouts P_ij from which the result is chosen randomly -- whatever Alice
> wins, Bob loses.
Are Alice and Bob picking strategically or randomly?
Since we're only considering EV, we can replace the
> distribution P_ij by its EV, and we have a symmetric two-player zero-sum
> game of *perfect* information which is equivalent to the original one for
> our purposes.
This does not degenerate to a game with perfect information because the two
players don't know the EV of the hands in advance. This only simplifies the
measurement of the outcome.
>
> The hypotheses above really are general enough to cover any form of
> headsup *limit* poker, at least. Nolimit, too, I think -- as long as
> the table stakes are FINITE. ;-p
>
I don't agree. I think they are poorly constructed.
> Now suppose that Alice has a mixed strategy
> PA = p_1.A_1 + p_2.A_2 + ... + p_m.A_m
> (where the p_i are nonnegative numbers adding up to 1) which has
> nonnegative EV for her against any strategy Bob chooses. That is,
> p_i is the probability that Alice will employ strategy A_i on any
> given hand. (The four rounds of action in hold'em make this analysis
> look suspect, but really it's okay. There can be billions of pure
> strategies according to all betting patterns, flops, turns, et cetera.)
Very true, the solution requires a simultaneous solution of the reaction
curves for all possible starting hands and all possible combinations of
cards on the flop, turn and river, conditional on whether or not both
players stay in. A few billion iterations probably needed for convergence.
In fact, her EV must be exactly 0 for each strategy regardless of what he
does. She will have one strategy for each possible hand, pre-flop, and
nested sub-strategies for all possible outcomes of the common cards.
>
> Here are three mild assumptions:
> 1. PA is not a pure strategy (so p_i < 1 for all i).
> 2. There are no dominated pure strategies (so 0 < p_i for all i).
> 3. Bob has a strategy QB against which PA has strictly positive
> expectation E > 0 for Alice.
>
> (If either 1. or 3. fails, the game is extremely boring -- under optimal
> play the EV is zero and the VARIANCE is zero! We can assume 2. becuase
> no one would play a dominated strategy under optimal play, anyway.)
Assumption 2 precludes assumption 1. Assumpton 3 says Alice has a winning
strategy. You have reintroduced your erroneous assumption of EV>0 instead of
EV .GE. 0. By introducing Assumption 3 you have reduced the problem to
finding a WINNING strategy. We know it doe not exist. Everything after this
is useless for finding a strategy that is EV=0.
The randomness the cards means variance > 0 and EV=0. Forget the pure
strategies. There is a mixed strategy solution.
>
> I will show that under these assumptions, the "guaranteed non-losing"
> strategy PA does not exist.
Of course that is your result, you assumed in assumption three there was a
winning strategy.
I get the impression you see these as all randomly chosen strategies. I see
each strategy as simply being a specific set of percentages attached to the
probabilities of checking, betting, raising and folding each hand at each
given point in the game conditional on the cards seen at that point in the
game. Using EV>0 as a straw man only work to disprove the existence of a
positive EV strategy. We already agree on that . It still says absolutely
nothing about the existence of a mixed strategy equilibirm with EV=0.
> Now, the EV for Alice of the strategy PA versus SB is -c.E < 0.
> So PA isn't the "guaranteed non-loser" it was cracked up to be.
Ahem! You assumed PA to be a guaranteed WINNER not a guaranteed NON-LOSER.
This is all wrong, well no, not wrong, it just doesn't answer the question.
You proved EV>0 does not exist. EV=0 does exist. (Stated this way for
emphasis, not to be insulting.)
>
> Cheers,
> Dave
The optimal set of strategies is such that each sub-strategy p_i for hands
i=1..(52*51/2) that is associated with a particular hand must have an EV of
zero regardless of the strategy played by the opponent. In a limit game this
will result in a optimal rates of bet, check, fold, raise, re-raise,
re-re-raise, and cap on the flop, turn and river for each possible hand
dealt, each possible combination of cards on the flop, each possible turn
card, each possible river card, all conditional on simultaneously solving
all of this for both players for all possible hands. Any play by your
opponent that is suboptimal will drive you to a corner solution (pure
strategy) on some type of play, so both players would have to adhere
strictly to the nash equilibrium.
As I may have mentioned earlier, we solved a simple river problem a while
back and found the optimal bet and bluff rates for a particular scenario.The
calculus was actually pretty easy for a single river problem. Solving
backward from there and solving simultaneously is miserable but possible.
the effective outcome becomes something like this:
At every stage of every hand youplay, you would caculate the probability of
winning that hand based on ALL available information. That probability would
determine the probability of any given action.
Regards,
Rick.
JonCooke
Can I raise 0.0001 units, and does that preclude a re-raise from my opponent?
Manny
If by "perfect poker" you mean this theoretical non-negative EV
strategy, then I don't think this is true. For instance, an
easy-to-develop unbeatable paper-rock-scissors strategy is complete
randomization. That strategy has 0 EV against an expert OR against
someone who plays Rock every single time.
I think that the poker strategy that we would come up with for
non-negative EV heads-up play would have the same property.
that might not even be what you were saying, though.
Manny
> Such a strategy almost certainly does not exist. Then again, it might.
>
Keep in mind, a non-negative EV strategy is very far removed from
creating a POS-EV strategy.
As in another of my replies, consider a game of paper-scissors-rock. A
non-neg strategy is simple to come up with. a pos-ev strategy is much
more difficult.
Just think of heads-up poker as the same thing, but with a much more
complicated set of rules. In the limiting case (i.e. if you play long
enough so that the effect of having the button on the first deal is
negated), it is still a symmetric zero-sum 2 player game. I believe
there is a theorem in game theory that states such a game has a
non-neg EV strategy against any other strategy.
Now, a caveat. The game is obviously 2 player, zero-sum. Each hand is
definitely not symmetric because of the button, but it looks like the
GAME is symmetric because the button switches places. HOWEVER, an
optimal solution might be able to find a non-neg EV strategy when it
has the button, but NOT when the opponent has the button, making the
overall game negative EV. In that sense, the desired solution may not
exist.
A. Prock
I doubt it. I asked him twice:
I got two responses, but neither of them had anything
resembling algorithmic information. In fact, he accused
me of being in league with Mason Malmuth.
- Andrew
A. Prock
>
>Heads up, the existence of an optimal strategy (of ev 0) can be
>proven. Proof involves stating that poker is a matrix game and
>applying the minimax theorem.
It's a BIG matrix too.
If we guees that there are (on average) 4 different ways to
play each street, that's 16 ways one could play each hand,
or 32 if we take position into account. Since there are 1326
starting hands, there are 32*1326 = 42432 ~= 40,000 different
possible strategies.
This would yeild a 40,000 x 40,000 = 1,600,000,000 entry matrix.
I'm actually surprised that no one has sovled this yet. Someone
did solve the preflop case with no bets or raises after the
flop.
It was pretty good stuff.
- Andrew
Piers Shepperson
> Is it theoretically possible to construct an algorithm that achieves
> non-negative expectation (never loses in the long run) against ANY
> possible opponent WITHOUT paying any attention to the way that opponent
> plays?
>
I believe Cutler W.H 'An optial strategy for pot liit poker' Amer
Maths Mounthly 82 (1975) 368-376. outlines an algorithm for a
simplified version of poker. You might like to read it.
Tom Weideman
> If by "perfect poker" you mean this theoretical non-negative EV
> strategy, then I don't think this is true. For instance, an
> easy-to-develop unbeatable paper-rock-scissors strategy is complete
> randomization. That strategy has 0 EV against an expert OR against
> someone who plays Rock every single time.
>
> I think that the poker strategy that we would come up with for
> non-negative EV heads-up play would have the same property.
This is not correct. Poker is more complex in a game-theoretical sense, and
the result is that if player A plays optimally, then player B must also play
optimally to achieve zero ev. A better parallel might be
rock-paper-scissors-pencil, where pencil only beats paper and loses to the
others. With the introduction of dominated strategies (and in poker they
appear easily and require deep knowledge to avoid), the property of locking
in a specific ev with one person playing optimally doesn't hold.
You may want to look at this old post to see an example of this:
http://groups.google.com/groups?hl=en&lr=&selm=B61BE2F6.2AB52%25zwishi%40pac
bell.net&rnum=1
Tom Weideman
Michael Bodell
No. 0.0001 is not an integer and as such not a valid bet. And
re-rasing is fine by opponent if you make a valid raise.
Rick McGrath
"Tom Weideman" <zwi...@attbi.com> wrote in message
news:B92CE467.12910%zwi...@attbi.com...
> Manny wrote:
>
> > If by "perfect poker" you mean this theoretical non-negative EV
> > strategy, then I don't think this is true. For instance, an
> > easy-to-develop unbeatable paper-rock-scissors strategy is complete
> > randomization. That strategy has 0 EV against an expert OR against
> > someone who plays Rock every single time.
> >
> > I think that the poker strategy that we would come up with for
> > non-negative EV heads-up play would have the same property.
>
> This is not correct. Poker is more complex in a game-theoretical sense,
and
> the result is that if player A plays optimally, then player B must also
play
> optimally to achieve zero ev. A better parallel might be
> rock-paper-scissors-pencil, where pencil only beats paper and loses to the
> others. With the introduction of dominated strategies (and in poker they
> appear easily and require deep knowledge to avoid), the property of
locking
> in a specific ev with one person playing optimally doesn't hold.
I agree. It is only negative ev if both play it perfectly. If only one plays
perfectly the outcome does not become high variance EV=0 for that person, it
becomes high variance positive EV for that person. The nash equilibrium is
not a maximum, it is a saddle point.
Rick McGrath
"Piers Shepperson" <piers.sh...@btinternet.com> wrote in message
news:a034af50.02061...@posting.google.com...
Cool, thanks for thecitation.
Rick
Dave Wagner
Paper-Rock-Scissors is an excellent example. As the theorem I
proved yesterday (which is not due to me -- it is in the original
von Neumann & Morgenstern paper) implies, if you know what your
opponent's strategy is, and it beats some strategy of yours, then
you can find a strategy that beats it. (Except in degenerate games
in which perfect play yields a payout of 0 on every round.)
Cheers,
Dave
Dave Wagner
Keith Ellul <kbe...@fe02.math.uwaterloo.ca> wrote:
>On Sun, 9 Jun 2002, Michael de la Maza wrote:
>
>> There is no such strategy. The proof begins: "Suppose that every
>> player is using the positive expectation strategy...."
>
>"Non-negative" and "positive" aren't the same thing. For example, look
>at my bankroll ;-).
>
>Anyway, I made some posts earlier where I said that I didn't think that
>such a strategy exists, but, after reading some posts, and doing some
>quick "research" on the subject (that is, I fired up google) it has
>become clear that I didn't know what I was talking about. Actually, I
>always knew that I didn't know anything about game theory... I just
>figured, hey, how hard can it be? ;-)
>
>Keith
>
Hi Keith,
I posted the proof yesterday.
Interested in a trip to Rama this weekend?
Dave
Barbara Yoon
> Is it theoretically possible to construct an algorithm that achieves
> paying any attention to the way that opponent plays?
Randy Hudson:
> Heads-up (without a rake), yes.
Keith Ellul:
> Can you prove this or are you guessing? It seems counter-intuitive to me...
Randy Hudson:
> It seems automatic to me. Heads-up means two-person game; no rake
> means zero-sum. There must exist a strategy that is unexploitable...
Rick McGrath:
> Playing "perfect poker"...
Manny:
> If by "perfect poker" you mean this theoretical non-negative EV strategy,
> then I don't think this is true. For instance, an easy-to-develop unbeatable
> paper-rock-scissors strategy is complete randomization. That strategy
> has 0 EV against an expert OR against someone who plays Rock every
> single time. I think that the poker strategy that we would come up with
> for non-negative EV heads-up play would have the same property.
Tom Weideman:
> This is not correct. Poker is more complex in a game-theoretical sense,
> and the result is that if player A plays optimally, then player B must
> also play optimally to achieve zero ev. A better parallel might be
> rock-paper-scissors-pencil, where pencil only beats paper and loses
> to the others. With the introduction of dominated strategies, the property
> of locking in a specific ev with one person playing optimally doesn't hold.
Rick McGrath:
> I agree. It is only negative ev if both play it perfectly.
Whaa?! In a "no rake...zero-sum" game...?!
Dave Wagner
news:<Pine.SOL.4.44.020611...@fe02.math.uwaterloo.ca>...
>> Such a strategy almost certainly does not exist. Then again, it might.
>>
>
>Keep in mind, a non-negative EV strategy is very far removed from
>creating a POS-EV strategy.
>
>As in another of my replies, consider a game of paper-scissors-rock. A
>non-neg strategy is simple to come up with. a pos-ev strategy is much
>more difficult.
>
>Just think of heads-up poker as the same thing, but with a much more
>complicated set of rules. In the limiting case (i.e. if you play long
>enough so that the effect of having the button on the first deal is
>negated), it is still a symmetric zero-sum 2 player game. I believe
>there is a theorem in game theory that states such a game has a
>non-neg EV strategy against any other strategy.
Against any one other particular strategy, yes. But against all other
strategies simultaneously, no. If your opponent knows your strategy,
and it beats some other strategy, then he can find a strategy which
beats you. Except in trivial and uninteresting cases.
>Now, a caveat. The game is obviously 2 player, zero-sum. Each hand is
>definitely not symmetric because of the button, but it looks like the
>GAME is symmetric because the button switches places. HOWEVER, an
>optimal solution might be able to find a non-neg EV strategy when it
>has the button, but NOT when the opponent has the button, making the
>overall game negative EV. In that sense, the desired solution may not
>exist.
Button, button, who has the button? It doesn't matter, it all averages
out. That is the excellent simplification of looking only at
*expectation*.
Cheers,
Dave
Rick McGrath
there, yes it should be EV=0. Thanks
Rick
"Barbara Yoon" <by...@erols.com> wrote in message
news:ae9496$sct$1...@bob.news.rcn.net...
Rick McGrath
Yes, but this application might be a little different because we are dealing
with both the information problem and stochastic dominance not pure
dominance. Rock paper scissors is ONLY an information problem. With full
information, Rock paper scissors is meaningless, yet a skilled poker player
and a novice who play hold'em face up (to get rid of the information
problem) will not randomly break even. The knowledge by the skilled player
of the relative dominance of hands will give an advantage. Therefore the
payout need not be exactly 0 every round, it only needs an EV of 0. The rest
of the vN-M discussion supports, I think, the existence of a nash
equilibrium resulting in EV=0 for both parties.
Rick.
>
> Cheers,
> Dave
Rick McGrath
behavior? Can maniacs be purely random? We had a discussion a month or two
ago about this. The bigger the difference between the skills of the players,
the more advantageous it is for the weak player to icrease the game variance
a much as possible. In the limit, the complete maniac never looks at his
cards.
Rick.
"ben morris" <benjami...@yale.edu> wrote in message
news:ae0em4$o48$1...@news.ycc.yale.edu...
> While there has to be game-theoretical solution to poker (otherwise Nash
> wouldn't be famous) that works against single-player deviations, but it's
> not possible to develop a strategy that will work against multiple
> non-rational opponents (i.e. the conditions at all full ring games). It
> doesn't even matter that the other players aren't colluding, if they are
all
> far from the equilibrium, your strategy is useless.
>
> An example of this kind of behavior is the 1st day game theory "pick a
> number" game, in which 100 people are asked to choose a number between 1
and
> 100, where a prize is given to the person (or divided among the persons)
who
> chooses the number closest to 1/2 the average of everyone else's choices.
> The nash equilibrium in this game is for everyone to choose 0, and if that
> were the default state, any single player deviating from 0 loses payoff
> (1/100th of the prize) and the rest of the players gain his share. But,
as
> is the case when this game is played in real life with real people, almost
> no-one plays the equilibrium, and if you want to win, you shouldn't
either!
> (in an average group of 100, the winning # is usually around 14)
>
> Of course, it would be possible heads-up, or if you could get your
algorithm
> to play 9 of the ten players on the table.
>
> As a side note, I've often wondered how much poker play at the higher
levels
> (i.e., more skilled, not just more money) approaches the N.E. solution to
> the game. If the top players were ever to get so good as to approximate
the
> equilibrium, none of them could ever profit from each other. This could
put
> a dent in the quest to make Poker a televised sport, as there will never
be
> superstars as long as the e.v. for all the top players is equal. (And
even
> though football, tennis, baseball, etc theoretically also have n.e.
> strategies, it's not the only component of games that come down to who is
> the strongest, most talented etc. In poker, "talented" generally comes
down
> to "who plays the best strategies")
>
> just my thoughts,
> ben
>
>
> "Thomas Conner Annandale" <gte...@prism.gatech.edu> wrote in message
> news:advq3u$8qh$1...@news-int.gatech.edu...
> > Is it theoretically possible to construct an algorithm that achieves
> > non-negative expectation (never loses in the long run) against ANY
> > possible opponent WITHOUT paying any attention to the way that opponent
> > plays?
> >
Rick McGrath
> In article <5e096d64.0206...@posting.google.com>,
> Manny <ceea...@yahoo.com> wrote:
> >Keith Ellul <kbe...@fe02.math.uwaterloo.ca> wrote in message
> news:<Pine.SOL.4.44.020611...@fe02.math.uwaterloo.ca>...
> >> Such a strategy almost certainly does not exist. Then again, it might.
> >>
> >
> >Keep in mind, a non-negative EV strategy is very far removed from
> >creating a POS-EV strategy.
> >
> >As in another of my replies, consider a game of paper-scissors-rock. A
> >non-neg strategy is simple to come up with. a pos-ev strategy is much
> >more difficult.
> >
> >Just think of heads-up poker as the same thing, but with a much more
> >complicated set of rules. In the limiting case (i.e. if you play long
> >enough so that the effect of having the button on the first deal is
> >negated), it is still a symmetric zero-sum 2 player game. I believe
> >there is a theorem in game theory that states such a game has a
> >non-neg EV strategy against any other strategy.
>
> Against any one other particular strategy, yes. But against all other
> strategies simultaneously, no. If your opponent knows your strategy,
> and it beats some other strategy, then he can find a strategy which
> beats you. Except in trivial and uninteresting cases.
Right, there is some strategy that makes all other strategies meaningless.
But it does not provide the maximum EV if the opponent plays sub-optimally.
Just better than EV=0. If you get greedy, then you can lose as well as win.
If you play the optimal strategy but you opponent does not, you make a small
positive profit with relatively low risk. If you want to chase after every
last nickel, you increase your risk quickly relative to your EV.
Rick.
>
>
> >Now, a caveat. The game is obviously 2 player, zero-sum. Each hand is
> >definitely not symmetric because of the button, but it looks like the
> >GAME is symmetric because the button switches places. HOWEVER, an
> >optimal solution might be able to find a non-neg EV strategy when it
> >has the button, but NOT when the opponent has the button, making the
> >overall game negative EV. In that sense, the desired solution may not
> >exist.
>
> Button, button, who has the button? It doesn't matter, it all averages
> out. That is the excellent simplification of looking only at
> *expectation*
>
> Cheers,
> Dave
Dave Wagner
Rick McGrath <rmcgr...@comcast.net> wrote:
>
>"Dave Wagner" <dgwa...@math.uwaterloo.ca> wrote in message
>news:ae92ts$p7r$1...@tabloid.uwaterloo.ca...
>> Paper-Rock-Scissors is an excellent example. As the theorem I
>> proved yesterday (which is not due to me -- it is in the original
>> von Neumann & Morgenstern paper) implies, if you know what your
>> opponent's strategy is, and it beats some strategy of yours, then
>> you can find a strategy that beats it. (Except in degenerate games
>> in which perfect play yields a payout of 0 on every round.)
>
>Yes, but this application might be a little different because we are dealing
>with both the information problem and stochastic dominance not pure
>dominance. Rock paper scissors is ONLY an information problem. With full
>information, Rock paper scissors is meaningless, yet a skilled poker player
>and a novice who play hold'em face up (to get rid of the information
>problem) will not randomly break even. The knowledge by the skilled player
>of the relative dominance of hands will give an advantage. Therefore the
>payout need not be exactly 0 every round, it only needs an EV of 0. The rest
>of the vN-M discussion supports, I think, the existence of a nash
>equilibrium resulting in EV=0 for both parties.
>
>Rick.
Stochasticity (randomness) can be ignored if we're only interested in
expected value. If you want to control variance as well, then that's
a more difficult issue.
Definitely, if both players play optimally, the EV is zero for both
players. Your example of a skilled vs. unskilled player is moot --
we're seeking a strategy which is EV>=0 against ANYONE! So you should
be throwing it against Daniel Negreanu, among others -- not against
the six fish on my block.
The information cascade due to the several rounds of action does look
like an interesting point at which the von Neumann-Morgenstern theory
might break down. Let me think. Before you have to act you get to
narrow your strategy -- am I playing my "T4o utg" game or my
"KK in the cutoff, 2 limpers one raise" game? Depending on your
action, the opponents take other actions, which in turn narrow your
choices of available good strategies. There is a huge jungle of
possibilities outside the window. But there are only finitely many
rounds of action, only finitely many players in the game, and only
finitely many things each player can do. You can list them all --
each pure strategy is something like this:
In 4th position holding Qc4h with the player utg folding, I will raise.
Having seen a re-raise and a cap, all folding to me, I will call.
Now that the flop comes AsAdKh, being the first to act, I will bet out...
et cetera. Note that this is not a good strategy. ;-) But it is a pure
strategy because it leaves no doubt about what will be done in any
circumstance of the game. There are only finitely many such strategies
(most of which are extremely stupid -- including flopping a royal,
betting and capping every street, and folding after everyone checks
the river.)
The interesting thing is that a strategy as above might apply only up
to a certain point in a hand, but then the play might deviate from
the hypotheses of the pure strategy. Once it no longer applies,
what to do next? In vN&M, you and the opponent choose a strategy
according to some distribution, compare them, and weigh the result.
That is, NO INFORMATION IS EXCHANGED! Clearly, poker is not like that.
I wonder whether vN&M addressed this issue. In any case, someone should!
Dammit! Another research project....
Thankyou very much!
-Dave
Manny
>
> > If by "perfect poker" you mean this theoretical non-negative EV
> > strategy, then I don't think this is true. For instance, an
> > easy-to-develop unbeatable paper-rock-scissors strategy is complete
> > randomization. That strategy has 0 EV against an expert OR against
> > someone who plays Rock every single time.
> >
> > I think that the poker strategy that we would come up with for
> > non-negative EV heads-up play would have the same property.
>
> This is not correct. Poker is more complex in a game-theoretical sense, and
> the result is that if player A plays optimally, then player B must also play
> optimally to achieve zero ev.
Not correct indeed. Simple simple examples can show why what I said is
wrong wrong wrong (the opponent folds 100% of his SB's for example).
But do you agree that a non-neg EV strategy exists for heads-up poker?
If not, see my questions below.
A better parallel might be
> rock-paper-scissors-pencil, where pencil only beats paper and loses to the
> others. With the introduction of dominated strategies (and in poker they
> appear easily and require deep knowledge to avoid), the property of locking
> in a specific ev with one person playing optimally doesn't hold.
>
> You may want to look at this old post to see an example of this:
>
> http://groups.google.com/groups?hl=en&lr=&selm=B61BE2F6.2AB52%25zwishi%40pac
> bell.net&rnum=1
>
>
> Tom Weideman
Thanks for the link.
To anyone with more knowledge of game theory:
I thought (from rudimentary knowledge of game theory) that symmetric,
zero-sum, two-player games were proven to have a strategy, regardless
of the opponents strategy, guaranteeing at least a 0 payout.
This theorem might also require that the game have finite state-space,
like chess or POKER, but I'm not sure this is necessary.
Q1: Is my statement about sym., zero-sum two-player games WRONG?
Q2: If my statement is correct, does heads up poker satisfy the
conditions of the statement? If not, why not?
Q3: To get back to the original poster's question. If the statement is
correct and heads-up poker satisfies the conditions, then can we agree
that heads-up poker must have a >=0 payoff strategy?
That's it for now.
Thomas Conner Annandale
> Well let us start with a simpler game. Player A and B have 100 units.
> A is forced to bet 2 unit to start then B puts in 4 units (forced) and
> then it is A's turn to act. Each player gets either 0 or 1 with 50%
> probability (independent of the other players result). If a player has
> a 1 and their opponent has a 0 they win. If both players have the same
> number they tie and split the money. Assume if A calls the 2 unit extra
> B can act (I.e., both blinds are live). Assume we have a no-limit
> situation where the players can raise by any integer amount. What's the
> optimum strategy?
> With a 1, you clearly want to raise as much as will get a call, unless
> no raise will get a call, in which case you raise and take the pot.
> With a 0, you clearly want to make any raise that will cause your
> opponent to fold, and you want to call versus another 0 but fold versus
> a 1.
> You want to be able to not lose money regardless of if you are facing:
> 1. Call every bet.
> 2. Raise every bet.
> 3. Call iff you have a 1.
> 4. Raise iff you have a 1.
> 5. Randomly raise regardless of cards with probability p, call with a 1
> in cases of 1-p, fold with 0 in the cases of 1-p.
> 6. A strategy made knowing your strategy.
> What is the correct strategy? How do the blinds effect the equilibrium?
I find this question to be rather interesting, and so even though I don't
have any headway into an answer, I'm making a reply in fear that that
thread will simply die out.
Is there really a systematic way to finding an optimal sollution to this
"simple" (yet still boggling, to me) problem? If so, I'd be really
interested to hear it. I'd be pleasantly surprised if there were any way
to solve this problem short of a brute search with a genetic algorithm.
I'm pretty much only interested in an algorithm that satisfies condition
six above (finding an optimal solution). The others seem solvable through
a little trial and error.
--
Thomas
www.boredatheist.com
Tom Weideman
> But do you agree that a non-neg EV strategy exists for heads-up poker?
> If not, see my questions below.
Of course I agree, assuming your use of the word "strategy" is broad enough
to include mixed strategies.
Tom Weideman
Gary Carson
(Dave Wagner) wrote:
>Stochasticity (randomness) can be ignored if we're only interested in
>expected value.
What?
How do you compute expected value if you ignore probability
distribution?
Gary Carson
http:// garycarson.home.mindspring.com
NOSPA...@sebastian9.com
According to Dave Wagner <dgwa...@math.uwaterloo.ca>:
> Now suppose that Alice has a mixed strategy
> PA = p_1.A_1 + p_2.A_2 + ... + p_m.A_m
> (where the p_i are nonnegative numbers adding up to 1) which has
> nonnegative EV for her against any strategy Bob chooses. That is,
> p_i is the probability that Alice will employ strategy A_i on any
> given hand. (The four rounds of action in hold'em make this analysis
> look suspect, but really it's okay. There can be billions of pure
> strategies according to all betting patterns, flops, turns, et cetera.)
>
> 1. PA is not a pure strategy (so p_i < 1 for all i).
> 2. There are no dominated pure strategies (so 0 < p_i for all i).
Note that the two parts of this statement are not exactly equivalent
- you can have an undominated pure strategy that still has p_i = 0
for some optimal mixed strategy (this implies that there is more
than one optimal mixed strategy for this game).
> 3. Bob has a strategy QB against which PA has strictly positive
> expectation E > 0 for Alice.
--
Dave Wallace (Remove NOSPAM from my address to email me)
It is quite humbling to realize that the storage occupied by the longest
line from a typical Usenet posting is sufficient to provide a state space
so vast that all the computation power in the world can not conquer it.
Rick McGrath
was trying to prove a strategy with a non-negative EV, I've found your
comments interesting and useful. Drop an email if you like.
Rick
"Dave Wagner" <dgwa...@math.uwaterloo.ca> wrote in message
news:ae9a9j$s84$1...@tabloid.uwaterloo.ca...
Stig Eide
a game where Game Theory only accomplishes to break even. You might
find it interesting to learn that there is held a yearly competiotion
to make the best RPS computer program. The best program to date,
"Iocaine Powder", only uses the Game Theoretical solution if he can't
beat the opponent with other methods.
You can read the authors description of the program here:
http://www.ofb.net/~egnor/iocaine.html
Peace!
Stig Eide
PS: You can find more info about the world of RPS here:
www.worldrps.com
Dave Wagner
Okay.... so Alice picks a strategy A_i and Bob picks a strategy B_j,
and then the outcome is determined randomly according to some distribution
P_ij depending on these strategies. That's a two-person game of imperfect
information. The actual outcome can vary from instance to instance. If
we're only interested in the expected values over the long haul, then we
can replace the distribution P_ij by its expectation E_ij. The result
is a two-person game of *perfect* information. And so there is no more
randomness in the game, except for that which is introduced by the players
when choosing a mixed strategy.
Cheers,
Dave
Dave Wagner
That's a good point, Dave. I don't really know if the nonexistence of an
unbeatable strategy can be proven in circumstances more general that the
ones I stated. But at least I was clear about my hypotheses, and they
don't seem (to me) to be horribly restrictive.
Cheers,
Dave
Keith Ellul
Hi Dave.
I am about 3 days behind on my r.g.p. reading. Like, for example, I'm
just reading this now.
I am still confused about this whole "perfect strategy" thing. I read
your proof and only got about half way through it before I realized
that I would have to read it carefully to get anything out of it.
Anyway I've saved it and I'll look through it when I am somewhat
awake.
As for Rama... well I guess the weekend is almost done ;-) Maybe some
other time. Have you ever played at the CNE? That is coming up. I
hear that it is real smoky but the games are juicy.
Keith
Keith Ellul
That was the original assumption.
Keith
Barbara Yoon
>>> I agree. It is only negative ev if both play it perfectly.
me:
>> Whaa?! In a "no rake...zero-sum" game...?!
Keith Ellul:
> That was the original assumption.
Yes...that's why the quote marks...
And so your own point here is...?!