Why my perft nps lower than usual nps ?

[Chan Rasjid]

Sven,

You are spot on. I found it independently, but too slow.

Code: Select all

...

So it could mean my ordering of neutral moves is too elaborate.

I can think of a possible reason why your original version failed. It is a common mistake, or let's call it "bad programming habit", to write big functions that serve for more than one purpose at once. In your case, your gen_all() function includes both move generation *and* move ordering, and it is also used for illegal move detection. By separating these issues you gain much more flexibility. It may turn out that the performance of perft() is much less crucial than the performance of your regular search, but nevertheless it can often be considered a design flaw to put too much functionality into one function, simply because that function becomes too specialized and is not easy to reuse at other places. Every time you want to use gen_all() you have to buy everything it includes, even if you don't like it. In your case, gen_all() was in fact not reusable for perft without accepting major drawbacks due to useless generation and ordering of irrelevant neutral moves.

As to your new implementation, I would still consider it as kind of an "intermediate" solution since I expect that your genqs() function includes move ordering, too, which has zero meaning for perft due to absence of alpha-beta. I would separate the ordering and the generation parts for both gen_all() and genqs(). Furthermore, I still think that legality check can be done much simpler and faster than by generating all capture moves. But maybe you are currently in a situation where you want to postpone "optimizations". (Having made perft faster by a factor of >10 may indeed be more than an "optimization", in this case I think you simply use a superior algorithm.) So separating ordering from generation can be useful, using a faster legality check is kind of "optional".

For your regular search, can you explain briefly how gen_all() works? Do you generate moves piece by piece and calculate ordering data immediately when a move is generated, stopping in the middle when generating a king capture?

Sven

My basic generation functions are genqs() and gen_neutral(). gen_all() is not used in my critical search() except for mate_search() and elsewhere like UCI move validation and debug autoplay. Coming to mate_search() means the game is won so this mate_search() is very simple and would not be a drag even if "transplated" to Rybka 4! - or it might give it another 10 elo!

Code: Select all

// the basic generation functions are genqs() and gen_neutral()
// prototype
move_t validate_partialmove(move_t move, int side);
move_t *genqs_all(move_t *m, const int s, const u64 k_brAttack[]);
move_t *genqs(move_t *m, const int side, const u64 k_brAttack[]);
move_t *gen_neutral(move_t *move, const int s, const u64 k_brAttack[], int *phase, const int gen_part);
int gen_root_move(rootmove_t *rootmove, check_t *check_s, const int side);
move_t * gen_all(move_t *move, const check_t *check_s, const int side);
move_t *gen_evade_check(move_t *m, const check_t *check_s, const int s);


move_t *gen_all(move_t *move, const check_t *check_s, const int side) {
   if (!check_s->type) {
      // !!! ugly k_brAttack[3]  - currently only used in gen_neutral for gen() brq check
      u64 k_brAttack[3];
      k_brAttack[0] =  ROT_DIAG7(king[side^1]) | ROT_DIAG9(king[side^1]);
      k_brAttack[1] = ROT_FILE(king[side^1]) | ROT_RANK(king[side^1]);
      k_brAttack[2] = k_brAttack[0] | k_brAttack[1];
      if ((move = genqs_all(move, side, k_brAttack)) != NULL) {
         // !!! incremental full generation likely not a good idea; currently disabled 
         int p = PhaseNeutralStart;
         move = gen_neutral(move, side, k_brAttack, &p, 0);
      }else {/* invalid, capt King */
         return NULL;
      }
      assert(*move == 0);
   }else {
      if (!is_sq_attacked_brq(king[side^1], side));
      else {/* invalid, capt King */
         return NULL;
      }
      move = gen_evade_check(move, check_s, side);
      assert(*move == 0);
   }
   
   return move;
}

I don't know why my info says I joined CCC in March 2006. I think I joined earlier, probably 2003 and was active for a while as I had many questions. I do learn a lot here and have read and are aware of most of the basics of chess programming. I consider my current engine "mature". The only things or the thing missing, of course, is the ELO not reaching that of ROBBOLITTO, "THE CLONE ". Imagine my earlier engine (before I come here) with a full transposition table had a hard time keeping up with TSCP! I got a lot of hint's here, just as Vasik Rajlich did ??? My engine could play a 100+ games in debug auto play mode without an assert() being triggered and it is very important - I have assert()s at every corner! I think only after a program is bug free can we think about other things (there of course is another simpler route ... ). I think I can now start thinking.

Move validation has been well covered in the past here. Most of the mature programs should have settled with a choice though "micro" optimization could still be done. My current method is that used by Crafty, king capture in the next node, unless it has switched camp. Now that you mentioned about validation, I might want to re-consider validation before "making" the move. Behind my mind, I seem to see now that I have all the functions that could make it slightly better and not hard to implement. I will think a little.

My engine is bitboard. For gen_qs(), the moves includes all captures, ep and promote. The sliding pieces are the first to be generated as, in my implementation, only these can do a king capture. It ranges through the B/R/Q bitboards for the pieces. On capture of a king, it returns, otherwise it packs the move with ordering info in the same integer-32. K/N/P capture of king is done when the king moves and it is cheap to check if it counter-threat any K/N/P through pre-calculated board[64]->kMap/nMap/pMap[2 sides]. Intuitively, I think my move generation cannot be "better". The only thing is how much to put into move ordering for non-captures. I expect all programs to be as efficient in the plain move generation part.

As for perft, I want only to use the real generator as perft is meant for it. I don't want to do even the slightest editing just in case bugs might enter hiding other real bugs. I would like to compare nps with other engines - don't know if Crafty or other engines can run perft through a command line.

BTW, Sven, have you a released version of your program (if you don't have one !!!) in linux. I want programs for testing.

Rasjid

[Sven]

Thanks for providing these code snippets. I'll have a look at these tomorrow.

I don't know why my info says I joined CCC in March 2006. I think I joined earlier, probably 2003 and was active for a while as I had many questions.

Technical reasons, I think it was a provider change causing the user database to be set up from scratch. You'll therefore see nobody here with a joining date earlier than 2006.

I do learn a lot here and have read and are aware of most of the basics of chess programming. I consider my current engine "mature". The only things or the thing missing, of course, is the ELO not reaching that of ...

Same problem here

My engine could play a 100+ games in debug auto play mode without an assert() being triggered and it is very important - I have assert()s at every corner!

I think I can compete with that (at least five at every corner)

Move validation has been well covered in the past here. Most of the mature programs should have settled with a choice though "micro" optimization could still be done. My current method is that used by Crafty, king capture in the next node, unless it has switched camp.

Crafty using king capture method? Not that I know of. After making a move, it checks whether the king has been left in check without generating moves, just by checking attacks to the king square. This is not the "king capture" method. Since also your engine is a bitboard engine, I wonder why you do not do the same, which would be straightforward and would have great potential to simplify your code.

On capture of a king, it returns, otherwise it packs the move with ordering info in the same integer-32. K/N/P capture of king is done when the king moves [...]

That surprises me, does that mean that your move generator does not detect all illegal moves? But then you would not be able to use that for your perft since there an illegal move is only found by returning NULL from the move generator?

BTW, Sven, have you a released version of your program (if you don't have one !!!) in linux. I want programs for testing.

I did not release a Linux version of Surprise officially. And currently I can't produce one from the old sources. Maybe Volker Pittlik has a Linux version, some time ago he made one for me.

Sven

[Chan Rasjid]

Thanks for providing these code snippets. I'll have a look at these tomorrow.

Crafty using king capture method? Not that I know of. After making a move, it checks whether the king has been left in check without generating moves, just by checking attacks to the king square. This is not the "king capture" method. Since also your engine is a bitboard engine, I wonder why you do not do the same, which would be straightforward and would have great potential to simplify your code.

On capture of a king, it returns, otherwise it packs the move with ordering info in the same integer-32. K/N/P capture of king is done when the king moves [...]

That surprises me, does that mean that your move generator does not detect all illegal moves? But then you would not be able to use that for your perft since there an illegal move is only found by returning NULL from the move generator?

Sven

Just so there is no mis-understanding, the "king-capture" validation of the move is this:
1) do a makemove() for move MMM
2) call search()
3) now do a gen_move() starting with Q/R/B captures. It the xside king of this node could be captured (within the move generation), then the last move made MMM is invalid. gen() stops search() returns INFI so that back at the parent node, it can now be ascertained MMM is invalid.

I remember clearly Bob then was supporting using this method and I still agree. If Crafty now has switched method, I do not know. I still think this method could be "sufficiently" efficient for most programs. The reason is rarely do we have such "discovered-check" type of illegal moves. Testing for legality of a move could be done actually fairly efficiently even w/o make()ing it - BUT THE COST TO TEST IS NEVER ZERO. Most of the time a move is legal and we finally have to make() and in the next node do a gen_move(). So why not delay testing and do it within gen_move()? An accumulated cost of "additional" testing per move make() may be appreciable. So this is the efficiency of the "king-capture" method.
Bob could have tested if such a method adds or take away 5 elo points!

But I would still think about what you have pointed out just in case I miss something

PS: A very good way to know if this method is efficient is by way of ipp* .... I don't know howto read codes by others!

Rasjid