Game combinations of tic-tac-toe [closed]

3

$begingroup$

How many combinations are possible in the game tic-tac-toe (Noughts and crosses)?

So for example a game which looked like: (with positions 1-9)

A1   --   B1



A2   --   B2



A3   --   --

[1][3][4][6][7] would be one combination

combinatorics combinatorial-game-theory tic-tac-toe

share|cite|improve this question

edited Jul 26 '16 at 22:03

Rodrigo de Azevedo

12.9k41856

asked Jan 2 '13 at 9:50

DanieldDanield

118115

$endgroup$

closed as off-topic by user21820, A. Pongrácz, Gibbs, mrtaurho, Eevee Trainer Jan 7 at 2:19

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – user21820, A. Pongrácz, Gibbs, mrtaurho, Eevee Trainer

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  4
  

  
  
  
  
  
  

  
  $begingroup$
  se16.info/hgb/tictactoe.htm
  $endgroup$
  – Daryl
  Jan 2 '13 at 10:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Daryl, if you feel up to it, you should repackage that as an answer citing that website so this question can have an answer.
  $endgroup$
  – Mark S.
  Nov 22 '13 at 3:42
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @MarkS. Sure thing.
  $endgroup$
  – Daryl
  Nov 22 '13 at 5:14
  

  
  
  
  

add a comment | 

3

$begingroup$

How many combinations are possible in the game tic-tac-toe (Noughts and crosses)?

So for example a game which looked like: (with positions 1-9)

A1   --   B1



A2   --   B2



A3   --   --

[1][3][4][6][7] would be one combination

combinatorics combinatorial-game-theory tic-tac-toe

share|cite|improve this question

edited Jul 26 '16 at 22:03

Rodrigo de Azevedo

12.9k41856

asked Jan 2 '13 at 9:50

DanieldDanield

118115

$endgroup$

closed as off-topic by user21820, A. Pongrácz, Gibbs, mrtaurho, Eevee Trainer Jan 7 at 2:19

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – user21820, A. Pongrácz, Gibbs, mrtaurho, Eevee Trainer

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  4
  

  
  
  
  
  
  

  
  $begingroup$
  se16.info/hgb/tictactoe.htm
  $endgroup$
  – Daryl
  Jan 2 '13 at 10:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Daryl, if you feel up to it, you should repackage that as an answer citing that website so this question can have an answer.
  $endgroup$
  – Mark S.
  Nov 22 '13 at 3:42
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @MarkS. Sure thing.
  $endgroup$
  – Daryl
  Nov 22 '13 at 5:14
  

  
  
  
  

add a comment | 

3

3

3

4

$begingroup$

How many combinations are possible in the game tic-tac-toe (Noughts and crosses)?

So for example a game which looked like: (with positions 1-9)

A1   --   B1



A2   --   B2



A3   --   --

[1][3][4][6][7] would be one combination

combinatorics combinatorial-game-theory tic-tac-toe

share|cite|improve this question

edited Jul 26 '16 at 22:03

Rodrigo de Azevedo

12.9k41856

asked Jan 2 '13 at 9:50

DanieldDanield

118115

$endgroup$

How many combinations are possible in the game tic-tac-toe (Noughts and crosses)?

So for example a game which looked like: (with positions 1-9)

A1   --   B1



A2   --   B2



A3   --   --

[1][3][4][6][7] would be one combination

combinatorics combinatorial-game-theory tic-tac-toe

combinatorics combinatorial-game-theory tic-tac-toe

share|cite|improve this question

edited Jul 26 '16 at 22:03

Rodrigo de Azevedo

12.9k41856

asked Jan 2 '13 at 9:50

DanieldDanield

118115

share|cite|improve this question

edited Jul 26 '16 at 22:03

Rodrigo de Azevedo

12.9k41856

asked Jan 2 '13 at 9:50

DanieldDanield

118115

share|cite|improve this question

share|cite|improve this question

edited Jul 26 '16 at 22:03

Rodrigo de Azevedo

12.9k41856

edited Jul 26 '16 at 22:03

Rodrigo de Azevedo

12.9k41856

edited Jul 26 '16 at 22:03

Rodrigo de Azevedo

12.9k41856

12.9k41856

asked Jan 2 '13 at 9:50

DanieldDanield

118115

asked Jan 2 '13 at 9:50

DanieldDanield

118115

asked Jan 2 '13 at 9:50

DanieldDanield

118115

118115

closed as off-topic by user21820, A. Pongrácz, Gibbs, mrtaurho, Eevee Trainer Jan 7 at 2:19

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – user21820, A. Pongrácz, Gibbs, mrtaurho, Eevee Trainer

If this question can be reworded to fit the rules in the help center, please edit the question.

closed as off-topic by user21820, A. Pongrácz, Gibbs, mrtaurho, Eevee Trainer Jan 7 at 2:19

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – user21820, A. Pongrácz, Gibbs, mrtaurho, Eevee Trainer

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  4
  

  
  
  
  
  
  

  
  $begingroup$
  se16.info/hgb/tictactoe.htm
  $endgroup$
  – Daryl
  Jan 2 '13 at 10:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Daryl, if you feel up to it, you should repackage that as an answer citing that website so this question can have an answer.
  $endgroup$
  – Mark S.
  Nov 22 '13 at 3:42
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @MarkS. Sure thing.
  $endgroup$
  – Daryl
  Nov 22 '13 at 5:14
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  4
  

  
  
  
  
  
  

  
  $begingroup$
  se16.info/hgb/tictactoe.htm
  $endgroup$
  – Daryl
  Jan 2 '13 at 10:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Daryl, if you feel up to it, you should repackage that as an answer citing that website so this question can have an answer.
  $endgroup$
  – Mark S.
  Nov 22 '13 at 3:42
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @MarkS. Sure thing.
  $endgroup$
  – Daryl
  Nov 22 '13 at 5:14
  

  
  
  
  

4

4

$begingroup$
se16.info/hgb/tictactoe.htm
$endgroup$
– Daryl
Jan 2 '13 at 10:00

$begingroup$
se16.info/hgb/tictactoe.htm
$endgroup$
– Daryl
Jan 2 '13 at 10:00

$begingroup$
@Daryl, if you feel up to it, you should repackage that as an answer citing that website so this question can have an answer.
$endgroup$
– Mark S.
Nov 22 '13 at 3:42

$begingroup$
@Daryl, if you feel up to it, you should repackage that as an answer citing that website so this question can have an answer.
$endgroup$
– Mark S.
Nov 22 '13 at 3:42

$begingroup$
@MarkS. Sure thing.
$endgroup$
– Daryl
Nov 22 '13 at 5:14

$begingroup$
@MarkS. Sure thing.
$endgroup$
– Daryl
Nov 22 '13 at 5:14

add a comment | 

2 Answers
2

active

oldest

votes

6

$begingroup$

This information is taken from this website.

A naive estimate would be $9!=362,880$, since there are $9$ possible first moves, $8$ for the second move, etc. This does not take into account games which finish in less than $9$ moves.

• Ending on the $5^text{th}$ move: $1,440$ possibilities


• Ending on the $6^text{th}$ move: $5,328$ possibilities


• Ending on the $7^text{th}$ move: $47,952$ possibilities


• Ending on the $8^text{th}$ move: $72,576$ possibilities


• Ending on the $9^text{th}$ move: $127,872$ possibilities

This gives a total of $255168$ possible games. This calculation doesn't take into account symmetry in the game.

share|cite|improve this answer

answered Nov 22 '13 at 5:21

DarylDaryl

4,74231835

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Accounting for symmetry, this can quickly be reduced by a factor of 6, as there are only 12 possible two move openings, not 8*9=72.
  $endgroup$
  – Pieter Geerkens
  Nov 22 '13 at 5:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  As that linked page makes clear at the bottom, symmetry allows a reduction by a factor of $8$ (i.e. rotations and reflections of a square) to $31896$, but arguably by a greater amount to $26830$.
  $endgroup$
  – Henry
  Jan 2 '15 at 11:18
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I am assuming I am asking a naive question here, but why isn't the answer $9! - sumlimits_{i=5}^{8} m_i = 235584$, where, $m_i$ are the number of games ending on $i$ moves (the numbers above). (From the overestimation of the games that take all 9 moves we subtract the ones that require less)
  $endgroup$
  – kyriakosSt
  Dec 3 '17 at 23:47
  

  
  
  
  

add a comment | 

0

$begingroup$

I will say that the board combinations are 3^9, which is 19683 possibilities, and 2032 winning positions. The answer of 9! is related to how many ways we have to fell all the positions, rather than the possible combinations.

I have answered this question already in another post, please see the next link: https://stackoverflow.com/a/54035004/5117217

Cheers!

share|cite|improve this answer

answered Jan 4 at 20:07

user5117217user5117217

1

$endgroup$

add a comment | 

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

active

oldest

votes

active

oldest

votes

6

$begingroup$

This information is taken from this website.

A naive estimate would be $9!=362,880$, since there are $9$ possible first moves, $8$ for the second move, etc. This does not take into account games which finish in less than $9$ moves.

• Ending on the $5^text{th}$ move: $1,440$ possibilities


• Ending on the $6^text{th}$ move: $5,328$ possibilities


• Ending on the $7^text{th}$ move: $47,952$ possibilities


• Ending on the $8^text{th}$ move: $72,576$ possibilities


• Ending on the $9^text{th}$ move: $127,872$ possibilities

This gives a total of $255168$ possible games. This calculation doesn't take into account symmetry in the game.

share|cite|improve this answer

answered Nov 22 '13 at 5:21

DarylDaryl

4,74231835

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Accounting for symmetry, this can quickly be reduced by a factor of 6, as there are only 12 possible two move openings, not 8*9=72.
  $endgroup$
  – Pieter Geerkens
  Nov 22 '13 at 5:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  As that linked page makes clear at the bottom, symmetry allows a reduction by a factor of $8$ (i.e. rotations and reflections of a square) to $31896$, but arguably by a greater amount to $26830$.
  $endgroup$
  – Henry
  Jan 2 '15 at 11:18
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I am assuming I am asking a naive question here, but why isn't the answer $9! - sumlimits_{i=5}^{8} m_i = 235584$, where, $m_i$ are the number of games ending on $i$ moves (the numbers above). (From the overestimation of the games that take all 9 moves we subtract the ones that require less)
  $endgroup$
  – kyriakosSt
  Dec 3 '17 at 23:47
  

  
  
  
  

add a comment | 

6

$begingroup$

This information is taken from this website.

A naive estimate would be $9!=362,880$, since there are $9$ possible first moves, $8$ for the second move, etc. This does not take into account games which finish in less than $9$ moves.

• Ending on the $5^text{th}$ move: $1,440$ possibilities


• Ending on the $6^text{th}$ move: $5,328$ possibilities


• Ending on the $7^text{th}$ move: $47,952$ possibilities


• Ending on the $8^text{th}$ move: $72,576$ possibilities


• Ending on the $9^text{th}$ move: $127,872$ possibilities

This gives a total of $255168$ possible games. This calculation doesn't take into account symmetry in the game.

share|cite|improve this answer

answered Nov 22 '13 at 5:21

DarylDaryl

4,74231835

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Accounting for symmetry, this can quickly be reduced by a factor of 6, as there are only 12 possible two move openings, not 8*9=72.
  $endgroup$
  – Pieter Geerkens
  Nov 22 '13 at 5:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  As that linked page makes clear at the bottom, symmetry allows a reduction by a factor of $8$ (i.e. rotations and reflections of a square) to $31896$, but arguably by a greater amount to $26830$.
  $endgroup$
  – Henry
  Jan 2 '15 at 11:18
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I am assuming I am asking a naive question here, but why isn't the answer $9! - sumlimits_{i=5}^{8} m_i = 235584$, where, $m_i$ are the number of games ending on $i$ moves (the numbers above). (From the overestimation of the games that take all 9 moves we subtract the ones that require less)
  $endgroup$
  – kyriakosSt
  Dec 3 '17 at 23:47
  

  
  
  
  

add a comment | 

6

6

6

$begingroup$

This information is taken from this website.

A naive estimate would be $9!=362,880$, since there are $9$ possible first moves, $8$ for the second move, etc. This does not take into account games which finish in less than $9$ moves.

• Ending on the $5^text{th}$ move: $1,440$ possibilities


• Ending on the $6^text{th}$ move: $5,328$ possibilities


• Ending on the $7^text{th}$ move: $47,952$ possibilities


• Ending on the $8^text{th}$ move: $72,576$ possibilities


• Ending on the $9^text{th}$ move: $127,872$ possibilities

This gives a total of $255168$ possible games. This calculation doesn't take into account symmetry in the game.

share|cite|improve this answer

answered Nov 22 '13 at 5:21

DarylDaryl

4,74231835

$endgroup$

This information is taken from this website.

A naive estimate would be $9!=362,880$, since there are $9$ possible first moves, $8$ for the second move, etc. This does not take into account games which finish in less than $9$ moves.

• Ending on the $5^text{th}$ move: $1,440$ possibilities


• Ending on the $6^text{th}$ move: $5,328$ possibilities


• Ending on the $7^text{th}$ move: $47,952$ possibilities


• Ending on the $8^text{th}$ move: $72,576$ possibilities


• Ending on the $9^text{th}$ move: $127,872$ possibilities

This gives a total of $255168$ possible games. This calculation doesn't take into account symmetry in the game.

share|cite|improve this answer

answered Nov 22 '13 at 5:21

DarylDaryl

4,74231835

share|cite|improve this answer

share|cite|improve this answer

answered Nov 22 '13 at 5:21

DarylDaryl

4,74231835

answered Nov 22 '13 at 5:21

DarylDaryl

4,74231835

answered Nov 22 '13 at 5:21

DarylDaryl

4,74231835

4,74231835

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Accounting for symmetry, this can quickly be reduced by a factor of 6, as there are only 12 possible two move openings, not 8*9=72.
  $endgroup$
  – Pieter Geerkens
  Nov 22 '13 at 5:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  As that linked page makes clear at the bottom, symmetry allows a reduction by a factor of $8$ (i.e. rotations and reflections of a square) to $31896$, but arguably by a greater amount to $26830$.
  $endgroup$
  – Henry
  Jan 2 '15 at 11:18
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I am assuming I am asking a naive question here, but why isn't the answer $9! - sumlimits_{i=5}^{8} m_i = 235584$, where, $m_i$ are the number of games ending on $i$ moves (the numbers above). (From the overestimation of the games that take all 9 moves we subtract the ones that require less)
  $endgroup$
  – kyriakosSt
  Dec 3 '17 at 23:47
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Accounting for symmetry, this can quickly be reduced by a factor of 6, as there are only 12 possible two move openings, not 8*9=72.
  $endgroup$
  – Pieter Geerkens
  Nov 22 '13 at 5:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  As that linked page makes clear at the bottom, symmetry allows a reduction by a factor of $8$ (i.e. rotations and reflections of a square) to $31896$, but arguably by a greater amount to $26830$.
  $endgroup$
  – Henry
  Jan 2 '15 at 11:18
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I am assuming I am asking a naive question here, but why isn't the answer $9! - sumlimits_{i=5}^{8} m_i = 235584$, where, $m_i$ are the number of games ending on $i$ moves (the numbers above). (From the overestimation of the games that take all 9 moves we subtract the ones that require less)
  $endgroup$
  – kyriakosSt
  Dec 3 '17 at 23:47
  

  
  
  
  

$begingroup$
Accounting for symmetry, this can quickly be reduced by a factor of 6, as there are only 12 possible two move openings, not 8*9=72.
$endgroup$
– Pieter Geerkens
Nov 22 '13 at 5:32

$begingroup$
Accounting for symmetry, this can quickly be reduced by a factor of 6, as there are only 12 possible two move openings, not 8*9=72.
$endgroup$
– Pieter Geerkens
Nov 22 '13 at 5:32

$begingroup$
As that linked page makes clear at the bottom, symmetry allows a reduction by a factor of $8$ (i.e. rotations and reflections of a square) to $31896$, but arguably by a greater amount to $26830$.
$endgroup$
– Henry
Jan 2 '15 at 11:18

$begingroup$
As that linked page makes clear at the bottom, symmetry allows a reduction by a factor of $8$ (i.e. rotations and reflections of a square) to $31896$, but arguably by a greater amount to $26830$.
$endgroup$
– Henry
Jan 2 '15 at 11:18

$begingroup$
I am assuming I am asking a naive question here, but why isn't the answer $9! - sumlimits_{i=5}^{8} m_i = 235584$, where, $m_i$ are the number of games ending on $i$ moves (the numbers above). (From the overestimation of the games that take all 9 moves we subtract the ones that require less)
$endgroup$
– kyriakosSt
Dec 3 '17 at 23:47

$begingroup$
I am assuming I am asking a naive question here, but why isn't the answer $9! - sumlimits_{i=5}^{8} m_i = 235584$, where, $m_i$ are the number of games ending on $i$ moves (the numbers above). (From the overestimation of the games that take all 9 moves we subtract the ones that require less)
$endgroup$
– kyriakosSt
Dec 3 '17 at 23:47

add a comment | 

0

$begingroup$

I will say that the board combinations are 3^9, which is 19683 possibilities, and 2032 winning positions. The answer of 9! is related to how many ways we have to fell all the positions, rather than the possible combinations.

I have answered this question already in another post, please see the next link: https://stackoverflow.com/a/54035004/5117217

Cheers!

share|cite|improve this answer

answered Jan 4 at 20:07

user5117217user5117217

1

$endgroup$

add a comment | 

0

$begingroup$

I will say that the board combinations are 3^9, which is 19683 possibilities, and 2032 winning positions. The answer of 9! is related to how many ways we have to fell all the positions, rather than the possible combinations.

I have answered this question already in another post, please see the next link: https://stackoverflow.com/a/54035004/5117217

Cheers!

share|cite|improve this answer

answered Jan 4 at 20:07

user5117217user5117217

1

$endgroup$

add a comment | 

0

0

0

$begingroup$

I will say that the board combinations are 3^9, which is 19683 possibilities, and 2032 winning positions. The answer of 9! is related to how many ways we have to fell all the positions, rather than the possible combinations.

I have answered this question already in another post, please see the next link: https://stackoverflow.com/a/54035004/5117217

Cheers!

share|cite|improve this answer

answered Jan 4 at 20:07

user5117217user5117217

1

$endgroup$

I will say that the board combinations are 3^9, which is 19683 possibilities, and 2032 winning positions. The answer of 9! is related to how many ways we have to fell all the positions, rather than the possible combinations.

I have answered this question already in another post, please see the next link: https://stackoverflow.com/a/54035004/5117217

Cheers!

share|cite|improve this answer

answered Jan 4 at 20:07

user5117217user5117217

1

share|cite|improve this answer

share|cite|improve this answer

answered Jan 4 at 20:07

user5117217user5117217

1

answered Jan 4 at 20:07

user5117217user5117217

1

answered Jan 4 at 20:07

user5117217user5117217

1

1

add a comment | 

add a comment | 

This page is only for reference, If you need detailed information, please check here