4x4x4 Tic-Tac-Toe
Oded Maron
of a 3-D 4x4x4 tic-tac-toe game?
(in the 3x3x3 case, the first player always wins, by the way).
Thanx,
Oded
ma...@levels.sait.edu.au
The 4*4*4 game is somewhat interesting, but I would like to point out to Oded
that the 4*4*4*4 game is m u c h more interesting to play - it is commonly
called 4-dimensional tic-tac-toe.
I would use a minimax algorithm with alpha-beta pruning to play this game.
It is not difficult and I could post the code for a 3*3 game with a 2-level
lookahead; the evaluation function for this game is taken directly from
David Levy's book: "Computer Gamesmanship". A 2-level lookahead is all that
is required here.
It is hard to find people to play 4*4*4*4 as it takes about an hour for a
well-thought-about game, so maybe I'll modify my program to play it.
Perhaps Oded would like to modify the current code to play a 4*4*4 game?
Ray
--
University of South Australia | Plus ca change, plus c'est la meme chose.
P.O. Box 1 | Ghing thien me how, ming thien gung me how.
Ingle Farm | Knobs, knobs everywhere,
South Australia | just vary a knob to think!
Greg Kuperberg
>Does anybody have a good algorithm or know of a reference to one for
>the problem of a 3-D 4x4x4 tic-tac-toe game?
According to *Winning Ways*, Vol. II, by Berlekamp, Conway, and Guy,
Oren Patashnik (o...@cs.stanford.edu) has developed a winning strategy
for the first player by means of an interactive human-computer search
that lasted several months.
----
Greg Kuperberg
gr...@math.berkeley.edu
Warwick Allison
>In article <15955.2...@levels.sait.edu.au>, ma...@levels.sait.edu.au wrote:
>>The 4*4*4 game is somewhat interesting, but I would like to point out to Oded
>>that the 4*4*4*4 game is m u c h more interesting to play - it is commonly
>>called 4-dimensional tic-tac-toe.
>Are you sure about that? In order to make a non-trivial game, the size of
>the grid has to be 1 more than the number of dimensions (so 3*3, 4*4*4,
>5*5*5*5 etc.) and no, I can't prove it; this is left as an exercise for the
>reader :-)
And just what does NON-TRIVIAL mean? Surely you realise that any game
of this nature has a fixed outcome, determined by who goes first. How trivial
is your meaning of `trivial' - someone mentioned 3x3x3 had a KNOWN solution
(I think first-player-wins), but so does 3x3: tie. As with any of these
games, either:
1. first player wins
2. first player loses
3. tie
No other outcomes are possible, providing each player has maximal
skill. In fact, in some games option 3 is impossible (definate winner).
Games do, however, vary in the degree of freedom players have. For
example, in classic 3x3 Tic-tac-toe, it is irrelevant where the first move
is made, a draw will still be forced. Also, if, say, the first move is in
the centre, the second move has a high degree of freedom in that it can
be at any corner (if you cancel symetry though, this is the only degree
of freedom).
As an example of the opposite, take the `pyramid' game, where a
triangle of 15 pieces (height = 5) is the gameboard, and each player may
take any number of adjacent pieces in a straight line...
eg.
* * *
* * * * * * *
* * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * * * * *
The loser is the player who take the last piece.
Rather than blurt it out, I'll make this a PUZZLE...
Who wins? FIRST or SECOND player?
POST replies. (:-)
--
_--_|\ war...@cs.uq.oz.au
/ * <-- Computer Science Department,
\_.--._/ University of Queensland,
v AUSTRALIA.
Ian Collier
>The 4*4*4 game is somewhat interesting, but I would like to point out to Oded
>that the 4*4*4*4 game is m u c h more interesting to play - it is commonly
>called 4-dimensional tic-tac-toe.
Are you sure about that? In order to make a non-trivial game, the size of
the grid has to be 1 more than the number of dimensions (so 3*3, 4*4*4,
5*5*5*5 etc.) and no, I can't prove it; this is left as an exercise for the
reader :-)
While I'm here, does anyone know a (analytical) function f for which
f(f(x)) = exp(x)
for all real numbers x?
Ian Collier
Ian.C...@prg.ox.ac.uk | i...@ecs.ox.ac.uk
Originated on Tuesday, 12th March 1991 at 11:39am GMT
Modified on Tuesday, 12th March 1991 at 11:40am GMT
Jim Roth
In article <1991Mar11.1...@agate.berkeley.edu>, gr...@garnet.berkeley.edu (Greg Kuperberg) writes...
I had a neat program for that game on the PDP-8 back in college, it took
its input from a light pen and recursively searched for forced wins
(and tried to block any forced wins the opponent may have had.)
One amazing heuristic that I used was that if a move which was postulated
in the course of trying to force a win came back from the recursion
empty handed, I put this move on a list of positions not to be tried
in the course of any other attempts at forcing a win. Rich Lary found
a counterexample to my idea but in nearly all cases it worked and
drastically cut the time to do the search for forced wins.
It was the first program I wrote that used recursion, It was fun
doing something that I didn't know that I was too ignorant to try doing
and I learned some neat stuff...
- Jim
Greg Kuperberg
}How trivial is your meaning of `trivial' - someone mentioned 3x3x3
}had a KNOWN solution (I think first-player-wins), but so does 3x3: tie.
}As with any of these games, either:
}
} 1. first player wins
} 2. first player loses
} 3. tie
Actually, for "these games", e.g. 15-in-a-row Tic Tac Toe on a
20x20x20x20x20x20x20x20x20x20 board, there is an easy argument that
shows that the first player can at least tie. For suppose that the
second player had a win. Then the first player could just play anywhere
and then use the second player's strategy. The initial `wasted' move
can only do three things:
1. It could make the first player win `prematurely'.
2. The second player might want to move there, which would be tough cookies.
3. The first player might want to move there, in which case she could
pretend that she did move there, and then make another random move
somewhere else.
This strategy-stealing argument is mentioned in *Winning Ways*, by
Berlekamp, Conway, and Guy. They say that many people have thought of
it, but apparently the first time it appeared in print was in
relatively recent papers by Hales and Jewett.
In some games of this sort, like Hex, there are no ties. The game of
Hex is played on a diamond-shaped playing field of hexagons, which I
will abbreviate with stars:
* * * * *
* * * * *
* * * * *
* * * * *
* * * * *
(Each star is meant to have six neighbors.) The players take turn
claiming spaces. The first player wins if she can connect left to
right, and the second player wins if she can connect top to bottom. By
the Hales-Jewett argument, this game is "solved", because the first
player has a winning strategy. But alas, no one knows such a
strategy. No one even knows an algorithm which can find such a
strategy on a moderate-sized board when implemented on a fast
computer.
----
Greg Kuperberg
gr...@math.berkeley.edu
David Feustel
years ago. He can be reached via phone at the Virgina Tech Math
department in Blacksburg, VA.
--
David Feustel, 1930 Curdes Ave, Fort Wayne, IN 46805, (219) 482-9631
EMAIL: netcom.com
Ian Collier
Rubik's magic: yes I did it. It's fairly trivial really :-)
Rubik's cube: I solve it layer by layer, that's the easiest for me
Rubik's revenge (4x4x4): Yes I can solve that in about 12 minutes. Find a
sequence of moves which permutes (say) three of the inner
edges (I can supply one of those if you want, I think), then
use it to pair up all pairs of inner edges, you're then left
with a 3x3x3 rubik's cube with a couple of minor complications
with `orbits'. That's not the best answer, but it's my answer :-)
In article <1...@uqcspe.cs.uq.oz.au>, war...@cs.uq.oz.au wrote:
>In <680...@uk.ac.ox.prg> i...@prg.ox.ac.uk (Ian Collier) writes:
>> In order to make a non-trivial game, the size of
>>the grid has to be 1 more than the number of dimensions (so 3*3, 4*4*4,
>>5*5*5*5 etc.) and no, I can't prove it; this is left as an exercise for the
>>reader :-)
>
> And just what does NON-TRIVIAL mean? Surely you realise that any game
>of this nature has a fixed outcome, determined by who goes first. How trivial
>is your meaning of `trivial' - someone mentioned 3x3x3 had a KNOWN solution
>(I think first-player-wins), but so does 3x3: tie.
Well I'm sorry for stating that without an explanation, you see someone told
me... :-) But clearly for 2x2 the third move always produces a win, and for
3x3x3 after one move by each player (x and o, say) it is possible for x to
force o's every move by making a line of 2 pieces, and on x's 4th move he
wins. Unfortunately a similar example for 4x4x4x4 escapes me, maybe someone
can settle the problem. As for 3x3 and 4x4x4, obviously 3x3 results in a draw
unless one player makes a mistake, but it's not quite as trivial as 2x2
(and it seems clear that nxn results in a draw for n>2) (forgive me for
waffling; I'm not a games theorist), and I personally don't know any winning
strategy for 4x4x4 (though someone did mention that this game has been solved).
>As with any of these
>games, either:
>
> 1. first player wins
> 2. first player loses
> 3. tie
>
> No other outcomes are possible, providing each player has maximal
>skill. In fact, in some games option 3 is impossible (definate winner).
What other outcomes can you imagine? :-) As for there being a fixed outcome,
well I suppose I can believe that, but I never really thought about it before.
So we come back to the original question... what did my friend mean when he told
me that a game of n dimensions and side n is trivial? I don't know.
>a triangle of 15 pieces (height = 5) is the gameboard, and each player may
>take any number of adjacent pieces in a straight line...
>
>eg.
> * * *
> * * * * * * *
> * * * * * * * *
> * * * * * * * * * * * *
> * * * * * * * * * * * * * * *
>
> The loser is the player who take the last piece.
Well there's a fairly well-known strategy in the case where players
may remove any peices in a *horizontal* line (usually the winner is the player
who takes the last piece(s), and in that case the winner is the first player,
but I think it can be amended so that the first player always forces the other
to take the last piece). This generalised version is, however, a mystery to me...
Ian Collier
Ian.C...@prg.ox.ac.uk | i...@ecs.ox.ac.uk
Originated on Friday, 15th March 1991 at 10:24am GMT
Warwick Allison
>A triangle of 15 pieces (height = 5) is the gameboard, and each player may
>take any number of adjacent pieces in a straight line...
>
>eg.
> * * *
> * * * * * * *
> * * * * * * * *
> * * * * * * * * * * * *
> * * * * * * * * * * * * * * *
>
> The loser is the player who take the last piece.
>
> PUZZLE: Who wins? First player or second player?
>
...but nobody managed to solve it.
Here is the answer...
The second player always wins. (and the first player always loses)
I found this one out using an exhaustive computer search (in 20 seconds).
Maybe this is a problem that is `best solved by a computer'.
*
* *,
Warwick.
Dana Richards
>>a triangle of 15 pieces (height = 5) is the gameboard, and each player may
>>take any number of adjacent pieces in a straight line...
>>
>>eg.
>> * * *
>> * * * * * * *
>> * * * * * * * *
>> * * * * * * * * * * * *
>> * * * * * * * * * * * * * * *
>>
>> The loser is the player who take the last piece.
>
>Well there's a fairly well-known strategy in the case where players
>may remove any peices in a *horizontal* line (usually the winner is the player
>who takes the last piece(s), and in that case the winner is the first player,
>but I think it can be amended so that the first player always forces the other
>to take the last piece). This generalised version is, however, a mystery to me...
restricting moves to a row is obviously just nim.
a rectangular version (with orthogonal moves) is known as nimbi
and is discussed in an early Gardner column (in his first book?).
in my 1976 MS thesis i claimed to be the first to study the triangular version
above and called it trimbi (though i probably found it discussed somewhere).
i showed that the first player wins for n (the length of a side) 1, 3, 4,
(using grundy functions) but i was apparently too lazy to solve n=5.
it did not have a nice analysis as i recall, but that was a long time ago ...
dana
Warwick Allison
>>> * * *
>>> * * * * * * *
>>> * * * * * * * *
>>> * * * * * * * * * * * *
>>> * * * * * * * * * * * * * * *
>>>
>>> The loser is the player who take the last piece.
>In my 1976 MS thesis i claimed to be the first to study the triangular version
>above and called it trimbi (though i probably found it discussed somewhere).
>i showed that the first player wins for n (the length of a side) 1, 3, 4,
>(using grundy functions) but i was apparently too lazy to solve n=5.
>it did not have a nice analysis as i recall, but that was a long time ago ...
In your game, The WINNER is the player who take the last piece, I
assume, since the n=1 case is trivial (first player takes only piece and wins).
Strangely, in the game I showed, n = 1, 3 and 5 are losing positions, while
n = 4 is a winning position, SO... if your thesis is right...
For a triangle of side four, the first player wins, regardless of
the winning condition. Interesting! (Though easily true)
By the way, the n = 5 case in my game is a losing position, so n = 6
is a winning position, since n = 6 can be made to n = 5 with a single move
(take an entire side away). So, for the puzzle:
*
* *
* * *
* * * *
* * * * *
* * * * * *, First player wins. quite a BIG result.