Editing Game complexity (section)

==Example: tic-tac-toe (noughts and crosses)==
For [[tic-tac-toe]], a simple upper bound for the size of the state space is 3<sup>9</sup> = 19,683. (There are three states for each of the nine cells.) This count includes many illegal positions, such as a position with five crosses and no noughts, or a position in which both players have a row of three. A more careful count, removing these illegal positions, gives 5,478.<ref>{{Cite web|url=https://math.stackexchange.com/questions/485752/tictactoe-state-space-choose-calculation|title=combinatorics - TicTacToe State Space Choose Calculation|website=Mathematics Stack Exchange|access-date=2020-04-08}}</ref><ref>{{cite web|last=T|first=Brian|title=Btsan/generate_tictactoe|website=[[GitHub]] |date=2018-10-20|url=https://github.com/Btsan/generate_tictactoe|access-date=2020-04-08}}</ref> And when rotations and reflections of positions are considered identical, there are only 765 essentially different positions.

To bound the game tree, there are 9 possible initial moves, 8 possible responses, and so on, so that there are at most 9! or 362,880 total games. However, games may take less than 9 moves to resolve, and an exact enumeration gives 255,168 possible games. When rotations and reflections of positions are considered the same, there are only 26,830 possible games.

The computational complexity of tic-tac-toe depends on how it is [[generalized game|generalized]]. A natural generalization is to [[m,n,k-game|''m'',''n'',''k''-games]]: played on an ''m'' by ''n'' board with winner being the first player to get ''k'' in a row. This game can be solved in [[DSPACE]](''mn'') by searching the entire game tree. This places it in the important complexity class [[PSPACE]]; with more work, it can be shown to be [[PSPACE-complete]].<ref name="Reisch1980b">{{cite journal | author = Stefan Reisch | title = Gobang ist PSPACE-vollständig (Gobang is PSPACE-complete) | journal = Acta Informatica | volume = 13 | issue = 1 | pages = 59–66 | year = 1980 | doi=10.1007/bf00288536| s2cid = 21455572}}</ref>