Car parking game strategy

See the original puzzle

The Car Parking Game isn't really a "puzzle" in the usual sense.  It's a game.  But it's one of those games which is simple enough that it is feasible to analyze who is winning at any given time.  Given any game-state, either the current player can force a win, or the other player can force a win.  I will denote these game-states as W and L respectively.

W and L states have a particular structure:

1. If the current player cannot make a move, then it is a W state, since the rules say that the current player wins.
2. If the game is in a W state, and the current player can make a move, then it is possible for the current player to make a move leading to an L state.
3. If the game is in an L state, then the current player can only make moves which lead to W states.

If you know which game-states are W and which are L, then the strategy is simple: always make moves leading to L states.  The implied puzzle is: which game-states are W, and which are L?

There are several ways to figure it out.  One is to do it by hand.  Or you can do it with a computer.  I did it both ways.  But I'm not going to show you that.

I also solved the problem using the third method: research!

The most difficult part of researching this kind of problem is finding the right keyword.  The keyword is "Kayles".  Kayles is a game involving a row of bowling pins.  Each player can either knock down a single bowling pin, or knock down two adjacent bowling pins (if there is no gap between them).  Kayles is equivalent to the Car Parking Game, because you can either park your car efficiently, taking up one spot, or inefficiently, parking across two spots.

There are two versions of Kayles.  There is "normal play", where if the current player has no possible move, then the current player loses.  And then there is "misère play", where if the current player has no possible moves, then the current player wins.  In Normal Kayles, you can use a simple strategy, similar to that of the Coins on a Table Game.  From a mathematical standpoint, normal play is also easier to completely analyze than misère play, because we can apply the Sprague-Grundy theorem.

The Car Parking Game is equivalent to Misère Kayles.  I was pleased to find that Misère Kayles has been completely solved!  Unfortunately, the solution is very complicated, and will not fit in the margins of this blog.  If you are able to decrypt the paper, that's quite an accomplishment, and I welcome you to use it to beat me at the Car Parking Game.