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.
- 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.
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?
As a game designer it's hard to see obscurity in move options as anything other than a flaw. I have an undying urge to eliminate all logistical considerations so that there's nothing distracting players from focusing wholly on strategy/tactics. Seems like it should be an easy thing to do, but it's often not.
ReplyDeleteI am game designer, as well and I totally agree with you, Nick. Great post!
ReplyDelete