Two small in-register-lookups

[Tord Romstad]

What do you guys use the square color for? I can't imagine that this could possibly be a performance bottleneck. I compute the square color in the most straightforward and stupid way possible, and it still doesn't show up in the profiler output at all. Currently I use the square color for the following purposes:

• Testing for opposite colored bishop endgames (only done in the endgame, and only when both sides have no minor pieces except a single bishop).
• Evaluating knights and bishops on weak squares. The bonus is increased if the other side has no minor pieces except a single bishop (or no minor pieces at all), and this bishop is of the wrong color.
• Evaluating KBN vs K endgames. The color of the bishop's square is used to drive the king into the right corner.
• Detecting KBP vs K draws with a bishop of the wrong color.
• Printing an ASCII board.

Most of these don't occur except in very rare cases. I guess that I use my square_color function less than once per node, on average.

Tord

[hgm]

Well, like Gerd says, it is mainly a bit-twiddling addiction. We don't do it because we need it to program Chess engines, but we do Chess programming because it provides us with a nice set of opportunities to come up with twiddles like this...

Upto now Joker only used the square color for evaluating King safety: if it makes a hole in the Pawn shield by advancing the Pawn directly in front of its King, it gets a lethal penalty if the opponent still has a Bishop of that color, and its own Bishop is not filling the hole.

In the version I am currentl testing, though, I use it also for good vs bad Bishop and B vs N evaluation: I count the number of own Pawns on each color, and subtract that (multiplied by a suitable weighting factor) from the value of the Bishop, double-counting Pawns on its own color (and half-counting Pawns on a- and h-file and 2nd and 7th rank, on the assumption that these are less of an obstacle). I have no idea yet if this helps.

The square color is only explicitly calculated for the Bishops, though: for the Pawn counting I use an array of 64 bytes (in 0x88 layout, shared with some other table indexed by square number) that has the Pawn weight (1 or 2, depending on if it is an fringe or center Pawn) in the low nybble for white squares and in the high nybble fror black squares. I can then simply add that for all the Pawns of a certain side, and later extract the totals from the nybbles and weight them depending on Bishop color.

Of course the end-game stuff you mention is very important, but Joker has no end-game code yet at all. My priority is to improve so that it can survive into the end-game... The weak squares is a nice idea. Joker's Knight scoring already involves a bonus for Knights on center squares that can no longer be attacked by a Pawn, and one can easily generalize that for Bishops.

The square-color calculation of the Bishops in Joker kind of a legacy thing: when I will finally do a clean-up of the code I will no longer use it, but derive the presence of Bishops of either color from a piece-makeup variable that is differentially updated on make/unmake. This piece-makeup distinguishes Bishops by color, and is currently used as an index in many tables. E.g. to see what the highest piece or the highest two pieces are (for futility pruning, or King safety), the total amount of non-Pawn material (for game-stage determination), number of non-pawns, if nul-move pruning is allowed, etc. I might as well get the material evaluation from there as well, so that I no longer have to differentially update that separately. And for the color of Bishops. The piece-makeup variable is updated by having a number for each piece type in the piece list (B=1 or 2, N=4, R=12, Q=36), that is subtracted from it when the piece is captured, so that a unique code results. (Yes, this system is not resistant to under-promotions. If I were ever to implement supernumerary under-promotions, it would have to reassign codes and recalculate the tables on make and unmake...)

[Tord Romstad]

Well, like Gerd says, it is mainly a bit-twiddling addiction. We don't do it because we need it to program Chess engines, but we do Chess programming because it provides us with a nice set of opportunities to come up with twiddles like this...

OK, I see.

To me, chess programming is more like an exercise in breaking up a complex problem into tiny and trivial sub-problems, and to solve these sub-problems in the most straightforward possible way. I don't like to use opaque, hackish or clever solutions unless there is a lot to gain.

My square_color function, therefore, is very prosaic:

Code: Select all

inline Color square_color(Square s) {
  return Color((int(square_file(s)) + int(square_rank(s))) % 2);
}

Of course, in a program where finding the color of a square is extremely important to performance, the best solution is to have a board with an odd number of files, and to simply compute the square color as the square index modulo 2. In my program (and in most others, I guess) it is much more important to be able to find the file or the rank of a square quickly, and therefore it is better to use a power of 2 for the number of files.

Upto now Joker only used the square color for evaluating King safety: if it makes a hole in the Pawn shield by advancing the Pawn directly in front of its King, it gets a lethal penalty if the opponent still has a Bishop of that color, and its own Bishop is not filling the hole.

Such a penalty might be a good idea, but I think it is better to keep it quite small (unless you add some additional conditions).

In the version I am currentl testing, though, I use it also for good vs bad Bishop and B vs N evaluation: I count the number of own Pawns on each color, and subtract that (multiplied by a suitable weighting factor) from the value of the Bishop, double-counting Pawns on its own color (and half-counting Pawns on a- and h-file and 2nd and 7th rank, on the assumption that these are less of an obstacle). I have no idea yet if this helps.

I have tried lots of variations of this, but to my frustration it never seemed to work.

The weak squares is a nice idea. Joker's Knight scoring already involves a bonus for Knights on center squares that can no longer be attacked by a Pawn, and one can easily generalize that for Bishops.

The important thing is whether it is possible for the opponent has no way to exchange the knight. If the knight is well placed, supported by a pawn, cannot be driven away by a pawn, and the opponent has no minor piece which can ever move to the square of the knight (i.e. no minor pieces at all or just a single bishop of the wrong color), the knight is extremely strong.

Tord

[hgm]

The important thing is whether it is possible for the opponent has no way to exchange the knight. If the knight is well placed, supported by a pawn, cannot be driven away by a pawn, and the opponent has no minor piece which can ever move to the square of the knight (i.e. no minor pieces at all or just a single bishop of the wrong color), the knight is extremely strong.

Yes, this was about the idea. But it stemmed from the time where Joker's piece value for Bishop was still a lot larger than for a Bishop. The bonus basically uograded the value of the Knight to that of a Bishop, and a later exchange for a Bishop would only confirm that. If there was no enemy Pawn in the file of the Knight before it, the bonus was even higher, as exchanging the Knight would create me a passer.

But now I am back to a more equal piece value for B and N (which might even reverse dependent on number of Pawns), so looking at the presence of the proper Bishop seems like a good idea.

[Gerd Isenberg]

Probably I will don't use that function at all. More likely I will work setwise, to get good-, bad-bishops and monochromie-, leukopenie- and melanpenie-pattern (Kmoch's german terms from "Die Kunst der Bauernfuehrung" ("Pawn power in chess")).

Gerd

[Gerd Isenberg]

You could of course replace the (sqr>>3^sqr)&1 by

Code: Select all

9*sqr & 8

for the purpose of making a boolean.

The multiplication could be implemented with a single LEA instruction:

Code: Select all

    movl  _sqr, %eax
    leal (%eax, %eax, 8), %eax
    andl  $8, %eax

In following routine vc2005 uses lea:

Code: Select all

u64 bitBoardOfsquareColor(unsigned int sq) {
    return _rotl64&#40;0xAA55AA55AA55AA55, (&#40;sq<<3&#41;+sq&#41; & 8&#41;;
&#125;

sq$ = 8
?bitBoardOfsquareColor@@YA_KI@Z PROC
  00000	8d 0c c9	 lea	 ecx, DWORD PTR &#91;rcx+rcx*8&#93;
  00003	48 b8 55 aa 55
	aa 55 aa 55 aa	 mov	 rax, aa55aa55aa55aa55H
  0000d	83 e1 08	 and	 ecx, 8
  00010	48 d3 c0	 rol	 rax, cl

but...

Code: Select all

u64 bitBoardOfsquareColor(unsigned int sq) {
    return _rotl64(0xAA55AA55AA55AA55, 9*sq & 8);
}

sq$ = 8
?bitBoardOfsquareColor@@YA_KI@Z PROC
  00000	6b c9 f9	 imul	 ecx, -7
  00003	48 b8 55 aa 55
	aa 55 aa 55 aa	 mov	 rax, aa55aa55aa55aa55H
  0000d	83 e1 08	 and	 ecx, 8
  00010	48 d3 c0	 rol	 rax, cl