Author: Heiner Marxen
Date: 06:13:51 06/01/02
For over 2 years I have thought from time to time about a technique
to recognize certain simple types of draws, which are not easily or
not at all recognizable by search. An application example is
a permanent check.
The basic technique is similar to the construction of EGTBs.
This week I have started to implement some experimental first version
(not yet ready), and I'd like to share my idea here. If anyone has
done something similar or read about it, I would like to hear about it.
AFAIK this technique is new.
I will try to use this technique in Chest, in order to cut off complete
search trees, where "draw at least" could be proven.
Playing programs for sure have different needs than a special mate
prover, but recognition of "at least draw" could be quite interesting
for playing programs in the endgame (IMHO).
Since I haven't finished any code, yet, I cannot say anything about
efficiency issues. But I'd like to discuss the idea and possible
applications, as well as implementation details (if anyone wants to).
As you will detect below, my thoughts are far from being
crystal clear. Yet I feel sure that the basic idea is good,
and can be implemented, and will yield draw evaluations,
which otherwise are hard to get.
---------------------------------------------------------------------
From a memo file...
Basic Idea
^^^^^^^^^^
We try to verify a simple defender strategy (like permanent check),
such that only two pieces are moving around, one defender and one
attacker piece.
We index all positions with those two pieces being at any square,
and either side to move, building something like a 2-piece EGTB,
but with further material on board, which just does not move.
Even if we do not succeed to prove that the attacker cannot escape,
we still can come up with a minimum depth that the attacker needs
to escape from the defender strategy. During this time the
attacker cannot achieve his goal.
The attacker (basically) must not have other legal moves than
those with his selected VP. Either we have another source of
information (e.g. TT aka hash table aka "acm") stating a minimum depth,
or our defensive strategy breaks, when the attacker can legally
move another piece.
The result of such a computation is either
- a minimum depth (in plies) that is needed to achieve the goal
the attacker searches for, or
- a proof that the attacker cannot achieve his goal at all.
That corresponds to a minimum depth of +Inf.
Applications
^^^^^^^^^^^^
- Permanent Check
A defender piece is hunting the aK.
- Corresponding squares
The defender K blocks out the attacker K. E.g. Fine #70.
---------------------------------------------------------------------
From the (incomplete) implementation...
Analysis with two virtual pieces.
The basic idea here is to perform an EGTB-like analysis for a certain,
restricted scenario:
- We need attacker/defender roles for this, i.e. help-jobs cannot come here.
- One side wants to achieve some goal within a finite amount of moves.
This is usually the attacker. He tries to achieve some goal, which
is not yet there: he wants to change something.
We call him here the "changer" C.
- One side wants to avoid the other side to achieve some goal,
by blocking him from changing the status quo.
This is usually the defender.
We call him here the "blocker" B.
- We pick two pieces (one of each side) and restrict to moving only
these two pieces. Since we do not really move them on the board,
these two pieces are called "virtual".
VP = virtual piece
- The blocker B voluntarily restricts himself to only move his VP,
and to not capture any C-piece. He wants to conserve the status quo.
That is his strategy (plan). If he cannot do so any more, his plan
fails at that point.
- The changer C tries to either achieve his goal directly within
the plan of B (if that is possible at all), or to break out of the
frame set by B's plan.
C succeeds (and B's strategy fails at this point) if either:
+ C's goal is achieved directly, despite B's strategy is still active.
+ C captures some B-piece
+ B cannot do a legal move according to his strategy.
- In the end (where C succeeds) we have a simple small ply-number,
which is still necessary (at least) for C to achieve its goal.
This is just a lower bound, not an exact value (in most cases).
- Where C cannot move any more (and has not achived its goal),
he will need infinitly many plies to achieve its goal.
Hence we will have a special encoding for "infinity".
- The "value" of all positions we index here, is the minimum amount
of plies still necessary to achieve C's goal.
- C tries to minimize the distance to his goal. Among all his legal
moves he selects the minimum value.
- B tries to maximize the distance to C's goal. Among all his legal
moves, which are admissable for his strategy, he selects the maximal
value.
- Whenever one side has no legal moves (within our framework),
we must decide directly for a "value".
In doubt (if we are not sure about another value) we choose value=0,
i.e. (may be) the changer C has achieved his goal now.
- From the terminal positions with the smallest values we work backwards
(like in EGTB construction) and assign all values one greater.
- When we have assigned all values, the still not assigned positions
are either not reachable, or have implicit value "infinity". This is
analogue * to assigning "draw" values to the rest of the positions
in EGTB construction.
Possible applications:
- The defender tries to do "permanent check".
- The defender tries to force stalemate (with a "wild" piece).
- The defender tries to block out the attacker (i.e. Fine #70).
Corresponding squares is a special case of this.
In most cases the attacker's (C's) VP will be its king, but this need
not always be so.
The important feature of this computation is, that we can assign values
to the "rest" of positions (infinities!). No normal tree search can
achieve that. While a hash table helps, a search still only derives
approximately the depth which was asked for.
Effectively we detect arbitrarily large, forced cycles.
This could also be applied to playing programs, which for the big cycle
now could derive an (upper or lower) bound of "draw", since one side
(the "attacker" C) is proven to not be able to win.
General restrictions:
- pawns as VP
We exclude pawn as VP in general. Pawn moves are not reversible,
and hence with pawns we cannot construct cycles at all.
While we still could get some distance info, our setup is much too
large for the very restricted case of a pawn moving (it would do at
most 6 moves (including promotion)).
- promotions
Since pawn are excluded as VP, promotions just do not occur.
- e.p.
Since VPs are no pawns, e.p. cannot occur within our setup.
If the initial position is marked to allow an e.p., and
+ B is to move, he just chooses to not use this move.
+ C is to move, we have a problem, and refuse to work.
- castling
While castling is possible for C, we refuse our work.
FFS: we may assure that castling goes away immediately (perm check)
Castling of B is no preblem: we choose to not use it (strategy limit),
and also, for consideration of legal moves (mate/stalemate) we know,
that when castling is a legal move, there is at least one legal
non-castling K-move.
Of course, many refinements and generalizations are possible.
We will consider those, when we have a working basic module,
and can collect experience with it from examples.
---------------------------------------------------------------------
There is even another, more abstract "connection":
in a way such an analysis starts with a "plan" or "strategy" of
the defender, and then tries to verify that it can be carried
on indefinitely (or at least for some guaranteed number of plies).
So, in a way, we deal with a "plan", here, don't we?
Ok, this is already very long.
Eagerly waiting for comments...
Heiner
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.