Distance to King

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

Gerd Isenberg
Posts: 2250
Joined: Wed Mar 08, 2006 8:47 pm
Location: Hattingen, Germany

Re: Distance to King

Post by Gerd Isenberg »

bob wrote:
hgm wrote:Look it up in a table indexed by (square - kingSquare).
or

distance = Max( abs(Rank(king) - rank(square)), abs(file(king) - file(square)));

That computes the so-called "taxicab distance" You take the largest of the vertical and horizontal distances.
Confusion ;-)

Isn't "taxicab distance" what I call Manhattan- or Taxi-distance, the shortest number of orthogonal king moves, thus the sum of abs rank- and file-distance?

Max of abs rank- and file-distance is simply called Distance or King-Distance also incorporating diagonal king moves. Right?
User avatar
michiguel
Posts: 6401
Joined: Thu Mar 09, 2006 8:30 pm
Location: Chicago, Illinois, USA

Re: Distance to King

Post by michiguel »

Gerd Isenberg wrote:
bob wrote:
hgm wrote:Look it up in a table indexed by (square - kingSquare).
or

distance = Max( abs(Rank(king) - rank(square)), abs(file(king) - file(square)));

That computes the so-called "taxicab distance" You take the largest of the vertical and horizontal distances.
Confusion ;-)

Isn't "taxicab distance" what I call Manhattan- or Taxi-distance, the shortest number of orthogonal king moves, thus the sum of abs rank- and file-distance?

Max of abs rank- and file-distance is simply called Distance or King-Distance also incorporating diagonal king moves. Right?
Chebyshev distance
http://en.wikipedia.org/wiki/Chebyshev_distance

Miguel
Gerd Isenberg
Posts: 2250
Joined: Wed Mar 08, 2006 8:47 pm
Location: Hattingen, Germany

Re: Distance to King

Post by Gerd Isenberg »

michiguel wrote: Chebyshev distance
http://en.wikipedia.org/wiki/Chebyshev_distance
Miguel
Ahh, Thanks!
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Distance to King

Post by bob »

Gerd Isenberg wrote:
bob wrote:
hgm wrote:Look it up in a table indexed by (square - kingSquare).
or

distance = Max( abs(Rank(king) - rank(square)), abs(file(king) - file(square)));

That computes the so-called "taxicab distance" You take the largest of the vertical and horizontal distances.
Confusion ;-)

Isn't "taxicab distance" what I call Manhattan- or Taxi-distance, the shortest number of orthogonal king moves, thus the sum of abs rank- and file-distance?

Max of abs rank- and file-distance is simply called Distance or King-Distance also incorporating diagonal king moves. Right?
You are right. Don't know what I was thinking. It is a special case since the king can close in two directions at once.
gladius
Posts: 568
Joined: Tue Dec 12, 2006 10:10 am
Full name: Gary Linscott

Re: Distance to King

Post by gladius »

bob wrote:
Gerd Isenberg wrote:
bob wrote:
hgm wrote:Look it up in a table indexed by (square - kingSquare).
or

distance = Max( abs(Rank(king) - rank(square)), abs(file(king) - file(square)));

That computes the so-called "taxicab distance" You take the largest of the vertical and horizontal distances.
Confusion ;-)

Isn't "taxicab distance" what I call Manhattan- or Taxi-distance, the shortest number of orthogonal king moves, thus the sum of abs rank- and file-distance?

Max of abs rank- and file-distance is simply called Distance or King-Distance also incorporating diagonal king moves. Right?
You are right. Don't know what I was thinking. It is a special case since the king can close in two directions at once.
I was also off in la-la land when I posted my king distance function :).

Ah well, we gave a good summary of the different king distance methods.
MattieShoes
Posts: 718
Joined: Fri Mar 20, 2009 8:59 pm

Re: Distance to King

Post by MattieShoes »

Just FYI, it's sometimes referred to as "tropism" or "king tropism". That might help any searches you may want to do.

There's no official distance value, and some may apply a different distance function based on the piece type... I think I've seen engines that take min(verticalDistance, horizontalDistance) for tropism with rooks, etc.
aberent

Re: Distance to King

Post by aberent »

Thank you for all your answers, I am a bit confused about which answer is correct though.

Is this the winner:


int manhattanDistance(int sq1, int sq2) {
int file1, file2, rank1, rank2;
int rankDistance, fileDistance;
file1 = sq1 & 7;
file2 = sq2 & 7;
rank1 = sq1 >> 3;
rank2 = sq2 >> 3;
rankDistance = abs (rank2 - rank1);
fileDistance = abs (file2 - file1);
return rankDistance + fileDistance;
}

Thanks
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Distance to King

Post by bob »

aberent wrote:Thank you for all your answers, I am a bit confused about which answer is correct though.

Is this the winner:


int manhattanDistance(int sq1, int sq2) {
int file1, file2, rank1, rank2;
int rankDistance, fileDistance;
file1 = sq1 & 7;
file2 = sq2 & 7;
rank1 = sq1 >> 3;
rank2 = sq2 >> 3;
rankDistance = abs (rank2 - rank1);
fileDistance = abs (file2 - file1);
return rankDistance + fileDistance;
}

Thanks
I believe you want to do this:

return (Max(rankDistance, fileDistance));

Since the king can move diagonally, which cuts both down at the same time.
Vinvin
Posts: 5228
Joined: Thu Mar 09, 2006 9:40 am
Full name: Vincent Lejeune

Re: Distance to King

Post by Vinvin »

aberent wrote:Thank you for all your answers, I am a bit confused about which answer is correct though.

Is this the winner:


int manhattanDistance(int sq1, int sq2) {
...
ManhattanDistance is not the right name ;-)
michiguel wrote: Chebyshev distance
http://en.wikipedia.org/wiki/Chebyshev_distance

Miguel
Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: Distance to King

Post by Sven »

Vinvin wrote:
aberent wrote:Thank you for all your answers, I am a bit confused about which answer is correct though.

Is this the winner:


int manhattanDistance(int sq1, int sq2) {
...
ManhattanDistance is not the right name ;-)
michiguel wrote: Chebyshev distance
http://en.wikipedia.org/wiki/Chebyshev_distance

Miguel
This last comment has potential to create about the same confusion as before in this thread :shock:

1) The winner is indeed "chebyshev distance" (Max(rankDist, fileDist)).

2) Name and implementation of the function "manhattanDistance()" given above are correct since the function calculates the "manhattan distance" or "taxicab distance" (rankDist+fileDist), but this is not the distance that was requested.

We'll get it right some day ...

Sven