Is bridge solvable?

[Gazumper]

Does bridge have a game theory optimal solution to maximize IMPS? In other words is there an optimal unexploitable way for a partnership to play in any given situation that is indifferent to the opps strategy. Does a perfect GIB exist?

 

There would be no bidding convention as such, all alerts are simply, "I have selected a bid from a range of possible bids and matching probabilities according to optimal game theory to maximize our IMPS", which is how the partnership understands it. Same goes for carding.

 

What if you didn't know your partner but you knew he/she was a perfect logician and would thus deduce the perfect strategy you would both be using? Multiple possible solutions would make this interesting.

[Fluffy]

There is a perfect play double dummy, and that was already solved long ago. SIngle dummy it depends on opponent's playing style so it is not solvable.

 

There is a perfect bidding system when the opponents remain silent, it would take several years to develop but since it would be useless nobody is working on it as far as I know. But in reality opponents do not remain silent, and a perfect system would depend on opponent's system, making it not solvable.

 

There could be a perfect bidding system if it is used by the 4 players exactly the same. Nobody is close to it either.

[hrothgar]

There is a perfect play double dummy, and that was already solved long ago. SIngle dummy it depends on opponent's playing style so it is not solvable.

 

This is nonsense. By definition, any game theoretic problem depends on the opponent's playing style.

 

At a high level, Fluffy is correct:

 

1. A trying to solve bridge as a whole would require enormous time / effort

2. No one is working on this

 

With this said and done, there have been game theoretic proofs of isolated problems such as restricted choice.

[cloa513]

That bidding descriptions leaves the result with so little information that is absolutely no way to get to close form the hands to do the analysis. Its worse than conventions.

[GreenMan]

This is nonsense. By definition, any game theoretic problem depends on the opponent's playing style.

 

The OP asked for a game-theoretic solution that did not require knowledge of the opps' style. I suspect the reference to GT was out of place here.

 

By my limited understanding of GT, any solution would depend on knowing the opps' strategy, e.g. what % of the time they bid strategically and falsecard. (e.g, restricted-choice calculations tend to assume random selection from equals, IIRC.) It also must account for the likelihood of opponents' errors -- the Principle of Restricted Talent, as Chthonic called it. Since these calculations change for each set of opponents, I suspect any such strategy would be effectively impossible to create.

 

Anyone with a better understanding of game theory is invited to correct my mistakes. :) I find it a fascinating field that I haven't had much opportunity to explore.

[hrothgar]

The OP asked for a game-theoretic solution that did not require knowledge of the opps' style. I suspect the reference to GT was out of place here.

 

By my limited understanding of GT, any solution would depend on knowing the opps' strategy, e.g. what % of the time they bid strategically and falsecard. (e.g, restricted-choice calculations tend to assume random selection from equals, IIRC.) It also must account for the likelihood of opponents' errors -- the Principle of Restricted Talent, as Chthonic called it. Since these calculations change for each set of opponents, I suspect any such strategy would be effectively impossible to create.

 

Anyone with a better understanding of game theory is invited to correct my mistakes. :) I find it a fascinating field that I haven't had much opportunity to explore.

 

I did my first graduate degree in game theory...

 

Few quick comments

 

1. Since Nash, the fundamental goal of game theoretic analysis is to prove the existence of an "equilibrium". Does there exist a set of strategies, once chosen, where no player has an incentive to deviate. The point of the analysis is to demonstrate that your behavior is "optimal" regardless of what strategy the opponents chose.

 

2. Its possible to add in errors by the opponents to this analysis. You can also bound their rationality (or equivalently, add the cost of calculating a strategy to the objective function). This type of analysis usually isn't considered that interesting since it develops into a question about your assumptions regarding the opponents.

[broze]

Another (more interesting?) question is whether the perfect bidding system would be consistent. That is to say holding the same cards under the exact same conditions would you always make the same bid? Certainly in the cardplay randomisation of spot cards is important for perfect defence. I wonder if an optimal bidding strategy would involve the randomisation of calls.

[GreenMan]

Thanks, hrothgar. :) So if I'm understanding correctly, there may or may not be an equilibrium where a game-theoretical optimal strategy exists, and it may be possible in principle to figure out whether this strategy exists and, if so, what it is. This strategy could then be programmed into GIB. It would be a lot of work and no one is bothering with it right now. A human using it would probably want to be able to adjust it according to who the opponents are (and partner, if he or she is also an unknown quantity), and that gets even messier.

 

So it's kind of an interesting question that is unlikely to be answered anytime soon. Bridge imitates life. :)

[hrothgar]

Another (more interesting?) question is whether the perfect bidding system would be consistent. That is to say holding the same cards under the exact same conditions would you always make the same bid? Certainly in the cardplay randomisation of spot cards is important for perfect defence. I wonder if an optimal bidding strategy would involve the randomisation of calls.

 

I believe (but can not prove) that mixed strategies factor into optimal bidding.

Personally, I've always wondered whether bidding systems exhibit transitivity.

 

If system A is objectively better than system B, and system B is better than system C, does it necessarily follow that A > C

 

I suspect that anyone hoping to seriously apply game theory to bridge is headed for a series of disappointments. Its not that I don't believe that game theory is applicable to the game, rather I strongly feel that the regulatory environment is designed to stifle change. You may very well learn a lot about a fairly interesting topic. Just don't expect to ever be able to apply any of this knowledge.

 

Here are a few practical example where game theory crops up. The first, and probably the best example, is restricted choice. This is a lovely example of what's known as a “mixed strategy” in which the defender randomizes which honor they are going to play. The “catch”, so to speak, is that this is a well known example. Strong players already know about restricted choice. Framing this as a game theory problem isn't really going to help your game that much.

 

A second, very interesting example, is the notion of a “psyche”. I have long argued that the behavior that is codified as a psyche is another example of a mixed strategy. Unfortunately, the regulatory structures in most locations don't permit players to use this concept to define their agreements.

Potentially, the most interested area of study is population dynamics, in which one studies whether a population of biddings systems can be “invaded” by a new strain. Its entirely possible that the relationship between bidding systems is best described as “Rock, Paper, Scissors”. There is no one best bidding system. The long term equilibrium is actually some optimal ratio of bidding systems. A monoculture is inherently unstable and could be invaded by some new strain.

 

I'm attaching an article I tried to get submitted to the Bridge World a few years back. I hope that people find this of interest.

 

Mixed Strategies as applied to Bridge

 

The academic discipline of game theory differentiates between “pure” strategies and “mixed” strategies. Pure strategies are deterministic. Players choosing a pure strategy follow a predictable course of action. In contrast, mixed strategies deliberately incorporate random action. The simplest example of a mixed strategy equilibrium is the Penny Matching game. Two players simultaneous display a penny. If the two coins “match” (both coins are heads or both coins are tails) then Player 1 keeps the two pennies. If the two coins don't match then Player 2 keeps both pennies. The only equilibrium strategy to this game is mixed. Each player should randomly determine whether to display Heads or Tails using a 50/50 weighting scheme.

The concept of a mixed strategy can be applied to a number of areas within bridge. The simplest and best know examples come from declarer play and defense. Many well understood problems like restricted choice make use of mixed strategies. For example, declarer leads a low Diamond into D QJ9 and plays the Queen after LHO plays low. RHO holds both the Ace and the King and needs to determine which card to cover with. Restricted choice analysis presumes that the defender is applying a mixed strategy will randomly chose to cover with the Ace or the King, once again applying a 50/50 weighing scheme.

Mixed strategies can also be applied to the design of bidding systems. Players applying a “pure” bidding strategy will always chose the same bid bid with a given hand. In contrast, players employing a mixed bidding strategy allow deliberate randomization. Consider the following example taken from Bridge My Way by Zia Mahmood. You hold

 

S AQJ3

H K5

D 873

C A653

 

The auction starts

 

1H – 1S

3S - ???

 

and you need to chose a rebid. Zia advocates a bidding style in which players should randomize between 4C and 4D cuebids. Zia never goes so far as to discuss probabilities, but hypothetically he might chose a 4C cuebid 80% of the time and a 4D cuebid 20% of the time. Alternatively, consider the following example: White versus Red partner opens 1H in first seat promising 5+ Hearts and 10-15 HCP. RHO passes. You hold:

 

S 742

H AK762

D 9732

C 4

 

I advocate a hypothetical “mixed” strategy in which players bidders

 

4H: 60% of the time

3NT: 20% of the time

2NT: 10% of the time

2D: 5% of the time

1S: 5% of the time

 

Players who adopt mixed bidding strategies allow for the use of multiple bids to describe a single hand. As a consequence, many responses could show radically different hand types. For example, players adopting Zia's Sting Cue bid style need to describe their 4C cue bids as either "First round control of Clubs or no control of clubs". In an equivalent fashion, my partners would need to describe my 3NT raise of a Precision 1H openings as either a strong balanced hand willing to declare 3NT OR a preemptive raise of Hearts.

 

In turn, this brings us to the last major area in which mixed strategies and bridge overlap: Regulatory structures. Few if any Zonal authorities incorporate mixed bidding strategies into their regulatory structures. Instead, regulators attempt to sidestep the issue using the concept of a psychic call. Regulators and players pretend that psychic calls are “deliberate and gross misstatements of honor strength or suit length”. In actuality, so-called psychic calls are a subset of a more complex meta-agreement involving mixed bidding strategies.

 

I argue that neither players nor regulators are served by this pretense. Complete disclosure can never be achieved unless the regulatory structure matches the actual strategies employed by players.

[nige1]

I believe (but can not prove) that mixed strategies factor into optimal bidding.

Agree (and I think you can prove it by analogy with Poker).

Personally, I've always wondered whether bidding systems exhibit transitivity. If system A is objectively better than system B, and system B is better than system C, does it necessarily follow that A > C

I'm unsure. What does it mean to say that call a > call b > call c > call a ? and if such a situation can arise, won't a mixed strategy work? Were that argument germane, would it also apply to Hrothgar's systems example, to produce a dominant mixed-strategy system (as good as or better than "Rock", "Paper", and "Scissors")?

I suspect that anyone hoping to seriously apply game theory to bridge is headed for a series of disappointments. Its not that I don't believe that game theory is applicable to the game, rather I strongly feel that the regulatory environment is designed to stifle change. You may very well learn a lot about a fairly interesting topic. Just don't expect to ever be able to apply any of this knowledge.

Agree. The "psych" examples in Hrothgar's article are an excellent illustration. Encrypted calls and signals are another fascinating taboo.

Here are a few practical examples where game theory crops up. The first, and probably the best example, is restricted choice [snip]

IMO, another frequent example requiring a simple mixed strategy is this kind of ending.[hv=pc=n&w=sahadac2&e=s2hdckjt]266|100| You are West, declarer in a notrump contract. Defender's ♣s include ♣AQ. Defenders know your hand; but you don't know which defender has what ♣ honour. Your LHO (North) leads a small ♣. What do you do? It's tempting to rise with ♣K because if that is the right guess you make the rest of the tricks. LHO knows this, however, so holding ♣Ax(..) will tend to cash ♣A and save you the guess. Let's refine this example. Suppose that you need the rest of the tricks to make your contract. Now, surely you must play ♣K? But wait! Would an expert West ever under-lead ♣A? Well then, should you cut your losses and finesse ♣T? Even in this extreme context, IMO, an expert defender should (sometimes) put you to the test. Theoretically, the mixed strategy depends on the contract and method of scoring. An intriguing follow-up question: Practically, the mix depends on your estimate of the state of the match, and how understanding and tolerant your team-mates are: but does it also depend on the length of the match? (IMO No).[/hv]

[hrothgar]

Agree.

 

I'm unsure. What does it mean to say that

call a > call b > call c > call a;

and if such a situation arose, wouldn't mixed strategy work?

 

 

Sorry if I was unclear. I was referring to systems as a whole rather than individual bids.

 

Imagine a case in which GIB were to play large numbers of boards with perfect implementations of Acol, Regres, and Roth-Stone

 

Hypothetically, it was revealed that

 

Acol > Regres

Regres > Roth Stone

Roth Stone > Acol

 

In this case, you can have a bidding system mono-culture.

(Any mono-culture could be invaded and displaced by another system)

 

The population equilibrium is some mixture of bidding systems in an optimal ratio...

[nige1]

Duplicate, sorry.

[hautbois]

I too suspect that bidding system superiority will not be transitive. We can find weak, tangential evidence in round robin or 3-way knock outs with 1 win a piece.

 

http://www.ny-bridge.com/allevy/computerbridge/2012scores.html

 

Bridge Baron beat Shark Bridge

Shark Bridge beat Jack

Jack beat Bridge Baron

 

I like the idea of par result. While it relies on double dummy analysis, it's a well-defined Nash equilibrium. I have to admit, I'm lost even trying to come up with the criteria that a single dummy or one hand solution to the game should meet. What exactly is the question being solved?

[hrothgar]

I too suspect that bidding system superiority will not be transitive. We can find weak, tangential evidence in round robin or 3-way knock outs with 1 win a piece.

 

http://www.ny-bridge.com/allevy/computerbridge/2012scores.html

 

Bridge Baron beat Shark Bridge

Shark Bridge beat Jack

Jack beat Bridge Baron

 

 

This could easily be a small sample size issue

(I'm always surprised at the limited number of hands used in computer versus computer matches)

[FM75]

NP Complete. Google it. Get out of game theory for you answer. Its problems are too simple.

[Antrax]

Checkers is EXPTIME-complete and it was solved recently. Don't confuse generalizations of games with finite real-world games.

[Scarabin]

Interesting discussion but is it getting anywhere? The answer to the OP seems to be "No", and is bridge really zero-sum? :unsure:

[hrothgar]

Interesting discussion but is it getting anywhere? The answer to the OP seems to be "No", and is bridge really zero-sum? :unsure:

 

Bridge is provably solvable via Zermelo's theorem.

Whether or not it is practically solvable is another question.

 

Bridge is almost certainly zero sum if you randomize seating...

[Scarabin]

I will have to pass on Zermelo's theorem since I have forgotten whatever knowledge of set theory I ever had in my salad days. I probably should pass on the theory as well.

 

At the risk of hijacking this post I do think that when the system-makers developed pre-determined bids to cover all common situations it became possible to mimic on computers human play in bridge. Possible but perhaps requiring a prohibitive amount of work.

 

The latter problem may be solved when more developers follow Bo Haglind's lead in making source code available. Perhaps then we can build "on the shoulders of giants" instead of endlessly reinventing the wheel.

 

I think Benito Garozzo once said "the longest journey starts with but a single step" and I think I can program a module to make opening leads to an acceptable standard, next to "read" opening leads for declarer and the leaders partner, then to play to the opening lead,etc. Who knows where it will end?

[AyunuS]

It is most definitely solvable, although it'd take a lot more effort than any of you probably think. Consider that the entire system could be different based on if your team went first or not, and on each combination of vulnerable, too. But there are only finitely many combinations of cards. Each system can be assigned a score based on its results in every possible hand, to come up with some sort of average. There would be one system that got the highest average. Same for defense. Of course, if you faced opponents that used many different defenses you'd have to come up with different systems to deal with each of those, which is unbelievably many possibilities if you ever plan to actually play competitively using such a system. And the though of trying to show that all possible other systems would result in a worse value on average is just an absurd amount of work to try to get through, even in one little situation. And then imagine doing that for each other situation. There won't be a solution to it any time remotely soon.

 

Long story short, I'm a math freak of nature and I can tell for sure that it is solvable, but it's hard for me to come up with a proof it.

 

Edit: btw, Zermelo's theorem doesn't work as this isn't a game of full information and one can lie about one's hand.

[Antrax]

it'd take a lot more effort than any of you probably think

What are you basing this on? Who said it seems easy or achievable with the current state of the art?

Each system can be assigned a score based on its results in every possible hand, to come up with some sort of average.

Ignoring the play? Or are you considering playing the hand single-dummy a solved problem? What score does reaching a 99% slam receive for the set of hands where every break is bad and every finesse is wrong?

Of course, if you faced opponents that used many different defenses you'd have to come up with different systems to deal with each of those, which is unbelievably many possibilities if you ever plan to actually play competitively using such a system. And the though of trying to show that all possible other systems would result in a worse value on average is just an absurd amount of work to try to get through, even in one little situation.

I really don't see the relevance. Given the opponent hands, some bidding system on earth has the "par final contract" bid that means "I am holding precisely these 13 cards" by the first opponent to bid. That system will beat the "best" system for that example. That's why you're not looking for some "always best" system.

 

Long story short, I'm a math freak of nature and I can tell for sure that it is solvable, but it's hard for me to come up with a proof it.

I have no clue what your credentials are, but I hope you're being ironic.

[hrothgar]

 

>> Long story short, I'm a math freak of nature and I can tell for sure that it is solvable, but it's hard for me to come up with a proof it.

 

I have no clue what your credentials are, but I hope you're being ironic.

 

FWIW, I agree with the previous poster.

 

Bridge is clearly in the set of games that is (in theory) solvable.

(So is chess)

 

Off the top of my head, I'm not sure how to prove this. (I had forgotten that Zermelo's theorem requires perfect information).

However, I'm guessing if I poked around through my old textbook's something would pop up.

 

For anyone whose interested, the following page has some good information

 

http://en.wikipedia.org/wiki/Extensive-form_game#Finite_extensive-form_games

[helene_t]

Acol > Regres

Regres > Roth Stone

Roth Stone > Acol

If this is the case it might just be because the optimal defense against a Regres 1st-seat pass is different from the optimal against a R-S 1st seat pass. There could be an optimal bidding system that defends differently against different 1st passes just like it defends differently against different 2♦ openings.

 

If we change the game so that it is played without disclosure then probably the optimal system would be a mixed strategy in which we chose a system randomly (from a menu of hundreds of systems) before each board without telling opps which one we chose. But that's quite different from bridge.

[FM75]

The perfect information objection to Zermelo's theorem is not applicable.

 

The set of all possibilities is clearly finite and enumerable.

6.35*10^11 deals * 4 positions for dealer * 4 vulnerability conditions * some number of scoring methods * a finite number of possible auctions.

 

So let's put number of scoring methods at about 5 for argument's sake, making the product of the middle three 80. Now we have:

5. * 10^13 times the number of auctions.

 

Anybody know off hand the number of possible auctions? There are 36 possible opening bids.

Starting with:

pppp

ppp1cppp

...

ppp1cppXppXXpp1d...7NppXppXX

...

7NppXppXX

 

:) This is a nice challenging problem. How many auctions?