Incremental Material Evaluation Idea

[cms271828]

Hi,

I'm not sure how the EVAL is normally done regarding material,
I always thought once you get to a leaf node, you just loop through
the pieces, adding the values for each piece.

It seems like a lot of work is being repeated at each leaf node,
so if you have a global variable MATERIAL initialized with material value of the board position about to be searched...

Then for each MAKE_MOVE, and UNDO_MOVE, you could remove the value of the piece from the FROM square, then add the value of the piece from the TO square.

Assuming a search tree with n plies, and branching factor b:
There would be b+b^2+...+b^n = b(b^n-1)/(b-1) total branches.
Since you have an undo move, you are really traversing 2b(b^n-1)/(b-1) branches.

During MAKE_MOVE:

Code: Select all

temp=-FROM_w+TO_w  -  TO_b  //Assuming white captures a blackpiece
MATERIAL += temp

During UNDO_MOVE

Code: Select all

MATERIAL -= temp

I use piece-square values, so that would require 3 array-look-ups, and 2 operations, if I just call this 4 array-look-ups, this averages to 2 array-look-ups for each branch traversed.

So with this method, there would be 4b(b^n-1)/(b-1) array-look-ups.


NEXT..
Considering the normal way I do evaluations, with the same tree as above, I would have b^n leaf nodes, so b^n evaluations.
Supposing each board contains P pieces, thats b^n*P array-look-ups.

Considering the inequality...
4b(b^n-1)/(b-1) < b^n*P

gives P >= 5 pieces (b>4 and n>1).

So with 5 or more pieces, using an incremental update for evaluation should be faster than doing the whole thing each time at each leaf node.

And with P=32 pieces, the effect should be even more dramatic, but I haven't calculated by how much yet.

Is this a good idea?

[Matthias Gemuh]

If you have to loop through the pieces in eval anyway for several reasons, you may as well count material in an eval loop.

Going the incremental way is only useful if you use that value in search or lazy eval.


Matthias.

[hgm]

I don't agree. Even if you loop through the pieces anyway, anything you d in that loop still represents work (a table lookup and an addition per piece) . The differential material eval saves you almost all that work.

uMax does evaluate material differentially.

Joker does it slightly differently: it updates a 'material composition indicator' for each side differentially. This is a number that uniquely specifies which non-pawn material you have, and thus can be used as an index in lookup tables to tell you all kind of things. Such as if you are allowed to do null-move pruning, if it is safe to come out with the King with this material, what is the value of the highest piece, and that of the two highest pieces together (for futility pruning). And, of course, how much the total is worth.

I encode this indicator through:
B = 1 (on white)
B = 2 (on black)
N = 4
R = 12
Q = 36

and the tables allow upto 3 Queens (so the index runs upto 144). Note that Bishops on different colors are counted as different piece types, so that you also can see which Bishop you or your opponent has (used for King safety, to penalize diagonal acces into the King fortress). The value of the Bishop pair can be incorporated in the total value.

Note I don't have to worry for more than 2 B, N or R, as Joker doesn't do under-promotions. In Joker80 I treat A and C like they are Q, and only allow promotion to A, C or Q (and not N, B or R).

[bob]

Hi,

I'm not sure how the EVAL is normally done regarding material,
I always thought once you get to a leaf node, you just loop through
the pieces, adding the values for each piece.

Nobody does that. Everyone is doing incremental material updates already. Been doing so since the 70's in fact.

It seems like a lot of work is being repeated at each leaf node,
so if you have a global variable MATERIAL initialized with material value of the board position about to be searched...

Then for each MAKE_MOVE, and UNDO_MOVE, you could remove the value of the piece from the FROM square, then add the value of the piece from the TO square.

Assuming a search tree with n plies, and branching factor b:
There would be b+b^2+...+b^n = b(b^n-1)/(b-1) total branches.
Since you have an undo move, you are really traversing 2b(b^n-1)/(b-1) branches.

During MAKE_MOVE:

Code: Select all

temp=-FROM_w+TO_w  -  TO_b  //Assuming white captures a blackpiece
MATERIAL += temp

During UNDO_MOVE

Code: Select all

MATERIAL -= temp

I use piece-square values, so that would require 3 array-look-ups, and 2 operations, if I just call this 4 array-look-ups, this averages to 2 array-look-ups for each branch traversed.

So with this method, there would be 4b(b^n-1)/(b-1) array-look-ups.


NEXT..
Considering the normal way I do evaluations, with the same tree as above, I would have b^n leaf nodes, so b^n evaluations.
Supposing each board contains P pieces, thats b^n*P array-look-ups.

Considering the inequality...
4b(b^n-1)/(b-1) < b^n*P

gives P >= 5 pieces (b>4 and n>1).

So with 5 or more pieces, using an incremental update for evaluation should be faster than doing the whole thing each time at each leaf node.

And with P=32 pieces, the effect should be even more dramatic, but I haven't calculated by how much yet.

Is this a good idea?

[Edsel Apostol]

Hi H.G.,

I want to adapt your idea but I have a few questions first.

How did you initialize your 144 entry table? Is this only for one side? I mean when you use it to index the material for the two sides, will you have a two dimensional array of 144 elements each index? How about including the pawns? Is each combination of pieces will produce a unique index number?

[hgm]

Currently I use it only for one side, and then just subtract them (for the total score, or number of pieces). I dis consider the idea of using a 144x144 table, but to merely save you the subtraction that would not pay off. I was not aware of enough non-additive interaction between piece composition to really exploit the extra possibilities such a 144x144 table would offer (say things of the type: Knights are better/worse than Bishops if the opponent has Rooks, but just the reverse if he hasn't). Unlike Bishops would be one thing you could work into the score then, bt that was about the only thing I could think of.

If you want to include Pawns, it would drive up the number of combinations for a single side by a factor 9. I do plan to count the number of Pawns of each side differentially (pack the two piece compositions and two pawn counts in the 4 different bytes of a 32-bit int, so they can be differentially updated in a single add.

If you want to make the Piece values dependent on the number of Pawns, say like value = baseValue + A*PawnCount, it means that your total evaluation contains a term A*PawnCount*NrBishopCount, and you can just as well group that term with the value of the Pawn: Value[P] = baseValue[P] + A*BishopCount. So what I do is tabulate the Pawn value as a function of the 144 piece compositions, and then multiply that with the PawnCount. Using 2D tables to tabulate products is not a competative way of doing multiplications. It would be feasible to combine that strategy with a 144x144 table (making own Pawns more valuable to the side who has more pieces, and enemy Pawns less).

[cms271828]

I modified code, and from the starting position, there is a 45% speed up.
So 45% more positions evaluated, which is more than I expected.

[bob]

I modified code, and from the starting position, there is a 45% speed up.
So 45% more positions evaluated, which is more than I expected.

Once you have a complex evaluation, that number will go _way_ down. It is a couple of percent at best...

[cms271828]

Yes, thats true, my evalutation is actually empty, except for the material part, so I expect it to go down a lot, but still, to go up by 45% is very good, means when I put it more eval code, it won't go down as much as it would if I just left the all the material eval inside the eval code, if that makes sense.