Tag Archives: math

Satisfaction Part 2

As I mentioned yesterday, one of the weaknesses of a work-to-schedule AI approach, with an exponentially growing search space, is that you can easily spend most of your time on an analysis that never ends up getting used. After all, if at each search depth you take more time than all of the previous depths put together, there’s no point starting a search in the whole second half of your allotted time. Continue reading Satisfaction Part 2

Isomorphism

Have you ever considered all of the empty space on a Checkers board? Half of the squares are unused. You might legitimately ask why they’re even there.

Transformed checkerboardThat, of course, raises the question of whether there’s any way for them not to be there, and it turns out that there is. Imagine removing all of the light spaces from the board, then rotate every dark space 45°. There’s some empty space now, so just sort of slide all the squares together. You’ll end up with something like this:

This is an example of what is called an isomorphism. Loosely put, an isomorphism is a translation between two things that preserves a certain set of their properties. In this case, the playable squares on the original board, with adjacency defined as diagonal, is isomorphic to the new board under orthogonal adjacency. In game design, isomorphism can be used to transform a game into a cosmetically different game, without altering the structure of its gameplay (a well-known example is that Tic Tac Toe is isomorphic to a game of picking numbers from a magic square).

I consider it a feature that the squares that were diagonally adjacent before are now orthogonally adjacent. Orthogonal moves are much more typical in most games, after all. This also seems like a good illustration of just how small the state space in Checkers really is. Of course, I’m talking about Anglo-American Checkers, or Draughts; most international variations are bigger.

Speaking of International Checkers, this leads us to something this variation might be good for. That game is played on a 10×10 board, is reputedly a better game, but is not readily available in the United States. I’ve just started reading R. Wayne Schmittberger’s New Rules for Classic Games, where he discusses both regional variants, and how to make your own equipment. If you were going to do that, you could use a lot less material (and have a more compact board for the same size of checkers) by throwing out the unused squares. Whether you’d like the un-Checkerslike appearance of the board is up to you.

Octagon grid for International CheckersBut, as long as we’re going with a different look, let’s go all the way. The checkers themselves don’t occupy all of the space within their squares, do they? You could squeeze things down a bit more by knocking the corners off. To preserve the common edge between adjacent spaces, let’s go with octagons. This actually restores the unplayable squares to the board, but in a form that can’t be mistaken for the playing spaces. And the pattern you end up with (shown here with the 10×10 international board) is, I think, very attractive.

It turns out, by the way, that this is only 75% of the width and height of the same thing as a square grid. This could be cramped to play, but is probably easier to print. At least it fits on an 11″×17″ sheet. In case you want to try, I’ve posted the same image at 10″×10″, 300 dpi.

This is the kind of thing my mind sometimes does when I’m falling asleep at night. I spent some time this morning coding up the pattern in nanDECK; maybe later I’ll put together a proper board.