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.
Re:Ultimate Tic Tac Toe by michaelfeathers on Tuesday June 18, 2013 @07:59AM (#5898639)
My favorite "mathematician game" is Sprouts: http://nrich.maths.org/2413

First heard about it in a column in Scientific American by A. K. Dewdney. The rules are simple and it is rather fun. In one of his columns he talked about playing a toroidal version where a line going off one edge of a rectangular page comes back in on the opposite side.

Re:Ultimate Tic Tac Toe by bumbledraven on Tuesday June 18, 2013 @03:10PM (#5901318)
There's a World Game of Sprouts Association that organizes a yearly tournament by email. The same Russian dude always wins. http://www.wgosa.org/champions.htm
Re:Ultimate Tic Tac Toe by gojomo on Tuesday June 18, 2013 @09:13PM (#5903132)
I remember another two-player pen-and-paper game I got from Scientific American long ago... I think it was called 'Loops'.

• the board is first built by each player alternating in drawing an oval lightly (as with pencil) until 5 ovals are placed; each oval after the first must intersect another in at least one place, such as a tangent, but usually more

• every intersection gets a dot to emphasize its role as a vertex; the oval segments between them are edges

• after the board is built, one player starts by picking any vertex, and tracing (heavily or with a unique pen color) an edge from that point to a new vertex, and then to another vertex, and then to another (3 segments end-to-end per turn)

• the next player starts from the vertex where the previous player ended; if for any of their 3 segments (including the 1st) there is no legal move, their turn ends and the other player has choice of vertex to begin their next move

• if a player's move completes a loop, they capture it (adding their initials inside); first to capture 3 loops wins

So for example, the 5-rings olympic logo is a legal board (though one which allows the 1st player to immediately capture a 2-segment oval on either end).

Anyone else play this? Do I remember the name right?

Re:Ultimate Tic Tac Toe by kernel_sanders on Tuesday June 18, 2013 @08:30AM (#5898730)
My Dad, a physicist, taught me that game as a kid. I have great memories of him producing a pen at any restaurant we might have been at, and he and I passing any waiting time playing sprouts on napkins or paper scraps. I since play it with my kids.
Re:Ultimate Tic Tac Toe by michaelfeathers on Tuesday June 18, 2013 @08:36AM (#5898745)
Did you ever learn about the variant called 'Brussels Sprouts' and the trick to winning?
Re:Ultimate Tic Tac Toe by coldpie on Tuesday June 18, 2013 @08:52AM (#5898818)
Please explain :)
Re:Ultimate Tic Tac Toe by michaelfeathers on Tuesday June 18, 2013 @09:04AM (#5898874)
If I remember correctly, instead of only allowing three edges to emanate from a vertex, you can have four. All other rules are the same. Apparently, in that set up, the the first player either always wins or loses depending upon whether the number of initial vertices is odd.
Re:Ultimate Tic Tac Toe by Someone on Tuesday June 18, 2013 @12:01PM (#5900051)
Re:Ultimate Tic Tac Toe by willvarfar on Tuesday June 18, 2013 @08:53AM (#5898824)
I particularly liked his Core War game too. Its still around, although admittedly quite low-key: http://en.wikipedia.org/wiki/Core_War
Re:Ultimate Tic Tac Toe by chinpokomon on Tuesday June 18, 2013 @01:51PM (#5900828)
I've committed countless hours to Core Wars and variations of the game. It is fantastic.
Re:Ultimate Tic Tac Toe by willvarfar on Tuesday June 18, 2013 @07:46AM (#5898608)
My daughters play a variant of tic-tac-toe with a physical board and just three stones each.

I brute-forced this with a little lunchbreak program and the visualisation output from graphviz was ... 340 MEGAPIXELS!

I blogged about it: http://williamedwardscoder.tumblr.com/post/35858593837/tic-t...

Re:Ultimate Tic Tac Toe by fduran on Tuesday June 18, 2013 @09:00AM (#5898856)
That's how we used to play as kids, there's an algorithm so that the first mover always wins.
Re:Ultimate Tic Tac Toe by Millennium on Tuesday June 18, 2013 @10:48AM (#5899496)
Sounds a lot like Three Men's Morris. Nifty.
Re:Ultimate Tic Tac Toe by shardling on Tuesday June 18, 2013 @11:41AM (#5899889)
A weird version of tic-tac-toe my friends and I came up with years ago: you play without a board. Any move is valid so long as you could superimpose a standard tic-tac-toe grid over the results. (You assume the marks are at the center of their respective squares; you allow the board to be at any scale or angle, but you can't skew it.)

The first two moves have no constraint, so you can just start with an X and O already on the board. And after a few moves there might be only one implied board possible, after which it reduces to the normal game. But I always thought it was an interesting twist.

Re:Ultimate Tic Tac Toe by lotharbot on Tuesday June 18, 2013 @12:32PM (#5900294)
Somebody posted another tic tac toe variant on HN some time ago, where the squares were numbered 1-9 and the goal was to get any three squares that summed to 15. It turns out this is equivalent to playing tic tac toe with sides that wrap around (like a torus).
Re:Ultimate Tic Tac Toe by Someone on Wednesday June 19, 2013 @04:34PM (#5908006)
No, that's 100% equivalent to tic tac toe (http://en.wikipedia.org/wiki/Tic-tac-toe#Variations)

(To see why no torus version exists: on a '3x3' torus, all squares are identical, so you have must four ways to get three in a row from each starting number. Also, the row/column/diagonal sum must be 15. However, starting with 9, there are only two ways to get 15 with: 1 and 5 and 2 and 4)

The variant with nine words, where selecting three words that share a letter wins the game, IMO is even better.

Re:Ultimate Tic Tac Toe by lotharbot on Wednesday June 19, 2013 @05:06PM (#5908246)
I may have misremembered the details of the game, or conflated it with another game.

What I remember clearly is that the game was equivalent of tic tac toe on a torus -- one could win with a "diagonal" of the form

.|x|.

x|.|.

.|.|x

as well as any of the traditional tic tac toe win conditions.

Re:Ultimate Tic Tac Toe by Someone on Wednesday June 19, 2013 @06:36PM (#5908892)
Tic tac toe on toruses is fairly popular as an educational toy, and there also is serious research on it, for example http://www.ux1.eiu.edu/~kwolcott/TTT.pdf. You might have mixed the 'on a torus' part with the 'using a magic square' part. No problem, but the two do not mix that way (maybe, on larger boards? That 4x4 Dürer square (http://mathworld.wolfram.com/DuerersMagicSquare.html) has zillions of 'add up to 34' sets of cells. There may be even better ones of larger size)
Re:Ultimate Tic Tac Toe by gohrt on Tuesday June 18, 2013 @04:24PM (#5901815)
also equivalent to covering every row and column on the board.
Re:Ultimate Tic Tac Toe by dreen on Tuesday June 18, 2013 @09:51AM (#5899126)
There is another great variant of Tic Tac Toe you can play on a Torus (a donut shape): http://upload.wikimedia.org/wikipedia/commons/1/17/Torus.png

The way to play is to "warp" each side of the board to the side opposite of it. For instance, playing on a 6x6 board with a win condition of length 5:

    .|X|.|.|.|.
    X|.|.|.|.|.
    .|O|.|.|.|.
    .|O|.|.|X|.
    .|.|O|X|.|.
    .|.|X|O|.|.
is a win for X, because the upper and lower ends of the board are synonymous.

I can't find any material about this on the net, I just played it in school on boring lessons (but more commonly we played for 5 in a row on an infinite board, I personally prefer the Torus)

Re:Ultimate Tic Tac Toe by arh68 on Tuesday June 18, 2013 @09:58AM (#5899156)
> Whichever square he picks, that’s the board you must play in next.

And what about the dual of this game, where whichever board you pick determines the square he plays next?

Re:Ultimate Tic Tac Toe by nawitus on Tuesday June 18, 2013 @09:44AM (#5899084)
Does anyone else play the 'infinite board' tic-tac-toe which requires you to get five in a row? It's what I used to play as a student, and it's pretty well-known at least where I live. Nobody bothers with the 3x3 version, but the five in a row version is pretty exciting and requires plenty of strategy and thinking ahead.
Re:Ultimate Tic Tac Toe by bierik on Tuesday June 18, 2013 @10:28AM (#5899370)
I think this is called "Gomoku" (just on a quasi-infinite board): http://en.wikipedia.org/wiki/Gomoku I used to play this a lot when I was still at the university
Re:Ultimate Tic Tac Toe by seri on Tuesday June 18, 2013 @11:43AM (#5899911)
Yup, Gomoku is a much more difficult game than it looks. Indeed, the game is challenging enough that there is a world championship every odd year. You can find the games from the last world championship here: http://renju.net/media/games.php?gameid=45016

I am amazed by the fact that Gomoku can be so hard to master with rules so simple you can explain to a five year old. And unlike Chess where there are a hundred year of theories to learn from before you can get going, Gomoku is still new. After a few weeks studying the standard surewin openings, you can expect to see things in a very different light and the game will get much more interesting.

Perhaps Gomoku is best known for programmers as a problem to solve. But it is nowhere near being solved. In fact, the best software are weaker than many top players.

I find Gomoku hits the sweet spot when it comes to my desire to play board games. It doesn't consume much of my time. I am always excited to find those long and obscure wins. I think the game needs more love from programmers like me.

Facebook page: https://www.facebook.com/GomokuWorld Play here: http://www.playok.com/en/gomoku/ Or here: http://fumind.com

Re:Ultimate Tic Tac Toe by fc2 on Wednesday June 19, 2013 @01:39AM (#5903884)
Gomoku has already been solved actually, maybe you were thinking of Go? There's a revised version called Connect6 though, in case you are interested.

https://en.wikipedia.org/wiki/Connect6

Re:Ultimate Tic Tac Toe by seri on Wednesday June 19, 2013 @09:25AM (#5905377)
Under free opening rules, Gomoku has been proved to be sure-win for black, aka the first player. This work done by Victor Allis could be part of the reason why Gomoku is undeservedly treated as a toy board game.

We have to remember, however, that this proof is computer search based. There was never an algorithm to find the best move given a random position. In other words, it only proves that these certain openings will guarantee black a win.

Those who loved the game came up with new opening rules. The world championships in 1989 and 1991 used the pro rule. After some evolutions, swap2 now became the standard. Under Gomoku swap2, the first player puts two black stones and one white stone on the board, and the second player can either pick one color, or puts two more stones and gives back the power to choose color to the first player.

I know about Connect6, and also a branch called Renju. But I find Gomoku more attractive. You should totally try it sometimes.

Re:Ultimate Tic Tac Toe by Delfino on Tuesday June 18, 2013 @08:05AM (#5898657)
Neat variant. I made something similar for the last ludum dare: http://madelfino.github.io/LD26/postcompo.html
Re:Ultimate Tic Tac Toe by M4v3R on Tuesday June 18, 2013 @08:43AM (#5898779)
Nice! Managed to beat it, but it wasn't easy: http://dl.dropbox.com/u/1127246/Screenshots/5ths.png
Re:Ultimate Tic Tac Toe by speeder on Tuesday June 18, 2013 @10:10AM (#5899223)
When my dad was at university he made just out of curiosity a AI to play Tic Tac Toe that started knowing nothing about the game, and tried to learn from playing against the player, until it became impossible to beat it.

Later someone complained with university administrators that my dad was "playing games" in the computer lab, and he got banned from it :/

But I guess this version might be even more interesting to make a AI test or something!

Re:Ultimate Tic Tac Toe by garethadams on Wednesday June 19, 2013 @03:10AM (#5904118)
The only winning move is not to play
Re:Ultimate Tic Tac Toe by mrspeaker on Tuesday June 18, 2013 @07:59AM (#5898640)
I don't understand the clarifying rule #2: "What if my opponent sends me to a board that’s full?" Isn't that impossible, as there is a maximum of 9 ways to be sent to each local area?
Re:Ultimate Tic Tac Toe by cousin_it on Tuesday June 18, 2013 @08:18AM (#5898698)
I think you can get sent to a full board only if the game started on that board.
Re:Ultimate Tic Tac Toe by jbri on Tuesday June 18, 2013 @09:28AM (#5898990)
Of course, there's a cascading effect where it's now possible to also overflow the board you chose with your free move.
Re:Ultimate Tic Tac Toe by elsporko on Tuesday June 18, 2013 @08:11AM (#5898675)
Isn't it possible that the first board played could become full since the first mark isn't the result of normal gameplay?

Move 0.

Re:Ultimate Tic Tac Toe by lke on Tuesday June 18, 2013 @08:17AM (#5898693)
If you look his Orwin Gambit start it would happen. It's because this the first move is done freely so you end up with one area ahead of it's paths (ie full but with only 8 path already taken).
Re:Ultimate Tic Tac Toe by joeyrobert on Tuesday June 18, 2013 @07:57PM (#5902828)
Another quick implementation of this game: http://joeyrobert.org/projects/ultimatetictactoe/
Re:Ultimate Tic Tac Toe by alphaoverlord on Tuesday June 18, 2013 @12:25PM (#5900224)
Perhaps the game is less deterministic 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. Then approaches like the Orwin gambit would not work (it is too costly to lose a board if it only lets you choose three spots.)
Re:Ultimate Tic Tac Toe by Kurtz79 on Tuesday June 18, 2013 @07:34AM (#5898574)
http://xkcd.com/832/

Randall Munroe could do a "small" update to this based on these rules... although it would take some time.

Re:Ultimate Tic Tac Toe by lucb1e on Tuesday June 18, 2013 @07:43AM (#5898596)
A "small" update? I think this is more like the difference between checkers and chess. But yes, relevant xkcd
Re:Ultimate Tic Tac Toe by tripzilch on Tuesday June 18, 2013 @11:30AM (#5899809)
> I think this is more like the difference between checkers and chess

I'm not sure what you mean by this?

BTW are you aware that despite it has only one type of stone and simpler rules, checkers is in fact the more complex game, to write an AI for?

Re:Ultimate Tic Tac Toe by saalweachter on Tuesday June 18, 2013 @12:44PM (#5900373)
Checkers has been solved. Both players can draw with perfect play.

The usual caveat with checkers is that you are probably not good at it. Even if it is simpler and smaller than chess, being a good chess player gives you no advantage and the game is still sufficiently complex that you can't quickly brute force it without years of practice. A chess master will get their ass handed to them by a skilled yokel.

Re:Ultimate Tic Tac Toe by pong_ on Tuesday June 18, 2013 @02:12PM (#5900964)
I guess you refer to International checkers (being from the Netherlands). Still a challenge for computers, given that the brute-force solution for American checkers doesn't work well for this larger board.

Much harder to program an AI for than chess, certainly. The computer never managed to beat the world champion in a match last year.

Re:Ultimate Tic Tac Toe by tripzilch on Wednesday June 19, 2013 @07:22PM (#5909140)
Cool, I didn't know there were multiple versions of checkers. I'll have to check (hah) out that solution for the American version though, always interesting (as well as what the differences in rules are). Off to Wikipedia, I guess ;-)
Re:Ultimate Tic Tac Toe by shawabawa3 on Tuesday June 18, 2013 @12:30PM (#5900268)
> checkers is in fact the more complex game, to write an AI for?

I'm almost certain that's false. Checkers is weakly solved (There are AI's that will never lose, only win or draw)

I assume you meant Go, not checkers. And that's mainly harder for AI because the board is 5 times bigger.

Re:Ultimate Tic Tac Toe by lucb1e on Tuesday June 18, 2013 @12:17PM (#5900151)
I don't know why you're downvoted for asking a question, but what I meant is this: The person I replied to said the admin of XKCD could do a "small" update to his post about tic tac toe. I remarked that this is not a small update, and used checkers and chess as an analogy. Chess is much more complex and harder to learn than checkers, and as you remarked, chess is indeed harder to write an effective AI for. Just like the difference between tic tac toe and ultimate tic tac toe ;)

Edit: I meant chess is harder to write an AI for of course, not checkers. Fixed.

Re:Ultimate Tic Tac Toe by yashg on Tuesday June 18, 2013 @07:29AM (#5898564)
This is brilliant! Has anybody created an online version of this?
Re:Ultimate Tic Tac Toe by monsterix on Tuesday June 18, 2013 @07:46AM (#5898607)
Re:Ultimate Tic Tac Toe by gambogi on Tuesday June 18, 2013 @07:37AM (#5898580)
I can bet you there will be now
Re:Ultimate Tic Tac Toe by ronaldx on Tuesday June 18, 2013 @02:42PM (#5901141)
It doesn't observe a win and for now you have to play against yourself, but:

http://xoxo.gl/ultimate

Re:Ultimate Tic Tac Toe by yarekt on Tuesday June 18, 2013 @02:55PM (#5901225)
http://ultic.waynecrouch.co.uk/

A quick hack while avoiding doing actual work. The code is on github, We might implement multiplayer soon

Re:Ultimate Tic Tac Toe by deletes on Tuesday June 18, 2013 @07:39AM (#5898582)
Important question, can this game be solved, like ordinary tic-tac-toe. Is there a solution that always leads to draw of defeat.
Re:Ultimate Tic Tac Toe by k2enemy on Tuesday June 18, 2013 @08:27AM (#5898718)
Zermelo's theorem[1] says "yes," although I don't know which it is (between draw, p1 win, p1 lose).

[1] https://en.wikipedia.org/wiki/Zermelo%27s_theorem_%28game_th...

Re:Ultimate Tic Tac Toe by CJefferson on Tuesday June 18, 2013 @08:31AM (#5898733)
In fact, it can't be a p1 lose, because the extra piece p1 gets can never be a disadvantage (you can prove this more carefully). The question is then is it a p1 win, or draw?

A similar situation arises in the game 'hex', except in that game there is no draw, so it has to be a p1 win!

Re:Ultimate Tic Tac Toe by Someone on Tuesday June 18, 2013 @12:06PM (#5900087)
"because the extra piece p1 gets can never be a disadvantage (you can prove this more carefully)"

Please do so, as I do not see that this is trivially true. I see two tricky cases:

- your opponent must play on the board where p1 is placed, and that board would have room iff p1 weren't present => Addition of p1 gives him a 'move anywhere' move.

- you must play on the board where p1 is placed, and that board would have room iff p1 weren't present. The normal argument 'move anywhere and assume that that 'anywhere' is where your first move went, and you just played p1' does not help here, as changing the first move may change where your opponent's first move could have gone.

Except from an exhaustive search, I do not see how to prove that you can prevent either case.

Re:Ultimate Tic Tac Toe by CJefferson on Tuesday June 18, 2013 @12:22PM (#5900199)
Yes, you are right.

Actually, the fact you force your opponent isn't the problem (I don't think) but the fact that the presence of that piece might later give p2 a free move, where previously they wouldn't means it doesn't work.

Sorry, that's what I get for thinking I didn't need to figure out all the details carefully!

Re:Ultimate Tic Tac Toe by lucb1e on Tuesday June 18, 2013 @07:45AM (#5898601)
Regardless of whether you can build a perfect AI on commodity hardware, though I haven't played this yet, it promises to be a much more interesting game than the normal tic-tac-toe!

Harder to draw a lot on napkins though, but then again, a single game takes much longer.

Re:Ultimate Tic Tac Toe by chii on Tuesday June 18, 2013 @09:13AM (#5898918)
use 9 napkins - problem solved ;)
Re:Ultimate Tic Tac Toe by ronaldx on Tuesday June 18, 2013 @02:51PM (#5901201)
if you use napkins then you can also move the boards around ;)
Re:Ultimate Tic Tac Toe by jjcm on Tuesday June 18, 2013 @03:29PM (#5901434)
The one I play with my friends is usually a 4-in-a-row, 4 level board. You can win on any individual level, or by creating a straight line of 4 that intersects plays on each level (so playing in the top right of each level would net you a win, for instance). It forces the players to keep a three dimensional model in their head and opens up the board for more counters/strategy.

Anyone care for a game?

    level 1    level 2    level 3    level 4
    .|.|.|.    .|.|.|.    .|.|.|.    .|.|.|.
    .|.|.|.    .|.|.|.    .|.|.|.    .|.|.|.
    .|.|.|.    .|.|.|.    .|.|.|.    .|.|.|.
    .|.|.|.    .|.|.|.    .|.|.|.    .|.|.|.
Re:Ultimate Tic Tac Toe by ronaldx on Tuesday June 18, 2013 @02:02PM (#5900910)
I made a quick HTML demo for playing through the game at http://xoxo.gl/ultimate
Re:Ultimate Tic Tac Toe by joelthelion on Tuesday June 18, 2013 @04:00PM (#5901643)
Now add an AI :)
Re:Ultimate Tic Tac Toe by ronaldx on Tuesday June 18, 2013 @08:57PM (#5903038)
You think so? I'm not very keen to work on an AI if there's proof of a quick win.
Re:Ultimate Tic Tac Toe by irunbackwards on Tuesday June 18, 2013 @03:19PM (#5901367)
We made this into an Android application about a year ago: http://superttt.com
Re:Ultimate Tic Tac Toe by lkozma on Tuesday June 18, 2013 @08:21AM (#5898702)
I recall seeing this before, called "crazy" tic tac toe:

http://tictactoe-cssi.appspot.com/ via: http://neil.fraser.name/news/2011/07/16/

Re:Ultimate Tic Tac Toe by deanclatworthy on Tuesday June 18, 2013 @09:04AM (#5898875)
The first of these doesn't follow the same rules as OP. It seems that you can retake a board if you get a new row in a box that has already been won.
Re:Ultimate Tic Tac Toe by h4pless on Tuesday June 18, 2013 @02:01PM (#5900901)
I haven't tested all the cases but this method seems to win every time I've tested it against myself:

Start on an edge-center container [N,E,S,W], marking it with it's corresponding sub-board space. Employ the Orwin gambit to fill the initial edge container. When your opponent selects the last space in the first container, wherever you are sent: pick it's corresponding sub-board space and then employ the Orwin gambit again and then repeat the routine until the game is finished. Your opponent gets to pick your next moves but because they eventually must send you to a filled square on the second and third rounds, you have the ability to control the game's end.

Starting in the center gives you a tactical disadvantage because it only leaves you 4 paths to victory compared to your opponents 8 with him/her in a position affecting 4 lines, whereas by starting on a side piece, you have 7 paths to victory and your opponents position only benefits him on 2 lines.

Re:Ultimate Tic Tac Toe by tictactoeten on Thursday June 20, 2013 @02:09AM (#5910465)
My team and I have implemented what you call Ultimate Tic Tac Toe as what we call Tic Tac Toe Ten. We put it out for iOS, Android, Windows Phone and have made board game sets to go into school districts with starting in 2008. If any of you in this community are interested in helping us to build out the backend analytics infrastructure to help us make the academic breakdown of this game useful for teachers and students please visit our community at https://www.facebook.com/tictactoeten and drop me a message or DM us on Twitter (@tictactoeten) ... we are also always looking for volunteers at our school tournaments where we pit kids against each other March Madness style with brackets and give out prizes to the winners ... we are here in the Bay Area, hope to meet some of you guys soon :)

cheers, @bware218

Re:Ultimate Tic Tac Toe by baritonehands on Wednesday June 19, 2013 @10:34PM (#5909817)
Re:Ultimate Tic Tac Toe by AUmrysh on Tuesday June 18, 2013 @08:33PM (#5902951)
What if you played it where the square selected is the direction you move to go to the next board. If the player selects the center square on a board, that board must be played again. If the player selects the left square, the board to the left must be played next. If a corner square is picked, you play the board to that diagonal direction.

If the corner is not attached to a board, you roll the board around as though the ends are connected (or as though it's an infinitely repeating tiling of the same game). For example, the bottom right square on the bottom right board makes the next board the top left.

The center-right square on the center-right board would result in the next board being the center-left board, and so on.

Would there be a gambit in this ruleset?

edit: So, it looks like the same gambit applies, instead of selecting the center piece you just pick the one pointing toward the center every time.

Re:Ultimate Tic Tac Toe by yarekt on Tuesday June 18, 2013 @09:15AM (#5898929)
http://graffitiwall.co.uk/ultimatetictactoe

My quick implementation of this game

Edit: For anyone who arrived 10 seconds after i posted that link, The board resembled the ultimate tic tac toe, and then quickly degraded into a paint fight

Re:Ultimate Tic Tac Toe by speeder on Tuesday June 18, 2013 @09:54AM (#5899140)
Interesting that hackers instead of working or reading HN are very interested in fighting over the board (ie: gray color people try to erase it, pink color try to draw a board, and blue color trying to play the game...)
Re:Ultimate Tic Tac Toe by danielweber on Tuesday June 18, 2013 @12:09PM (#5900104)
"Someone keeps stealing my letters" http://www.lunchtimers.com/
Re:Ultimate Tic Tac Toe by cilo on Tuesday June 18, 2013 @10:16AM (#5899292)
Who needs comments, all posts should just have a graffiti wall. What could go wrong?
Re:Ultimate Tic Tac Toe by frogpelt on Tuesday June 18, 2013 @10:01AM (#5899175)
There's a way to prevent the Orlin gambit. Allow the player with the last three in row to take another turn.

This creates a means of alternating who goes first.

I'm not sure whether this gives too much advantage to the other player or not.

Re:Ultimate Tic Tac Toe by akincisor on Tuesday June 18, 2013 @04:36PM (#5901906)
It does. He can now force you to now place pointless moves in the center square.
Re:Ultimate Tic Tac Toe by GotAnyMegadeth on Tuesday June 18, 2013 @11:17AM (#5899711)
My friends used to play something similar with connect 4. You don't expect to meet people who are good at connect 4, but these two guys beat me 100% of the time...
Re:Ultimate Tic Tac Toe by gwern on Tuesday June 18, 2013 @02:25PM (#5901040)
Re:Ultimate Tic Tac Toe by sudhirj on Tuesday June 18, 2013 @12:29PM (#5900260)
Can anyone else hear the quiet roar of a thousand not-so-silent fans as they struggle to dissipate heat caused by furious Xcode and RubyMotion compilations?
Re:Ultimate Tic Tac Toe by gamegoblin on Tuesday June 18, 2013 @12:28PM (#5900249)
Another interesting way to play tic-tac-toe that makes it a lot harder:

There is a bag of numbers 1-9. Players take turns moving numbers from the central bag to their own private bags, removing that number from play. Whenever a player has a subset of exactly 3 numbers that sums to 15, they win.

This is isomorphic to tic-tac-toe since the magic square for a 3x3 board has rows/columns/diagonals that sum to 15.

Re:Ultimate Tic Tac Toe by solox3 on Tuesday June 18, 2013 @11:48AM (#5899944)
It happened a while back, when Bobby Kehres told my colleague and I about the game. https://github.com/1337/Tic-Tac-Toe-Extreme
Re:Ultimate Tic Tac Toe by rfisher1968 on Tuesday June 18, 2013 @10:30AM (#5899382)
I made this a while back. It a HTML5 game made with construct2. http://jenpop.com/game.php?gurl=games/uttt
Re:Ultimate Tic Tac Toe by roryokane on Tuesday June 18, 2013 @09:34PM (#5903227)
Your game is just Tic-Tac-Toe on a 6x6 board. It is not the same game as the Ultimate Tic-Tac-Toe described in the article.
Re:Ultimate Tic Tac Toe by crimzonphox on Wednesday June 19, 2013 @01:20PM (#5906834)
My favorite Mathematics game is: http://en.wikipedia.org/wiki/Connect_Six

Mathematically fair

Re:Ultimate Tic Tac Toe by randren on Wednesday June 19, 2013 @12:58AM (#5903806)
Kid-tested. The 7-year-old loves it. Thank you for saving me from plain-old Tic Tac Toe games with my kid.
Re:Ultimate Tic Tac Toe by minikomi on Wednesday June 19, 2013 @01:02AM (#5903818)
What happens to the game if you switch order when you take a board?
Re:Ultimate Tic Tac Toe by iguana on Tuesday June 18, 2013 @03:21PM (#5901383)
Someone needs to write a JavaScript implementation of this!