Search algorithm testing

Code, algorithms, languages, construction...
Post Reply
ppyvabw
Posts: 29
Joined: Sat Nov 01, 2014 12:51 am
Real Name: Adam

Search algorithm testing

Post by ppyvabw » Wed Nov 04, 2015 1:17 am

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.

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

Post by hyatt » Wed Nov 04, 2015 5:25 pm

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...

ppyvabw
Posts: 29
Joined: Sat Nov 01, 2014 12:51 am
Real Name: Adam

Re: Search algorithm testing

Post by ppyvabw » Fri Nov 06, 2015 12:52 am

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.

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

Post by hyatt » Fri Nov 06, 2015 4:55 am

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.

Post Reply