## 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…

This entry was posted in Games, Test your intuition and tagged , , . Bookmark the permalink.

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

1. James says:

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?

• Gil Kalai says:

Dear James, yes, by winning strategy I mean winning with certainty.

2. ori says:

What happens if there are equal bids?

• Gil Kalai says:

Dear Ori, lets assume that in this case we flip a coin on who will move.

• Then the term “winning strategy” makes no sense anymore, because you made the game nondeterministic.

• Anonymous Rex says:

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.)

• Reshef Meir says:

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.

3. phiippe says:

Does the X player get to see the O player’s bid after each round or only who has lost or won?

• phiippe says:

nevermind! It’s worst case.

• Gil Kalai says:

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…

4. Benoit says:

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.

5. N says:

Got a bound of 161, assuming they never make equal bids and the bids are integral.

6. N says:

Hi, I think now I have a solution that shows 150 suffices.

~101.84 ?

8. Greg Friedman says:

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. 9. Boris says: 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). • Boris says: In the Richman game, I get 133/123 *$100 ~ $108.13. • Peter says: 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.

10. Boris says:

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!

• Boris says:

(Err, TWO units of money.)

11. Guaraldi says:

With reasonable confidence I can say the answer for guaranteed victory is $136 12. Lucian says: 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. • Lucian says: 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. • Lucian says: Nevermind, my other calculation was excluding a case, while 124.38 works it looks like it could be done for lower 13. It seems to me the Y value to ensure three moves is not 300 but 101+202+404 = 707. Once you’ve paid the first move, the other player has 201. • Lucian says: According to the example given, the winning bid doesn’t go to the other player, it is just spent. 14. David Joerg says: It is cruel to post a problem like this without the solution. I have things to do! 15. keithg says: 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. • Lucian says: 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. 16. sp2hari says: Nice question, do you know this question is available at https://www.hackerrank.com/challenges/biddingtictactoe. Programmers who want to try their intuition can give it a try 😉 17. bowaggoner says: 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?

• bowaggoner says:

(That line should of course be 9/(9-2) * 100.)

• Peter says:

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.

18. LJ says:

133. Any less and O can at the very least force a draw

• LJ says:

but that is under the premise that when it is a draw, both parties pays the sum, but neither makes a move.

19. Deaths Heir says:

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

• Deaths Heir says:

and that’s a guaranteed victory, with O not being able to make a single move.