Nimbers in Konane

I saw a lot of awesome talks at the BIRS workshop in January that I still want to report about. One of these was an awesome talk by Carlos dos Santos that really struck me as a computer scientist. It used a real reduction-like strategy to prove that for any k, *k can be written as a Konane position! A cool result with a cool proof!

Gamesters are interested in which game values exist for different rulesets. Elwyn Berlekamp asked, "What is the habitat of *2?" meaning, which rulesets have a position equal to *2. For Domineering, it was quite complicated to find a *2 position!

Carlos dos Santos does infinitely better with Konane, finding an algorithm to construct a board of value *k for any natural number k. The paper is here. The algorithm is elegant and recursive, and each resulting position has a very clear focal point where one of two or three pieces will be able to make the first move. Naturally, the *4 Konane board is much more complex than the *4 Nim board, but the difficulty is showing that for each successive power of 2, that nimber can be generated. Indeed, I assumed *1, *2, and *3 could be created, but *4 would require a 3-dimensional board.

Instead, they all exist, and the result is something I wish I could ask my algorithms class to learn!