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 

GM = {〈B〉| B is a position in generalized go-moku, where player “X” has a winning strategy}.

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. Show that GM ∈ PSPACE.