bidfight

April 30, 2012
So almost 20 years ago I did a small programming challenge with my Freshman roommate Rob... we came up with a simplistic bidding game (a slightly simplified version of a card game) and we decided to write programs and see whose program would do better at it. Each program had the values 1-10 and it could use each value once, and then they would bid for the values 1-10 coming out in random order.

Ideally, you would write a program that would know what it was holding, and what was left on the pile, and what the opponent still had available to bid, but Rob and I both punted and just mapped a static ordering. If I remember correctly his program was a bit better than mine.

I realized that the "static ordering" method meant some patterns would be more successful at the games then others, and I made up a "survival of the fittest" game of it in QuickBasic, but it didn't get very far in figuring out the "champion". I then thought it would be cool to fight ALL the permutations against all the other permutations and graph it out, but I couldn't think of a good way of generating all the permutations. So I wrote this email to my Computer Science 101 professor asking for help. (The email is a little tough for me to read now, just because it's such an ugly mix of faux humbleness and precociousness. And even beyond my aparent love for Unix style 8-character usernames.)

The good-ish news is that, in the 20 or so years since then, I have the tools (both mental and computer) to write a solution for the problem in a few hours. (Using a simple brute force method to count from 00000 to 99999 or so, and then seeing which of those numbers were "legal patterns" using each digit from 1 to 5 once.) The result looks like this:



It's kind of nice and fractal-y. In running it I learned the straight forward, bid what each thing is worth pattern (12345) is the best bet, winning 104 out of 120 battles. It ties with 12345 (of course) 13542 23145 32415 42351 and loses to 12453 13425 13452 14352 21453 23415 23451 23541 24351 31452 32451. You can see it on the top horizontal line, with red indicating a victory for the horizontal player, blue meaning a loss, and gray a tie.

I also generated the version with 6 bids:. Plotting that shows the pretty fractal-ness more clearly, though my crude algorithm takes a little longer to show at first. (It's 720x720. The next size up would be 5040x5040, which is higher rez than monitors I have handy.) It has a pleasing irregular quilt-like quality
Make love when you can. It's good for you.
Kurt Vonnegut

I feel that the right technology can solve any problem, including us.

We are born between feces and urine.