I spend a bunch of time perusing questions posed to the cstheory stackexchange page. Lately, I saw this question about a variant to the puzzle PushPush. The idea is that you have a grid, with a boundary and some obstacles. There is a square on the grid that is the goal, and a disc that is trying to reach the goal. Each turn, the player moves the disc in one of the cardinal directions until the disc hits the boundary or an obstacle, then it stops. The question is whether the player can move the disc to the goal.
I would expect the questioner to have trouble finding information about this if they're looking through combinatorial game theory papers, as it is a one-player game.
Perhaps there are some nice ways to add a second player and make this combinatorial. Here are a few options off the top of my head:
* Impartial version: take turns making moves, whichever player reaches the goal on their turn wins.
* Balanced Partisan: there are two goals, one belonging to each player. If the disc stops in a goal, the corresponding player wins, regardless of who moved it.
* Different Roles: One player is trying to reach the goal while the other player moves the disc and tries to prevent the player from reaching the goal.
The interesting part about this is that the puzzle version is in P, but some of these two-player variants might have a more difficult computational complexity! (Or maybe you can prove me wrong there!)
A Domino-Covering Problem
5 weeks ago