The game of Lielow
Via Hacker News for some reason: the game of Lielow, recently invented by Michael Amundsen and Alek Erickson. Lielow is played with checkers on an 8×8 board; the only additional thing you need is something to mark each player’s king (e.g. a couple of coins).
Each player starts with eight pieces, or “stacks,” located on the second rank (where the pawns start in chess). Each stack starts with height 1.
Players alternate turns and cannot pass. On your turn, move one of your stacks, queenwise, exactly the same number of spaces as its current height. If your stack lands on an empty space, add 1 to its height. If it lands on an enemy stack, remove the captured stack from the game and reset your own stack’s height to 1. If it lands outside the 8×8 board entirely, remove it from the game. Landing on a friendly stack is not allowed.
If, at the end of your turn, you have a unique tallest stack, that stack becomes your “king.” Place your king-marker (“crown”) on it to indicate this. (If you have no unique tallest stack, your crown stays wherever it was.)
If your king is captured, or moves off the board, then you lose.
So far, this seems like one of those games that a computer can play much better than a human. It’s a combinatorial game — no hidden information, no randomness — so the computer can search the game tree; and there are never more than 64 possible moves from any given state, so the tree search isn’t even terribly intractable.
The computer opponent reliably beats me, although I have managed to beat it twice so far (among many losses). Playing versus the computer is probably a good way to learn, but also a good way to get discouraged because there’s no difficulty setting: the computer will simply cream you mercilessly over and over until you start to learn some defensive tactics.
For example, if you can manage to set up pairs of pieces mutually defending each other, that seems to be a good way to avoid surprise attacks by the computer. Undefended pieces have a way of getting gobbled up. Vice versa, “defending” the king means leaving its avenues of escape open (and then avenues from there, and so on). Meanwhile, as in chess, exchanges are possible and it will help to focus several attacks on the same square. Watch out for attacks that come diagonally with the same value (e.g. a 3 attacking a 3) or half the value (e.g. a 2 attacking a 4). The center four squares do not seem valuable (as in chess) but are a good place for a 5-high king to get stranded and die.
Puzzle: What’s the longest possible game of Lielow?
Game creator Michael Amundsen asks: What’s the longest possible game of Lielow? (Assuming both players are cooperating to prolong the game, of course.) So far, my longest game is 197 ply, via a strategy of fattening up all the stacks and then sacrificing half of them to shrink the other half:
Can you find a legal sequence of moves longer than 197-ply?
Puzzle: Is a 64-broad position reachable?
I said above that there are never more than 64 possible moves from any given position (because you have only eight pieces, and each of them has only eight possible directions in which to move). It’s trivial to find a board position with 64 (distinct) possible successors; but can you prove that such a position is reachable in a legal game?
I strongly suspect that this isn’t hard, but I haven’t really tried it myself yet.