21
$\begingroup$

This game has two players, Spoiler and Solver. We start with a solved 3x3x3 rubik's cube (to make the problem easier).

Solver and Spoiler take turns making 90 degree twists (starting with Solver). The cube is forbidden from ever repeating a position (besides the start position). This guarantees the game is finite.

If at any point (besides the beginning), the rubik's cube is in a solved state, Solver wins. If the game ends before that (because a position is entered with no valid moves), Spoiler wins.

An example game would be F,F;F,F (using basic rubik's cube notation). Solver wins this game. If a game goes through each position that is one move away from the solved state, and afterwards goes to some unsolved state, Spoiler will win (since it is now impossible to get to the solved state).

So, which player has the winning strategy?

EDIT: It may be simpler to consider the same problem with the 15 puzzle first.

Improve this question
$\endgroup$
6
  • 6
    $\begingroup$ Now I'm wondering if this sort of game has been studied before for other groups with specified generators; is there an existing name for this sort of game? $\endgroup$
    – Harry Altman
    Commented Apr 21, 2018 at 19:53
  • 1
    $\begingroup$ @HarryAltman no idea. If you find one, let me know. A related game is the Sudoku solver spoiler game. $\endgroup$
    – Christopher King
    Commented Apr 21, 2018 at 19:54
  • 6
    $\begingroup$ You're talking about a self-avoiding walk on a Cayley graph, where each player takes turns deciding which edge to traverse from the current vertex. I like @HarryAltman's idea of looking at simpler groups first. $\endgroup$
    – Jim Conant
    Commented Apr 21, 2018 at 20:31
  • 2
    $\begingroup$ Phrased in the Cayley graph language, it maybe makes more sense not to have two different kinds of players, but just to have both players trying to keep making moves until one is unable to visit a new vertex (and thereby loses). $\endgroup$
    – Sam Hopkins
    Commented Apr 21, 2018 at 20:50
  • 1
    $\begingroup$ @SamHopkins: That's also an interesting game to play on a finite directed graph, but I think it's a different game. $\endgroup$
    – Lee Mosher
    Commented Apr 21, 2018 at 21:56

1 Answer 1

Reset to default
5
$\begingroup$

Not an answer, but just a thought or two about the problem. With the quarter turn metric the Cayley graph is a 12-regular graph. Every element in the Rubik's group can be assigned a "rank", the value of the smallest number of moves to get back to the origin. By making a parity argument, we can see that a quarter turn (move on the Cayley graph) always changes this number by 1 or -1. So we could arrange the Cayley graph like a Hasse diagram.

I think understanding the size of the various levels (not sure if that's the term, but the collection of elements having the same minimum solve number) might be key to understanding any strategy for either player. For example on the first turn the state of the cube is at level 1. The Solver can't undo this move and will be forced to move to level 2. The Spoiler clearly wouldn't move the state back to level 1, so moves up to 3. I think a naive strategy for the Spoiler might be to try to move the puzzle up in level all the time. There are more level 3 states than level 2 states, so (being generous with the symmetry and structure of the Cayley graph) I suspect he can move to enough level 3 states any time the puzzle return to a level 2 state and exhaust the level 2 possibilities for the Solver, thus shutting the Solver off from victory.

This is just my initial thoughts. I will update if I think of something more, or if the structure of the Cayley graph turns out to be structured in such a way as to stop this strategy. Let me know if anyone manages to build off this idea.

EDIT: According to https://www.cube20.org/qtm/, the largest sized level is at 21. Being odd, these are states the Spoiler moves the puzzle to. I think that if the Spoiler tries to keep the puzzle at 21, then he might be able to exhaust the 20 level or the 22 level, before the level 21 states are exhausted.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ I recommend not using gender-specific pronouns when referring to hypothetical players such as Spoiler. Gender bias against women in mathematics is already serious enough that we should be conscious of every possible chance not to exacerbate those biases. $\endgroup$
    – Greg Martin
    Commented Jul 6, 2018 at 7:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .