Cole@38 + Joseph@45: Yes, I realized the same thing about terminal positions after sleeping on it. More trickily, we also would run into problems with forced captures (e.g., it's the only way to answer a check, or artificial "almost-stalemate" positions). I think there's no shame in allowing 0 moves between positions for \$$\leq \$$: after all, it is \$$\leq \$$ and not \$$< \$$.

By the way, as long as we're being picky, I'm assuming we're including all state (castling rights, en passant ability) in the definition of a position.