An idea for all you chess programmers.

Archive of the old Parsimony forum. Some messages couldn't be restored. Limitations: Search for authors does not work, Parsimony specific formats do not work, threaded view does not work properly. Posting is disabled.

An idea for all you chess programmers.

Postby Paul » 16 Mar 2001, 04:36

Geschrieben von: / Posted by: Paul at 16 March 2001 04:36:42:
If my understanding of it is correct, null move pruneing searches "very good" looking moves at a reduced depth.
Why not do the same for very bad looking moves?
Paul
 

Re: An idea for all you chess programmers.

Postby Carmelo Calzerano » 16 Mar 2001, 11:34

Geschrieben von: / Posted by: Carmelo Calzerano at 16 March 2001 11:34:36:
Als Antwort auf: / As an answer to: An idea for all you chess programmers. geschrieben von: / posted by: Paul at 16 March 2001 04:36:42:
If my understanding of it is correct, null move pruneing searches "very good"
looking moves at a reduced depth.
Why not do the same for very bad looking moves?
Not exactly; null move algorithm basically detects "very good" _positions_
allowing the opponent to move twice in a row, and then performing a reduced
depth search: if that search returns an "high enough" score for the null-moving
side (ie, if the opponent is not able to bring the score below beta even moving
twice in a row), the original position is supposed to be "enough good" and a
fail-high score is returned without further searching.
A "very bad move" will bring to a "very good position" for the opponent, so
that the null-move algorithm will prune the branch at the next ply: in fact
that's exactly what null-move does! :-)
You could suggest to prune (or search at reduced depth) "bad looking moves" in
the current ply, without waiting for the null-move fail high at the next ply;
in fact it is often done, but using different algorithms than null-move.
Null-move is simply not suitable for doing that, being based on the idea that
moving twice in a row is an _advantage_: it answers to the question "Am I so
good that I'll win even letting my opponent moving twice in a row?"; it cannot
answer to questions like "Am I so bad that (...) ?" (BTW, it is sometimes used
to detect opponent's mate threats too, but it's not exactly the same thing).
Bye,
Carmelo
Carmelo Calzerano
 

Re: An idea for all you chess programmers.

Postby Aaron » 16 Mar 2001, 20:39

Geschrieben von: / Posted by: Aaron at 16 March 2001 20:39:04:
Als Antwort auf: / As an answer to: Re: An idea for all you chess programmers. geschrieben von: / posted by: Carmelo Calzerano at 16 March 2001 11:34:36:
Hello. Since we are having a little computer chess lesson here, I decided to join in..
If my understanding of it is correct, null move pruneing searches "very good"
looking moves at a reduced depth.
Not exactly; null move algorithm basically detects "very good" _positions_
allowing the opponent to move twice in a row, and then performing a reduced
depth search: if that search returns an "high enough" score for the null-moving
side (ie, if the opponent is not able to bring the score below beta even moving
twice in a row), the original position is supposed to be "enough good" and a
fail-high score is returned without further searching.
I think i get the idea of the null move..Basically if the position is so good for you, that your opponent can move twice and still not get a advanatage the position is probably too good [Is that fail-high I never really got it, despite reading a couple of computer chess books and websites] , for you, that your opponent won't allow it , hence we don't need to search furthur?
What exactly do you mean by search at a reduced depth? I understand that all programs do incremental or iterative searches..Eg search up to depth 1, then 2, then 3 etc etc..
So what does search at a reduced depth move? Say this time you are supposed to search up to depth 8, when do you try a null move? And if you do it at say 6 ply, would search at a reduced depth means you search 1 more ply and that's it??

Clueless (Aaron)
Aaron
 

Re: An idea for all you chess programmers.

Postby Dieter Buerssner » 17 Mar 2001, 16:40

Geschrieben von: / Posted by: Dieter Buerssner at 17 March 2001 16:40:26:
Als Antwort auf: / As an answer to: Re: An idea for all you chess programmers. geschrieben von: / posted by: Aaron at 16 March 2001 20:39:04:
Hello. Since we are having a little computer chess lesson here, I decided to join in..
If my understanding of it is correct, null move pruneing searches "very good"
looking moves at a reduced depth.
Not exactly; null move algorithm basically detects "very good" _positions_
allowing the opponent to move twice in a row, and then performing a reduced
depth search: if that search returns an "high enough" score for the null-moving
side (ie, if the opponent is not able to bring the score below beta even moving
twice in a row), the original position is supposed to be "enough good" and a
fail-high score is returned without further searching.
I think i get the idea of the null move..Basically if the position is so good for you, that your opponent can move twice and still not get a advanatage the position is probably too good [Is that fail-high I never really got it, despite reading a couple of computer chess books and websites] , for you, that your opponent won't allow it , hence we don't need to search furthur?
What exactly do you mean by search at a reduced depth? I understand that all programs do incremental or iterative searches..Eg search up to depth 1, then 2, then 3 etc etc..
So what does search at a reduced depth move? Say this time you are supposed to search up to depth 8, when do you try a null move? And if you do it at say 6 ply, would search at a reduced depth means you search 1 more ply and that's it??
Carmelo allready answered this:
Yes. But how do we know, that the position is good enough without moveing? In general, this will need a search. So, instead for searching the position with the side to move, we pass the right to move, and let the opponent move again and search this position. If the position with the opponent to move would be searched at the same depth, nothing would be saved in general. So, the idea is, when we actually want to analyze this position to depth N, (which means, that after any of our moves, we search the position with depth N-1), to proove, that this really is a superior position, it is enough to pass the right to move, and analyze with depth N-(R+1). R is the null move depth reduction (my term, I am not sure, if this is the correct term). So, at the start of the searching process, a search is started with reduced depth, that will need much less time.
If we get a fail high here, we stop searching this position, and assume, that the position is too good, and probably an inferior move of the opponent further up in the search tree got refuted. Also, this method can fail. I.e. in Zugzwang situations. Here it is an actual advantage, to pass the right to move to the other side, and the proove above will be wrong. There exist methods, to avoid this.
Yes, it hink, this is the case for most programs.
I guess the idea of Paul was the following: Say we want to find the best move in the start position. Assume, that we want to analyze all positions to depth 5 (so we want to analyze any position after each of the 20 moves of white to depth 4). Actually this is done by a "normal" (without pruning mechanisms) chess search alogorithms. But now, we might want to search the moves. Say there is some indication, that some moves are better than others. We might decide (how to do this would be the difficult thing) that e4 and d4 look most interesting, followed by Nf3, Nf6, c4 and f4. The other moves look only little interesting. So we might want to only search e4 and d4 at full depth (4), Nf3, ... at slightly reduced depth (3) and the other moves at even more reduced depth (2).
Nullmove does something similar really.
-- Dieter
Dieter Buerssner
 

Re: An idea for all you chess programmers.

Postby Aaron » 18 Mar 2001, 09:41

Geschrieben von: / Posted by: Aaron at 18 March 2001 09:41:50:
Als Antwort auf: / As an answer to: Re: An idea for all you chess programmers. geschrieben von: / posted by: Dieter Buerssner at 17 March 2001 16:40:26:
Hello Dieter, I was hoping you would answer.
I think i get the idea of the null move..Basically if the position is so good for you, that your opponent can move twice and still not get a advanatage the position is probably too good [Is that fail-high I never really got it, despite reading a couple of computer chess books and websites] , for you, that your opponent won't allow it , hence we don't need to search furthur?
Yes. But how do we know, that the position is good enough without moveing? In general, this will need a search. So, instead for searching the position with the side to move, we pass the right to move, and let the opponent move again and search this position.
If the position with the opponent to move would be searched at the same depth, nothing would be saved in general. So, the idea is, when we actually want to analyze this position to depth N, (which means, that after any of our moves, we search the position with depth N-1), to proove, that this really is a superior position, it is enough to pass the right to move, and analyze with depth N-(R+1). R is the null move depth reduction (my term, I am not sure, if this is the correct term). So, at the start of the searching process, a search is started with reduced depth, that will need much less time.
If we get a fail high here, we stop searching this position, and assume, that the position is too good, and probably an inferior move of the opponent further up in the search tree got refuted. Also, this method can fail. I.e. in Zugzwang situations. Here it is an actual advantage, to pass the right to move to the other side, and the proove above will be wrong. There exist methods, to avoid this.
I guess the idea of Paul was the following: Say we want to find the best move in the start position. Assume, that we want to analyze all positions to depth 5 (so we want to analyze any position after each of the 20 moves of white to depth 4). Actually this is done by a "normal" (without pruning mechanisms) chess search alogorithms. But now, we might want to search the moves. Say there is some indication, that some moves are better than others. We might decide (how to do this would be the difficult thing) that e4 and d4 look most interesting, followed by Nf3, Nf6, c4 and f4. The other moves look only little interesting. So we might want to only search e4 and d4 at full depth (4), Nf3, ... at slightly reduced depth (3) and the other moves at even more reduced depth (2).
Nullmove does something similar really.
-- Dieter

IC. So it's still a search but a very weird one , since you
search from a position that the oppponent has moved twice. But wouldn't the information obtained from here be useless for storing in the transposition table since the position searched is in some sense not "real"? Or perhaps it's still useful when you search to a deeper depth and use null move again?
so R=1 means you search 1 ply
less etc.. Also does Yace usually use R=3? Seems very agressive..Or does the
values in Yace.ini [Yace_high/low] file mean something else?

The double null move thing right? I will go think about it.
But your [actually Paul's] idea seem to imply that you actually "decide"
from the start position, which are moves that will be searched to a lesser depth? Don't you actually do that deeper into the move tree?
What do you mean by "In early game the null move algorithm will use
null_low when the current search depth is small (smaller or equal null_split)
and null_high, when it is high"
[From the Yace readme file]
Is it because in the early game there are more pieces on the board hence more
moves to consider and as such Yace usually searches to far lower search depths?
Hence it will use the null setting set in null_low?
So with setting Null_high 4.0, Null_low 3.0 and Null split 4.5
whenever Yace searches to depth 5 and above it will do a depth reduction of 4?
I must be misunderstanding something..Since your default Null_split of 4.5 strikes me as not very useful is reached very quickly anyway? For the current Yace, it makes no difference of course since Null_high and low is the same value.
Also does it make more sense for Null_high values to be higher than Null_low?

Thanks Dieter, for your explainations and I appreciate it. I know how busy you are with making Yace a program that even commercials fear.
It seems to me Yace has made it, and seems to be respected as one of the stronger programs perhaps on par with Crafty . You can tell just by seeing how popular Yace is when many people choose to use Yace as a representive of the strongest free engines to round out a tournament of professional programs.
Aaron
Aaron
 

Re: An idea for all you chess programmers.

Postby Dieter Buerssner » 18 Mar 2001, 21:49

Geschrieben von: / Posted by: Dieter Buerssner at 18 March 2001 21:49:54:
Als Antwort auf: / As an answer to: Re: An idea for all you chess programmers. geschrieben von: / posted by: Aaron at 18 March 2001 09:41:50:
I think i get the idea of the null move..Basically if the position is so good for you, that your opponent can move twice and still not get a advanatage the position is probably too good [Is that fail-high I never really got it, despite reading a couple of computer chess books and websites] , for you, that your opponent won't allow it , hence we don't need to search furthur?
Yes. But how do we know, that the position is good enough without moveing? In general, this will need a search. So, instead for searching the position with the side to move, we pass the right to move, and let the opponent move again and search this position.

IC. So it's still a search but a very weird one , since you
search from a position that the oppponent has moved twice. But wouldn't the information obtained from here be useless for storing in the transposition table since the position searched is in some sense not "real"?
Or perhaps it's still useful when you search to a deeper depth and use null move again?
so R=1 means you search 1 ply
less etc.. Also does Yace usually use R=3? Seems very agressive..Or does the
values in Yace.ini [Yace_high/low] file mean something else?
The double null move thing right? I will go think about it.
But your [actually Paul's] idea seem to imply that you actually "decide"
from the start position, which are moves that will be searched to a lesser depth? Don't you actually do that deeper into the move tree?
What do you mean by "In early game the null move algorithm will use
null_low when the current search depth is small (smaller or equal null_split)
and null_high, when it is high"
[From the Yace readme file]
Is it because in the early game there are more pieces on the board hence more
moves to consider and as such Yace usually searches to far lower search depths?
Hence it will use the null setting set in null_low?
So with setting Null_high 4.0, Null_low 3.0 and Null split 4.5
whenever Yace searches to depth 5 and above it will do a depth reduction of 4?
I must be misunderstanding something..Since your default Null_split of 4.5 strikes me as not very useful is reached very quickly anyway? For the current Yace, it makes no difference of course since Null_high and low is the same value.
Also does it make more sense for Null_high values to be higher than Null_low?
Perhaps, yes. But this won't be a big disadvantage. "Useless" doesn't really hurt. Also, after some tempo maneuver, you might get to the same position as "real".
I think not in this case, because the depth in the transposition table will not be enough. The best move after the null move can be used for move ordering, after doing a null move in the same position later at higher search depth.
It depends, how you define it (I find the definition of R also confusing).
R=1 means you do a null move and search the position after the null move with one ply less, than you would search the position after a legal move. This means, that the position you are looking at, you are searching with R+1 plies less for the other side to move.
No, Yace uses R=2 by default in middle game and R=1 in the late endgame (null_e 2), no nullmove in pawn endings. null_h 3 means R=2, sorry ...
[Avoid Zugzwang problems]
Yes. Also, disabling nullmove in late endgame, when in check and perhaps other cases. In Yace, I don't use double null move, as described by Vincent. Before the null move is done, I search the position at much reduced depth. Only when this gets a fail high, I try nullmove. But in principle, I believe this is the same thing.
There is also some indication, that in "real games", this does not really help. I believe, i.e. Fritz does not do this. When doing double nullmove or similar, you will get less nullmove cutoffs, and reach the same search depth only after longer time in general.
Yes. But I think the concept is in principle the same. BTW. With start position, I would mean any position visited in the search tree. The recursive concept of alpha-beta search make any visited position a "start postion" for an analysis of a certain depth.
Actually, this is phrased badly. "In early game" should read "when not in late endgame (less than two rooks on the board)". (Earlier versions of Yace defined late endgame differently)
Not really. With "current search depth", I don't mean the depth for the "root position", but rather the depth left to search for a position inside the search tree.
I hope, the above makes it clearer. I fear, all tis is not very easy to understand, without investing some time in chess search algorithms. Yace implements so called "dynamic null move". It is described by Ernst Heinz. You can download a preprint of his paper. I don't have an URL handy, but you should find it by browsing through CCC archives. There are other papers relevant to this discussion available at the same site, one is about extended futility pruning (from memory).
Actually, I would think, yes. But results of Ernst Heinz show different.
Note, that when I first implemented dynamic nullmove, I thought, I get reproducable and significantly better results by using null_h 4. I cannot reproduce anymore. It may well be, that I have broken something.
Regards,
Dieter
Dieter Buerssner
 


Return to Archive (Old Parsimony Forum)

Who is online

Users browsing this forum: No registered users and 10 guests