~loop

https://twitter.com/alilleybrinker

~loop/chirp-devel

Last active 5 months ago

~loop/chirp-announce

Last active 5 months ago
View more

Recent activity

Re: I Solved British Square 30 days ago

From Andrew Lilley Brinker to ~skeeto/public-inbox

Hi, I’d posted this on the GitHub repo before realizing you may not see it there. The link to the original is here, but I’ve copied it as well: https://github.com/skeeto/british-square/issues/1

"Hi there! I saw the blog post and wanted to point you to some work in combinatorial game theory which may be relevant.
It looks, from my quick assessment, like British Square 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. It's pseudocode and may be unnecessary here, but I'm happy to look for it if you'd like to see it.

To expand: the basic idea is that Nim is well understood, so if you can reduce the game or a subgame to Nim, you can derive and apply a winning strategy. This is always possible for impartial games with the normal play convention, and possibly true otherwise. In Dots & Boxes, there is a subgame which is Nim-equivalent, and the goal of two expert players is to guide the game states to a Nim-equivalent state where they are guaranteed to win (which is not inherently possible, thus Dots & Boxes doesn't have a guaranteed winning strategy for the whole game, although one exists for the subgame).”

Fun work!

- Andrew Lilley Brinker

Twitter: alilleybrinker