Enumerating Contract Bridge Auctions with Lisp

I’ve been a fan of Contract Bridge for a long time.  I’m really bad at it, but all the same, I find it fascinating and compelling.  One of the interesting facts about Bridge is the astronomical number of possible auctions.  For any given deal, there are over 128 × 1045 possible auctions. The exact number is:

128,745,650,347,030,683,120,231,926,111,609,371,363,122,697,557

That’s a lot!  Being the nerd that I am, I decided to dust off my LISP skills (mostly neglected since college) and write a program to enumerate them.  To wit:

(setf allbids
      '("1C" "1D" "1H" "1S" "1NT"
        "2C" "2D" "2H" "2S" "2NT"
        "3C" "3D" "3H" "3S" "3NT"
        "4C" "4D" "4H" "4S" "4NT"
        "5C" "5D" "5H" "5S" "5NT"
        "6C" "6D" "6H" "6S" "6NT"
        "7C" "7D" "7H" "7S" "7NT"))

(defun printMore (bidList bidStr)
  (if (null bidList) nil
    (progn
      (mapcar #'(lambda (p)
                  (printAuctions bidList (concatenate 'string bidStr p (car bidList))))
              '(" " " P " " P P "))
      (printMore (cdr bidList) bidStr))))

(defun printAuctions (bidList bidStr)
  (let* ((matrix
          '(nil
            " P P Dbl"
            " P P Dbl Rdbl"
            " P P Dbl P P Rdbl"
            " Dbl"
            " Dbl Rdbl"
            " Dbl P P Rdbl"))
         (bidMatrix (mapcar #'(lambda (x)
                                (concatenate 'string bidStr x)) matrix)))
    (dolist (x bidMatrix)
      (progn
        (print (concatenate 'string x " P P P")
               (printMore (cdr bidList) x))))))

(defun printSomeAuctions (startBid &optional (prefix nil))
  (let ((bidPos (position startBid allbids :test #'equal)))
    (if bidPos
        (let ((bidList (nthcdr bidPos allbids)))
          (printAuctions bidList (concatenate 'string prefix (car bidList)))))))

(defun printAllAuctions ()
  (progn
    (print "P P P P")
    (mapcar #'(lambda (p)
                (printSomeAuctions "1C" p))
            '(nil "P " "P P " "P P P "))))

(printAllAuctions) will iterate through and print out every possible Bridge auction.  Don’t hold your breath waiting for it to finish, though.  The computer I was using, a Linux box running CLISP, printed out around 14,000 auctions per second.  At that rate, it will take 291.4 × 1033 years to complete.  That’s over 21 septillion (21 × 1024) times the age of the known universe.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s