Bidding hex November 28, 2008Posted by Noah Snyder in Mathcamp, Uncategorized.
Looking for a fun but math-y activity to fill your long weekend? Try bidding hex on facebook! Feel free to challenge me if you’re looking for an opponent. The facebook program was written by Jay Bhat and the AI is based on another program written by Elina Robeva (and would be much stronger if Facebook let it think longer).
I learned about discrete bidding games from Sam Payne at Mathcamp last summer. Sam and Mike Develin have a beautiful paper on the subject which I highly recommend. In particular the appendix on different tie-breaking methods is quite entertaining. They also have a crazy result that says that in bidding tic-tac-toe you should open in the center unless you start with five chips each 3 chips and your opponent starts with 2 chips and the tiebreaker! I’ll try to give you a glimpse of their results, but don’t let that stop you from reading their paper.
The basic idea is that the two players each start with a stack of chips. We independently choose the number of chips we’d be willing to pay the other player for the right to move. Whoever chooses a larger number pays that amount and moves. In order for this method to be practical you should have a finite stack of discrete chips (as opposed to say bidding in real numbers) which means you need to fix a tie-breaking method. Sam’s favorite method involves a tie-breaking chip. One player starts with the tie-breaker chip, if there’s a tie then the person who has the tie-breaking chip wins if she chose to bid it, and loses if she chose to keep it.
Although for practical purposes having discrete chips is convenient, mathematically continuous bidding is more convenient. This theory was worked out by Richman. The key idea is that in any position there’s a key threshold which tells you which proportion of chips you need to tie (and another threshold which tells you which proportion you need to win). For example, if I win only when I have 2/3 or more of the chips, then the Richman threshhold is 2/3. The beautiful result of Richman’s is that continuous bidding games are closely related to random turn games!
In a random turn game two players flip a coin each turn and the winner of the flip gets to move. In a random turn game in any position there’s some probability that each player wins with optimal play. Richman’s theorem says: “In any position in any nice game the probability P that A beats B and the Richman threshold for bidding T satisfy T+P=1.” So if in a position I need 2/3 of the chips to win, then in a random turn game I have a 1/3 chance of winning!
In practice though, bidding games and random turn games are very different. Suppose you’re playing an opponent who is significantly better than you at random turn hex. Say you make a mistake and now you’re in bad position where you have only a 1/3 chance of winning. That’s not so bad, after all you still have a 1/3 chance of winning. However, if you make the same mistake in bidding hex you just lose (unless you miraculously have 2/3 of the money which you won’t because you got into this position by mistake). And that’s without the fact that you could play the right moves the whole game but lose with poor bidding! In fact, Elina’s program is essentially unbeatable at bidding hex. The key to the computer’s success is that random turn hex can be analyzed nicely (via The Mathematical Tourist).