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.)