1. 22

  2. 2

    Looks like this is almost an impartial game, but without the normal play convention (because the game doesn’t end when one player is without valid moves, but when both are without valid moves, akin to Dots & Boxes). I’d guess that a subpart of the game is reducible to Nim (via the Sprague-Grundy Theorem), in the same manner as Dots & Boxes, and may thus be analyzed in a similar manner. I highly recommend Elwyn Berlekamp’s writing on the game in both “Winning Ways” (chapter 16) and “The Game of Dots & Boxes.”

    On a personal note, I have an undergrad paper floating on a hard drive somewhere which includes a dynamic programming algorithm for efficient nim-value calculation in Dots & Boxes, designed to make it more feasible to write a skilled automated player for the game.

    1. 1

      This was a very pleasant read, with a clear picture of the path taken by the author, and the problem they solve; thanks for sharing!