efficient algorithm for safety of pieces
Deniz Yuret
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
> 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
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
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
> +---+---+---+---+---+---+---+---+
> 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
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
>
>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