checks in q-search.

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
bob
Posts: 20930
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: checks in q-search.

Post by bob » Tue Sep 02, 2008 11:30 pm

Tord Romstad wrote:
Zach Wegner wrote:Also, as Gary brings up, delta pruning is an important topic to consider. I try noncapture checks after all the captures are tried. IMO you pretty much have to delta prune checks as well, because any captures you try that happen to be checks will be subject to delta pruning (unless you check for this...). Not delta pruning checks can lead to big branching factors too.
Delta pruning is the same as futility pruning, isn't it? I never futility prune checks (neither in the main search nor in the quiescence search), and it doesn't seem to hurt my branching factor much. Futility pruning of checks doesn't make sense at all, IMHO.

Tord
Delta pruning is a horrible name, but it came from others noticing how I exclude captures that can't possibly bring the score back above alpha, even if SEE says the capture is good. I have (had) a variable named "delta" that indicated how much material gain I needed to make the capture searchable, and someone named it "delta pruning" and it has lived on since. It is only done in the q-search.

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: checks in q-search.

Post by Zach Wegner » Wed Sep 03, 2008 1:52 am

Tord Romstad wrote:Delta pruning is the same as futility pruning, isn't it? I never futility prune checks (neither in the main search nor in the quiescence search), and it doesn't seem to hurt my branching factor much. Futility pruning of checks doesn't make sense at all, IMHO.

Tord
Basically. The difference between futility and delta pruning (as I define it...) is that a SEE value is used for the material gain instead of a simple material difference, and the move is also pruned if SEE<0.

I would guess that you don't search captures in qsearch with SEE<0? I don't, and logically you should also do the same to non-capture checks (searched after every capture).

So to clarify, right now ZCT doesn't use delta pruning in the futility pruning way, but just prunes all moves in qsearch (provided we aren't in check) if SEE<0. I had some problems with delta (=futility) pruning checks based on alpha, so I took that part out. The branching factor difference there isn't so big, but taking out the SEE does make a difference to me.

Tord Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Re: checks in q-search.

Post by Tord Romstad » Wed Sep 03, 2008 3:31 am

Zach Wegner wrote:
Tord Romstad wrote:Delta pruning is the same as futility pruning, isn't it? I never futility prune checks (neither in the main search nor in the quiescence search), and it doesn't seem to hurt my branching factor much. Futility pruning of checks doesn't make sense at all, IMHO.

Tord
Basically. The difference between futility and delta pruning (as I define it...) is that a SEE value is used for the material gain instead of a simple material difference, and the move is also pruned if SEE<0.

I would guess that you don't search captures in qsearch with SEE<0? I don't, and logically you should also do the same to non-capture checks (searched after every capture).
Thanks for the clarification! You are right, I do prune checks with SEE<0. In fact I prune even discovered checks with SEE<0, which is stupid, because the SEE value is usually totally irrelevant for such checks. I should fix this some day.

Tord

bob
Posts: 20930
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: checks in q-search.

Post by bob » Wed Sep 03, 2008 4:55 am

Tord Romstad wrote:
Zach Wegner wrote:
Tord Romstad wrote:Delta pruning is the same as futility pruning, isn't it? I never futility prune checks (neither in the main search nor in the quiescence search), and it doesn't seem to hurt my branching factor much. Futility pruning of checks doesn't make sense at all, IMHO.

Tord
Basically. The difference between futility and delta pruning (as I define it...) is that a SEE value is used for the material gain instead of a simple material difference, and the move is also pruned if SEE<0.

I would guess that you don't search captures in qsearch with SEE<0? I don't, and logically you should also do the same to non-capture checks (searched after every capture).
Thanks for the clarification! You are right, I do prune checks with SEE<0. In fact I prune even discovered checks with SEE<0, which is stupid, because the SEE value is usually totally irrelevant for such checks. I should fix this some day.

Tord
Good point, in fact, and I actually generate the checks in two passes, direct first, discovered second, although it is possible that a direct check is also a discovered check. I don't generate them twice, but it would be at the front. I was thinking about a pointer to the first of the discovered checks (if more than one) and not SEEing those at all...

something to think about, although it is probably a tiny issue in reality.

bob
Posts: 20930
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: checks in q-search. (Update again)

Post by bob » Wed Sep 03, 2008 5:13 am

Code: Select all

Rank Name               Elo    +    - games score oppo. draws  ---------LOS----------
   1 Glaurung 2.1       181    5    5 20270   77%   -33   17%     100100100100100100100
   2 Fruit 2.1           68    5    4 20260   64%   -33   23%    0   100100100100100100
   3 opponent-21.7       27    4    4 20263   59%   -33   33%    0  0    99100100100100
   4 Glaurung 1.1 SMP    13    5    5 20261   56%   -33   21%    0  0  0   100100100100
   5 Crafty-22.2        -30    5    5 23504   43%    20   22%    0  0  0  0    67 99100
   6 Crafty-22.2R2      -32    4    4 38910   43%    20   22%    0  0  0  0 32    99100
   7 Crafty-22.2R1      -37    4    4 38909   42%    20   23%    0  0  0  0  0  0   100
   8 Arasan 10.0       -190    4    5 20269   29%   -33   19%    0  0  0  0  0  0  0   
Here's the latest. Test is a little over half done for the third version. 22.2 is the qcheck + R=3 version, R1 = no qchecks, R2 = qchecks, with R=2~3

Uri Blass
Posts: 9138
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: checks in q-search.

Post by Uri Blass » Wed Sep 03, 2008 5:26 am

Tord Romstad wrote:
Zach Wegner wrote:Also, as Gary brings up, delta pruning is an important topic to consider. I try noncapture checks after all the captures are tried. IMO you pretty much have to delta prune checks as well, because any captures you try that happen to be checks will be subject to delta pruning (unless you check for this...). Not delta pruning checks can lead to big branching factors too.
Delta pruning is the same as futility pruning, isn't it? I never futility prune checks (neither in the main search nor in the quiescence search), and it doesn't seem to hurt my branching factor much. Futility pruning of checks doesn't make sense at all, IMHO.

Tord
I do not see why it does not make sense at all.
You can use delta pruning also for checks when you simply use bigger margin.

It is not 100% safe but by the same logic you can claim that pruning checks with SEE<0 does not make sense even if they are direct checks because there may be an indirect threat.

Uri

Uri Blass
Posts: 9138
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: checks in q-search.

Post by Uri Blass » Wed Sep 03, 2008 5:30 am

bob wrote:
Tord Romstad wrote:
Zach Wegner wrote:
Tord Romstad wrote:Delta pruning is the same as futility pruning, isn't it? I never futility prune checks (neither in the main search nor in the quiescence search), and it doesn't seem to hurt my branching factor much. Futility pruning of checks doesn't make sense at all, IMHO.

Tord
Basically. The difference between futility and delta pruning (as I define it...) is that a SEE value is used for the material gain instead of a simple material difference, and the move is also pruned if SEE<0.

I would guess that you don't search captures in qsearch with SEE<0? I don't, and logically you should also do the same to non-capture checks (searched after every capture).
Thanks for the clarification! You are right, I do prune checks with SEE<0. In fact I prune even discovered checks with SEE<0, which is stupid, because the SEE value is usually totally irrelevant for such checks. I should fix this some day.

Tord
Good point, in fact, and I actually generate the checks in two passes, direct first, discovered second, although it is possible that a direct check is also a discovered check. I don't generate them twice, but it would be at the front. I was thinking about a pointer to the first of the discovered checks (if more than one) and not SEEing those at all...

something to think about, although it is probably a tiny issue in reality.
I wonder why this order of generating.

It may be better to generate discover checks first because there are more dangerous and it may be logical to try them first.

Uri

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: checks in q-search.

Post by Zach Wegner » Wed Sep 03, 2008 5:40 am

Tord Romstad wrote:Thanks for the clarification! You are right, I do prune checks with SEE<0. In fact I prune even discovered checks with SEE<0, which is stupid, because the SEE value is usually totally irrelevant for such checks. I should fix this some day.

Tord
Well, I'm actually way behind in this respect. My check generator doesn't even generate discovered checks (I went for simplicity mainly), and I don't look to see if a move is a check (discovered or not) before pruning it.

I have been looking into this matter in the past few days though. I wanted to set a flag in the move if it gives check, to use in pruning/reduction decisions. On a related note, I figured I'd bite the bullet and switch to legal move generation. It's been a while since I did that, and it can be ugly, but perhaps I can make it clean and efficient. It's already getting interesting--since AFAIK there's no open source legal move generators, I have to just make it up. I inevitably have more fun programming when that happens.

Gerd Isenberg
Posts: 2246
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: checks in q-search.

Post by Gerd Isenberg » Wed Sep 03, 2008 7:09 am

Zach Wegner wrote:
Tord Romstad wrote:Thanks for the clarification! You are right, I do prune checks with SEE<0. In fact I prune even discovered checks with SEE<0, which is stupid, because the SEE value is usually totally irrelevant for such checks. I should fix this some day.

Tord
Well, I'm actually way behind in this respect. My check generator doesn't even generate discovered checks (I went for simplicity mainly), and I don't look to see if a move is a check (discovered or not) before pruning it.

I have been looking into this matter in the past few days though. I wanted to set a flag in the move if it gives check, to use in pruning/reduction decisions. On a related note, I figured I'd bite the bullet and switch to legal move generation. It's been a while since I did that, and it can be ugly, but perhaps I can make it clean and efficient. It's already getting interesting--since AFAIK there's no open source legal move generators, I have to just make it up. I inevitably have more fun programming when that happens.
Looking for pinned pieces for both sides can be combined with finding discovered checks for both sides if you use fill-stuff. Also, if side not to move has discovered (or even double) check at the tips we may reconsider standing pat with static eval >= beta.

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: checks in q-search.

Post by sje » Wed Sep 03, 2008 8:52 am

Zach Wegner wrote:It's already getting interesting--since AFAIK there's no open source legal move generators, I have to just make it up.
Well, there may be no open source legal-only move generators in C/C++.

But in the snippets thread I've been posting Common Lisp versions for legal-moves-only generators (five classes: not-in-check, evasion, gainer, holder, checking) along with move counting and mate detection routines.

Post Reply