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

http://gilkalai.wordpress.com/2013/03/15/test-your-intuition-17-what-does-it-take-to-win-tic-tac-toe/

by ColinWright • 13 years ago

46 5 13 years ago

gilkalai.wordpress.com

Someone2• 13 years ago

A first step that brings the limit down: with only 100 in hand, O cannot beat you more than twice with a bet of 34 or more. So, bidding 33 on each turn is sufficient to win. That definitely is doable with at most 5 turns that you win for a total cost of 165.

However, the second square isn't worth as much to the one who already won the first, as it leaks information about his strategy. If you won the first, it may be better to let the other player win the second, draining his resources, allowing you to get the other squares you need cheaper.

Because of that, it may be possible to get the maximum down from that 165 (my intuition says you can, but I am too lazy to do the calculations now)

jbri• 13 years ago

The comments clear it up a little - a coin flip breaks tied bids, and you're looking for an amount that would let you win even in the worst case. So you'd need to be able to pay 34/round to only allow your opponent two plays.

It's worthwhile to note that if you win the first two turns, you can bid the house on the third turn and your opponent has to respond in kind - otherwise they lose. Then you can simply outbid them for two other spaces.

Supposing you take the center and a corner, in the first two rounds, then you only need to have 51 to spend on the last space in order to win. Your opponent pays 51 and blocks, leaving them on 49. You can bid 25 to set up a fork, your opponent blocks (leaving them with 24), then you pay 25 each to play out a different win. Or if your opponent doesn't block, you have enough left to convert one of the two wins guaranteed.

So, 119 points is sufficient to win if you suppose that your opponent lets you take those first two spaces for 34 points in each. You could probably get it even lower if you realize that you have two fork opportunities, so you could probably bid even lower than 51 and still force out a win.

I'll leave determining how many points a win takes if your opponent does block one of your first two moves as an exercise for someone else.

Someone2• 13 years ago

OK. After some more thinking, I think one can always win with 132 in hand by always bidding 33:

If O takes the first two, you win the next three for 33 each and win.

If O leaves you the first two for 33 each, take centre and a corner. O must take the third to block you. If he also takes the fourth, he must leave open a row that you can complete in two turns.

If O takes the first and leaves you the second, pick a corner, or, if O left it, the centre. If O takes the third, he must leave open a row for you to take in two more turns. If he leaves you the third, he can block one row, forcing you to use four X-es.

If O leaves you the first, then takes the second, pick centre. If he takes the third, he can't prevent you from completing a row with 3 X-es. If he leaves you the third, he can force you to use at least 4 X-es.

I do not rule out further improvements, maybe even to a conclusion that you need less than 100. For example, if O takes centre and corner for 34 each, you must bid 33 to guarantee blocking his win. After that, you can afford bidding 16 next. If you lose that bet, O has at most 16 left, allowing you to win the two squares you need for 17 each, for a total expense of less than 100.

gelisam• 13 years ago

The way in which ties are resolved is very important. I had assumed that in case of a tie, neither player won the bidding war, so they had to bet again. Under that interpretation, the worst case is that O always bets the same as X, trapping the game into a non-productive sequence of tied bids. The only way to avoid this is to always bet more than O can possibly bet, which means we need more than 300.

Fortunately, Gil Kalai has added in the comments that tied bids are resolved with coin flips, so if you can find a winning strategy in both sub-trees, ties are fine.

dmxt• 13 years ago

Apparently my ISP blocked that website for some reason. Corbina, RUS.

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

Related Stories