How to test an alpha beta implementation?

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
jesper_nielsen

How to test an alpha beta implementation?

Post by jesper_nielsen » Fri Sep 14, 2007 6:15 pm

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

Dann Corbit
Posts: 11169
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: How to test an alpha beta implementation?

Post by Dann Corbit » Fri Sep 14, 2007 6:40 pm

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.


User avatar
hgm
Posts: 24619
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: How to test an alpha beta implementation?

Post by hgm » Fri Sep 14, 2007 7:17 pm

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.

Post Reply