Are there any strategies or methods to test the search algorithm? I have used Perft to test my move generation, and all is fine with that. But I have just completed my (parallel) search function and I'd like to reassure myself that it is actually doing what is expected. I added a few lines to my code to print out the move list at a node at a certain ply, to check if it generates the moves in a sensible order, and it does do something a little unexpected.
I am only using a very simple evaluation at this stage though (just material and piece-square scoring -- I find it amazing that even such a simple evaluation function can actual make it play moves that you might see in an actual game), so it may well be perfectly ok, and it may just be that my poor human brain can't work out what it's doing. I have a feeling, but I was hoping for any tips/suggestions for an actual empirical test of the algorithm, rather than just guessing or playing thousands of games.
Search algorithm testing
-
hyatt
- Posts: 1242
- Joined: Thu Jun 10, 2010 2:13 am
- Real Name: Bob Hyatt (Robert M. Hyatt)
- Location: University of Alabama at Birmingham
- Contact:
Re: Search algorithm testing
probably the simplest starting point is to find some easy mate positions and run them one at a time. Look at the depth where you see the mate and then evaluate whether or not that looks reasonable. That eliminates evaluation entirely. You could also do the same for some forced 3-fold repetition positions to make sure you see those at the depth you expect...
Re: Search algorithm testing
Ok, thanks, I'll try that. I still have to implement a 3 fold repetition thing, but I have done that before -- should be no trouble.
The thing that it is doing is:
Program is black. I added some code to print out the move list at ply 1 during blacks turn (so white's reply) and A2-A3 keeps appearing high in the move list after black's first move in the opening. Sometimes it appears as the hash move -- i.e. it caused a beta cut-off at ply 1. I can kind of believe why A2-A3 might be a reasonable killer move in the opening to ward off the bishop pin of the knight against the king, but not why it would cause a beta cut-off at ply 1.
It only does this after a particularly bad move by black though, like moving the f pawn. My feeling is that it does this because A2-A3 is the first move that would be generated by my move generator in the absence of any move ordering, and that would be sufficient to refute the bad move by black. My counter argument to this though is that I am not sure if the complexity of my evaluation is sufficient for the program to know that moving the f pawn during the opening is bad; at present, I'm only searching to depth 8.
The thing that it is doing is:
Program is black. I added some code to print out the move list at ply 1 during blacks turn (so white's reply) and A2-A3 keeps appearing high in the move list after black's first move in the opening. Sometimes it appears as the hash move -- i.e. it caused a beta cut-off at ply 1. I can kind of believe why A2-A3 might be a reasonable killer move in the opening to ward off the bishop pin of the knight against the king, but not why it would cause a beta cut-off at ply 1.
It only does this after a particularly bad move by black though, like moving the f pawn. My feeling is that it does this because A2-A3 is the first move that would be generated by my move generator in the absence of any move ordering, and that would be sufficient to refute the bad move by black. My counter argument to this though is that I am not sure if the complexity of my evaluation is sufficient for the program to know that moving the f pawn during the opening is bad; at present, I'm only searching to depth 8.
-
hyatt
- Posts: 1242
- Joined: Thu Jun 10, 2010 2:13 am
- Real Name: Bob Hyatt (Robert M. Hyatt)
- Location: University of Alabama at Birmingham
- Contact:
Re: Search algorithm testing
About all I can suggest is to add code to print the tree as it is searched, particularly scores and bounds. If you PST arrays are using very small values, then this might end up being pretty random as far as evaluations go.