News for hackers. Stuff that matters.
Re:Ultimate Tic Tac Toe by quesera on Tuesday June 18, 2013 @08:40AM (#5898767)
I think the Orwin gambit can be extended to win the game every time.

- Force opponent to fill center miniboard, as he describes.

- Force opponent to fill (e.g.) northeast corner in the same way. Opponent now has taken two miniboards, and you have none, but you are one turn away from taking each of the remaining seven.

- Pick SW corner of SW corner. You have taken SW corner miniboard. Opponent is forced to play in same SW miniboard, already won by you.

- Pick SW corner of S. You have taken S miniboard. Opponent is forced to play in SW corner again, already won by you.

- Pick SW corner of SE corner. You have taken SE corner miniboard.

- Done. You win.

Like regular tictactoe, there is an advantage to going first. Unlike regular tictactoe, the advantage can't be compensated for. Otoh, the second player can use the same strategy with a little more carefulness, as long as they start early.

So either player can force the other into a protracted certain loss, unless there's an agreement or a rule against it. That's no fun.

EDIT: actually, you can win every time, in far fewer moves, and not using the Orwin gambit at all. It's not necessary to force your opponent to fill any of the miniboards, not even the center.

I think this will win in ten moves and never lose driver control (excuse the notation): C/C, C/SW, C/S, [opponent takes C], C/SE, NE/SW, NE/S, NE/SE, [opponent takes NE], SW/SW [you take SW], SW/S [you take S], SW/SE [you take SE, and win]. A variation can be used by either player early in the game, but whoever starts with control would be foolish to lose it.

If this is a game played by mathematicians, either I'm wrong, or there are additional rules. :)

EDIT2: C/C (first move above) is unnecessary. Nine moves. Perfect inning.

Re:Ultimate Tic Tac Toe by matchu on Tuesday June 18, 2013 @03:19PM (#5901365)
Here's an implementation that pretty much does exactly that. If someone can beat this bot, lemme know: https://www.khanacademy.org/cs/in-tic-tac-toe-ception-perfec...

And here's James Irwin's original implementation, auto-set to a Monte-Carlo AI and with a rules variation that (to my knowledge) prevents Perfect Bot from winning. Play with the config variables at the top for some other AIs and 2-player games and whatnot. https://www.khanacademy.org/cs/in-tic-tac-toe-ception/167633...

Re:Ultimate Tic Tac Toe by NKCSS on Wednesday June 19, 2013 @03:08AM (#5904113)
Well, if the game would be changed to disallow 'moves' in won sections, you'd have a completely different game where this 'exploit' of opponent trapping does not work.
Re:Ultimate Tic Tac Toe by nkoren on Tuesday June 18, 2013 @04:30PM (#5901868)
The first one is beatable if -- and only if, I believe -- a square with two three-in-a-rows in it counts as both an X and an O. If this is the case, then O can win one round before X has a chance to it. But otherwise -- as you have it configured, where the first to get a three-in-a-row sets the larger square to either an X or an O -- it's unbeatable.
Re:Ultimate Tic Tac Toe by WarDekar on Wednesday June 19, 2013 @02:22AM (#5903996)
There are definitely bugs- I played the 2nd link and on several moves the AI moved in the wrong region. I played in the SW block in the E square and then the AI played in the same SW block as me, then did the same thing on the next turn playing in the wrong region.
Re:Ultimate Tic Tac Toe by matchu on Wednesday June 19, 2013 @02:24PM (#5907274)
Could it be because of the rules variation? See the comments on rule 5b to negate Perfect Bot's strategy: if forced to an already-won region, the player may choose any region.
Re:Ultimate Tic Tac Toe by triangleman83 on Tuesday June 18, 2013 @07:19PM (#5902679)
Yep I don't see any way of beating that bot. You whipped that up just today?
Re:Ultimate Tic Tac Toe by matchu on Tuesday June 18, 2013 @08:20PM (#5902898)
The KA folks were playing this in the office a few weeks back, James wanted to make a good AI for it, spent a weekend or so on it, and discovered the Perfect Bot in the process. My sole contribution to this program (in addition to moral support!) was creating a copy that's set to Perfect Bot by default for y'all's convenience, but his original has all sorts of crazy config.
Re:Ultimate Tic Tac Toe by tensaix2j on Tuesday June 18, 2013 @09:33PM (#5903224)
Does the AI always have to make the first move?
Re:Ultimate Tic Tac Toe by matchu on Tuesday June 18, 2013 @10:20PM (#5903392)
For Perfect Bot's strategy to work, yeah, but the environment is very open to configuration. Set xIsComputer to false and yIsComputer to "monte" for a fun challenge in which you go first.
Re:Ultimate Tic Tac Toe by gcb0 on Tuesday June 18, 2013 @10:17PM (#5903381)
Technically a game of tic tac toe is comprised of two matches, one each player starting
Re:Ultimate Tic Tac Toe by antoko on Tuesday June 18, 2013 @09:44AM (#5899080)
either I'm wrong

TLDR: you're wrong.

C/C, C/SW, C/S, [opponent takes C], C/SE, NE/SW, NE/S...

after C/SE, your opponent has control and can go anywhere that is available in the center board they've already won, so you can't assume you're next play will be NE.

More importantly after you've sent them to the SW board with NE/SW they can go anywhere except the middle and so they then have the initiative.

Hmm, It looks like you switched notation halfway through? I was assuming board/position and only showing player 1 moves but that doesn't after losing the center board

Regardless you lose the initiative after 5 moves.

Re:Ultimate Tic Tac Toe by quesera on Tuesday June 18, 2013 @10:55AM (#5899547)
Ouch, yes. My EDIT passages are totally wrong. Sorry, I oversimplified the rules there.

The initial idea (extending Orwin Gambit) should still be leverageable into a much better position. This might fall short of a certain win though, if the opponent plays a proper response strategy -- which we should probably assume if the contestants are peer mathematicians. :)

Re:Ultimate Tic Tac Toe by rdsubhas on Tuesday June 18, 2013 @01:17PM (#5900597)
How about an addition to the rules:

| The very first move in the game must not be in the center board (or more specifically CC)

So player has to pick some other board. If they choose C in that board, then they're fucked, the next player will end up playing the Orwin Gambit. So both players will avoid C like the plague until they're sure the Orwin Gambit is no more applicable.

Even if I start with some board (say NE), and in the first move itself I play a C and thereby giving the other player an option of taking the Orwin Gambit, it still can't be effectively used. Because I can later play NE again in the C table, thereby outplaying the gambit (since the C inside NE is already used).

Edit: Formatting

Re:Ultimate Tic Tac Toe by nmat on Tuesday June 18, 2013 @10:22AM (#5899322)
I got confused with the notation so I used paintbrush: http://imgur.com/a/tZPjl

The standard strategy (without optimization) seems to work perfectly. You gain control by forcing the oponent to fill out the miniboards. The last move on the second exhausted miniboard will allow you to choose any miniboard, so it's an easy win.

EDIT: like 3pt14159 pointed out, O might cause you problems if he immediately picks the center in the NW miniboard. This needs further testing...

Re:Ultimate Tic Tac Toe by triangleman83 on Tuesday June 18, 2013 @10:43AM (#5899458)
I'm coming up with the same as you. You have to make your 9th move sub board match the greater board location, so in this case NW board and NW corner. Now wherever they move will send you to a different board, where you can make the move there to the NW corner, and they are forced back to the NW board. Repeat until you have two in a row on most of the boards and you should be able to make the win.
Re:Ultimate Tic Tac Toe by 3pt14159 on Tuesday June 18, 2013 @10:47AM (#5899488)
What if o took the centre of the board?
Re:Ultimate Tic Tac Toe by triangleman83 on Tuesday June 18, 2013 @10:55AM (#5899544)
Then according to the rules, X gets to move anywhere. Pick another corner board, make a move in the NW corner, which forces them back to the NW board. Then their best option is to move in the same square of the board you just came from, since you won't be able to send them back to the NW board again. In that case, you move in the same corner as the board you are in, forcing their reply to the same board you're playing on.

This would be the general strategy, although I am now no longer sure you can force a win through. The options for moves for O starts to grow past what I can work through in Paint right now.

Re:Ultimate Tic Tac Toe by Houshalter on Tuesday June 18, 2013 @04:31PM (#5901870)
After that it's pretty easy to force a win. Whatever square they send you to, you just send them back to one of those two squares.
Re:Ultimate Tic Tac Toe by 3pt14159 on Wednesday June 19, 2013 @01:58PM (#5907085)
I challenge you to a game where you are X then. Because I can't figure out how you force a win like that.
Re:Ultimate Tic Tac Toe by 3pt14159 on Wednesday June 19, 2013 @02:14PM (#5907199)
I take it back. The key is to line up three master blocks with x's free move. Then the game is perfectly won by x.
Re:Ultimate Tic Tac Toe by Houshalter on Wednesday June 26, 2013 @10:12PM (#5950344)
I'm not entirely sure how to do it anymore, but playing with the perfect AI posted somewhere else in this threat convinces me it's impossible to win if you don't start first.
Re:Ultimate Tic Tac Toe by Someone on Tuesday June 18, 2013 @08:51AM (#5898812)
"Fill center, as he describes. Fill (e.g.) northeast corner in the same way."

I don't think you can force that. When you have the nine center squares of each square and he has the 8 non-center squares of the center square, it is your opponent's move.

The 'force-fill the center square' only works because, in your first move, you occupied the center square. That move prevents your opponent from ever picking the center of the center, thus forcing you to move in the center square.

Re:Ultimate Tic Tac Toe by jbri on Tuesday June 18, 2013 @09:02AM (#5898868)
Instead of filling the center square on the last board, you can fill the corresponding square and then start forcing your opponent to win that board.
Re:Ultimate Tic Tac Toe by 3pt14159 on Tuesday June 18, 2013 @09:39AM (#5899050)
Doesn't quite work, since the opponent can chose the centre square which leaves you with a free move, but whatever master square you place your free move in, can no longer be used to force him back into the same master square.
Re:Ultimate Tic Tac Toe by homonculus on Tuesday June 18, 2013 @11:59AM (#5900031)
The opponent can't choose the center square because you've already filled them all in the initial phase of the gambit.
Re:Ultimate Tic Tac Toe by PebblesRox on Tuesday June 18, 2013 @04:11PM (#5901730)
"Instead of filling in the center square on the last board..."
Re:Ultimate Tic Tac Toe by PebblesRox on Tuesday June 18, 2013 @04:10PM (#5901725)
Why not? All the other squares are empty except for their centers. You can put your opponent wherever you want.
Re:Ultimate Tic Tac Toe by chasb on Tuesday June 18, 2013 @09:39AM (#5899054)
I don't think so. At Orwin -1, picking a non-center move forces O to one of 6 perimeter boards, none of which have that corresponding perimeter position filled. This cedes initiative to O.
Re:Ultimate Tic Tac Toe by neruson on Tuesday June 18, 2013 @08:53AM (#5898825)
Unless I'm missing something, this wouldn't work because the Orwin gambit gives initiative back to the opponent by sending them back to the center board when it's already full. They would have the chance to employ the strategy back against you before you could pull this off.
Re:Ultimate Tic Tac Toe by triangleman83 on Tuesday June 18, 2013 @09:58AM (#5899157)
The Orwin Gambit actually doesn't go quite so far as to force the win, however if you forget about filling that last center and instead go for a corner, then you can continue to force them back to the same corner over and over. So the Gambit is fallible, but if you back it up one step, it can continue the force to the inevitable win.
Re:Ultimate Tic Tac Toe by chasb on Tuesday June 18, 2013 @10:09AM (#5899212)
No. You lost the initiative (the ability to force their next move) when you sent them to an open board.
Re:Ultimate Tic Tac Toe by triangleman83 on Tuesday June 18, 2013 @10:17AM (#5899296)
I don't believe you will ever send them to an open board. O makes all its 8 initial moves in the center, and the 9th move for X will be in the last empty board. I think that it depends on what their last move in the center board is. If they send you to a corner, I believe you can force the win. If they send you to the SW corner, you make the first move in that square to the SW corner. This forces them to reply in the same SW corner. Wherever they go, you make your move in the next square in the SW corner, bringing them back to that corner again.
Re:Ultimate Tic Tac Toe by chasb on Tuesday June 18, 2013 @11:32AM (#5899830)
Nope. You can only hold the initiative through 9 moves. After X9 to board B, O9 to center. X10 can pick any board C with subposition B, but O10 can force a return to board C. X10 has occupied the forcing position = lost initiative.
Re:Ultimate Tic Tac Toe by opendomain on Tuesday June 18, 2013 @09:48AM (#5899106)
The answer is obvious: the next player must play the corresponding board UNLESS it is already won. Thne they can choose which board to go to randomly.
Re:Ultimate Tic Tac Toe by danielweber on Tuesday June 18, 2013 @12:04PM (#5900073)
This raises an interesting wrinkle: a sub-board can be won by both X and O, if you can keep on playing after it is won.
Re:Ultimate Tic Tac Toe by alphaoverlord on Tuesday June 18, 2013 @12:23PM (#5900207)
Perhaps the game makes more sense if you can choose any board as soon as the board is won - not when it is filled. Then, you can only force 3 moves before you have to give up control.