King of high dimensional space
Which has more mobility on an empty chessboard: a rook, a king or a knight?
On an ordinary 8 by 8 chessboard, a rook can move to any one of 14 squares, no matter where it starts. A knight and a king both have 8 possible moves from the middle of the board, fewer moves from an edge.
If we make the board bigger or higher dimensional, what happens to the relative mobility of each piece? Assume we're playing chess on a hypercube lattice, n points along each edge, in d dimensions. So standard chess corresponds to n = 8 and d = 2.
A rook can move to any square in a coordinate direction, so it can choose one of n-1 squares in each of d dimensions, for a total of (n-1)d possibilities.
A king can move a distance of 0, 1, or -1 in each coordinate. In d dimensions, this gives him 3d - 1 options. (Minus one for the position he's initially on: moving 0 in every coordinate isn't a move!)
What about a knight? There are C(d, 2) ways to choose two coordinate directions. For each pair of directions, there are 8 possibilities: two ways to choose which direction to move two steps in, and then whether to move + or - in each direction. So there are 4d(d - 1) possibilities.
In short:
- A king's mobility increases exponentially with dimension and is independent of the size of the board.
- A rook's mobility increases linearly with dimension and linearly with the size of the board.
- A knight's mobility increases quadratically with dimension and independent of the size of the board.
The rules above are not the only way to generalize chess rules to higher dimensions. Here's an interesting alternative way to define a knight's moves: a knight can move to any lattice point a distance a5 away. In dimensions up to 4, this corresponds to the definition above. But in dimension 5 and higher, there's a new possibility: moving one step in each of five dimensions. In that case, the number of possible knight moves increases with dimension like d5.
Related post: A knight's random walk in 3 or 4 dimensions