Consider QBF, the Quantified Boolean Formula problem, as a combinatorial game ruleset. The problem is rephrased as determining the winner of the game where two opposing players take turns assigning values to Boolean variables. In this paper, three variations of games are applied to create seven new rulesets: whether each player is restricted to where they may play, which values they may set variables to, or whether conditions they are shooting for at the end of the game dier. The complexity for determining which player can win is analyzed for all games. Of the seven, two are trivially in P and the other five are PSPACE-complete. Two of these hard games are impartial, (the only known impartial formula rulesets incorporating unassigned variables), and two are hard for 2-CNF formulas.
展开▼
