I'm not sure I understand your numbers. but the issue is this: A legal move generator does more work screening out illegal moves as it produces the list. It does this extra work for _every_ move that is generated. Crafty Doesn't do the in check test on at least 1/2 of the moves generated, because for two consecutive plies, you look at all moves at one of them, and just one move at the other...jwes wrote:I ran some stats on crafty and got thisbob wrote:Actually that is _the_ point. AKA procrastination. I only check for legality when I actually have to make the move on the board, In fail-high (CUT) nodes, I generally search just one move and only legality-check that move (if not already in check).Edsel Apostol wrote:We're doing almost the same except that you make the move before determining if that still leaves the king hanging and therefore leads to an illegal position while my implementation is that I check before making the move if it is legal, thereby saving me the call to unmakemove if it is indeed illegal. It doesn't really matter anyway as most pseudo-moves are legal.
In the case of hash moves and killer moves, I have a routine to check if it is a valid move for that position, therefore it is safe from hash collisions as it makes sure that the move is valid, after that I double check with calling moveIsLegal and that should never leave the king hanging. It's pretty safe, I have not experience any crash or something due to illegal move, it's what Glaurung and Fruit is doing too. Glaurung even uses this technique to avoid using locks in the transposition table as the hash move is being validated anyway.
When in check I also have a legal move generator just like in Crafty and I don't call any move validation for that routine also.
check called/moves generated = 1.09, check called/moves made = 1.54 , check called/incheck = 13.62
This makes a legal move generator look better, as it may be expensive, but I doubt it is more expensive than calling incheck 30 times.
I tried it both ways when I first started Crafty. In fact I tried three approaches...
1. Just use pseudo-legal moves and in-check each one as it is actually made on the game board.
2. Do legal move generation. This was actually pretty easy in early versons of Crafty since I had the attacks_from and attacks_to bitboards handy. But this was slower.
3. use 1 above plus a legal move generator when in check. This has the added benefit of not trying illegal moves when most moves are illegal. This was the fastest approach I found and is what I use today.
A legal move generator has two isues.
(1) generating moves when not in check requires checking along a specific rank/file/diagonal that bears on the king, if a piece is moved from that diagonal/rank/file.
(2) generating moves when in check is a completely different animal because the move has to either remove the checking piece, or interpose on the rank/file/diagonal if checked by a sliding piece, or move the king. The GenerateCheckEvasions() code in crafty is a bit complex to think about but is not that big in terms of lines of code.
Different data structures might make my approach worse for other programs of course. But I've spent years trying to find the fastest solution for each performance issue identified in Crafty.