Notes on Tic-Tac-Toe (Noughts and Crosses)

Up to

Home

Maths

Site Map

Text version

Notes on Tic-Tac-Toe (Noughts and Crosses)	-- Fred Curtis
[Normal 3 x 3 Tic-Tac-Toe] [2D Configuration counts] [3D 3 x 3 x 3 Tic-Tac-Toe] [Symmetries] [Source Code] [Chronology] [References]

Normal 3 x 3 Tic-Tac-Toe

I'd heard that the first player (say X) in a normal 3x3 tic-tac-toe game could "force a draw", which I took to mean "can't always force X-wins, but can force X-wins or a draw", since the usual goal for each player is to win.

So, the questions arose:

Can X force a draw?
Can O force a draw?
Can O force a X-wins?
Can X force a O-wins?

To answer these questions, I wrote a program (ttt-2d-forced.pl) to analyse force moves in tic-tac-toe. The answer, which surprised me, was that either player can force any one of the outcomes:

X-wins or Draw
O-wins or Draw
X-wins or O-wins

So, for example, if one player attempts to force a draw, the other player can force someone to win. If player X attempts to lose, the other player can thwart that goal by forcing X-wins or Draw.

2D Configuration counts

Configurations in 2D 3x3 Tic-Tac-Toe ignoring symmetries
Depth	No. of Configurations
Depth	Total	Non-Terminal	Terminal
0	1	(empty board) 1	0
1	3	3	0
2	12	12	0
3	38	38	0
4	108	108	0
5	174	153	21
6	204	183	21
7	153	95	58
8	57	34	23
9	15	(ties) 3	12
Total	765	630	135

Configurations in 2D 4x4 Tic-Tac-Toe ignoring symmetries
Depth	No. of Configurations
Depth	Total	Non-Terminal	Terminal
0	1	(empty board) 1	0
1	3	3	0
2	33	33	0
3	219	219	0
4	1413	1413	0
5	5514	5514	0
6	20122	20122	0
7	50215	49935	280
8	112379	111737	642
9	179510	174568	4942
10	245690	238920	6770
11	245690	225404	20286
12	193318	177276	16042
13	110452	89454	20998
14	41870	33900	7970
15	10489	6715	3774
16	1059	(ties) 688	371
Total	1217976	1135901	82075

Configurations in 2D 5x5 Tic-Tac-Toe ignoring symmetries
Depth	No. of Configurations			1.5GHz Pentium4 RH Linux 7.2
Depth	Total	Non-Terminal	Terminal	Run Time	CPU Time	Storage used
1	6	6	0
2	85	85	0
3	904	904	0
4	9664	9664	0
5	66859	66859	0
6	443850	443850	0
7	2105695	2105695	0
8	9469965	9469965	0	6m	6m	0.1Gb
9	32188170	32180742	7428	31m	30m	0.4Gb
10	102962268	102938806	23462	2h01	1h50m	1.2Gb
11	257389392	257040090	349302	5h56m	5h24m	3.0Gb
12	599872560	599058840	813720	14h50m	13h25m	7.3Gb
13	?	?	?	?	?	?

3D 3 x 3 x 3 Tic-Tac-Toe

This game is can be trivially won by the first player by playing a piece in the central space. I'd heard that a draw was impossible because there are too many winnable lines (49) for the first player to place their 14 pieces without winning. In fact, the figures computed below indicate that the game must terminate after 26 pieces are played, i.e. after the second player's last piece is played.

Configurations in 3D 3x3x3 Tic-Tac-Toe ignoring symmetries
Depth	No. of Configurations				1.5GHz Pentium4 RH Linux 7.2
Depth	Estimated	Actual Total	Non-Terminal	Terminal	Run Time	CPU Time	Storage used
0	0	1	(empty board) 1	0
1	1	4	4	0
2	14	31	31	0
3	183	254	254	0
4	2194	2512	2512	0
5	16819	17834	17459	375
6	123338	124162	121897	2265
7	647522	644288	600488	43800
8	3237609	3038859	2833234	205625	4m	4m
9	12302916	11517172	9632913	1884259	15m	15m	0.1Gb
10	44290496	37147332	31049722	6097610	1h01m	57m	0.5Gb
11	125489739	104801129	72876736	31924393	3h15m	3h03m	1.2Gb
12	334639305	231884196	160769332	71114864	7h24m	6h53m	2.3Gb
13	717084225	486231284	257101228	229130056	15h22m	14h19m	4.0Gb
14	1434168450	728803783	382334736	346469047	1d00h30m	23h13m	7.0Gb
15	2330523731	1103946447	405190002	698756445	2d08h35m	2d03h38m	16.4Gb
16	3495785597	1090187836	393304705	696883131	1d18h58m	1d17h22m	11.7Gb
17	4272626841	1128648719	263805390	864843329	1d14h51m	1d12h14m	12.1Gb
18	4747363156	700867318	158449550	542417768	16h49m	15h31m	8.0Gb
19	4272626841	457435053	62552397	394882656	9h29m	9h39m	3.5Gb
20	3418101473	165743273	21347314	144395959	3h01m	2h53m	1.6Gb
21	2175155483	60903253	4409874	56493379	51m	49m	0.4Gb
22	1186448445	11368950	741017	10627933	8m	8m	0.1Gb
23	494353519	1976917	64592	1912325	1m	1m
24	164784506	150672	3881	146791
25	38027194	8588	64	384
26	5850338	115	0	115
27	417881	0	0	0

Note on estimates - the number ways of arranging p₁ pieces of player 1 and p₂ pieces of player 2 in a board with n slots is: (number of ways of placing p₁ pieces in n slots) * (number of ways of placing p₂ pieces in remaining slots) = [n choose p₁]*[(n-p₁) choose p₂) = [n!/(p₁!*(n-p₁)!)]*[(n-p₁)!/(p₂!*(n-p₁-p₂)!)] = n!/(p₁!*p₂!*(n-p₁-p₂)!). If we assume that almost none of these configurations has any self-symmetry (see Symmetries below), then we can divide by a factor of d!*2^d where d is the number of dimensions. For a 3x3x3 board, the estimate for a given p₁ and p₂ is: 27!/(48*p₁!*p₂!*(n-p₁-p₂)!).

Symmetries

When using computer programs to investigate tic-tac-toe games, as with many other puzzles, it is convenient to group together configurations which are essentially the same. For example, in the 2D 3x3 game, the first player might place a piece on an edge, and the second player might place a piece in a corner next to the first player's piece. This can be done in 8 ways, all of which can be treated the same (by appropriate rotation/reflection of the board) in terms of further possible moves and outcomes.

A d-dimensional cube has d!*2^d distance-preserving symmetries. Imagine one corner of the cube placed at the origin in d-space, with d axes radiating from the origin. Now imagine the origin translated to one of the 2^d corners. The d axes radiating from the new corner can be assigned in d! ways to the edges radiating from the new corner.

Number of distance-preserving symmetries of a d-dimensional cube
d	Number of symmetries
2	2!2² = 24 = 8
3	3!2³ = 68 = 48
4	4!2⁴ = 2416 = 384

Source Code

ttt-2d-forced.pl - Code for analysis of forced moves in normal 2D tic-tac-toe game.
ttt.cc - Code for counting terminal/nonterminal games of tic-tac-toe played in a d-dimensional cube.

Chronology

2002-08-13 Eric Dew posts a speculation to UseNet, piquing my interest
2002-09-07 Finished code for analysis of forced moves in normal tic-tac-toe game. Started this web page
2002-09-17 Wrote up results for normal 2D 3x3 game
2002-09-19 Started on configuration count for 3D 3x3x3 game
2002-10-02 Completed non-terminal configuration count for 3D 3x3x3 game

References

UseNet article which motivated this page
The non-recursive code for producing successive permutations in ttt.cc was based on permutation code by Phillip Paul Fuchs

	This page last changed: 20 Jul 2003
[Validate HTML]

Donate free
food & land

Feedback by email
or Web form

d	Number of symmetries
2	2!2² = 24 = 8
3	3!2³ = 68 = 48
4	4!2⁴ = 2416 = 384