Hi, I am currently working on a (still) primitive chess engine, with only minimax, alpha-beta with almost-random ordering, brain dead material evaluation, and have just added quiescence search on captures. What I have discovered is that, adding quiescence search seems to make the tree explode. With quiescence search, in midgame, my engine takes around 2 minutes to do a 0-ply search (no full-width at all). That is not what I have expected. Does this sound normal to people who have written chess engines? Or did I make some mistake in my algorithm? (Without quiescence, my engine can search 3-4 plies full width in midgame) Thank you very much. Matthew Lai

Hey there,

I wrote a chess engine back in high school and quiescence tree explosion is something I had to deal with. The bottom line is that from a typical midgame position, all capture qnodes can outnumber all hitherto considered AB nodes by a factor of 4:1.

While I was developing my engine, I had a midgame benchmark position that I often tested against. You can try running your engine on this position to see if you get similar results.

I get:
ply: 6, ABnodes: 1127422, Qnodes: 4057411 (max depth of Q-tree = 23 ply)

If you're interested in more details, check out my release notes for version 3.0 of Fimbulwinter, when I implemented qsearch.

Best of luck!

Make sure you order captures in some sensible way, so alpha-beta can prune large subtrees. "Largest victim, smallest attacker" is a good enough choice. If that still explodes, you have a bug somewhere.

Quote:
Hey there,

I wrote a chess engine back in high school and quiescence tree explosion is something I had to deal with. The bottom line is that from a typical midgame position, all capture qnodes can outnumber all hitherto considered AB nodes by a factor of 4:1.

While I was developing my engine, I had a midgame benchmark position that I often tested against. You can try running your engine on this position to see if you get similar results.

I get:
ply: 6, ABnodes: 1127422, Qnodes: 4057411 (max depth of Q-tree = 23 ply)

If you're interested in more details, check out my release notes for version 3.0 of Fimbulwinter, when I implemented qsearch.

Best of luck!

Thank you for your help. Apparently something is wrong with my implementation... My number of Qnodes is more than 1000 times my number of ABnodes in midgame =)

Just to make sure I am counting the nodes right. I count the number of calls to Minimax as ABnodes, and number of calls to quiescenceSearch as Qnodes. Is that how you are doing it, too?

Thank you very much

Quote:
Make sure you order captures in some sensible way, so alpha-beta can prune large subtrees. "Largest victim, smallest attacker" is a good enough choice. If that still explodes, you have a bug somewhere.

Thank you for the suggestion. I will try to implement that once I fix my algorithm =).

Quote: Original post by cyberfish

Quote:
Make sure you order captures in some sensible way, so alpha-beta can prune large subtrees. "Largest victim, smallest attacker" is a good enough choice. If that still explodes, you have a bug somewhere.

Thank you for the suggestion. I will try to implement that once I fix my algorithm =).

What I am saying is that ordering the captures might be the fix you are looking for. I am assuming you are already using alpha-beta pruning... right?

Quote:
What I am saying is that ordering the captures might be the fix you are looking for. I am assuming you are already using alpha-beta pruning... right?

I see... I was thinking that that is meant to be an optimization as opposed to a fix, because I presumed that my engine should be able to search 0-ply without it. Yes, I am already using alpha-beta.

Thank you

Yeah, if you are doing a 0-ply search, your ABnodes should be 0.

Here's an easy test - do a 0-ply search on the opening position. If your qsearch finds any captures, you have something seriously wrong. Then try a 0-ply search on an empty board position with only 1 possible capture. Then 1 possible capture with 1 possible re-capture.

Do you have a transposition table in-place yet? If you're getting 1000:1 qnodes to ABnodes, it would be interesting to know whether you are re-examining the same positions many times, or if the positions you are examining are random garbage. As a sanity check, you could construct a histogram of the Zobrist hash keys you're generating to see if you are re-visiting the same position a million times.

Thank you for your help. I do not have a transposition table in place yet.

I will do the tests you mentioned once I have access to my development machine.

Thank you

I did the tests you mentioned and had my engine print out the whole search tree. I don't see anything wrong with it.

I guess I will have to implement a transposition table now and see if that helps.

Thank you very much.