evluating the correctness of my qSearch

Discussion of chess software programming and technical issues.

Moderator: Ras

Fguy64
Posts: 814
Joined: Sat May 09, 2009 4:51 pm
Location: Toronto

evluating the correctness of my qSearch

Post by Fguy64 »

Ok I have my first qSearch up and running with mixed results. I have a hard time convincing myself that it is working as it should, given the design. My impression is that my qSearch works very well when there is a chance to win material, but it's sense of danger is not what I would like. I don't have proper diagnostics yet, I know it would help, it is on my to-do list.

I tried to follow Bruce Moreland's pseudo code.
http://web.archive.org/web/200404270144 ... escent.htm

ok, you can test out the engine using the link in my sig, on my programmer's page you will see links to the engine code. There are buttons for pasting full fen string and also for generating PGN.

Here is a summary of the engine:
fixed depth negamax alphaBeta.
Eval is material only, using traditional piece values. No piece/square points.
full capture search with move ordering which maximizes the difference (by subtracting) in value between captured piece and capturing piece. (MVV/LVA I think )
no hash table

here is an example played at ply=3
r1bqkbnr/ppppppp1/6n1/3P3p/4PP1P/2P2N2/PP4P1/RNBQKB1R b KQkq - 1 7

the engine plays 7...Rb8? I can see that that would be the logical move if there was no quiescence, but surely 8.f5 is part of normal search of 7...Rb8 and at ply=3 there would be captures for white that would be picked up by Q.
User avatar
xsadar
Posts: 147
Joined: Wed Jun 06, 2007 10:01 am
Location: United States
Full name: Mike Leany

Re: evluating the correctness of my qSearch

Post by xsadar »

Fguy64 wrote:Ok I have my first qSearch up and running with mixed results. I have a hard time convincing myself that it is working as it should, given the design. My impression is that my qSearch works very well when there is a chance to win material, but it's sense of danger is not what I would like. I don't have proper diagnostics yet, I know it would help, it is on my to-do list.

I tried to follow Bruce Moreland's pseudo code.
http://web.archive.org/web/200404270144 ... escent.htm

ok, you can test out the engine using the link in my sig, on my programmer's page you will see links to the engine code. There are buttons for pasting full fen string and also for generating PGN.

Here is a summary of the engine:
fixed depth negamax alphaBeta.
Eval is material only, using traditional piece values. No piece/square points.
full capture search with move ordering which maximizes the difference (by subtracting) in value between captured piece and capturing piece. (MVV/LVA I think )
no hash table

here is an example played at ply=3
r1bqkbnr/ppppppp1/6n1/3P3p/4PP1P/2P2N2/PP4P1/RNBQKB1R b KQkq - 1 7

the engine plays 7...Rb8? I can see that that would be the logical move if there was no quiescence, but surely 8.f5 is part of normal search of 7...Rb8 and at ply=3 there would be captures for white that would be picked up by Q.
MVV/LVA means that you search captures of the most valuable pieces first, but consider the piece doing the capturing only if there are two captures of the same piece type.
For example, you want to search QxQ before you search PxR. This makes your qsearch faster by first eliminating the pieces with the most moves available to them. Also, many times the big pieces may be undefended, leading to quick beta cutoffs. And, of course, if you have QxQ available to you, and you first try PxR instead, then QxQ will be available to the opponent on the next ply (unless his queen is pinned, of course).

As to your original question, you can try printing out the search data for the moves you mention to see exactly what's happening.
Fguy64
Posts: 814
Joined: Sat May 09, 2009 4:51 pm
Location: Toronto

Re: evluating the correctness of my qSearch

Post by Fguy64 »

xsadar wrote:
Fguy64 wrote:Ok I have my first qSearch up and running with mixed results. I have a hard time convincing myself that it is working as it should, given the design. My impression is that my qSearch works very well when there is a chance to win material, but it's sense of danger is not what I would like. I don't have proper diagnostics yet, I know it would help, it is on my to-do list.

I tried to follow Bruce Moreland's pseudo code.
http://web.archive.org/web/200404270144 ... escent.htm

ok, you can test out the engine using the link in my sig, on my programmer's page you will see links to the engine code. There are buttons for pasting full fen string and also for generating PGN.

Here is a summary of the engine:
fixed depth negamax alphaBeta.
Eval is material only, using traditional piece values. No piece/square points.
full capture search with move ordering which maximizes the difference (by subtracting) in value between captured piece and capturing piece. (MVV/LVA I think )
no hash table

here is an example played at ply=3
r1bqkbnr/ppppppp1/6n1/3P3p/4PP1P/2P2N2/PP4P1/RNBQKB1R b KQkq - 1 7

the engine plays 7...Rb8? I can see that that would be the logical move if there was no quiescence, but surely 8.f5 is part of normal search of 7...Rb8 and at ply=3 there would be captures for white that would be picked up by Q.
MVV/LVA means that you search captures of the most valuable pieces first, but consider the piece doing the capturing only if there are two captures of the same piece type.
For example, you want to search QxQ before you search PxR. This makes your qsearch faster by first eliminating the pieces with the most moves available to them. Also, many times the big pieces may be undefended, leading to quick beta cutoffs. And, of course, if you have QxQ available to you, and you first try PxR instead, then QxQ will be available to the opponent on the next ply (unless his queen is pinned, of course).

As to your original question, you can try printing out the search data for the moves you mention to see exactly what's happening.
right ok I can see that I have misinterpreted MVV/LVA. That will be easy to fix. I have PxB being ordered the same as BxR, because of the equality of the differences in piece values (2).

I don't know if that will change any evals, but I'll fix that tomorrow and we take it from there.
Fguy64
Posts: 814
Joined: Sat May 09, 2009 4:51 pm
Location: Toronto

Re: evluating the correctness of my qSearch

Post by Fguy64 »

anyways, never mind, my capture moveGen is bug ridden.
User avatar
xsadar
Posts: 147
Joined: Wed Jun 06, 2007 10:01 am
Location: United States
Full name: Mike Leany

Re: evluating the correctness of my qSearch

Post by xsadar »

Fguy64 wrote:anyways, never mind, my capture moveGen is bug ridden.
Yes, it's really hard to debug a search (or even know if it needs to be debugged) if you have a buggy move generator. I recommend you don't put off a 'perft' function any longer. Really, you should make sure you have a bug-free move generator before you even attempt anything else. Here's some good information on testing your move generator with perft/divide: http://www.rocechess.ch/perft.html
Apparently the epd file with all the test positions (with precomputed values) has disappeared from that site, and I don't know of any other place to find it on the web, so I've (temporarily) uploaded it to my site here: http://www.mikeleany.com/mgtest.epd
Just compare your engine's values with the values in the file for the given depth. I've automated the process in my engine.
Fguy64
Posts: 814
Joined: Sat May 09, 2009 4:51 pm
Location: Toronto

Re: evluating the correctness of my qSearch

Post by Fguy64 »

xsadar wrote:
Fguy64 wrote:anyways, never mind, my capture moveGen is bug ridden.
Yes, it's really hard to debug a search (or even know if it needs to be debugged) if you have a buggy move generator. I recommend you don't put off a 'perft' function any longer.
noted. Soon. I've taken a couple of runs at Perftt, one of these days I'll follow it through. Not having it is the reason I am sticking with just a standard material based eval() for now. Easier to find bugs. Anyways, I was a little sloppy with my testing this time around. Lesson learned.
User avatar
Kempelen
Posts: 620
Joined: Fri Feb 08, 2008 10:44 am
Location: Madrid - Spain

Re: evluating the correctness of my qSearch

Post by Kempelen »

xsadar wrote:Yes, it's really hard to debug a search
What I do is dump all the search as a XML file, so you can walk for the seach as a tree with a xml-viewer. Also you can write attributes in each node (extensions, eval, ....). In moments, a 8-depth tree can be easy viewed and navigated, more than that could make very bigs files. Anyway this is a very useful tool for me to debug
Fermin Serrano
Author of 'Rodin' engine
http://sites.google.com/site/clonfsp/
Fguy64
Posts: 814
Joined: Sat May 09, 2009 4:51 pm
Location: Toronto

Re: evluating the correctness of my qSearch

Post by Fguy64 »

Kempelen wrote:
xsadar wrote:Yes, it's really hard to debug a search
What I do is dump all the search as a XML file, so you can walk for the seach as a tree with a xml-viewer. Also you can write attributes in each node (extensions, eval, ....). In moments, a 8-depth tree can be easy viewed and navigated, more than that could make very bigs files. Anyway this is a very useful tool for me to debug
hmm, and it doesn't sound that hard to implement. So just to clarify, so you are able to walk thruough the search dump using a chessboard viewer? Is such a viewer readily available to download?

Unfortunately in my case, in a sense it was nothing that I can blame on the lack of a nifty tool. A proper test of capture moveGen before I implemented my qSearch would have saved me some headaches. :lol:
User avatar
Kempelen
Posts: 620
Joined: Fri Feb 08, 2008 10:44 am
Location: Madrid - Spain

Re: evluating the correctness of my qSearch

Post by Kempelen »

Fguy64 wrote: hmm, and it doesn't sound that hard to implement. So just to clarify, so you are able to walk thruough the search dump using a chessboard viewer? Is such a viewer readily available to download?
It is not very hard to implement. The goal is to walk throught the search in a xml viewer, not a chessboard viewer. Anyway it would be not too hard to write a translator from the xml to a pgn file, althought it looks to me that current pgn chessviewers availables out there would not work with a pgn file so big.
For me it is enough to walk thought the search in the xmlviewer.

Of course, first thing is to make sure movegen works perfectly.....
Fermin Serrano
Author of 'Rodin' engine
http://sites.google.com/site/clonfsp/
Fguy64
Posts: 814
Joined: Sat May 09, 2009 4:51 pm
Location: Toronto

Re: evluating the correctness of my qSearch

Post by Fguy64 »

OK Fermin, noted. Thanks for the tips.

Anyways, I'm pretty sure I worked all the bugs out of my capture moveGen, although I couldn't be bothered to add LVA move ordering for en-passant to pawn captures. Things look pretty good, the website is updated. I did add promotion moves to qSearch, I can see adding check also, so probably that'll be the next thing I try.