Content deleted Content added
The table for GO seemed too crowded and so I've decided that the extra information may be better to stay in the wiki page of "Go in mathematics". |
Citation bot (talk | contribs) Add: website. | Use this bot. Report bugs. | Suggested by Abductive | Category:Game theory | #UCB_Category 204/205 |
||
Line 41:
==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 cell and 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.
| |||