Perft speed

[ericlangedijk]

You can have a look at the sourcecode of crafty to see how it's done. The code is in option.c

[Kempelen]

You can have a look at the sourcecode of crafty to see how it's done. The code is in option.c

I have seen at the Crafty code that legality check is computed at search():

Code: Select all

/************************************************************
 *                                                          *
 *   Now iterate through the move list and search the       *
 *   resulting positions.  ...
 
 ...
 
  while ((tree->phase[ply] =
          (ply > 1) ? ((tree->inchk[ply]) ? NextEvasion(tree, ply,
                  wtm) : NextMove(tree, ply, wtm)) : NextRootMove(tree, tree,
              wtm))) {

	......
			  
    MakeMove(tree, ply, tree->curmv[ply], wtm);
    if &#40;tree->inchk&#91;ply&#93; || !Check&#40;wtm&#41;)                  <-check_legal
		do &#123;
		   ....
	
		&#125;
	&#125;
  &#125;
  

Also, in quiesce() the routine for legal check is similar to in search.

This change the ways to compare perf times. I.e. my engine checks if the move is legal before returning makemove (it return true or false if the move is legal). Crafty perf time does not take into account this issue so I can't compare times.

I suppose Crafty does so because efficient matters, as before Check() it tests for 'tree->inchk[ply]' with I suppose is a kind of check-cache (which I dont know how it works).

[Pablo Vazquez]

You can have a look at the sourcecode of crafty to see how it's done. The code is in option.c

I have seen at the Crafty code that legality check is computed at search():

Code: Select all

/************************************************************
 *                                                          *
 *   Now iterate through the move list and search the       *
 *   resulting positions.  ...
 
 ...
 
  while ((tree->phase[ply] =
          (ply > 1) ? ((tree->inchk[ply]) ? NextEvasion(tree, ply,
                  wtm) : NextMove(tree, ply, wtm)) : NextRootMove(tree, tree,
              wtm))) {

	......
			  
    MakeMove(tree, ply, tree->curmv[ply], wtm);
    if &#40;tree->inchk&#91;ply&#93; || !Check&#40;wtm&#41;)                  <-check_legal
		do &#123;
		   ....
	
		&#125;
	&#125;
  &#125;
  

Also, in quiesce() the routine for legal check is similar to in search.

This change the ways to compare perf times. I.e. my engine checks if the move is legal before returning makemove (it return true or false if the move is legal). Crafty perf time does not take into account this issue so I can't compare times.

I suppose Crafty does so because efficient matters, as before Check() it tests for 'tree->inchk[ply]' with I suppose is a kind of check-cache (which I dont know how it works).

I think that's just to save some time. If 'tree->inchk[ply]' is true, it means that the side to move was in check before making the move, so only legal evasions were generated and you don't need to verify that you leave your king in check after the move is made.

[bob]

I know NPS is not everything but some basic speed would be nice.
Perft(6) takes 14 seconds here. 3 times as slow as Crafty's...
Well I'm working on it

Just don't forget Amdahl's law. If your move generation is only 10% of total search time, speeding it up so that it is only 5% is not a very big gain... Even though it is going twice as fast..

[bob]

Some engines hash perft counting, so keep that in mind when you do comparisons.

Correct. Here are a couple of examples from Crafty, starting position. Core-2 duo laptop (2.53ghz):

model name : Intel(R) Core(TM)2 Duo CPU P9600 @ 2.53GHz

perft 5: total moves=4865609 time=0.22

perft 6: total moves=119060324 time=5.36


No hashing or other tricks inside Crafty... it was never intended to be a speed test, but was a "correctness test" instead...

Bob, do you a checklegal() into makemove() or into the search()?

I do it separately, in Search(). I do it right after MakeMove(), obviously, but I kept it separate to make the code more manageable. This means I have to do it inside perft as well...

[bob]

As far as I could see Bob (Crafty) generates captures first. Then if a king is taken there the result is discarded.

This is in the q-search only. In the full search, you will find this:

Code: Select all

    MakeMove(tree, ply, tree->curmv[ply], wtm);
    tree->nodes_searched++;
    if (tree->inchk[ply] || !Check(wtm))
      do {

That dangling "do {" is the main body of the search. After the matching "}" I UnmakeMove() and continue to the next one, if there is one.

[bob]

You can have a look at the sourcecode of crafty to see how it's done. The code is in option.c

Aha, so you are talking about perft... That code was written well before the current search, back then I used the "capture the king" trick everywhere to detect that the king was left in check and the move was illegal. When I added null-move, you can't do that, because you don't want to do a null-move if you are in check, it causes the check to be incorrectly evaluated.

[bob]

You can have a look at the sourcecode of crafty to see how it's done. The code is in option.c

I have seen at the Crafty code that legality check is computed at search():

Code: Select all

/************************************************************
 *                                                          *
 *   Now iterate through the move list and search the       *
 *   resulting positions.  ...
 
 ...
 
  while ((tree->phase[ply] =
          (ply > 1) ? ((tree->inchk[ply]) ? NextEvasion(tree, ply,
                  wtm) : NextMove(tree, ply, wtm)) : NextRootMove(tree, tree,
              wtm))) {

	......
			  
    MakeMove(tree, ply, tree->curmv[ply], wtm);
    if &#40;tree->inchk&#91;ply&#93; || !Check&#40;wtm&#41;)                  <-check_legal
		do &#123;
		   ....
	
		&#125;
	&#125;
  &#125;
  

Also, in quiesce() the routine for legal check is similar to in search.

This change the ways to compare perf times. I.e. my engine checks if the move is legal before returning makemove (it return true or false if the move is legal). Crafty perf time does not take into account this issue so I can't compare times.

I suppose Crafty does so because efficient matters, as before Check() it tests for 'tree->inchk[ply]' with I suppose is a kind of check-cache (which I dont know how it works).

I think that's just to save some time. If 'tree->inchk[ply]' is true, it means that the side to move was in check before making the move, so only legal evasions were generated and you don't need to verify that you leave your king in check after the move is made.

That's correct. I extend when I give check, not when I escape check, so when I check and extend, at the next ply I don't need to do the legality check. If in_check[ply] is true, then I used GenerateCheckEvasions() which only generates legal moves, making the legality check unneeded. None of this is used for perft of course...

[ericlangedijk]

I don't see much more optimization.
- I don't do anything special when there are 2 processors.
Could this be a factor?
- and what about the processor cache? how to make the most hits?
- stack is slow?

I'm not much of a hardware scientist... so any tips and tricks for optimizing are welcome.