Hello All You Smart People!
I have recently started re-writing my chess engine, and this time, i have decided to develope a lot of test methods for it, before adding any complexity.
So right now i have a simple move generator.
A very simple piece square table and material evaluation.
And a straight alpha-beta search with a simple quiescent search also.
Nothing else.
The move generator is tested using a lot of known perft values for various positions.
The evaluation is verified to be at least symmetrical by a simple test reading epd files and reversing the positions, comparing the evaluations.
But what about the search??
Is it possible to verify the correctness of the alpha-beta implementation?
As it is now, it is simple, but when null move, pvs, extensions, lmr, etc. is added, it becomes incresingly complex to verify it.
My thoughts so far is to dump the search to a file, and then writing a "tree-viewer" for it and basically go it over by hand.
Is there an alternative/better/easier way to test/verify a search implementation?
Kind regards,
Jesper
How to test an alpha beta implementation?
Moderators: hgm, Rebel, chrisw
-
Dann Corbit
- Posts: 12540
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: How to test an alpha beta implementation?
Some people have already written tree viewers. I think Remi did one.
Just write a super simple mini-max and comare the results.
You should get exactly the same answers with alpha-beta as mini-max at the same depth (unless you add pruning like null move or history reductions which can change the answers).
For depths more than 6 it isn't practical, but it is a very good indication that the algorithm is working.
Finally, if you get puzzled, just post your code here and some smart chess programmers will look it over and tell you if it is OK or if you went off somewhere.
Just write a super simple mini-max and comare the results.
You should get exactly the same answers with alpha-beta as mini-max at the same depth (unless you add pruning like null move or history reductions which can change the answers).
For depths more than 6 it isn't practical, but it is a very good indication that the algorithm is working.
Finally, if you get puzzled, just post your code here and some smart chess programmers will look it over and tell you if it is OK or if you went off somewhere.
-
Dann Corbit
- Posts: 12540
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
-
hgm
- Posts: 27801
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: How to test an alpha beta implementation?
What I did was the following:
First suppress the beta cutoffs, and count the horizon nodes, to see if you reproduce the perft results. (E.g. if move sorting is done correctly, and does not cause duplicates or moves to go missing.)
Then enable the beta cutoffs, and use 'fail hard'. This makes you very sensitive for faulty cutoffs, as the score returned for a failing move is just at the edge where it would be chosen. If there is an error in your cutoffs, it will almost immediately lead to playing of non-sensical blunders, like latting capture high pieces, or overlooking mate in one.
First suppress the beta cutoffs, and count the horizon nodes, to see if you reproduce the perft results. (E.g. if move sorting is done correctly, and does not cause duplicates or moves to go missing.)
Then enable the beta cutoffs, and use 'fail hard'. This makes you very sensitive for faulty cutoffs, as the score returned for a failing move is just at the edge where it would be chosen. If there is an error in your cutoffs, it will almost immediately lead to playing of non-sensical blunders, like latting capture high pieces, or overlooking mate in one.