## Saturday, February 2, 2013

### Multi-Dimensional Tic-Tac-Toe

In theory, any game that has a finite number of players, a finite number of moves, and a lack of random chance, can be "solved".  There are three no one expects the Spanish Inquisition possible outcomes to a solved game.  I was going to say win, lose or draw, but that leaves out some things,  First off not all games are two player, second perpetual game-play is a possibility I knew about and was planning to mention before I wrote "Three."

These all assume a lack of mistakes:
1 Player 1 always wins.
2 Player 2 always wins.
2a Player N (where N is a finite integer greater than two and less than or equal to the number of players in the game) always wins.
3 The game always ends in a tie.
4 The game never ends.

Tic-Tac-Toe is a solved game.  If no one makes a mistake, no one wins.  Don't believe me?  I give you that scene from War Games.  (Rota, for comparison, is a game where if no one makes a mistake the game never ends.)

At some point in the past, I remember trying to extend the same functionality into additional dimensions.  First off it's worth noting that, and I'll use this fact extensively if I ever get around to writing up my thing on 3-d chess, a line is to two-space as a plane is to 3-space.  So maybe the rules in three dimensions should be that you have to complete a plane rather than a line.

This wasn't what I was thinking in the past and is not what I will use the bulk of this post to discuss, but I will give a quick explanation of what it would mean.

-

There are three basic planes on a simple 3d grid, but one needs more space than a 3x3x3 board allows to make all 3x3 planes:

Thus there are 15 possible 3x3 planes in a 3x3x3 grid (as compared to 8 3-long lines in a 3x3 grid.)
Of them 9 are flat, 6 are diagonal edge-to-edge (as compared to 6 being flat and 2 diagonal in a 3x3 grid.)

The center is included 9 of them (1/3 of the flat, all diagonals), any given face center is included in 5 (3 flats, 2 diagonasls), any given edge is in 4 (3 flat, 1 diagonal) and any given corner is in 5 (3 flat, 2 diagonal.)

In traditional Tic-Tac-Toe the center is included in 4 lines (1/3 of the flat, all diagonals), any given edge is in 2 (both flat) and any given corner is in 3 (2 flat, 1 diagonal.)

The reason I'm not much a fan of this method of Tic-Tac-Toe 3d is that a 3 square line is easy to miss, but a nine cube plane is kind of obvious.

It still, at least, maintains the basic function because it's always going to end in a draw without a mistake, but part of the idea of extending it to higher dimensions was to make a mistake more likely as complexity increased (I know I went to five or six dimensions.)

So the idea was that it would remain a relatively easy to miss three in a row, not a plane.  Plus, I'm not sure if I'd really thought about using planes instead of lines when using three dimensions instead of two.  I think that came from my understanding of a rook.

-

Make Tic-Tac-Toe into three dimensions by making it a 3x3x3 grid and the first player always wins.

The first player takes the center.  I was going to say that it doesn't matter in the least where the second played moved but that's not entirely true.  If the second player took a corner that does change things.  So first assume the first player took an edge or a face center. The first player takes a corner right next to it.

That forces the second player to take the opposite corner to stop the first player from getting three in a row. Then the first player plays a face center next to their corner.

(Red for player one, light blue for player two's first move as it could be either of those and it doesn't matter which, dark blue for player two's forced moves.)

Player two is screwed.  Block the vertical line through the center and player one wins with a diagonal across the top.  Block the diagonal and player one wins with the vertical.

Now assume player two took a corner, Player one still takes the corner closest, which still forces player two into the opposite corner.  Now player one has to be defensive otherwise player two will win with a corner to corner diagonal.  This forces player two to make a defensive move, and payer one is free to fork again:

Exact same endgame as we had before.  Player two can choose how to lose, but there's no way to avoid losing.  That's not Tic-Tac-Toe, at least not to me.  A perfect game should end in a draw, losing should require making a mistake.

The center clearly hold too much power, we have to lose it.  (Note that I could have done essentially the same thing if I'd started with center then edge.)

So now we get this:

Unfortunately that still doesn't solve the problem.  The corners are likewise too powerful.  Player 1 can still force a win, so we're left with this thing that doesn't look much like a Tic-Tac-Toe board:

I'm not sure if I considered just removing face centers, but that doesn't solve the problem anyway.  Face centers plus center removed I'm not sure on.  Give me a moment to check.

Moment taken.  If anything it makes the unavoidable loss even more brutal on player two.

So, we're sticking with the above board, which doesn't have any diagonals (shameful loss) but does, I think, lead to a draw if no one screws up.  I think, I probably haven't done as much checking as I should.  Anyway, four dimensions.  First, let us extend the above board without too much thought as to whether or not it leads to forced wins.

I already extended a board without much explanation, now I should probably give some.  Before we just took a 3x3 and made it into a 3x3x3, which is relatively straight forward. this requires some more thought into what it means to extend a board into a higher dimension because we've got a strange shape to begin with.

First off note that we're working on something with symmetry, no matter how you rotate the above shape in three dimensions it'll always look the same.  So to extend we keep that symmetry.

Since I don't have a four dimensional space the extra dimension will be represented by extra boards.  Just like how I represented three dimension in two by using extra boards (note the three levels on the thing above.)  I could have put those boards side by side, if I wanted, and it still would have been the same game, it would just have given less of an impression of the 3d structure I was trying to imitate.  For the fourth dimension we will put boards side by side.

Now, about distance.  Moving between adjacent boards is moving one space.  So take a look at this image:

The orange spots are all the same distance from the center, as are the green.  But the orange spots are at the center of the top and bottom boards and at the edges of the center board.  That's because the edges of the center board are one step away from the center, but the top and bottom boards are each one step away from the center in themselves, so the same place (the center) is one step away.

And I feel like I'm beating the obvious here.  There's nothing really special going on about this, just imagine turning the thing on its side and rotating the squares to create new flat boars and you'll see it's all the same.

The point is this: put extend the board above into four dimensions and you get this:

(By the way, how do people feel about a sentence with two colons, as above.  Kosher?  Blasphemy?  Something in between.)

Now that's just taking the 3d board and making it symmetrical under 4d rotation.  Something that I think managed to completely escape my notice when I was first doing this (but god only knows where those notes are so I'm working entirely from distant memory) was that if I had done the same thing when extending into 3d I would have gotten a board without corners anyway.

(Unfortunately removing the corners first still doesn't let us keep the center.)

The corners were a new kind of space, impossible in 2d but obvious in 3d.  I could see what would happen if I added in the 4d equivalent here, but for now I'm going to stick with trying to reconstruct what I made lo those many years ago.

For anyone confused by what these pieces on the new boards are, here's a picture using the same color coding as before (click to enlarge):

And here are some examples of possible winning moves that cross the three 3d boards (again, click to enlarge):

Diagonals are still impossible, but as mentioned back at 3-d, I couldn't find a way to save them without allowing player 1 to force a win.  So, basically, on a given board three in a row is exactly what you'd expect, and across boards it's three in the same place on each board.

And some quick tests show that my original work, which did indeed look like that, before getting extended to additional dimensions, was flawed.

---

Though actually more extensive tests show that, yes, it's flawed, but it actually can take a while to figure out how to force victory from given positions.  Still, no mistakes and the first to move automatically wins.  The goal was for automatic draws in the absence of mistakes.

And it looks like restricting the first player to starting on a less powerful square doesn't change that.  Can't take away more pieces like I did after the conversion to two pieces, there's only two types left and take away either one and it makes it impossible to get three in a row.

I wondered if maybe returning the center, but not letting it be taken until the second move (thus giving it to player two) might fix things but then it just made things always win for player two.  Presumably some balance can be found between returning the middle square overpowering everything and keeping the current game board allowing the first player to force a win, but damned if I know what it is and I'm actually fairly tired right now.

Anyway, if it doesn't work in four dimensions it certainly won't work in higher ones that use it as a base, but as I recall the plan was to look something like this for five:

And just add this above and below for six:

-

And that was the plan at any rate, near as I can remember it.

1. If the problem is that there are too many dimensions and therefore too many different ways to put together a line, how about requiring a complete plane in order to win?

1. In higher dimensions that might work because it can be confusing to even tell what a plane is at first glance, in 3d it's just too obvious. The idea is no-mistakes=not-losing, but complex to the point it's easy to make a mistake. Seeing that two things are lined up to make for 3 in a row next move is easy to miss, seeing that eight things are lined up to make for a plane next move is harder to miss.

I wonder if it might be possible to stick to the original idea, and keep the center piece and thus diagonals if instead of making one line one was required to make two, or (N-1) where N is the number of dimensions.

The problem in 4 as it appears above, and 3d with a center is that the first player can force the second to move around the board as they choose, never getting in a free move because of the need to block that first line. If the first line can be given away, that changes everything. Not sure if it solves everything, but it changes everything.

One thing that I like about not adding new types of squares (every square above is either a 2d edge or a 2d corner) is that it makes for strange shapes of boards instead of a 3x3x3x.... hypercube.

2. In theory, any game that has a finite number of players, a finite number of moves, and a lack of random chance, can be "solved".

Actually, I believe you're missing one condition - the game must also have no hidden information (i.e. all players are aware of the complete game state). The game Stratego, for instance, is a game with hidden information (you do not know the values of the other player's pieces until they are revealed by an attack).

1. I do believe that you're probably right. In certain situations the uncertainty might be able to be accounted for thus allowing a game to be solved, but in other situations, Stratego probably among them, the uncertainty would probably override the possibility of a solution.

Finity still means that one can determine all possible games, but when uncertainly reaches a certain point a solution would be probabilistic (right move is the one that has the least possible chance of you losing/highest possibly chance of you winning/whatever your priority is) rather than deterministic.

Of course, the same can be said of games with random chance involved. It's possible to determine what leads to the highest possible chance of you winning, it's not possible to solve in the way it is with something like tic-tac-toe or chess.

So, I think you're right.