Author: Gerd Isenberg
Date: 10:46:37 11/17/05
Go up one level in this thread
On November 17, 2005 at 09:29:39, Jarkko Pesonen wrote:
>Is there any simple algorithm to calculate
>how many jumps it takes for knight to get some specific square?
>
>Or any simple precalculated table structure.
>
>Thanks
>
>Jarkko Pesonen
With two squares you may use a precalculated 64*64 array to get the theoretical
shortest knight-distance.
More sophisticated is it setwise with bitboards, considering also a set of
taboo-squares, the knight can not enter, e.g. own pawns/pieces.
You may use a simple fill-algo, something like this on the fly:
input: knights - a set of knights trying to reach the target set in n moves
target - the set of target squares to reach in n moves
taboo - a set of squares excluded from the path
fillSet = knights;
niter = 0;
while ( (fillSet & target) == 0 && niter < MAXITERATIONS) {
niter++;
attacks = getKnightAttacks(fillSet) & ~taboo; // all attacks
if ( (attacks &~ fillSet) == 0 ) // does it grow?
return MAXITERATIONS; // no, flood stops return none path exist
fillSet |= attacks;
}
getKnightAttacks most likely does two times two (horizontal) shifts with board
wrap ands. And two times two (vertical) shifts all ored together for the final
result.
You may use CCC-Search engine to look for Steffan Westcott's shortest path and
fill-stuff algorithms, e.g:
http://chessprogramming.org/cccsearch/ccc.php?art_id=252020
Gerd
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.