Evaluation speedup or (dynamic evaluation)

[MikeGL]

First, sorry I'm just a hobbyist coder, but I have some bad opinion on
modern day eval functions.

I have browsed codes of eval() of some engines and noticed a bunch of
useless code which can't be applied on the current board position.

There are lines of code for checking if(BAD_Bishop) or if(BishopPair) or
if(King_Uncastled), which just makes the evaluation function slow due to
useless knowledge which can't be applied all the time. Like when in
endgame phase without bishops, it would be useless to keep on checking
those codes related to bishops.


GMs just uses specific knowledge and includes this to his assessment of current position on hand.
To make engines assess a position like a GM, I think Evaluation functions
can be implemented similar to the techniques used by modern malwares
like zbot/zeus. Modern/polymorphic malwares just injects some code to a
running process, and I think similar technique can be used by a chess
engine. Using this code injection techniques, chess engines can then
inject only a lean specialised knowledge, or specialised eval function,
which can be used for the current position.


Like during K+B+N vs K endgame, most engines can't announce
checkmate without the use of a TB, but if an engine can grab a file and
inject this knowledge to its own running process, then an engine can
announce mate without using a TB. Similar eval injection can be done on
specific opennings where PST can change depending on the openning, or
knowledge of R endgames.

[bob]

First, sorry I'm just a hobbyist coder, but I have some bad opinion on
modern day eval functions.

I have browsed codes of eval() of some engines and noticed a bunch of
useless code which can't be applied on the current board position.

There are lines of code for checking if(BAD_Bishop) or if(BishopPair) or
if(King_Uncastled), which just makes the evaluation function slow due to
useless knowledge which can't be applied all the time. Like when in
endgame phase without bishops, it would be useless to keep on checking
those codes related to bishops.


GMs just uses specific knowledge and includes this to his assessment of current position on hand.
To make engines assess a position like a GM, I think Evaluation functions
can be implemented similar to the techniques used by modern malwares
like zbot/zeus. Modern/polymorphic malwares just injects some code to a
running process, and I think similar technique can be used by a chess
engine. Using this code injection techniques, chess engines can then
inject only a lean specialised knowledge, or specialised eval function,
which can be used for the current position.


Like during K+B+N vs K endgame, most engines can't announce
checkmate without the use of a TB, but if an engine can grab a file and
inject this knowledge to its own running process, then an engine can
announce mate without using a TB. Similar eval injection can be done on
specific opennings where PST can change depending on the openning, or
knowledge of R endgames.

Did you look at multiple engines? Mine, for example, does not check for bishop pair or bad bishops if there are no bishops on the board... I simply call EvaluateBishops() which promptly returns if there are none...

[rbarreira]

It's an interesting idea, but it looks like a lot of added complexity for little benefit.

If the code injection / code generation runs too often, this screws up with the L1 code cache which may decrease performance instead of improving it. Reminds me of John Carmack's (game engine programmer) statements about Wolfenstein 3D's dynamic code generation for rendering. It was great on 386 CPUs if I recall correctly, but on 486 and above (or was it Pentium?) it actually decreased performance due to thrashing the cache.

[MikeGL]

Did you look at multiple engines? Mine, for example, does not check for bishop pair or bad bishops if there are no bishops on the board... I simply call EvaluateBishops() which promptly returns if there are none...

I have downloaded crafty's source and checked from your official site just now.
crafty's has indeed a straighforward and simple check for B. The for loop checks if
there are Bishops on the board and majority of the code are disregarded if there are none.

But there still seems to be some overhead, even a single call on EvaluateBishops() has
many instructions including push and pops of a couple of registers plus the push and pop of parameters.
Plus the following, which is just outside the for loop:
int score_eg = 0, score_mg = 0, enemy = Flip(side);
tree->score_mg += sign[side] * score_mg;
tree->score_eg += sign[side] * score_eg;

I don't imply the above eval is lousy, I know that the majority of
chess programmers already noticed your obvious C wizardry in crafty.

But there must be some ways to disable or replace that function once there
are no bishops on board, with eval that's more usefull and which can be
effectively applied on the current position and the 'near future' position, as
GMs don't keep on asking himself, "ok how's my bishops or how's my minor pieces",
if he already knew those were swapped 20 moves ago.
It's a waste of time for GMs to keep on asking such a question,
and hence will also be a waste of cpu cycles for machines.

[mcostalba]

You can write different evaluation functions then use function pointers (set at root) to call the correct one down in the tree. But personally I think it is totally useless and focusing on the wrong direction. The correct direction is to use a profiler.

[Sven]

You can write different evaluation functions then use function pointers (set at root) to call the correct one down in the tree. But personally I think it is totally useless and focusing on the wrong direction. The correct direction is to use a profiler.

Correct, and furthermore these "eval function pointers" would have to be updated forth and back with each make/unmake move, introducing a lot of additional if's.

@Mike:

It's a waste of time for GMs to keep on asking such a question, and hence will also be a waste of cpu cycles for machines.

I think this is a basic misunderstanding. The human brain, including that of a GM, works differently from a CPU. For instance, humans are able to recognize patterns by using something like "visual perception". Computers recognize information built upon bits and bytes, no need to explain that further here. The most efficient way for a computer to obtain certain information from given data, like "are any bishops of color X present, and if so, what is the positional score related to these bishops?", differs a lot from the way a human will obtain the corresponding information (not "the same" since humans usually do not calculate centipawn scores).

Plus the following, which is just outside the for loop:
int score_eg = 0, score_mg = 0, enemy = Flip(side);
tree->score_mg += sign[side] * score_mg;
tree->score_eg += sign[side] * score_eg;

The overhead for these statements is quite small compared to the overhead of frequently accessing "tree->score_mg" and "tree->score_eg" directly within the loop since these are memory accesses while score_eg/score_mg will be kept in registers. So in fact the code above is most probably a valid optimization.

Sven

[bob]

Did you look at multiple engines? Mine, for example, does not check for bishop pair or bad bishops if there are no bishops on the board... I simply call EvaluateBishops() which promptly returns if there are none...

I have downloaded crafty's source and checked from your official site just now.
crafty's has indeed a straighforward and simple check for B. The for loop checks if
there are Bishops on the board and majority of the code are disregarded if there are none.

But there still seems to be some overhead, even a single call on EvaluateBishops() has
many instructions including push and pops of a couple of registers plus the push and pop of parameters.
Plus the following, which is just outside the for loop:
int score_eg = 0, score_mg = 0, enemy = Flip(side);
tree->score_mg += sign[side] * score_mg;
tree->score_eg += sign[side] * score_eg;

I don't imply the above eval is lousy, I know that the majority of
chess programmers already noticed your obvious C wizardry in crafty.

But there must be some ways to disable or replace that function once there
are no bishops on board, with eval that's more usefull and which can be
effectively applied on the current position and the 'near future' position, as
GMs don't keep on asking himself, "ok how's my bishops or how's my minor pieces",
if he already knew those were swapped 20 moves ago.
It's a waste of time for GMs to keep on asking such a question,
and hence will also be a waste of cpu cycles for machines.

I don't see how to avoid it without a test. How can you determine whether to call the function or not without testing. And if you test, you may as well do it in the place where it makes the most sense. In Crafty, I tested the idea of seeing if I had a piece before calling the piece evaluation. But I STILL need the test in the function to determine when all have been processed. When you think about it, what I do is actually pretty efficient.

One could possibly do N evaluations, each with one or more piece types missing for a specific color. But again, you have to decide somewhere which one of those to call. I've run across one or two machines over the past 45 years or so that could do this pretty well. One could have an array of function addresses to jump to, and when a piece type no longer exists, you could set the address in the array to zero. On those machines, a "branch and link" to address zero was an effective noop... But not today that I know of.

[MikeGL]

I don't see how to avoid it without a test. How can you determine whether to call the function or not without testing. And if you test, you may as well do it in the place where it makes the most sense. In Crafty, I tested the idea of seeing if I had a piece before calling the piece evaluation. But I STILL need the test in the function to determine when all have been processed. When you think about it, what I do is actually pretty efficient.

One could possibly do N evaluations, each with one or more piece types missing for a specific color. But again, you have to decide somewhere which one of those to call. I've run across one or two machines over the past 45 years or so that could do this pretty well. One could have an array of function addresses to jump to, and when a piece type no longer exists, you could set the address in the array to zero. On those machines, a "branch and link" to address zero was an effective noop... But not today that I know of.

Noted. thanks for all responses

[syzygy]

In principle what you propose is of course possible. For example, at sufficiently long time controls it might even pay off to dynamically compile at the root node the evaluation function with only those features that might still apply (so leaving out bishop code if all bishops have already been captured). Instead of dynamic compilation one could also precompile a dozen evalution functions with various features on and off, then pick the one you need at the root of the search. (It would of course not make sense to select an appropriate evaluation function at every node of the tree. It might make sense to select one at nodes a few ply from the root, to be used in the node's subtree.)

The gain is probably too small for the (programming) effort. When programs cannot be improved anymore by algorithmic changes or better data structures or coding, this might be the way to extract the last few ELO points.

[bob]

In principle what you propose is of course possible. For example, at sufficiently long time controls it might even pay off to dynamically compile at the root node the evaluation function with only those features that might still apply (so leaving out bishop code if all bishops have already been captured). Instead of dynamic compilation one could also precompile a dozen evalution functions with various features on and off, then pick the one you need at the root of the search. (It would of course not make sense to select an appropriate evaluation function at every node of the tree. It might make sense to select one at nodes a few ply from the root, to be used in the node's subtree.)

The gain is probably too small for the (programming) effort. When programs cannot be improved anymore by algorithmic changes or better data structures or coding, this might be the way to extract the last few ELO points.

How is that going top work when you can promote TO a bishop in the search. This is a decision that can only be made dynamically, at the point where an evaluation is needed.