Tag bridge (3)

bridge update (or: programming is hard)
Mood: worried
Posted on 2010-10-27 14:00:00
Tags: bridge projects programming
Words: 477

After vacation and traveling and such, I've been working on the bridge program again. I'm at the point in the webOS client where I can now play a complete hand, bidding and all. It even looks relatively nice with cards sliding around, things fading into view, etc. Ask me to show it off if you're interested sometime!

So the next task is adding the AI for playing cards. I've decided to go with a rule-based system, where there are a bunch of rules that can decide if they apply. So I have "second hand low" and "third hand high" rules that go near the end (since they're fairly generic).

Last night I tried to sit down and really hammer out the rule that applies if you can determine exactly what will be played. If you're the last player on the trick, this is relatively easy - see if your partner is winning, if not win as cheaply as you can, if so (or if you can't win) throw some trash.

Even this is a little vague - what card should I throw away? Well, if there's only one suit I can play it's easy, but if not then it's hard. So I put this off with a TODO.

The tricky part is if you're the third player on the trick and the fourth player is the dummy. Then it's something like: look at all dummy's cards and the declarer's card that was played (if it's currently winning), then see if I can beat all these. If so, play the cheapest. If not....well, we are in the third hand and we'd like to force dummy's best card if we can. So find dummy's second best card and see if we can at least beat that. If not...well, at least we should try to beat the current high card played by declarer. If we can't do that, then just toss something.

--

This took a while to code up, and I need to test it thoroughly because I'm very much not confident in it. And it still leaves a lot of details out - what if dummy has AK6 and I have the 57 - under the algorithm I'd play the 5 which is pretty clearly wrong. It seems like to handle this case I should have been keeping track of which cards are winners in their suit, which is another layer of complexity!

And all this is for a (all things considered) pretty simple case where I can see all the cards. I'd also like to keep track of how many cards of each suit each person has (based on the bidding), which would help but would also add enormous complexity.

Maybe the AI should cheat and see all the cards? Is there some better thing to keep track of?

It could be a long time before the game seems to play intelligently...

2 comments

minnesota, civ 5, bridge
Mood: busy
Posted on 2010-09-20 12:07:00
Tags: pictures bridge projects programming
Words: 208

I went to Minnesota last week on a recruiting trip and took a few pictures:

Civilization 5 is releasing tomorrow! The full manual is available online (warning: 233 page .pdf) and it look spretty good. I do miss having a paper manual, though.

I've been working on the bridge program for webOS. It's coming along nicely - the framework is all in place to bid and play, and I've done some of the graphical stuff so you can almost actually play a hand on the webOS emulator. The next big thing to do is the AI for bidding and playing, which will probably be big tasks. We're going to be fairly busy over the next month or two so I'm not expecting much progress for a while. (also, Civ 5 coming out certainly doesn't help :-) )

Happily, since webOS is Javascript-based it was pretty easy to make a webpage version of the game, which will make testing out AI algorithms, etc. much easier.

Eric Fischer took census data on race and mapped where people live in major cities. (here's Houston, Austin, and San Antonio) Some patterns definitely jump out at you, but if you zoom in you can see there's nowhere that's exclusively one race, which is a good thing.

1 comment

Friday bridge math puzzle!
Mood: tired
Posted on 2007-01-19 08:19:00
Tags: bridge math
Words: 763

onefishclappin forwarded me this fascinating puzzle yesterday, and I thought "Ooh, I should figure this out", then started thinking about it, then went back to work for about 5 seconds, then gave up and worked it out (roughly). Here it is:


After you've dealt out a hand, are there more different legal ways to play out the hand, or more ways to bid the hand?

Here, only legal plays and bids are counted, so no bids or plays out of turn, insufficient bids, revokes, etc. Other than that, the plays or bids don't have to make any particular bridge sense, they just have to be legal.

There are few things I like better than a good combinatorics puzzle. Here's the analysis I sent her, along with some better numbers: (don't read if you want to try it yourself!)

My gut instinct was that there were more ways to play out the hand, so let's look at that first. It depends what the hands are (since you have to follow suit), but there are at most 13!^4 ways to do this, and you can achieve this is each player is dealt a full suit of cards (each player can play their cards in any order). The least number of ways would be if each person got a 4-3-3-3 distribution, and is something like (13!/(4!*3!*3!*3!))*(3!^4)^4 ((13!/(4!*3!*3!*3!) for the order the suits are played in, 3!^4 for the order of cards in a suit for each person, and the ^4 for all 4 suits). That's just an estimate, though: 13!^4 is definitely an upper bound.

The number of ways to bid is a little more tricky. If you're not familiar, there are 35 "normal" bids (1-7 in clubs, diamonds, hearts, spades, and notrump) and the bids have to be in ascending order (or pass). If the other team bid, you can double, which means that they can then redouble, both of which are cancelled when a new "normal" bid is made. The bidding is ended by three passes.

My first analysis said that there are 2^35 choices for which bids are made along the way, and there are around 10 ways for transitioning from bid to bid (number of passes and doubles & redoubles), so that would give (2*10)^35. This isn't quite right, though: firstly there are 21 ways to transition between bids (see below for a list). More importantly, it's really the sum from i=0 to 35 of 4*(35 C i)*21^(i-1)*7, where i is the number of "normal" bids that are made (4 for number of passes at the beginning, 7 is the number of ways to go from the last bid to the end of the bidding). I think that's right (although the i=0 case is wrong; it should be 1, since the only way to have 0 bids is four passes). So, this is 1 + 28 * sum from i=1 to 35 of (35 C i)*21^(i-1). Hmm, not sure off the top of my head to simplify this, but a quick script to compute this gives 128745650347030683120231926111609371363122697557 (1.287*10^47), which is the answer that the sender of the email got and the answer found elsewhere too. So I got lucky that my initial estimate was fairly wrong in concept, it ends up being close to the same! (20^35 is 3.44*10^45)

And 13!^4 is "only" 1.5*10^39, so the answer is that there are one million times as many ways to bid a hand than to play it (and really, more than that for most usual hands). Fascinating problem - thanks onefishclappin!

List of bid transitions: this is the list of the 21 ways to get from one bid (B1) to the next bid (B2) while keeping the auction alive. p=pass, D=double, R=redouble. It took a few minutes to get these right!
B1 B2
B1 p B2
B1 p p B2
B1 D B2
B1 D p B2
B1 D p p B2
B1 p p D B2
B1 p p D p B2
B1 p p D p p B2
B1 D R B2
B1 D R p B2
B1 D R p p B2
B1 D p p R B2
B1 D p p R p B2
B1 D p p R p p B2
B1 p p D R B2
B1 p p D R p B2
B1 p p D R p p B2
B1 p p D p p R B2
B1 p p D p p R p B2
B1 p p D p p R p p B2

Update: a nice simplification of the number of auctions that doesn't require a script!

5 comments

This backup was done by LJBackup.