Computer Chess Club Archives




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

Author: leonid

Date: 16:23:06 05/24/01

Go up one level in this thread

On May 24, 2001 at 18:24:50, Heiner Marxen wrote:

>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".

After your terminology I speek about "defender". It will be the end of search.
Just one ply with "attackers" moves and one ply with "defender" moves.

It will be only two plys search if all moves regarded are all the time
completely legal. It will be three plys search is moves are illegal and must be
verified for "defender" in the third ply.

>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.

My proceed this way:

1) Attacker ply search only for checking legal moves.

2) Defender ply search just one legal move. If move is found - no mate.
                                            No move found - mate.

My question was about "defender" ply. In this ply my program start all the time
with the search for "one legal move" for king. Reason - when king is under the
check it is very often king that do the move. My question was if you start your
search for possible "one legal move" with king.

If "defender" start its search for possible "one legal move" not with kings but
with other pieces, then time of search is almost the same as before. Time was
found by searching mate for few positions 8 moves deep. Even if time was almost
identical (only 1% of difference), NPS went up in about 25%. Reason for 25%
increase - program is forced to generate more moves to reach the response.
Almost equal time - kings moves demand more time for verication of legality.

Maybe this time you could understand what I was been talking about. If not -
never mind. It was more by curiosity. I just want to see how close we came by
writing the same logic. Do we coincide even in tiny details?

>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 ;-]

This resemble very much to what I have in my program. Before generating legal
moves for certain position, all data needed for recognizing legality of those
moves is found in advance. This is why more legal moves found for each ply, more
efficent is move generator. And this is why verification of 90 moves for
legality will take only slightly more time then verification of 30 moves.

Thanks for patience,

>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.04 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.