Test Your Intuition (17): What does it Take to Win Tic-Tac-Toe

(A few more quantum posts are coming. But let’s have a quick break for games.)

Tic Tac Toe is played since anciant times. For the common version, where the two players X and O take turns in marking the empty squares in a 3 by 3 board – each player has a strategy that can guarantee a draw.

Now suppose that the X player has a budget of Y dollars, the O playare has a budget of 100 dollars and before each round the two players bid who makes the next move. The highest bidder makes the move and his budget is reduced by his bid.

For example, if, to start with, the X player have 120 dollars, and if for the first move X bids 40 dollars and O bids 30 dollars, then X will make the first move and will be left with 80 dollars while O will be left with his 100 dollars.

What would you expect the minimal value of Y is so the X player has a winning strategy? Of course if Y>300, X can make 3 uninterrupted moves and win, but perhaps much less is enough?

(Thanks to Reshef Meir and Moshe Tennenholtz)

Update: Another variant of this game is when the player winning the turn pays his bid to the other player. (This version is called “Richman game,” while the variant above is called “Poorman game”. In this case if Y> 800 the X player can play three moves and win. And again the question is what is the infimum value of Y for which the X player can force a win…

40 thoughts on “Test Your Intuition (17): What does it Take to Win Tic-Tac-Toe”

1. James

If the bids are made simultaneously, we might have to consider mixed strategies. By “winning strategy”, do you mean a strategy that wins with probability 1? There might be other interesting thresholds: when does X have a strategy that wins with positive probability? When does X have a strategy that wins with positive probability and loses with probability 0?

1. Anonymous Rex

Re tom (@goiken): Gil’s response to James indicates that the condition is “winning with certainty”. In terms of the coin flip, this means you must win regardless of how the coin flips.

If you’re okay with making the game assymetric, then an alternative interpretation is the following: before each move, X makes a bid. Since we’re in the worst case, we may as well assume O’s bid is the exact same amount. Again since we’re in the worst case, we may as well let O choose whose bid is successful.

In other words, X bids an amount, and O decides whether or not he or X will pay that amount for the privilege of moving. (If X bids more money than O has, then of course X moves.)

2. Reshef Meir

You can set the tie breaking any way you want, it does not change the infimum value of Y. For convenience you can assume that X plays in case of a tie, in which case the infimum becomes minimum.

1. Gil Kalai Post author

Dear Phiippe, lets assume that X gets to see O’s bid, but as you said it is not important. Actually, I should have said infimum Y and not minimum Y in the post…

2. Benoit

Interesting problem!
The second simplest bound (the first being 303, with the coin flipping rule and if they bid integers) seems to be 228 (and X should bet 25 or 26 the first time), since X can afford to give away the first move if he can move three times in a row after that.

3. Greg Friedman

Hi Gil, Doe player O know how much money player X has to start? I’m not sure if it’s relevant, but assuming yes, I think I can also show that X can win with $150+\epsilon. 4. Boris If the currency is infinitely divisible, then I believe X can guarantee a win iff their ratio of money strictly exceeds 396925/389763. Multiplied by$100, this is around $101.84 (confirming Mohammad’s answer). 1. Peter I haven’t fully automated my computation, so I may be fouling things up with transcription errors, but I am getting closer to 1.0169. As a point of reference, if we win the first two bids, my strategy suggests placing a bid of 7/15*$100 on the final bid.

My actual answer is 296273/1066185 + 527/1935 + 7/15 = 120467/118465, where essentially I am making every possible route through the game tree equally expensive, and so these would be the first three bids if we win all of them.

5. Boris

If the currency is divisible down to the dollar, (I believe) X wins with at least $104. If we correctly model US currency as divisible down to the cent, X wins with at least$101.86. In both cases, you only lose one unit of money due to the discretization!

6. Lucian

I’d have to say the answer for the infimum is 12,600/121 or about 104.13 Not sure how others are guaranteeing a win for less. But I stand to be corrected.

1. Lucian

My previous calculation was off, I believe it is 15,050 / 121 or about 124.38
I’m curious to see how some people managed lower.

7. keithg

It’s a hard to answer question because of vagueness. Mainly the fact that you don’t state that Y has to overbid X each time in order to win. Because if he doesn’t, the first move instantly becomes irrelevant. If you do (Or if you’re allowed to see their bid first), then it’s (Y+1), mainly because there’s no way you could lose if you have to bid higher.

There are a bunch of other vague rules I’m not sure on, but I’ll just leave that up to you. I am worn out, have been working on this for almost 1 hour now, and I still haven’t gotten very far without the aid of a simulation. Maybe later. Maybe.

1. Lucian

Because he’s looking for the infimum it doesn’t really matter and we can assume that one outbids the other by some small epsilon > 0 to make a win.

8. bowaggoner

Cool question! Reshef’s comment implies that we should not require bids to be integral, so let me assume we win ties. (If not, just bid epsilon higher.) I think a rough lower bound on the answer is that if your budget is less than (9/7)*100 = 128.57…, then there is an opponent against whom you do not win — in fact, you do not even make three moves.

To see this, suppose all possible games you’re playing end in at most “k” rounds. Suppose that you make at least three moves against every possibly strategy; so every possible strategy makes at most k-3 moves. Then for every subset of k-2 rounds, you bid at least $100 total (else some opponent matches your bids plus epsilon and wins all k-2 of them). The lowest-cost way to achieve this is to spend 100/(k-2) in each of the k rounds, so you have to spend at least k/(k-2)*100 total to guarantee that you make a move in 3 rounds out of k. The smallest this value can be is when k is maximal, and all tic-tac-toe games end in at most 9 rounds, so 9/(9-7) * 100 should be a lower bound. Am I misunderstanding anything? 1. Peter I think by being somewhat vague about what constitutes a “strategy” you are enforcing stronger conditions than need exist. In particular, when you mention “every subset of k-2 rounds” it seems like you are assuming a fixed bid amount based on the number of moves alone. In particular, our response against a strategy that outbids us every turn as long as it can need not have anything to do with our response to a strategy that, say, only bids a nonzero amount when it would lose otherwise. Thus your justification, that some opponent could bid in such a way as to block us out, doesn’t really apply. That will have to be true of our bids in the case that we keep losing, but needn’t be if we have already made a move. This is still a useful condition for finding a solution, but has narrower scope than you are suggesting. 1. LJ but that is under the premise that when it is a draw, both parties pays the sum, but neither makes a move. 9. Deaths Heir For Richman Game, I’ve done the math. The maximum X player will need to beat O, while O has a starting fund of$100, is $707. Here’s each round, with both parties bids for said round X$101 <—Round Winner, loses $101 O$100 <—Round loser, gains $101 X$202 <—Round Winner, loses $202 O$201 <—Rounder loser, gains $202 X$404 <—Game Victory, loses $404 O$403 <—Game lost, gains $404 Total of X's money spent to win the game:$707