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.
evluating the correctness of my qSearch
Moderator: Ras
-
- Posts: 814
- Joined: Sat May 09, 2009 4:51 pm
- Location: Toronto
-
- Posts: 147
- Joined: Wed Jun 06, 2007 10:01 am
- Location: United States
- Full name: Mike Leany
Re: evluating the correctness of my qSearch
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.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.
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.
-
- Posts: 814
- Joined: Sat May 09, 2009 4:51 pm
- Location: Toronto
Re: evluating the correctness of my qSearch
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).xsadar wrote: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.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.
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.
I don't know if that will change any evals, but I'll fix that tomorrow and we take it from there.
-
- Posts: 814
- Joined: Sat May 09, 2009 4:51 pm
- Location: Toronto
Re: evluating the correctness of my qSearch
anyways, never mind, my capture moveGen is bug ridden.
-
- Posts: 147
- Joined: Wed Jun 06, 2007 10:01 am
- Location: United States
- Full name: Mike Leany
Re: evluating the correctness of my qSearch
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.htmlFguy64 wrote:anyways, never mind, my capture moveGen is bug ridden.
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.
-
- Posts: 814
- Joined: Sat May 09, 2009 4:51 pm
- Location: Toronto
Re: evluating the correctness of my qSearch
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.xsadar wrote: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.Fguy64 wrote:anyways, never mind, my capture moveGen is bug ridden.
-
- Posts: 620
- Joined: Fri Feb 08, 2008 10:44 am
- Location: Madrid - Spain
Re: evluating the correctness of my qSearch
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 debugxsadar wrote:Yes, it's really hard to debug a search
-
- Posts: 814
- Joined: Sat May 09, 2009 4:51 pm
- Location: Toronto
Re: evluating the correctness of my qSearch
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?Kempelen wrote: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 debugxsadar wrote:Yes, it's really hard to debug a search
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.

-
- Posts: 620
- Joined: Fri Feb 08, 2008 10:44 am
- Location: Madrid - Spain
Re: evluating the correctness of my qSearch
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.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?
For me it is enough to walk thought the search in the xmlviewer.
Of course, first thing is to make sure movegen works perfectly.....
-
- Posts: 814
- Joined: Sat May 09, 2009 4:51 pm
- Location: Toronto
Re: evluating the correctness of my qSearch
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.
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.