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.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.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.
Tord
checks in q-search.
Moderators: hgm, Rebel, chrisw
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: checks in q-search.
-
- Posts: 1922
- Joined: Thu Mar 09, 2006 12:51 am
- Location: Earth
Re: checks in q-search.
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.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
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.
-
- Posts: 1808
- Joined: Wed Mar 08, 2006 9:19 pm
- Location: Oslo, Norway
Re: checks in q-search.
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.Zach Wegner wrote: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.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
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).
Tord
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: checks in q-search.
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...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.Zach Wegner wrote: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.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
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).
Tord
something to think about, although it is probably a tiny issue in reality.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: checks in q-search. (Update again)
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
-
- Posts: 10296
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: checks in q-search.
I do not see why it does not make sense at all.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.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.
Tord
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
-
- Posts: 10296
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: checks in q-search.
I wonder why this order of generating.bob wrote: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...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.Zach Wegner wrote: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.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
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).
Tord
something to think about, although it is probably a tiny issue in reality.
It may be better to generate discover checks first because there are more dangerous and it may be logical to try them first.
Uri
-
- Posts: 1922
- Joined: Thu Mar 09, 2006 12:51 am
- Location: Earth
Re: checks in q-search.
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.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
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.
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: checks in q-search.
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.Zach Wegner wrote: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.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
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.
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: checks in q-search.
Well, there may be no open source legal-only move generators in C/C++.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.
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.