Author: Heiner Marxen
Date: 06:04:16 06/03/02
Go up one level in this thread
On June 02, 2002 at 22:02:21, Vincent Diepeveen wrote:
>On June 01, 2002 at 11:35:31, Dan Andersson wrote:
>
>Hello Dan,
Since I started this thread, let me jump in, Voncent.
I'll try to clarify several points.
My original posting wasn't very clear, probably.
>You are talking in chinese for me, whereas an algorithm
>is needed.
>
>Please give some pseudo code will you of your idea?
>
>Right now the pseudo code would be:
>
>int MyIdea(int unknown) {
> for( not interesting ) {
> do enumerate(something useless);
> }
> conclusion = DoSomethingVague(which i won't show);
>}
>
>You present MyIdea and show the enumeration,
>but the real problem is the problem below to 'dosomethingvague' in the
>above example. And the fact that it won't ever get shown in
>semi-pseudo code to the readers of the article.
>
>Let's start with enumerating the state space.
>
>Do you mean 'search space' perhaps? If so, HOW do you enumerate
>and what is the USE of it?
Yes and no.
The "state space" he talks about (I too), is a very limited part of the
search space of a chess program. It is a bit similar to EGTBs:
EGTBs enumerate all positions of a certain kind (very limited set of
pieces on board). So, EGTBs are not a solution to the overall problem,
but rather solve a certain set of postions which occur in the late endgame.
The interesting point here is, that the normal tree search often is not
capable to yield the same result in acceptable time.
With that spirit in mind, I tried to sketch an approach to solve another
(very limited) kind/class of positions, where the normal tree search
mostly is not capable to come up with the correct result, or needs a lot
of time and a lot of depth.
This kind of positions I try to target are drawn positions, more exactly:
positions, where one side can be shown to not loose anymore, because
that side can force draw, e.g. by permanent check, or by using a system
of "corresponding squares".
The limited search/state space handled here (my proposal) is:
- Given a certain complete position,
- pick one white and one black piece (e.g. both kings)
- enumerate all possible (legal) combinations of squares (0..63 x 0..63)
where these two pieces could happen to be
- enumerate both sides as "to move"
- let all other pieces stay where they are in the original position
Those are at most 64x64x2 = 8192 positions.
Those 8192 positions are the state space I and Dan talk about.
>To get concrete: I already give in debugmode each position diep searches a
>64 bits number, starting by 0 then second position 1 etcetera.
That is something completely different.
>Secondly, you seem to only look for a win for the attacker. How
>about if score is -0.030. You talk about recognizing a draw
>only however. There is a lot between losing, drawing and winning.
Sure.
The technique I talk about shall yield a statement like "black cannot loose
anymore, here" or, if that cannot be shown to be true, it yields "dunno".
That shall not replace evaluation or tree search completely, but it could
augment tree search: _if_ the result is "black cannot loose anymore",
we can draw conclusions from that for the evaluation, right? It is a bound.
_If_ we additionally find "white cannot loose anymore" we can even conclude
a "draw", and the complete search tree can be cut off, since the obtained
draw result is as exact as if an EGTB would have said so.
>Even though the result of a game can always be seen as
>losing or winning, it is pretty RUDE/CRUDE to divide it in
>win/draw/loss. It means you get huge round off errors.
Nobody proposes to do so in general.
But sometimes in the late endgame such CRUDE evaluations are possible.
>Right now in DIEP i evaluate a positoin between -infinite and +infinite
>where infinite is about 1 million.
>
>So i can get a score 0.020 which is better than 0.013, so there
>is some discrimination. No rude rounded off values as in the below
>text.
>
>Mate threats are not relevant first 35 moves of the game or so,
>chance i mate my opponent first 35 moves of the games is like zero.
Yes, I agree.
In rare cases a draw by permanent check may occur that early.
>With current search i already find mate in 20 without problems (especially
>when it is forced).
>
>However recognizing whether a difficult openings line leads to a draw
>is pretty interesting.
Exactly.
Recognizing (some) draws is the target.
Although probably not ones directly out of the opening, but rather
in the late endgame.
>How do you plan to search however, depth limited alfabeta?
The search is not changed, it is extended by a certain special case,
like you do when you add EGTBs.
Whenever a certain condition is met, you "probe" this special feature,
and are happy when it pops up with a definitive result. If it comes up
with a "dunno" (what EGTBs also do in case of a missing table), you just
continue the search as always.
Dan's hint (as I understand him) was to look into PN-search like techniques
to achieve the same result as I try to do with an EGTB-like technique,
because PN-search may probably be faster and less limited.
I hope I could clear up a bit.
Cheers,
Heiner
>The below description is not implementable.
>
>Please show some pseudo code!
>
>>The idea is similar to enumerating the state space in simple endgames. You will
>>select a won or unevaluated state for the attacker and a drawn or unevaluated
>>state for the defender. This will become an exact graph of the state space after
>>the iterations produce no more states. There are a few problems AFAIK. When will
>>you trigger the start of the algorithm? When is it cost effective, size of the
>>graph? How will you limit the enumeration, escape conditions? And it will work
>>much better when you have one attacker and one defender. In an ordinary game
>>search the position might be ambigious as to the eventual outcome and attacker
>>and defender might switch place due to a latent mate threat for example. The
>>idea will work wonders on fortress positions with locked pawns. But for more
>>dynamic positions with distinct conversions, a proof-number search or lambda
>>search will be more efficient. A PN^2 search will find a draw as easily as a win
>>given the right termination conditions.
>>
>>MvH Dan Andersson
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.