As I begin the trip down to the
University of West Georgia for
Integers, I want to be sure to report on another awesome thing I saw in
Banff back in January.
For most games I'm interested in, the rules are simple. Deciding whether one move is legal is usually an easy task. Usually, it's even easy to list all the moves. (Some games, such as
Phutball, may have an exponential number of moves, so this task may not be considered "easy".) The challenge usually arises in finding the best move, not just one that works.
This is not always the case for
International Draughts. For my American comrades,
Draughts is the word the rest of the world uses for variations of the game Checkers. International Draughts is a variant played on a 10x10 board that is one of many "pub games" popular in Europe. The game is different from "standard" draughts in two big ways:
- Regular pieces may jump other pieces forward or backward.
- Crowned (Kinged) pieces can move as many spaces in one direction as desired, even after jumping another piece.
- A turn must include capture of as many opponents' pieces as possible.
This last rule is extremely interesting! Not only must your turn consist of a capture (jumping a piece) if possible, it must capture as many pieces as it can. If you watch the animation on the wikipedia page, it becomes clear that once you have a crowned piece, this maximizing move is not always trivial to find.
In fact, this question was posed last year as a theoretical computer science question:
Is it NP-hard to find a legal move? Bob Hearn rose to the challenge and showed that it is, in fact, an NP-hard question. Bob presented this result at BIRS. I've never seen a game where it's computationally difficult to figure out whether you made a legal move!
How is this policy enforced in the "real world" of international draughts?
