Bidding Tic Tac Toe Winning Strategy?

At a recent leadership program I was introduced to a bidding version of naughts and crosses. It is a blind bidding variant of Gambling Tic Tac Toe created by Craig Huneke. Here are the rules

  1. Both players start with $3 in coins
  2. Both players write secret bids then reveal together
  3. The winner places their winning bid on the square of their choice to mark their move
  4. The winner now has less money to bid with. Repeat steps 2-3 until one player has a line of 3.
For example, the game might go as follows
  1. Player 1 bids $0.75, and Player 2 bids $1
  2. Player 2 wins, and places $1 (their bid) on the center square
  3. Player 1 bids $1, and Player 2 bids $1.25
  4. Player 2 wins so places $1.25 on one of the corner squares
  5. Now Player 1 still has $3, but Player 2 is only left with $0.75
  6. Player 1 can now bid $1 three times in a row, getting three squares in a row and winning
It seemed that there should be a winning strategy. Perhaps always playing a third of your remaining funds. I started filling pages of paper with games. It seemed that bidding a third of your funds, rounded to the nearest penny was a good strategy. So I decided to write a program that could play this variant of gambling tic tac toe. I would then teach it various strategies and let it play against itself ala Wargames (1983) but without the total global annihilation.

Since I had been wanting to experiment with Google Apps Script, I decided to write this in a Google Spreadsheet. I created a 3x3 table for the board, and wrote a function that would play the best move. So I would mark an X in a cell, click Play and the computer would add an O in the best cell. I then tweaked it so it could play either X or O, and then added an Auto Play so it could play itself.

The rules of tic tac toe and the best move at any point are straightforward, so this was easy. Although later as I added the bidding component it occurred to me that in this variant of tic tac toe, the best move is sometimes different. For example, you may not want to block the opponent if you can win the next 3 bids, if the blocking move does not set you up to play 3 squares in a row.

I then added a table with the current amounts for each of player X and O, and their bids, along with buttons for Check Bid and Reset. So I could enter bid amounts for both players, click Check Bid, and the computer would determine the winner and play the best move for that player. This at least let me more quickly test out some different strategies. The program also recorded all the moves on a History sheet along with the winner. Next I added Auto Bid. This automatically generated bids for each player and played out a complete game, recording the moves and the winner on the History sheet. For now each player was playing randomly. And finally I was ready to start testing out strategies. 

I wrote the program in a way that different gaming strategies could be plugged in for each player. Each strategy was implemented as a function that received the current amount that the player (opponent) had, and the current amount that the computer (self) had. The function would return the amount that the computer should bid.

The most basic strategy just bid randomly some number less than the amount that the computer had without considering how much the opponent had.

// bid randomly
function randomBid(playerAmount,computerAmount) {
  return Math.round(100 * computerAmount * Math.random())/100;

Letting the computer play itself randomly for a while,  I realized that I needed to add a few more rules to the play. If a player could win with the next move, then he should bid one penny more than his opponent currently has (if he has that much). Similarly, if the opponent could win on their next move, then the player should also play one penny more than his opponent. This should be independent of the strategy they are playing.

Also, independent of the strategy, a player should never bid more than a penny more than the other player currently has. So if a player has $3, and their opponent has only $1, then no matter what the strategy picks, they should never play more than $1.01. With these rules all coded, I let the computer play itself randomly.

Pretty quickly a pattern began to emerge. More often than not, the player that lost the first round ended up winning the game. Not always, but a significant amount of the time. So I added a new strategy

// random bid upto half my amount
function randomLowBid(playerAmount,computerAmount) {  
  return Math.round(50 * computerAmount * Math.random())/100;    

I played randomLowBid against randomBid and it trounced it. Now I wanted to try out the strategy that I first thought of.

// bid 1/3 of my amount
function strategyThirdBid(playerAmount,computerAmount) {
  return Math.round(100*computerAmount/3)/100;

This did pretty well, beating randomLowBid about 5:1. I tried several other strategies. I had each of them compete with randomLowBid and strategyThirdBid:

// strategyInverseMoveSix - start bidding 1/6 of my amount less one penny, then 1/5 less one penny, ...
// strategyInverseMove - start bidding 1/5 of my amount, then 1/4, ... until 1/2
// strategyThirdMinusOne - bid 1/3 of my amount less one penny
// strategyThirdPlusFlip - bid 1/3 of my amount plus or minus a penny alternately
// strategyThirdBid - bid 1/3 of my amount
// strategyFifthBid - bid 1/5 of my amount
// randomBid - bid randomly
// strategyOneCent - bid $0.01
// strategyNextTime - bid so that if I win I can still win next time
// strategyLoseLoseWin - bid to lose 1st two hands

My favorite strategy which wins against almost anyone was one I named strategyForceFish. On your first two hands you play 75 cents. After this you play 1/3 of your remaining funds on each bid. The "force" bit in the name comes from the strategy trying to force the opponent under $1.50. The "fish" bit comes from not being able to come up with a succinct way of explaining the other bits of the strategy. I would have put more effort into naming it if I'd known it was going to be so successful.

// bid .75 first two hands to try and force him under 1.50 then 1/3 of amount
function strategyForceFish(playerAmount,computerAmount) {
  if (moveNumber < 3) return 0.75;
  if (moveNumber > 2) return Math.round(100*computerAmount/3)/100;

In the end I didn't really get to the point of finding an ultimate winning strategy. Playing against a randomLowBid strategy, the strategyForceFish wins 1181:27. It also beats strategyThirdBid and all the other strategies above. But since a randomLowBid strategy does occasionally beat it, there is obviously a better strategy (assuming there is indeed a winning strategy). If someone else takes this further or comes up with any other interesting strategies, please post them in a comment.

Here is a link for the Google Spreadsheet with the Google Apps Script to play this variant of gambling tic tac toe: Bidding Naughts and Crosses. To be able to use it you will need to copy it to your own Google Account first (File > Make a Copy...). You should then be able to click Auto Bid and watch it play a game. If you click "Play Lots" it will play 30 games. The winning and losing strategies for each game are recorded on the WinningStrategies sheet, and the pivot table on the Strategy Report sheet shows which strategies have won against others.

To change the strategy that each player uses, change the following highlighted bits of code

  var xStrategy = "strategyForceFish";
  var oStrategy = "strategyThirdBid";
  do {
    nextRow = history.getRange(history.getLastRow()+1,1,1,6);
    // generate player bid using defined strategy
    playerBid = generateBid("X",strategyForceFish);

    // generate computer bid using defined strategy
    computerBid = generateBid("O",strategyThirdBid);

It's clear that the game of Gambling Tic Tac Toe is far more sophisticated than I first imagined. One more twist that makes the game even more complicated is to imagine that each player gets their $3 with some random mix of coins. Each bid must be a whole number of coins. This is actually how we played the game, but I decided that trying to model that was too complicated for starters.

If anyone knows if there is a winning strategy for this game, and what it is, please post in the comments. Until then I'll keep playing strategyForceFish.

No comments:

Post a Comment