The Japanese game go-moku is played by two players, “X” and “O” on a 19 × 19 grid. Players take turns placing markers, and the first player to achieve five of her markers consecutively in a row, column, or diagonal is the winner. Consider this game generalized to an n × n board.

Let.$\mathit{G}\mathit{M}\mathbf{=}\mathbf{\left\{}\begin{array}{l}\mathbf{\left(}\mathbf{B}\mathbf{\right)}\mathbf{|}\mathbf{B}\mathbf{i}\mathbf{s}\mathbf{a}\mathbf{p}\mathbf{o}\mathbf{s}\mathbf{i}\mathbf{t}\mathbf{i}\mathbf{o}\mathbf{n}\mathbf{i}\mathbf{n}\mathbf{g}\mathbf{e}\mathbf{n}\mathbf{e}\mathbf{r}\mathbf{a}\mathbf{l}\mathbf{i}\mathbf{z}\mathbf{e}\mathbf{d}\mathbf{g}\mathbf{o}\mathbf{-}\mathbf{m}\mathbf{o}\mathbf{k}\mathbf{u}\mathbf{,}\\ \mathbf{w}\mathbf{h}\mathbf{e}\mathbf{r}\mathbf{e}\mathbf{p}\mathbf{l}\mathbf{a}\mathbf{y}\mathbf{e}\mathbf{r}\mathbf{“}\mathbf{X}\mathbf{”}\mathbf{h}\mathbf{a}\mathbf{s}\mathbf{a}\mathbf{w}\mathbf{i}\mathbf{n}\mathbf{n}\mathbf{i}\mathbf{n}\mathbf{g}\mathbf{s}\mathbf{t}\mathbf{r}\mathbf{a}\mathbf{t}\mathbf{e}\mathbf{g}\mathbf{y}\end{array}\mathbf{\right\}}$

By a position we mean a board with markers placed on it, such as may occur in the middle of a play of the game, together with an indication of which player moves next. Showthat .$\mathit{G}\mathit{M}\mathbf{\in }\mathit{P}\mathit{S}\mathit{P}\mathit{A}\mathit{C}\mathit{E}$

PSPACE is the collection of all decision problems that a Turing machine can answer using a polynomial space in computational complexity theory.

The algorithm is then shown to run in polynomial space. Assume that the position P denotes the player who will move next.

In go-moku, the following procedure determines if player "X" has a winning strategy; in other words, it determines GM. The algorithm is then shown to run in polynomial space. Assume that the position P denotes the player who will move next.

M = "On input (P), where P is a generalised go-moku position:

1. Accept if "X" is next to move and has a chance to win this turn.

2. Reject if "O" is next to move and has a chance to win this turn.

3. If "X" is next to move but cannot win this round, recursively call M on (P'), where P' is the updated position P with player "Xmarker "'s on position p and "O" is next to move, for each free grid position p.

4. Accept if one or more of these calls accepts. If none of these options are available, then reject.

5.If "O" is next to move but cannot win this turn, recursively call M on (P'), where P' is the updated position P with player "Omarker "'s on position p and "X" is next to move, for each free grid position p.

6. Accept if all of these calls accept. "Reject if one or more of these calls rejects."

The recursion stack is the only space requirement of the algorithm.

There are at most ${\mathit{n}}^{\mathbf{2}}$ levels of recursion, and each level adds a single position to the stack utilising at most$\mathit{O}\mathbf{\left(}\mathit{n}\mathbf{\right)}$ space.

As a result, the method runs in $\mathit{O}\mathbf{\left(}{\mathit{n}}^{\mathbf{3}}\mathbf{\right)}$space.