A question for anyone versed in complexity or combinatorial game theory: I have a two-player game with a certain set of rules defining which moves are allowed and when. This ruleset is intentionally minimal, meaning that each player has a lot of options for most of their respective turns. If I add two additional restrictions on allowed moves such that the number of moves a given player has from a given position is never greater than the number of moves they would have without those restrictions, I can prove the game to be PSPACE-complete. Does this imply anything about the complexity of the game when those restrictions are removed?
Background: For my final project in a game theory course in college, I created a two-player combinatorial game, which I gave the provisional name "Negative". Negative is played on a square grid with black and white tokens; one player is Black and the other is White. Play alternates between moves, with a move being to remove a token of the current player's color from the board and then inverting the color of all neighboring tokens (the neighbors of a token are the four squares on the grid that are orthoginally adjacent). Play ends when the player to move is unable to remove a token of their color; the player to make the last move wins.
Here, L is Black and R is White.
If I add the additional conditions that any token with no neighboring tokens cannot be removed and that no token with more same-colored neighbors than opposite-colored neighbors may be removed, I can prove that this "Restricted Negative" is PSPACE-complete. The proof relies on reducing any starting position in the formula game with no negated variables into a Restricted Negative position, then showing that a player can only win the Restricted Negative position if they could win the formula game (under perfect play).
The Formula Game is a two-player game in which players take turns selecting variables from a set subject to a logical statement A. Play continues until no more variables can be selected. If, when all variables have been chosen, A is true when all variables selected by player one are set to true and all variables selected by player two are set to false, player one wins. The formula game with no negated variables is known to be PSPACE-complete.
It is possible to perform this reduction in polynomial time in the number of input variables, and a complete analysis of the game tree can be done in polynomial space, so Restricted Negative is PSPACE-complete.
I cannot extend this to the unrestricted case, because I can no longer force both players to cooperate. It is easy to construct examples of positions where a player will lose in Restricted Negative but win in Negative; for example, {BBWW}, where B is a black token and W is a white token, is a loss for the first player to move in Restricted Negative but a win for the first player to move in Negative. This means that neither player is obligated to follow the strategy they would use in Restricted Negative, since not doing so might be to their advantage.
My question is this: Is Negative necessarily more complex (or at least no less complex) than Restricted Negative, and is there a way to prove this based solely on the presence of having at least as many options from every position?
I can provide a link to the more detailed, if informal, analysis of the game, if necessary.
Author
Topic: Mathematics Help Thread (Read 228093 times)