efficient algorithm for safety of pieces

54 views

Deniz Yuret

Mar 18, 1993, 1:14:43 PM3/18/93
to
During the course of building a chess program, we encountered the following
problem: Assume you are white, and it is black's turn to play. You want to know
if black can capture one of your pieces and win material. The information you
have is the piece being attacked, the pieces that are defending it, and the
pieces that are attacking it. Can you find a non-recursive algorithm to compute
safety just from this static data. (Details you might consider are whether
defending or attacking pieces cover one another, whether you just captured a
piece and want to take that into account in your calculation.)

deniz

dwe...@uoft02.utoledo.edu

Mar 19, 1993, 12:09:06 AM3/19/93
to
In article <1oae6j...@life.ai.mit.edu>, de...@crunch-berries.ai.mit.edu (Deniz Yuret) writes:
> During the course of building a chess program, we encountered the following
> problem: Assume you are white, and it is black's turn to play. You want to know
> if black can capture one of your pieces and win material. The information you
> have is the piece being attacked, the pieces that are defending it, and the
> pieces that are attacking it.

> Can you find a non-recursive algorithm to compute
> safety just from this static data.

No. No I can't. hey...that was easy!!!

>
> deniz
>

hey, let me know if you need any other questions answered. ;-)

don wedding

John Black

Mar 19, 1993, 3:05:23 AM3/19/93
to
Playing "solitaire chess" is fast becoming my favorite method of study. It
allows me to closely simulate playing conditions and exercise my judgement and
calculating abilities. For you other players who also use solitaire chess to
study, I have a few questions (along with my answers):

1. What are your sources for these tests? (Mine are the monthly Pandolfini
columns in _Chess Life_ and the book "Test your Opening, Middlegame,
and Endgame Play" by Ken Smith and Roy DeVault.)

2. How much time do you spend per move on average? (I spend about 5 minutes
per move on average.)

3. Is your solitaire chess rating close to your USCF rating? If "no," what is
the differential and how many tests have you taken? (Mine is about
200 points above my USCF rating after 15 tests.)

4. Does your score vary widely depending on the style of the game? (I do
markedly better in attacking games than in positional games.)

5. Do you think these things are helping your chess? Have you measured any
improvement? (I definitely have.)

If you would please take a few minutes to reply to me directly (j...@ingres.com)
I'd be happy to summarize.

Thanks,

john//
j...@ingres.com

John Black

Mar 19, 1993, 3:17:03 AM3/19/93
to
A flyer for the local LERA Class tourney this weekend has on it the following
position:

+---+---+---+---+---+---+---+---+
8 | |...| |...| |...| k |...|
+---+---+---+---+---+---+---+---+
7 |...| |...| |...| |...| | Uppercase is White
+---+---+---+---+---+---+---+---+ Lowercase is Black
6 | |...| |...| |...| |...|
+---+---+---+---+---+---+---+---+ o == pawn
5 |...| |...| |...| |...| |
+---+---+---+---+---+---+---+---+
4 | |...| |...| |...| |...| Caption: "White to Play; who wins??"
+---+---+---+---+---+---+---+---+
3 |.o.| |.o.| |...| |...| |
+---+---+---+---+---+---+---+---+
2 | |...| |...| |.O.| O |.O.|
+---+---+---+---+---+---+---+---+
1 |...| K |...| |...| |...| |
+---+---+---+---+---+---+---+---+
a b c d e f g h

I spent an embarrassing long time trying to solve this (almost 2 hours) and I
believe I finally have the answer. But I checked every endings book I have
and I could NOT find this study anywhere (even in Averbakh/Maizelis). Can
anyone point me to a reference so I can check my solution?

Thanks,

john//
j...@ingres.com

Fabian Maeser

Mar 19, 1993, 8:38:29 AM3/19/93
to
In article <1993Mar19....@pony.Ingres.COM> j...@Ingres.COM (John Black) writes:

> +---+---+---+---+---+---+---+---+
> 8 | |...| |...| |...| k |...|
> +---+---+---+---+---+---+---+---+
> 7 |...| |...| |...| |...| | Uppercase is White
> +---+---+---+---+---+---+---+---+ Lowercase is Black
> 6 | |...| |...| |...| |...|
> +---+---+---+---+---+---+---+---+ o == pawn
> 5 |...| |...| |...| |...| |
> +---+---+---+---+---+---+---+---+
> 4 | |...| |...| |...| |...| Caption: "White to Play; who wins??"
> +---+---+---+---+---+---+---+---+
> 3 |.o.| |.o.| |...| |...| |
> +---+---+---+---+---+---+---+---+
> 2 | |...| |...| |.O.| O |.O.|
> +---+---+---+---+---+---+---+---+
> 1 |...| K |...| |...| |...| |
> +---+---+---+---+---+---+---+---+
> a b c d e f g h
>
>
>I spent an embarrassing long time trying to solve this (almost 2 hours) and I
>believe I finally have the answer. But I checked every endings book I have
>and I could NOT find this study anywhere (even in Averbakh/Maizelis). Can
>anyone point me to a reference so I can check my solution?
>
>Thanks,

Solution ...

The following position can be found in many endgame books:
(unfortunately I don't remember any book-titles...)

| | | |
--+---+---+---+--
|...| k |...| White to play (Uppercase) cannot
--+---+---+---+-- avoid the blockade of his pawns
| |...| | (the pawns may NOT be on the 2nd rank,
--+---+---+---+-- but the king may be on the 8th!)
|...| |...|
--+---+---+---+--
..| P |.P.| P |
--+---+---+---+--
| | | |

(1)

The following pawn structures are "lost" for the pawn-side to move:

| | | | | | | | | | | |
--+---+---+---+-- --+---+---+---+-- --+---+---+---+--
|...| |...| |...| |...| |...| |...|
--+---+---+---+-- --+---+---+---+-- --+---+---+---+--
| k |...| | | |.k.| | | P |.k.| P |
--+---+---+---+-- --+---+---+---+-- --+---+---+---+--
|.P.| |...| |...| P |...| |...| P |...|
--+---+---+---+-- --+---+---+---+-- --+---+---+---+--
..| |.P.| P | ..| P |. .| P | ..| |...| |
--+---+---+---+-- --+---+---+---+-- --+---+---+---+--
| | | | | | | | | | | |

(2) (3) (4)

| | | | | | | | | | | |
--+---+---+---+-- --+---+---+---+-- --+---+---+---+--
|...| |...| |...| k |...| |.k.| |...|
--+---+---+---+-- --+---+---+---+-- --+---+---+---+--
| P |.k.| | | |. .| | | |...| |
--+---+---+---+-- --+---+---+---+-- --+---+---+---+--
|...| P |...| |.P.| P |...| |.P.| P |...|
--+---+---+---+-- --+---+---+---+-- --+---+---+---+--
..| |...| P | ..| |. .| P | ..| |...| P |
--+---+---+---+-- --+---+---+---+-- --+---+---+---+--
| | | | | | | | | | | |

(5) (6) (7)

and so on...

back to the original position:

Obviously, white can only move pawns and therefore will lose
if his pawns get blocked.
Black's strategy is quite simple: "attack" the pawns to force them
ALL to advance from the 2nd rank. This first attempt to block the pawns
will fail because white has the choice to move his last pawn on the 2nd
by 1 or by 2 squares. But after that, black is able to reach one of the
positions above, at least position (1) with his king on the 8th.

E.g. 1.f4 Kg7 2.g4 Kf6 3.f5

- 3.h4? Kg7! -> Position (1)
- 3.h3 Kg6 and 3.g5+ Kg6 are very similar to the main variation

3...Kg5 4.h3(!) [4.h4+ Kf6 -> Position (2)] 4...Kf6 5.h4 Kf7! and now:

- 6.h5 Kg7 7.g5 Kg8! [Position (1)] 8.f6 Kf7 9.h6 Kg6
- 6.g5 Kg7 7.f6+ Kg6 [Position (5)] 8.h5+ Kf7 9.h6 Kg6

and black wins easily!

febi

--
Fabian Maeser
Institut fuer Theoretische Informatik
ETH Zurich Switzerland
e-mail: mae...@inf.ethz.ch

Robert Hyatt

Mar 19, 1993, 2:58:35 PM3/19/93
to

We have such a piece of code in Cray Blitz. It's only shortcoming is that
is simply looks at a "square" and determines if the other side can capture
on it with a gain of material. In doing this, it assumes all pieces can
participate in the capture/exchange sequence. If one of these pieces is
overloaded, it will produce wrong answers.... same if one of the pieces is
pinned, etc. It is used *only* to "grossly" determine if a capture is
good, and should be examined first, or bad and should be examined last.

Bob

--
!Robert Hyatt Computer and Information Sciences !
!hy...@cis.uab.edu University of Alabama at Birmingham !

Lloyd Lim

Mar 20, 1993, 1:36:20 AM3/20/93
to
In article <1993Mar19....@cis.uab.edu> hy...@cis.uab.edu (Robert Hyatt) writes:
>
>We have such a piece of code in Cray Blitz. It's only shortcoming is that
>is simply looks at a "square" and determines if the other side can capture
>on it with a gain of material. In doing this, it assumes all pieces can
>participate in the capture/exchange sequence. If one of these pieces is
>overloaded, it will produce wrong answers.... same if one of the pieces is
>pinned, etc. It is used *only* to "grossly" determine if a capture is
>good, and should be examined first, or bad and should be examined last.

A similar exchange evaluator is described in D. Spracklen and K. Spracklen,
"An Exchange Evaluator for Computer Chess", Byte, vol 3, no 11, Nov 1978,
pp 16-28. The idea behind these things is pretty simple.

+++
Lloyd Lim Internet: l...@cs.ucdavis.edu
Lim Unlimited America Online: LimUnltd
330 W. Iris Ave. AppleLink: LimUnltd
Stockton, CA 95210-3738 CompuServe: 72647,660