7

Is there a practical way of computing the shortest path from a square to another, for a knight? (for a human chess player, not for a computer)

Usually, when I want to send my knight from a square to another, I try to find a path with a rather empirical way. "OK, to get there, I should go here or here... But this square is attacked, so I can only go here..." and so on. Is there a more straightforward approach?

Thanks in advance.

3
  • Thanks but it does not answer my question. My question is about human players, not algorithms. I don't think that the human player build the graph in his head! – pim999 Mar 19 '14 at 14:06
  • If it's long enough to be nontrivial, it's probably a waste of moves, and the board will change by the time it gets there. Spending several moves developing one piece is generally not a good idea (although of course there are exceptions). – Acccumulation Jan 25 '20 at 0:16
9

To me the easy human way it is to start from the square that you want to go to (backtracking approach), lets call it 'A' and exclude from the path calculation the direct linked paths from 'A' that you can't go to because they are attack or there is a piece on it.

For example, you want to go to the square c4, so the directed linked paths will be from by a5, a3, b2, d2, e3, e5, d6 and b6, but if only the square a5 and b6 are available you can reduce your calculation to only to 2 paths now. Furthermore, if you use this "technique" you can check if the target square is reachable at all (if have at least 1 directed linked path not being occupied or attacked).

After doing that, you go to the position where you knight stands and you check which are the squares that you can go to. Using this two phase approach you reduce you tree of calculation immensely.

You should also know beforehand how many moves you need to go from one square to another with your knight, in order to avoid the calculation of larger paths than the ones really need it. I din't check online to find any heuristic for this but I can give you some inside tips about it:

  • The Knight on a black square can only go to a white square and vise-versa, in the next move;
  • Every square on the diagonal of the actual square of the Knight can be reach in only two moves. Square (x,y) to the squares (x-1,y+1), (x+1,y+1), (x+1,y-1) and (x-1,y-1) takes 2 moves;
  • The squares up, above, right and left of the actual square takes 3 moves;
  • Every square on the diagonal of the actual square with a one square between them (e.g actual square = c4, target square a6), takes 4 moves.
  • Every square on the diagonal of the actual square with a 2 squares between them (e.g actual square = c4, target square f7), takes only 2 moves.

Finally, if you are in a given color square you will take a odd number of moves to reach the opposite color square. If the target square have the same color as the square that you are in now it will take a even number of moves.

4

It's well documented.

It's actually a fairly boring metric. The only special cases are the squares next to the knight and the squares on the same diagonal that are two squares away. In all other cases, quite regular.

If you mean with other pieces on the board, you get a shortest path problem which is related to the Travelling Salesman Problem but is soluble in polynomial time.

2
  • This does not really answer my question. My question is on how a human player compute the shortest path (without or with other pieces on the board). Your answer is about how a computer would answer the question. I might be wrong but I don't think that a human chess player build the graph in order to search for a path. Beside, I don't think that the shortest path with other pieces relates to a Travelling Salesman problem. I think that even in this case it should be a Breadth-first search, so it is far less complex than the travelling salesman. – pim999 Mar 19 '14 at 14:01
  • Well, in your head, you're building graphsto find out by basically doing breadth-first. There's quite a bit of intuition connected to it, of course. If this is what you are aiming at, I may change the answer. – chaosflaws Mar 19 '14 at 15:43
1

I know this is a super old question. I made a program that outputs all the positions a knight can be relative to starting position within six moves(which happens to be the maximum number of moves needed to get anywhere)

0: (0, 0) 
1: (2, 1) 
2: (2, 0) (3, 3) (4, 2) (3, 1) (1, 1) (4, 0) 
3: (3, 2) (5, 4) (4, 1) (3, 0) (6, 1) (6, 3) (4, 3) (5, 0) (1, 0) (5, 2) 
4: (7, 3) (6, 4) (5, 5) (6, 6) (7, 1) (4, 4) (6, 0) (6, 2) (7, 5) (2, 2) (5, 1) (5, 3) 
5: (7, 4) (6, 5) (7, 0) (7, 6) (7, 2) 
6: (7, 7)

Number on the left is turn number, and the list on the right corresponds to all the positions the knight can be in with duplicate positions removed (we don't care that you can go back to your starting position for example, these are the shortest paths to each of these positions). Also, no negative numbers are represented. For example 2,1 -2,1, 2,-1 and -2,-1 are all considered the same position. Also the biggest number is always shown first. For example (4,2) means the night can move 4 spaces in some direction, and then 2 in an orthogonal direction.

One more caveat is that these numbers are the theoretical minimum with no pieces in the way, and a theoretical infinite plane to work with. That is, to achieve this could potentially require moves that exit the game board and come back. I think it only requires exiting in rare cases. For example, if you're in a corner of a board and want to move 1,1 toward the center, the 2 moves that should be able to do this require you going out of bounds first.

Memorizing this is probably not that useful, but there's some interesting takeaways that may be worth noting.

For example, it takes a whole 3 moves to move a knight 1 square forward.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.