Three Dimensional Chess Knight Moves
Three Dimensional Chess Knight Moves
Love chess, multi-dimensionality, and Python? Well, then we have the post for you! Read on to learn how to use Python to see how many moves a knight can make in 3D chess.
Join the DZone community and get the full member experience.Join For Free
Hortonworks Sandbox for HDP and HDF is your chance to get started on learning, developing, testing and trying out new features. Each download comes preconfigured with interactive tutorials, sample data and developments from the Apache community.
I've written before about a knight's random walk on an ordinary chess board. In this post, I'd like to look at the generalization to three dimensions (or more).
So what do we mean by 3D chess? For this post, we'll have a three-dimensional lattice of possible positions, of size 8 by 8 by 8. You could think of this as a set of 8 ordinary chess boards stacked vertically. To generalize a knight's move to this new situation, we'll say that a knight move consists of moving 2 steps in one direction and 1 step in an orthogonal direction. For example, he might move up two levels and over one position horizontally.
Suppose our knight walks randomly through the chess lattice. At each point, he evaluates all possible moves and chooses one randomly with all possible moves having equal probability. How long on average will it take our knight to return to where he started?
As described in the post about the two-dimensional problem, we can find the average return time using a theorem about Markov chains.
The solution is to view the problem as a random walk on a graph. The vertices of the graph are the squares of a chess board and the edges connect legal knight moves. The general solution for the time to first return is simply 2 N/k where N is the number of edges in the graph, and k is the number of edges meeting at the starting point.
The problem reduces to counting N and k. This is tedious in two dimensions and gets harder in higher dimensions. Rather than go through a combinatorial argument, I'll show how to compute the result with a little Python code.
To count the number of edges N, we'll add up the number of edges at each node in our graph and then divide by 2 since this process will count each edge twice. We will iterate over our lattice, generate all potential moves, and discard those that would move outside the lattice.
from numpy import all from itertools import product, combinations def legal(v): return all([ 0 <= t < 8 for t in v]) count = 0 for position in product(range(8), range(8), range(8)): # Choose two directions for d in combinations(range(3), 2): # Move 1 step in one direction # and 2 steps in the other. for step in [1, 2]: for sign0 in [-1, 1]: for sign1 in [-1, 1]: move = list(position) move[d] += sign0*step move[d] += sign1*(3-step) if legal(move): count += 1 print(count // 2)
This tells us that there are N = 4,032 nodes in our graph of possible moves. The number of starting moves k depends on our starting point. For example, if we start at a corner, then we have 6 possibilities. In this case, we should expect our knight to return to his starting point in an average of 2*4032/6 = 1,344 moves.
We can easily modify the code above. To look at different size lattices, we could change all the 8s above. The function
legal would need more work if the lattice was not the same size in each dimension.
We could also look at four-dimensional chess by adding one more range to the position loop and changing the combinations to come from
range(4) rather than
range(3). In case you're curious, in four dimensions, the graph capturing legal knight moves in an 8 by 8 by 8 by 8 lattice would have 64,512 edges. If our knight started in a corner, he'd have 12 possible starting moves, so we'd expect him to return to his starting position on average after 5,275 moves.
Published at DZone with permission of John Cook , DZone MVB. See the original article here.
Opinions expressed by DZone contributors are their own.