Enumerating Contract Bridge Auctions with Lisp

lpaulriddle

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.