Page 1 of 1
Test data for basic (reverse) move generation?
Posted: Sat Mar 30, 2013 3:44 am
by RexButler
Is there anywhere I can find test data for the (admittedly simple) problem of move generation, stepping both 1 ply forwards or -backwards-? I had something in the form of FEN strings in mind, but the exact format is not important. I'm looking for such data because I'm building a simple GUI program and want to test my move generation. I don't want to assume by move generation algorithm works by inspection only (especially in the retrograde case). In each case, I would consider good test data to have at least 10-15 starting positions for various sorts.
If I can't find such data, I may just have to take it up as a mini project and post it here.
Thanks much!
Re: Test data for basic (reverse) move generation?
Posted: Mon Apr 01, 2013 8:09 pm
by User923005
Every open source chess program will have a move generator. You will have to be careful though, because some chess programs have move generators that make pseudo-legal moves and only test them later.
Here are some stand-alone move generator projects with source code (look for perft):
http://home.hccnet.nl/h.g.muller/dwnldpage.html
http://members.ziggo.nl/allard.siemelin ... index.html
http://home.arcor.de/dreamlike/chess/
A google search for "perft chess" will probably be helpful.
Re: Test data for basic (reverse) move generation?
Posted: Wed Jun 12, 2013 3:36 am
by sje
The answer is to use Monte Carlo testing. Have the program play a hundred million random games (each move picked at random for both sides until a mate or draw). After each move, the retro generator is run and a test is made to verify that the move just made had been retro generated. Simple and easy!
Re: Test data for basic (reverse) move generation?
Posted: Thu Jun 13, 2013 6:34 am
by lucasart
sje wrote:The answer is to use Monte Carlo testing. Have the program play a hundred million random games (each move picked at random for both sides until a mate or draw). After each move, the retro generator is run and a test is made to verify that the move just made had been retro generated. Simple and easy!
That's a very bad idea. First of all, writing the "retro generator" is going to prove very difficult. And secondly, it still doesn't check anything: suppose your generator generates illegal moves and your retro generator also generates them backward.
Perft if the right way to validate a move generation + board play/undo code, and makes it very easy to debug. All you need it another program that does correct perft, and display the perft(n-1) to find the bug in a maximum of N-1 iterations, everytime the perft(N) is incorrect. There are many many programs that can do that, for example qperft by HG Muller (and pretty much any open source engine can either do it or be hacked easily to do it).
Re: Test data for basic (reverse) move generation?
Posted: Thu Jun 13, 2013 8:09 am
by User923005
I am pretty sure it was a joke.
Did you notice the "hundred million games" followed by "simple and easy"?
If you played games at game in one second, it would take three years if the computer ran uninterrupted around the clock.
SJE is a pretty smart cookie, and would have well understood the ramifications of his "simple suggestion."
There are retro programs available, including some with source code.
Re: Test data for basic (reverse) move generation?
Posted: Thu Jun 13, 2013 1:13 pm
by sje
I've done the random game thing myself, long ago. Since all moves for both sides are selected at random with no thinking, thousands of games per second can be played. A hundred million games takes only minutes to generate on a fast machine. What can be simpler or more easy than picking a move at random?
Obviously, the assumption is that the forward move generation is working properly before doing any work on a retro generator.
Re: Test data for basic (reverse) move generation?
Posted: Sat Jun 15, 2013 3:01 pm
by marcelk
sje wrote:The answer is to use Monte Carlo testing. Have the program play a hundred million random games (each move picked at random for both sides until a mate or draw). After each move, the retro generator is run and a test is made to verify that the move just made had been retro generated. Simple and easy!
This is a very good idea in principle.
However it tests completeness and not soundness (regardless of the correctness of the forward generator).
For that you also need to check that every generated retro-move is a valid forward move from the position after unmake.
Otherwise I could get away with a retro "generator" that returns the same list of pseudo-retromoves every time.
Re: Test data for basic (reverse) move generation?
Posted: Fri Jul 12, 2013 4:56 pm
by bluefever
RexButler wrote:Is there anywhere I can find test data for the (admittedly simple) problem of move generation, stepping both 1 ply forwards or -backwards-? I had something in the form of FEN strings in mind, but the exact format is not important. I'm looking for such data because I'm building a simple GUI program and want to test my move generation. I don't want to assume by move generation algorithm works by inspection only (especially in the retrograde case). In each case, I would consider good test data to have at least 10-15 starting positions for various sorts.
If I can't find such data, I may just have to take it up as a mini project and post it here.
Thanks much!
There is a really good perft position file on the ROCE chess engine site (I can't post links, but it comes up in google). it has about 130 positions to test, with leaf counts for depths 1 to 5/6
As well as this, implement a divide function - in other words, show the leaf nodes for each first move in the perft.
A winboard engine called Sharper has a divide command - if you type 'divide 5' into the console it will do a depth 5 perft, showing the leaf nodes by move. You can use this to find bugs pretty quickly, as you can see which move is incorrect, and do a perft at depth - 1 after this move has been made and so on.
If you can correctly satisfy the numbers in the file from the ROCE site, the generator is probably ok
as an example, here are the first few:
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1 ;D1 20 ;D2 400 ;D3 8902 ;D4 197281 ;D5 4865609 ;D6 119060324
r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1 ;D1 48 ;D2 2039 ;D3 97862 ;D4 4085603 ;D5 193690690
4k3/8/8/8/8/8/8/4K2R w K - 0 1 ;D1 15 ;D2 66 ;D3 1197 ;D4 7059 ;D5 133987 ;D6 764643
4k3/8/8/8/8/8/8/R3K3 w Q - 0 1 ;D1 16 ;D2 71 ;D3 1287 ;D4 7626 ;D5 145232 ;D6 846648
4k2r/8/8/8/8/8/8/4K3 w k - 0 1 ;D1 5 ;D2 75 ;D3 459 ;D4 8290 ;D5 47635 ;D6 899442
r3k3/8/8/8/8/8/8/4K3 w q - 0 1 ;D1 5 ;D2 80 ;D3 493 ;D4 8897 ;D5 52710 ;D6 1001523
4k3/8/8/8/8/8/8/R3K2R w KQ - 0 1 ;D1 26 ;D2 112 ;D3 3189 ;D4 17945 ;D5 532933 ;D6 2788982
r3k2r/8/8/8/8/8/8/4K3 w kq - 0 1 ;D1 5 ;D2 130 ;D3 782 ;D4 22180 ;D5 118882 ;D6 3517770
8/8/8/8/8/8/6k1/4K2R w K - 0 1 ;D1 12 ;D2 38 ;D3 564 ;D4 2219 ;D5 37735 ;D6 185867
8/8/8/8/8/8/1k6/R3K3 w Q - 0 1 ;D1 15 ;D2 65 ;D3 1018 ;D4 4573 ;D5 80619 ;D6 413018
4k2r/6K1/8/8/8/8/8/8 w k - 0 1 ;D1 3 ;D2 32 ;D3 134 ;D4 2073 ;D5 10485 ;D6 179869
r3k3/1K6/8/8/8/8/8/8 w q - 0 1 ;D1 4 ;D2 49 ;D3 243 ;D4 3991 ;D5 20780 ;D6 367724
r3k2r/8/8/8/8/8/8/R3K2R w KQkq - 0 1 ;D1 26 ;D2 568 ;D3 13744 ;D4 314346 ;D5 7594526 ;D6 179862938
r3k2r/8/8/8/8/8/8/1R2K2R w Kkq - 0 1 ;D1 25 ;D2 567 ;D3 14095 ;D4 328965 ;D5 8153719 ;D6 195629489
r3k2r/8/8/8/8/8/8/2R1K2R w Kkq - 0 1 ;D1 25 ;D2 548 ;D3 13502 ;D4 312835 ;D5 7736373 ;D6 184411439
r3k2r/8/8/8/8/8/8/R3K1R1 w Qkq - 0 1 ;D1 25 ;D2 547 ;D3 13579 ;D4 316214 ;D5 7878456 ;D6 189224276
1r2k2r/8/8/8/8/8/8/R3K2R w KQk - 0 1 ;D1 26 ;D2 583 ;D3 14252 ;D4 334705 ;D5 8198901 ;D6 198328929
2r1k2r/8/8/8/8/8/8/R3K2R w KQk - 0 1 ;D1 25 ;D2 560 ;D3 13592 ;D4 317324 ;D5 7710115 ;D6 185959088
r3k1r1/8/8/8/8/8/8/R3K2R w KQq - 0 1 ;D1 25 ;D2 560 ;D3 13607 ;D4 320792 ;D5 7848606 ;D6 190755813