More on legal move generation

[jwes]

I changed crafty 21.6 to count the number of times the Check function (macro) is called and the total number of moves generated. I ran two quick tests and got these figures:

Bratko-Kopec - Check called 3,124,087,357 times, 3,092,715,884 moves generated, 2,289,587,972 nodes
One game - Check called 5,180,932,688 times, 5,068,870,121 moves generated, 3,786,496,761 nodes

One of the arguments against legal move generation is that it is a waste of effort to validate moves that are not made. These figures show that a legal move generator does not have to be extremely efficient before it is better than calling Check on each move as it is made.

[Michael Sherwin]

But, Bob's argument (part of it anyway) was that he does not have a check function for testing legality and Crafty's check function is only for assigning extentions. Bob says, that Crafty uses its move generator to detect capturing the other sides king and then switching to check evasion code when check is detected.

[bob]

I changed crafty 21.6 to count the number of times the Check function (macro) is called and the total number of moves generated. I ran two quick tests and got these figures:

Bratko-Kopec - Check called 3,124,087,357 times, 3,092,715,884 moves generated, 2,289,587,972 nodes
One game - Check called 5,180,932,688 times, 5,068,870,121 moves generated, 3,786,496,761 nodes

One of the arguments against legal move generation is that it is a waste of effort to validate moves that are not made. These figures show that a legal move generator does not have to be extremely efficient before it is better than calling Check on each move as it is made.

I don't follow your logic. It is _much_ harder to generate legal moves than to generate pseudo-legal moves. The cost for check testing has to be pretty high to outweigh the cost of generating legal moves, particularly over the course of a real game where checks are not as common and pseudo-legal moves are legal most of the time...

One quick bit of analysis is to determine how much time is spent in Check(). It is not very much. Attacked() is the name of the function you want to look for in the profile data...

[jwes]

I changed crafty 21.6 to count the number of times the Check function (macro) is called and the total number of moves generated. I ran two quick tests and got these figures:

Bratko-Kopec - Check called 3,124,087,357 times, 3,092,715,884 moves generated, 2,289,587,972 nodes
One game - Check called 5,180,932,688 times, 5,068,870,121 moves generated, 3,786,496,761 nodes

One of the arguments against legal move generation is that it is a waste of effort to validate moves that are not made. These figures show that a legal move generator does not have to be extremely efficient before it is better than calling Check on each move as it is made.

I don't follow your logic. It is _much_ harder to generate legal moves than to generate pseudo-legal moves. The cost for check testing has to be pretty high to outweigh the cost of generating legal moves, particularly over the course of a real game where checks are not as common and pseudo-legal moves are legal most of the time...

One quick bit of analysis is to determine how much time is spent in Check(). It is not very much. Attacked() is the name of the function you want to look for in the profile data...

I tried this on Bratko-Kopek and got these numbers:

Code: Select all

total time........................       14:27
Check ............................        1:14
Movgen ...........................        1:45

I don't know how much slower a legal move generator is. Another idea is a move generator that also determines if a move gives check. This can be done while adding only a few percent to the movegen time.

[ilari]

Another idea is a move generator that also determines if a move gives check. This can be done while adding only a few percent to the movegen time.

This is exactly what I've done in Sloppy. I use the information mainly for move ordering, extensions and reductions. Doing this takes about 7% of cpu time.