Winboard Forum

Hi,

It would be helpfull if there was data available on the wiki which help you verify if your minimax/negamax/alphabeta/etc implementation is correct.

What I propose is calculate the optimal move
- with the regular shannon algorithm, e.g. as described at http://en.wikipedia.org/wiki/Evaluation_function
- no pruning or anything
- for e.g. 1 ply, 2...6 plies

When this information is available, a chess programmer can verify that his/her implementation of minimax/etc is correct so that he/she can safely proceed with implementing the more interesting stuff.

Unfortunately, that requires a whole new set of hoops to jump through to make your evaluation function compliant for testing, because you have to make your engine comply exactly to a "random" set of constraints.

There are implementation issues with the Shannon algorithm as described on that page that you may not want to waste time on. For example, mobility is defined as the number of legal moves, rather than pseudolegal, requiring me to do an extra legality check in the evaluation that I wouldn't otherwise. Also, many items, like center control aren't defined in that particular reference, and I have to put in extra work to make sure that my definition of "doubled pawn", etc. matches exactly. A lot of extra work that then gets thrown away.

Robert,

That's not what I'm suggesting.
I propose that a wiki-page is created with calculated data to test the tree routines. Testcases for the tree.
The implementation of the alpha beta/negamax/etc. algorithms, not the evaluator.
So that's why I suggest to use a really simple evaluator that only looks at the number of pieces, the number of possible moves, etc.

I'm hoping that some day the wiki will contain enough of these verification pages so that people have to spend less time debugging code that has been implemented a thousand times so that they can focus more on the idea they want to try.

I'm not suggesting ready-made code, I'm suggesting testcases so that one can verify that the implementation they did is indeed correct.

Especially usefull since sometimes bugs give better playing chess engines (from what I've read in the local computer chess magazine) making it more difficult to determine that indeed there's a bug.

I hope I made myself clear, not my native language etc

Right, but in order to test the tree routines, my engine has to have the exact same specification for my evaluation function as the generating program does. The page that you link to has factors like center control, isolated pawns, mobility (legal vs. pseudo-legal), that you have to program in exactly in order to be able to test against the posted solutions. If your results don't match, is your search routine wrong, or did you make a mistake in programming the evaluation? Now you have two things to debug.

Also, for anything beyond the trivial minimax, the only thing you can check against is the returned score, because the order in which the moves are searched affects the tree shape. If you use a simple evaluation, then you will often return the exact same score even if the search algorithm is flawed, because so many positions return the same score (e.g. material is even). If you use a more complicated evaluation, you're back to the first problem. Plus I'm spending time writing and testing an evaluation function that I don't intend to use for real.

And then, once you get past the basic minimax/negamax/alphabeta algorithms, you lose the ability to do even these types of comparisons, since so many things interact with each other. So the scope is very narrow - you're only testing about 20 lines of code that you can practically copy and paste from Bruce Moreland's web pages.

Good testbeds of perft are critical to getting your program on your feet. Sample positions of "you need a working hashtable to find the mate" are helpful. I would be all for better pseudocode on implementing fail-hard vs fail-soft on the Wiki.

But a testbed for minimax or alphabeta feels like going to the store to buy a sledgehammer when you want to put a pushpin on the bulletin board. Really you can just push it in with your thumb.

Edited to add: Sorry if I came off sounding harsh here. Even if I don't think it's workable, it was a good question to raise.

ok