Skip to content
This repository has been archived by the owner on Oct 26, 2023. It is now read-only.

Saying there are 9^3 possible games for tic-tac-toe is incorrect #1

Open
birgersp opened this issue Apr 26, 2017 · 1 comment
Open

Comments

@birgersp
Copy link

birgersp commented Apr 26, 2017

As stated here;

There are 9 choices for the 1st move, 8 for the 2nd move, 7 for the 3rd move, etc., giving us an upper bound of 9! = 987654321 = 362880. But this is an overestimate, because some games end in 5, 6, 7 or 8 moves. The true figure is actually 255168.
If we take symmetry into account, the number reduces substancially. For example, there are now only 3 choices for the first move and at most 5 choices for the second move. In fact, the total is reduced to 26830 distinct games, of which 172 end in 5 moves, 579 end in 6 moves, 5115 end in 7 moves, 7426 end in 8 moves, 8670 result in a win in 9 moves and 4868 result in a draw. There are a number of Web sites providing a full analysis. See for example http://www.se16.info/hgb/tictactoe.htm

@JKCooper2
Copy link
Owner

Thanks, I'll update a bit later

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants