Problems implementing quiescense search

[Fguy64]

OK, I followed the comments made at the beuwolf page http://www.frayn.net/beowulf/theory.html and implemented a straightforward capture search, only evaluating captures and ending each branch when there was no more captures. seems straightforward enough, and according to my take on what Frayn says, it shouldn't take too long. But it does. At ply = 3, it extended the time taken for the engine to respond to 1.e4 from from a few seconds at most to three minutes, and that is with alpha-beta pruning on the q-search.

So I guess I am missing something somewhere. I could post my code. But I thought I'd post the question first to see if anything obvious sticks out.

regards.

[plattyaj]

It sounds so obviously broken that it's probably trivial to find the bug if you step through it with the debugger. At ply 3 from the opening position there shouldn't be enough possible captures to do anything. Probably putting printfs in would find it too.

Make sure you aren't allowing the king to get captured - if you don't generate truly legal moves, that's a possibility and who knows what your program will do then.

As you progress, you will produce a smaller tree if you sort the moves so you always do the most valuable captures first but even if you completely reversed that, that wouldn't explain a few minutes.

Andy.

[bob]

OK, I followed the comments made at the beuwolf page http://www.frayn.net/beowulf/theory.html and implemented a straightforward capture search, only evaluating captures and ending each branch when there was no more captures. seems straightforward enough, and according to my take on what Frayn says, it shouldn't take too long. But it does. At ply = 3, it extended the time taken for the engine to respond to 1.e4 from from a few seconds at most to three minutes, and that is with alpha-beta pruning on the q-search.

So I guess I am missing something somewhere. I could post my code. But I thought I'd post the question first to see if anything obvious sticks out.

regards.

If a three ply search takes a few seconds, you have a problem that needs to be solved before worrying about q-search. A 3 ply search ought not take but a few hundred to a few thousand nodes, including the q-search. That is a sub-millisecond amount of time.

[bob]

It sounds so obviously broken that it's probably trivial to find the bug if you step through it with the debugger. At ply 3 from the opening position there shouldn't be enough possible captures to do anything. Probably putting printfs in would find it too.

Make sure you aren't allowing the king to get captured - if you don't generate truly legal moves, that's a possibility and who knows what your program will do then.

As you progress, you will produce a smaller tree if you sort the moves so you always do the most valuable captures first but even if you completely reversed that, that wouldn't explain a few minutes.

Andy.

Also a common mistake is to hash in the q-search, and always try the hash move first, even though it is usually not a capture. This will blow the search up badly.

[Sven]

Did you also have a look at Bruce Moreland's pages? They are still a good reference to get a basic understanding of some key concepts.

I guess it is very likely that
a) you are not ordering captures properly in qsearch, and/or
b) you have a bug that lets your tree explode.

How many nodes does your algorithm search during these N minutes?

Sven

[tvrzsky]

only evaluating captures and ending each branch when there was no more captures.

And what about possibility of standing pat? https://chessprogramming.wikispaces.com ... nce+Search

[Fguy64]

OK Thanks for the comments.

Mr Hyatt, my remark about a three ply search taking a few seconds was careless. In fact, a 3-ply search by Black in response to 1.e4, without quiescense, takes about 100 milliseconds. Thats negamax + alphabeta. I suspect my legal move generation process, or my position representation, could use some improvements but they work properly, touch wood.

Sven I am not doing any particular ordering or selection of captures.

My quiescense search is esentially the same as my as my normal negamax search, except that it deals of course with all legal captures, and not legal moves. Also as mentioned there is no ordering of capture moves. My negamax search works fine. The stop criteria is not based on ply=0, but on my getCaptures function returning an array of size 0.

I'm not doing any hashing anywhere in the program, if my understanding that hashing deals with move transposition is correct.

Interestingly, even though it is slow, the q-search seems to be working.

Anyways, I'm working on the trace, and improving my gathering of statistics, so I guess once I get that sorted out i'll have a better idea what is going on. And i'll have a look at some of the suggested resources

thanks again

[Zach Wegner]

Add a stand pat (as mentioned by Filip) and your problems will go away. Quiescence search _requires_ a stand pat condition.

[Fguy64]

Add a stand pat (as mentioned by Filip) and your problems will go away. Quiescence search _requires_ a stand pat condition.

noted. I'll put a priority on that and let you know how it goes.