🚀 go-pugleaf

In article <vmx209wpxd0.fsf@minnie.i-have-a-misconfigured-system-so-shoot-
me>, Allwyn Carvalho <allwyn@ia-us.com> writes

>Is it always possible to force a mate with a Queen vs. a Rook (ie one
>player has a Queen, the other a Rook, and those are the only pieces on
>the board apart from the Kings).  If so, what is the strategy?

Technically this item is out of place in GNU newsgroup (see FAQ), but
nevertheless is relevant as an example of difficult positions which chess
progs must deal with (and it's fascinating), so here goes....

This ending requires very precise play - see Keres 'Practical Chess Endings'
1973 translated J Littlewood 1974 pub Batsford, London, (my copy printing of
1986).  See chapter 3 - Queen endings, section Queen v Rook.

That gives several good examples of strategy required, which is basically to
drive the king into a side file and/or back rank.  To achieve this the King
& Queen must cooperate in attacking the King, giving it only a few
restricted squares to move to, whilst at the same time threatening the rook.
The latter takes several forms, the main one being threat of a fork (Q
checks whilst attacking Rook).  However there are a few special positions
which are drawn - either stalemate or repetition.

<snip>

[I suspect, but haven't completely demonstrated, that in the position given
in the posting (WRd6, WKd7, BKe5, BQg1, white to move), black wins.]

>Thanks in advance.
>
>- allwyn

However programming wise there is a different way of looking at this
problem.  You've only got 4 pieces on the board, giving you nominally
64*63*62*61 = 15,249,024 different arrangements.  Each of these has 2 cases
- depending on side to move so there are really 30,498,048 different board
positions.  (This number ignores arrangements where both sides are in check,
kings next to each other etc, so it's an over-estimate.)

When you consider that direction of play (up-down or left to right) is
immaterial with these pieces, rotating the board and reflecting positions
reduces the actual no of logically distinct positions to less than 0.5
million.

It is well within the capacity of a PC to store all these positions (whether
30m or 0.5m).  Any move is then simply the number of another of the
positions.  The problem then reduces to finding the longest chain of
positions until mate, stalemate, position repeats, or whatever.  

I've an idea that something like this was programmed 10-15 years ago and a
very slippery eel it proved, gathering fresh momentum on the slightest
mistake by its opponent.   But I'm not sure whether it was the Q-R ending or
some other limited piece ending.  Anyone out there know?

Program design-wise too, it would be interesting to know to what extent a
human chess master follows the strategy approach as against the position
knowledge approach.  That's the sort of Q which needs exploring in depth
before we can hope to get chess progs which actually make you feel as if you
are playing a REAL chess player, not a machine. 

Hope that helps.  Enjoy your chess.

-- 
philip