~skeeto/public-inbox

1

Re: I Solved British Square

Details
Message ID
<FFFDB5DC-03A6-42C6-ACBC-52B33165D1BE@gmail.com>
DKIM signature
pass
Download raw message
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
GitHub alilleybrinker
Sourcehut: ~loop

Re: I Solved British Square

Details
Message ID
<20201101172719.p3hjuurxbh7ezf2s@nullprogram.com>
In-Reply-To
<FFFDB5DC-03A6-42C6-ACBC-52B33165D1BE@gmail.com> (view parent)
DKIM signature
missing
Download raw message
Thanks for the information, Andrew. I *did* see the GitHub issue, but 
when I saw I needed to catch up on the terminology (which you had kindly 
linked), I set aside replying until I had done so. Then I put off that 
reading. Sorry!  However, I'm now caught up.

> I'd guess that a subpart of the game is reducible to Nim

What subpart did you have in mind? I had at one point considered a 
bottom-up approach with dynamic programming, but I didn't have the 
exhaustive list of 6,955 terminal states from which to start, at least 
not with without first taking a different approach.

As a kind of stretch goal, I would like to reduce the CPU and memory 
requirements needed for perfect play. Since I now have the exhaustive 
list of terminal states, perhaps it could serve as the basis for a more 
efficient search. Then maybe combine that with pre-computed opening play 
in order to completely cull some early branches.
Reply to thread Export thread (mbox)