Tic-tac-toe

Consider the game of noughts and crosses (or tic-tac-toe, if you like).

Two players take turns marking a grid with Xs and Os. The first to get three in a row - vertically, horizontally, or diagonally - wins.

For the first move, there are 9 nine places to choose from. Next, there is a choice of 8. This reduces to 7, 6, and so on until one person wins (or the grid is filled). 

You can easily calculate how many ways there are of populating the 3-by-3 grid with Xs, Os, and empty spaces. Each position has the possibility of being occupied by an X, an O, or a blank, so the total number is 3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 x 3, or 3 to the power of 9. 

That works out to be 19,683 permutations. They include every possible legal and illegal arrangement.

The above position could never arise in an actual game. For any particular arrangement to be able to occur, it must have as many (or 1 more) X's than O's (if the first player starts with X). Therefore, the set of arrangements that could occur in a game is a much smaller subset of the total set of 19,683 permutations. 

This sort of thing - game complexity - interests a certain type of person. It need not occupy us now, but for the purposes of future discussion please keep it in mind.