Help Needed Interpreting Profiler Output!

[syzygy]

I'm not saying that checking legality before making a move can't help for a normal search, but my point is that a perft and an alpha-beta search are very different in this respect.

At the leaves of a perft, you only want to know if a move is legal or not:

Code: Select all

  if (move_is_legal) perft_count++;

The naive way of implementing this is:

Code: Select all

  make_move(move);
  if (king_not_in_check) perft_count++:
  unmake_move(move);

Any move legality check that is better than this will improve your perft speed. You will win time for every move.

When you perform an alpha-beta search, it is entirely different. What you want is:

Code: Select all

  if (move_is_legal) {
    make_move(move);
    ...
    unmake_move(move);
  }

The naive way of implementing this is:

Code: Select all

  make_move(move);
  if (king_not_in_check) {
    ...
  }
  unmake_move();

The majority of moves are legal, so for the majority of moves this naive implementation is at least close to optimal. If your alternative move legality check is not highly optimised, the alternative costs more time for the majority of moves. For a minority of moves you will win back some time. I'm sure it is possible to make this an overall win, but you need to work hard.

For perft you don't need to work hard at all to win time using a legality check other than the naive one. Any alternative check that is cheaper than make_move plus check whether king is in check plus unmake_move is a guaranteed win.

[tpetzke]

I'm not saying that checking legality before making a move can't help for a normal search, but my point is that a perft and an alpha-beta search are very different in this respect.

Yes, I fully agree. I'm not doing it this way to speed up my perft. It just makes my code a bit cleaner.

Since making/unmaking a move is not so cheap in my program
- updating the hashes
- updating the piece bitboards and utility bitboards
- creating a history record
- check for repetition and set the 3-fold repetition flag
- testing and set a flag whether on the new board the new side to move is now in check

it is overall at least not a loss in my program if I perform some legal checks unnecessarily but avoid making unnecessary moves.

So I just introduce a bit of diversity in the engine universe in the middle field. Because there is certainly a lack of that at the top.

Thomas...

[Sven]

The majority of moves are legal, so for the majority of moves this naive implementation is at least close to optimal.

Your conclusion is wrong since the majority of legal moves does not need any "is king left in check" test to find out that they are legal.

If your alternative move legality check is not highly optimised, the alternative costs more time for the majority of moves. For a minority of moves you will win back some time. I'm sure it is possible to make this an overall win, but you need to work hard.

This is wrong, too, in my opinion. There is no need for a "highly optimised" legality check, it needs just those things that I already mentioned a couple of times. The big saving is (and that has not been my own idea but is well-known for many years already) to fully skip the "is king left in check" for most moves. And that is cheaper than the "naive method" for legal as well as illegal moves, for perft as well as normal search.

No hard work involved at all, unless you consider maintaining a separate evasion generator and calculating all pinned pieces as hard work But the concept also works without such an evasion generator, it may only be less efficient in that case.

Sven

[syzygy]

No hard work involved at all

What is hard is subjective, but do you at least acknowledge that there is a huge difference between perft and alpha/beta search in respect of the potential benefit of move legality checking (as opposed to make/check/unmake)? This difference is not subjective.

For the rest, yes I do consider that efficiently keeping track of the different cases of evasions / non-evasions / pinned pieces / non-pinned pieces / etc. and handling them all correctly requires a significant effort compared to the effort of creating a correct move generator that does not do all that. If you're a beginner desiring to create a functional chess engine, going for an optimised perft by gaining a bit on this side (which will improve perft times but not so much if at all the search) is not necessarily the best way to go forward.

[Sven]

No hard work involved at all

What is hard is subjective, but do you at least acknowledge that there is a huge difference between perft and alpha/beta search in respect of the potential benefit of move legality checking (as opposed to make/check/unmake)? This difference is not subjective.

Well, before reading your last sentence I was tempted to reply "what is huge is subjective"
Indeed there is a difference, of course. But I see enough benefit for the normal search as well to be sure that this difference is not negligible.

If you're a beginner desiring to create a functional chess engine, going for an optimised perft by gaining a bit on this side (which will improve perft times but not so much if at all the search) is not necessarily the best way to go forward.

You are absolutely right, it's not suitable for "beginners". But it is suitable for someone who has a working engine, sufficient chess programming knowledge and good programming skills, wants to improve his engine a little bit, and knows that no "huge" ELO gain can be expected from it.

Another point: sometimes a very inefficient perft implementation (I don't say this was the case here) is accompanied by similar less efficient elements of the normal search. For instance, obviously both access the same move generator and make/unmake functions (otherwise perft would not make any sense as a testing procedure), so any substantial performance improvement in these components should be beneficial for perft and search as well. Readers should note the word "substantial" since many small speedups of the move generator show no measurable gain in strength because of the small portion that an engine spends within the move generator, but introduce potential risks.

Sven

[syzygy]

No hard work involved at all

What is hard is subjective, but do you at least acknowledge that there is a huge difference between perft and alpha/beta search in respect of the potential benefit of move legality checking (as opposed to make/check/unmake)? This difference is not subjective.

Well, before reading your last sentence I was tempted to reply "what is huge is subjective"
Indeed there is a difference, of course. But I see enough benefit for the normal search as well to be sure that this difference is not negligible.

What do you mean by the last sentence? There is a fundamental difference between the benefit of legality checking for perft and that for alpha/beta. That with a proper implementation there can be "enough benefit" for the normal search has little to do with this difference (and certainly does not turn it from negligible to not negligible).

If you're a beginner desiring to create a functional chess engine, going for an optimised perft by gaining a bit on this side (which will improve perft times but not so much if at all the search) is not necessarily the best way to go forward.

You are absolutely right, it's not suitable for "beginners". But it is suitable for someone who has a working engine, sufficient chess programming knowledge and good programming skills, wants to improve his engine a little bit, and knows that no "huge" ELO gain can be expected from it.

Of course, otherwise engines such as Stockfish wouldn't be doing it.

Another point: sometimes a very inefficient perft implementation (I don't say this was the case here) is accompanied by similar less efficient elements of the normal search. For instance, obviously both access the same move generator and make/unmake functions (otherwise perft would not make any sense as a testing procedure), so any substantial performance improvement in these components should be beneficial for perft and search as well.

But exactly this may very well break down when you move from make/test/unmake to a (suboptimal) move legality testing. The suboptimal move legality testing will still easily improve perft times. It will not speed up the search.