6-uniform Maker-Breaker game is PSPACE-complete (Q6081384)

The paper deals with the problem of determining the winner of a Maker-Breaker game. In this kind of game, a set of subsets is given, which elements all belong to a finite universe set. At each turn, one player seizes one element among those that were not selected in previous steps. The Maker wins if he is able to select every element of at least one subset. The Breaker wins if he can select at least one element for each subset. \par The winner individuation problem was proved PSPACE-complete in a 1976 paper by Schaefer for games in which subsets are bound to have size not exceeding 11. In this paper the authors significantly improve the result by proving the PSPACE-completeness of the problem when the maximum subset size is limited to 6. Moreover, the authors also provide NL-hardness results for some simpler game cases.\par The paper basically consists of the results, proofs, it is opened by a very nice introduction where the problem is stated and some relevant literature is referred to and is closed by a brief section restating the problem resulting state of the art so that open cases are clearly pinpointed.\par Overall, a paper certainly worth reading.