Hi everyone.
I have a question: is it possible to create a 2800 elo (theoretical) chess engine without using the null move observation?
If so what would be the algorithms that it would use?
Without the null move observation
Moderators: hgm, Rebel, chrisw
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: Without the null move observation
Possibly.
Personally, I think (Multi)ProbCut or MultiCut may be used, but these tend to hurt engine playing strength and tactics.
Late Move Reductions, probably Move Count Based Pruning is a must.
Then Futility Pruning, ectc.
Matthew:out
Personally, I think (Multi)ProbCut or MultiCut may be used, but these tend to hurt engine playing strength and tactics.
Late Move Reductions, probably Move Count Based Pruning is a must.
Then Futility Pruning, ectc.
Matthew:out
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Without the null move observation
Should be doable with work. Last time I tested, null-move was worth maybe 100 Elo or so, when used in conjunction with LMR. LMR does a lot of what null-move does, and vice versa.Barardo wrote:Hi everyone.
I have a question: is it possible to create a 2800 elo (theoretical) chess engine without using the null move observation?
If so what would be the algorithms that it would use?
-
- Posts: 879
- Joined: Mon Dec 15, 2008 11:45 am
Re: Without the null move observation
Well, if you really talk of the "null-move-observation", there is
a clear NO. The null-move-observation is the fundamental
base of every quiescence search in todays standard search techniques.
In context to pruning and reduction techniques it may be possible to
reallocate the gain to other known algorithms like mentioned by Matthew
or like Bob said, an improved LM-technique may do the job.
Michael
a clear NO. The null-move-observation is the fundamental
base of every quiescence search in todays standard search techniques.
In context to pruning and reduction techniques it may be possible to
reallocate the gain to other known algorithms like mentioned by Matthew
or like Bob said, an improved LM-technique may do the job.
Michael
Re: Without the null move observation
That's exactly what I was talking about.
What I really should have asked was: are there sufficient algorithms to allow one to create an engine that doesn't use The null move observation? What would it use for search and evaluation?
What I really should have asked was: are there sufficient algorithms to allow one to create an engine that doesn't use The null move observation? What would it use for search and evaluation?
-
- Posts: 27788
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Without the null move observation
I don't think the null-move observation can be equated to stand-pat. It says there is almost always a better move than a null move. But stand-pat scores are not supposed to be lower bounds, and thus do not depend on that assumption. They are simply estimates of how good the position is. And they only have to be any good in positions where the best move is not a capture, as in QS captures are explicitly searched.Desperado wrote:Well, if you really talk of the "null-move-observation", there is
a clear NO. The null-move-observation is the fundamental
base of every quiescence search in todays standard search techniques.
It is quite possible to design a branch-termination scheme that violates the null-move-observation, and would be more accurate. E.g. taking note of forks and skewers against the side to move, and assign scores below current eval when they exist. This is usually not competitive, because it is computationally expensive, but that is a different matter.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Without the null move observation
CPW supports more what Michael wrote, and I have the same opinion. Regarding the QS example, stand-pat scores are of course supposed to be lower bounds within the QS context. The name "null move observation" might be misleading since what is meant is not exactly the "null move" (as in null move pruning, do a virtual move that only changes the active color) but a "do nothing, stop searching at this node". In this sense, the stand-pat score in QS is used under the assumption that from all quiet moves there will be at least one that is at least as good as the estimation given by the static stand-pat score, since otherwise we could not use that score as a reference against which we compare all captures.hgm wrote:I don't think the null-move observation can be equated to stand-pat. It says there is almost always a better move than a null move. But stand-pat scores are not supposed to be lower bounds, and thus do not depend on that assumption. They are simply estimates of how good the position is. And they only have to be any good in positions where the best move is not a capture, as in QS captures are explicitly searched.Desperado wrote:Well, if you really talk of the "null-move-observation", there is
a clear NO. The null-move-observation is the fundamental
base of every quiescence search in todays standard search techniques.
It is quite possible to design a branch-termination scheme that violates the null-move-observation, and would be more accurate. E.g. taking note of forks and skewers against the side to move, and assign scores below current eval when they exist. This is usually not competitive, because it is computationally expensive, but that is a different matter.
Sven
-
- Posts: 879
- Joined: Mon Dec 15, 2008 11:45 am
Re: Without the null move observation
Well i think you can suppose a standPat score to be a lower bound.hgm wrote:I don't think the null-move observation can be equated to stand-pat. It says there is almost always a better move than a null move. But stand-pat scores are not supposed to be lower bounds, and thus do not depend on that assumption. They are simply estimates of how good the position is. And they only have to be any good in positions where the best move is not a capture, as in QS captures are explicitly searched.Desperado wrote:Well, if you really talk of the "null-move-observation", there is
a clear NO. The null-move-observation is the fundamental
base of every quiescence search in todays standard search techniques.
It is quite possible to design a branch-termination scheme that violates the null-move-observation, and would be more accurate. E.g. taking note of forks and skewers against the side to move, and assign scores below current eval when they exist. This is usually not competitive, because it is computationally expensive, but that is a different matter.
doNullmove(),
standPat = -evaluate();
undoNullmove()
if(standpat>=beta) return(standpat)
There it is, the NMO. We did a nullmove, and our argument is that if the nullmove fails high, there is at least another one which is going to be better than the nullmove. So, at the moment i cannot follow you.
The different matter isnt really a different matter in the context of the
original question. For me a 2800 elo Engine is a competitive one.
But you are right with the point, that a different branch termination scheme is possible. And maybe it is indeed possible from the viewpoint
of a super strong engine like Stockfish for example, to try out sth. in
that direction. It would be interesting if Stockfish with another branch
termination scheme could hold the level of 2800. A buffer of 400 Elo is a lot.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Without the null move observation
I don't agree. The null-move observation is, simply "If I pass, and let my opponent make two moves in succession, and he STILL can not come up with a winning advantage, then his position is very bad, and mine is very good."Desperado wrote:Well, if you really talk of the "null-move-observation", there is
a clear NO. The null-move-observation is the fundamental
base of every quiescence search in todays standard search techniques.
In context to pruning and reduction techniques it may be possible to
reallocate the gain to other known algorithms like mentioned by Matthew
or like Bob said, an improved LM-technique may do the job.
Michael
I don't see that concept in q-search. That's not the same as either standing pat, or trying a check or capture.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Without the null move observation
Sorry, that is NOT null-move. The null-move-observation, as defined by Beal, was simply "If one side makes two consecutive moves without an intervening move by the opponent, and he can not produce a significant advantage by doing so, then his position is very bad, or, in our parlance, the side playing the null have a very strong position.Desperado wrote:Well i think you can suppose a standPat score to be a lower bound.hgm wrote:I don't think the null-move observation can be equated to stand-pat. It says there is almost always a better move than a null move. But stand-pat scores are not supposed to be lower bounds, and thus do not depend on that assumption. They are simply estimates of how good the position is. And they only have to be any good in positions where the best move is not a capture, as in QS captures are explicitly searched.Desperado wrote:Well, if you really talk of the "null-move-observation", there is
a clear NO. The null-move-observation is the fundamental
base of every quiescence search in todays standard search techniques.
It is quite possible to design a branch-termination scheme that violates the null-move-observation, and would be more accurate. E.g. taking note of forks and skewers against the side to move, and assign scores below current eval when they exist. This is usually not competitive, because it is computationally expensive, but that is a different matter.
doNullmove(),
standPat = -evaluate();
undoNullmove()
if(standpat>=beta) return(standpat)
There it is, the NMO. We did a nullmove, and our argument is that if the nullmove fails high, there is at least another one which is going to be better than the nullmove. So, at the moment i cannot follow you.
In the above, there is no "second consecutive move" so there is no "null-move-observation criterion that has been satisfied. You have to do a null-move and then let the opponent move again, else it is not a valid "null-move search."
I already know the answer and have posted this previously. I ran 30K games using Crafty, with and without null-move. Maybe 120 Elo loss, max. The thread can be found with a search. Maybe 1-2 years ago max.
The different matter isnt really a different matter in the context of the
original question. For me a 2800 elo Engine is a competitive one.
But you are right with the point, that a different branch termination scheme is possible. And maybe it is indeed possible from the viewpoint
of a super strong engine like Stockfish for example, to try out sth. in
that direction. It would be interesting if Stockfish with another branch
termination scheme could hold the level of 2800. A buffer of 400 Elo is a lot.