Bidding System System

As I may have mentioned earlier, there’s two phases of a single hand of bridge: the auction, and the part where you actually play the cards you were dealt. There’s lots of different bidding systems a partnership might use during the auction to decide how their bids will tell each other what they’re holding. So, to get a computer to play bridge, it’s necessary to program into it at least one bidding system.

So take a fairly common system such as, say, Standard American Yellow Card. Quick, what’s the best way to implement that?

As you can see if you click that link, a human-comprehendable description of the system involves all sorts of special cases. If your partner opens the bidding, the “rules” you’re supposed to follow when your partner opens with 1♠, 1NT, 2♣ or 2♠ are completely different. While from a coding point of view you’d like to implement a few basic, universally-applicable rules and have the complex behavior naturally follow from that, it seems unlikely that that’s really possible without lots of special cases.

It seems as though that, at a high enough level at least, you need some sort of finite state machine, where each state is associated with the set of rules you want to use to determine your next bid, and certain bids (by you or your partner) switch you over to a different state.

But even within each state, there’s lots of conditions to check for to decide which bid to make at any given point. A plain old code implementation leaves you with plenty of conditionals checking for each case you’re interested in. This becomes problematic when you then turn to writing the code that interprets what another player’s bid means. This ends up being sort of like your bidding code, but turned inside-out, since you’re now taking a bid and figuring out what conditions caused that bid to be made. If you squint a bit, this looks a lot like duplicating all your code, which is bound to leave you with hard-to-find bugs; inevitably your bid interpreter is going to misinterpret something in some cases.

Naturally, what you’d like to do is write the rules to follow once, and be able to use those rules going both in the forward direction (here’s what I know, what should I bid?) and the backwards direction (here’s what he bid, what does he have?). Thus our rules are implemented not as code but data. But can whatever data structure we use be expressive enough to adequately say what the rules are without winding up reimplementing half a “real” programming language in the process? There’s enough trickiness afoot in the bidding systems where the answer isn’t immediately obvious.

Of course, a theorist might argue that on a von Neumann architecture there’s no real difference between “code” and “data” anyway, but there’s a big difference in practice between analyzing a set of rules written in XML and analyzing the Python code you wrote to do something. A Lisp devotee might brag that Lisp lets you treat code as data, but nobody actually uses Lisp.

In my tinkering so far I’ve sort of been doing the state-machine-in-Python approach, but having to write functions going forward and backward is getting to be a pain. I think I’ll try writing bidding system rules in XML and then write generic “bidding” and “interpretation” functions that use it, and see if that turns out to be more promising. Hopefully the XML won’t wind up being something silly like this:


<?xml version="1.0" encoding="UTF-8"?>
<compilation-unit>
    <preprocessor>
        <include path="system" src="stdio.h"/>
    </preprocessor>
    <function>
        <name>main</name>
        <return-type>
            <int/>
        </return-type>
        <parameter-list>
            <parameter>
                <name>argc</name>
                <type>
                    <int/>
                </type>
            </parameter>
            <parameter>
                <name>argv</name>
                <type>
                    <array>
                        <pointer>
                            <char/>
                        </pointer>
                    </array>
                </type>
            </parameter>
        </parameter-list>
        <body>
            <statement>
                <call>
                    <target>
                        <identifier>printf</identifier>
                    </target>
                    <argument-list>
                        <argument>
                            <string>Hello, world!  I am %s.\n</string>
                        </argument>
                        <argument>
                            <ternary>
                                <condition>
                                    <greater-than>
                                        <first>
                                            <identifier>argc</identifier>
                                        </first>
                                        <second>
                                            <integer>0</integer>
                                        </second>
                                    </greater-than>
                                </condition>
                                <if-true>
                                    <subscript>
                                        <base>
                                            <identifier>argv</identifier>
                                        </base>
                                        <index>
                                            <integer>0</integer>
                                        </index>
                                    </subscript>
                                </if-true>
                                <if-false>
                                    <string>anonymous</string>
                                </if-false>
                            </ternary>
                        </argument>
                    </argument-list>
                </call>
            </statement>
            <statement>
                <return>
                    <integer>0</integer>
                </return>
            </statement>
        </body>
    </function>
</compilation-unit>

(If you’re bored, try writing some XSLT that converts that back into real C.)

5 Responses

  1. Out of pure curiosity, do you work on things like Wallace and your Bridge programs for fun? For a project, or a competition? I think any reason (or others) are fine, I’m simply curious.

    Also, the code is pretty. It kinda looks like a zoomed in picture of the starfighter from Galaga.

  2. It’d actually be somewhat useful that given an arbitrary C file, generate a parse tree to be used for analysis,especially if it tokenized comments like JavaDoc variants work. However, actually having to write in the tree is much less efficient. :)

    There would be some good merit in a reasonable XML schema that could express card playing logic. However, it has to keep some knowledge of what’s been done in a clean way or else the number of states explodes.

    I’d encourage you to come up with a design that’s slightly more abstract so that you could use it for Euchre and Poker as well. I think it’d be a good open source project. I’d prefer to use C# 3.0 on it and take advantage of expression trees and lambdas which would be helpful in the evaluation. My second choice might be something like F# or ML.

    It’d be for card playing AI what LEX/YACC were to parsers/compilers.

  3. Ryan: For fun, mostly. Which is why output suddenly plummits when I get distracted by some new shiny thing.

    Jeff: Essentially, that’s just rendering a compiler’s abstract syntax tree as an XML file, which would be pretty straightforward. Of course, for C you’d lose all your preprocessor stuff, which technically is all in a different language anyway. I don’t think there’d be a way to convert non-preprocessed C into XML that wasn’t horrifically convoluted. (Consider #ifdef-ing out a conditional but leaving its body alone, for example.)

    I’m not talking about the *playing* logic, just the *bidding* logic. There’ll be some behind-the-scenes variables and stuff that prevent it from being a “pure” state machine. If not for the need to go both ways with the bidding systems, I’d just use straight code, since that’s easy enough to swap out anyways.

    I would certainly not object to a card playing program that supported multiple games, sort of like what AisleRiot does with solitaire games in GNOME. I’m just not aware of some analogous program for multi-player card games.

    And FYI, AisleRiot happens to use Scheme for its game-specific code, presumably since there’s an embeddable Scheme interpreter for C in GNOME.

  4. I still remember Vitek saying of a company that used a Scheme to C compiler commenting on the resulting C code “That’s uh, are coding convention”

  5. our

Comments are closed.