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.
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...
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.
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.
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.
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.
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.
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.
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
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. :)
| 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).
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...
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.
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.
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.
"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.
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.
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.
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.
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.
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.
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.
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.
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.
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
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?
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.
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.
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.
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).
(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.
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)
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)
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.
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
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.
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.
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!
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?
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).
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.)
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.
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.
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 ;-)
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.
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!
"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.
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!
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.
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.
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.
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 :)
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.
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
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...)
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...
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?
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.
- 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.