Game complexity: Difference between revisions

Revision as of 12:18, 8 July 2004

Revision as of 17:18, 8 July 2004

Line 13:

==Example: [[tic-tac-toe]]==

A simple upper bound for the size of the state space is 3⁹ = 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 gives 5,478. When symmetricalrotations and reflections of positions are considered the same, there are only 765 essentially different positions.

A simple upper bound for the size of the game tree is 9! = 362,880. (There are nine positions for the first move, eight for the second, and so on.) This includes illegal games that continue after one side has won. A more careful count gives 255,168 possible games. When symmetricalrotations 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 [[mnk-games|''m'',''n'',''k''-games]]: played on an ''m'' by ''n'' board with winner being the first player to get ''k'' in a row. It is immediately clear that this game can be solved in [[DSPACE]](''mn'') by searching the entire game tree. This places it in the important complexity class [[PSPACE]]. With some more work it can be shown to be [[PSPACE-complete]].