Computer Chess Club Archives




Subject: Re: Mating proving techniques (was: One very easy mate to solve.)

Author: Heiner Marxen

Date: 15:24:50 05/24/01

Go up one level in this thread

On May 24, 2001 at 15:50:42, leonid wrote:

>Hi, Heiner!

Hi Leonid!

>One question but about something else. Do you remember in your "mate2" search
>what pieces you look at first for responding side? Side that respond on attack.
>When I regarded quickly your description, I had the impression that we did
>almost the same work on this level even if names are different. Only I am
>curious to know what pieces you search first for responding side. Had the
>impression that it is not for the kings moves that your program look frist. My
>program search for one legal king's moves and only later one legal move for the
>other pieces.

Some terminology, first.
A classic mate problem mostly is stated as "white to move and mate in N".
Then, I call white the "attacker" and black the "defender".
The attacker moves are solution "candidates", and the defender moves I
call "answers".

We talk about the last three (legal) plies of a mate-in-2: a candidate
followed by an answer, followed by a mate move.

In a normal mate search we have to consider (search) all legal candidates,
one answer for each of them, and then detect, that there is no mate move
left (most of the time).

In normal search Chest would prefer checking and capturing moves as answer.
But the "mate2" module tries to replace the search of some of the
candidates, by proving that there exists an answer after which there will
not be any mate move.

Here, a fixed answer is picked for all candidates.  It is one of the available
king moves.  If there is none available, "mate2" just fails.
To pick a king move was just the most simple choice: the king is always there.
Also, "mate2" has to be quick, quicker than the search it replaces, so it
better not considers too many alternatives.
Chest picks that king move which has maximal king mobility after the move.

How Chest manages to prove, that after a candidate move, and a fixed answer
there will not be any mate move possible, is somewhat involved.  Chest
estimates the set of flight squares around the defender king (to be mated)
that is guaranteed to be left after candidate and answer, and then with
the help of precomputed tables matches that against the attacker material
on the board.  Often enough it finds "the attacker cannot cover all those
flight squares in just one move", which is the desired result.
[More details available on request ;-]

There is a long comment at the top of "mate2.c", but I'm not sure whether
it is legible for anyone except myself  :-(
If you have more questions, just continue to ask :-)

> When king is searched later, speed is almost identical but
>slightly lower. All difference could be around 1%. NPS will be much higher.
>Could go up 25%. I speak all the time about what is in your program 3 plys

Unfortunately, I did not understand this part.  If you want me to understand
it, you have to rephrase.


>I just went today to this part and looked if something in the past was not done
>in its best. Tried to change the generation of moves for in mate in 1 (in your
>its is mate in 2) but reached the same response that I remember was found many
>years ago. I still wonder how you did this part.

This page took 0.01 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.