mathematics - lolcatz can haz ur infinit cheeseboard

This is a problem on an infinite chessboard with pieces called lolcatz. They can move like queens or knightriders, but have a strange disadvantage...

... you've never heard of knightriders? Well, they're long-range knights. They make an odd number of regular knight moves in the same direction at once. Knightriders can jump over pieces, except those on the intervening squares that it could have landed on. (So, b1-e7 only requires c3 to be vacant, d5 can be occupied.) Like regular knights, knightriders land on a square of opposite colour to their starting square.

There are no knightriders in this puzzle -- just lolcatz, which have rook, bishop, or knightrider moves available. The squares that can be reached by a lolcat in one move are illustrated here.

Other than that, the puzzle involves standard chess pieces with their usual moves: pawns, knights, bishops, rooks, and queens (no kings).

Anyway, as I was saying... lolcatz have a strange disadvantage: if a piece captures a lolcat, or lands where it could be captured by an enemy lolcat in one move, then, the piece gets to make an extra move. Though it has to transmogrify first, naturally...

...how does transmogrification work, you ask? Well, if you've ever seen a transdimensional kitten playing with a hypersphere of cosmic yarn immersed in de Sitter space, then it happens pretty much they way you think it does:

• If a piece lands where it could be captured by a lolcat moving as a rook (marked red in the picture), then it becomes a bishop.


• If a piece lands where it could be captured by a lolcat moving as a bishop (marked green in the picture), then it becomes a rook.


• If a piece lands where it could be captured by a lolcat moving as a knightrider (marked blue in the picture), then, it becomes a pawn if it was moving away from the lolcat, and it becomes a knight (not a knightrider) if it was not moving away from the lolcat.


• If a piece captures a lolcat, then it becomes a lolcat.


• If a pawn moves from a square where it could be captured by a lolcat, and moves away from that lolcat, then, the pawn becomes a queen. And, the queen still gets an extra move in this case, but, this extra move must also be away from that lolcat, and onto a square where it could be captured by that lolcat.

If multiple cases apply (due to multiple enemy lolcatz), then the moving player chooses which case applies.

The puzzle is this: There is an initially empty chessboard that is infinite in all directions. First white chooses any square to place a white bishop, then black chooses any (empty) squares to place any (finite) number of black lolcatz. Then white moves first. Win by capturing all enemy pieces. Does white have a winning strategy? Or can black place lolcatz so as to evade white indefinitely, or force a win?

No that's not a mistake: white, with a single bishop, versus as many lolcatz as black wants, in any position black wants.

Still have questions? Here's some fine print which tries to anticipate them:

1. "Extra move" means that the player may move that same piece again before the other player gets a turn. And if this extra move results in another extra move, the player may move it again, and so on.


2. The extra move is granted even if the piece transmogrifies to the same type (eg. bishop lands where it would turn into a bishop).


3. The transmogrification happens after the move that caused it, and before the extra move that it causes. That is, the extra move must be to a square reachable as the new type of piece.


4. The transmogrification applies to a moving piece, and does not apply when the square the piece is on changes due to a lolcat moving.


5. "Moving away from the lolcat" means that distance from the lolcat in question, as measured in king moves, is greater after the move than before it.


6. "Choosing which case applies" means that if there are multiple enemy lolcatz that could reach the square in question (or the player is capturing an enemy lolcat that could also be reached by one or more enemy lolcatz), then the moving player selects one of those (or the one captured), and applies the transmogrification rule as if that were the only lolcat.



7. The extra move is not obligatory. If the extra move is passed, the transmogrification is passed too. If the extra move is used, the transmogrification must happen first.


8. Even though the chessboard has no edges, there is still a forward direction for pawns, which is opposite for white and black.


9. When a piece transmogrifies to a pawn, it does not get an initial two-step move.


10. There is no 50-move draw rule, white has as many moves as needed.


11. When you capture a piece with a lolcat, it is usual but not obligatory to say omnomnom.

The fine print covers all the relevant questions that I could think of, but if anything is still unclear please ask!

Answer

Unless I'm mistaken, the result is

Unknown.

Reading through the wall of text, the rules seemed a bit too complicated for it to be "just some random game", so figuring out the magic seemed interesting.

To figure out if the bishop can capture all the lolcats on his first move, we need a "hitbox" for the lolcat; that is, the set of all those squares from which there is an extra move path to capturing the lolcat.

Since a bishop, rook, queen or a lolcat can always reach the same rank as any lolcat, we can start on that rank without loss of generality. We'll also assume that the lolcat is on a white square as in the example picture.

If we end up on a white square, our distance from the lolcat is even, and since we are now a bishop, we can halve the distance by moving to the diagonal, turning into a rook, and moving back to the lolcat's rank.

(Sample moves for getting from distance 4 to distance 2)

If we are on a black square, we must find a knightrider square (in the appropriate direction so that the pawn move is away from the lolcat. This is always possible because of the symmetry of the board: going aroung the lolcat with bishop moves rotates the pawn move direction, but doesn't otherwise affect the position), then transmorgify to a queen, and return to the lolcat's rank diagonally away. Because of how the knightrider squares are spaced, this always exactly triples our distance, and adds one square to it from the pawn move.

(Sample moves for getting from distance 3 to distance 10.)

Notice that these are the only move sequences that change the bishop's distance from the lolcat while still providing extra moves.

All this changes in the near vicinity of the lolcat: if we can get the distance to 1, then we can capture the lolcat:

So to recap: Our horizontal distance is N. If N is even, we can halve it, and if N is odd we go to 3N+1. If we get N to 1, we capture the lolcat, and get to hunt the next one with the same strategy.

So if we could always get from any N to 1, then the bishop would always win on the first turn: every lolcat would then have an infinitely long continuous hitbox. So all we have to know is: can we always get to 1 using this process?

This method of generating the next number is known as the Collatz Sequence. Lothar Collatz of University of Hamburg conjectured in 1937 that the answer is "yes, you'll always reach 1", but to this day, there is no definite answer; the problem is often said to be completely out of reach by the current mathematical methods.

In addition to that, a very strong reason I believe this has to be the intended solution is that

"Lolcatz" happens to be an anagram of "Collatz".

As for the strategy of the lolcatz player:

If the Collatz conjecture surprises us, and there indeed is some number M, from which the process never reaches one, then the lolcatz player can forever evade capture, because there is a hole (by necessity, several actually, but that's not important here) in the hitbox: after the bishop is placed, put a single lolcat exactly M squares left of the bishop. (Count the squares very carefully. If M exists, it will be larger than several quintillion, all numbers smaller than that have already been checked by computer.) The bishop cannot obviously get to any winning square, so after going around in useless circles, the (now multiply transmuted) bishop will probably want to stop at some point.

* If the bishop stopped at a transmutation point, the lolcat can, of course, just capture the piece and win. (It's probably worth mentioning, that the stopped piece can only be a queen if it is stopped on such a transmutation point; the queen's only allowed move is to go to such a spot.)

* If the bishop stopped after making any other move, the lolcat can become a copycat, and make the same move (eg. 42069 squares northwest) that the bishop last made. This is always possible because of the versatility of the lolcat: every regular chess piece's every possible move is available to it. Since this resets their relative position to a "known non-winning" position, the bishop can never catch the lolcat.

* The only exception would be "skipping the extra move after transmuting into a queen", but luckily the rules say that if you pass the extra move, you also have to skip the transmutation, so copying the pawn's move is quite enough to save the lolcat.