[FOM] AI-completeness

[joeshipman@aol.com]

Tim,

The situation for specific endings is somewhat different than you 
describe, though your essential point is unaffected:

1) K+Q vs K+B+B and K+Q vs K+B+N are both always won for the Queen 
except for 2 specific "fortresses" which were discovered by Lolli and 
Karstedt respectively in the 18th and 19th centuries. Consensus opinion 
of Grandmasters before the databases were developed was correct for K+Q 
vs K+B+N and incorrect for K+Q vs K+B+B. In both cases, it is easy for 
the stronger side to prevent the fortress if the weaker side cannot 
reach it within  a very few moves; but in the case of the B+N, the 
winning strategy is "easy", while in the case of the B+B, it is "hard" 
to make real progress (it is easy to prevent the fortress but hard to 
find the Zugzwangs that defeat several other pseudo-fortresses).

2) K+Q vs K+N+N was known to have fortresses but was believed to be a 
win in general; the database research showed that the two knights were 
able to reach a drawing fortress much more often than had previously 
been believed ("most of the time" when the K and 2 knights are close 
together and not on the edge and the opposing King is far away), though 
there are still many positions won for the Queen.

3) The other 5-piece ending where conventional wisdom was overturned 
was K+B+B vs K+N where it was previously known how to break the 
standard fortress, but the tricky maneuvers to prevent the weaker side 
setting up the same fortress in a different corner were not understood.

4) In K+B+N vs K+N, there is one class of positions in which the B+N 
have an extremely long and difficult win, which was well-understood by 
study composers pre-database.

5) All of these 5-piece endings, plus R+P vs R, are within the capacity 
of a human grandmaster to learn how to play almost perfectly. The only 
5-piece ending which is too difficult for humans to learn the general 
case of is K+Q+P vs K+Q.

6) The known 6-piece endings which take hundreds of moves are K+Q+N vs 
K+R+R and K+R+B vs K+N+N, which are won in general but too difficult 
for humans to make progress in (though since they are won "in general" 
humans can't really "spoil" the position which they very easily do in 
K+Q+P vs K+Q).

7) In the situation you mention with K+R+R vs K+R+N, isn't it the case 
that the "won" positions are sparse?

8) Re the ending you mention with K+Q+N vs K+R+B+N: I was not aware 
that this had been solved; are the "won" positions sparse or dense, and 
what other 7-piece endings have been solved?

-- JS


*************
People had developed endgame theory prior to the large-scale 
computation
of tablebases, but a significant amount of this theory was shown to be
incorrect.  For example, K+Q vs. K+B+B (or K+N+N) was thought to be 
often
drawn, whereas now we know that it is almost always a win for K+Q.  If 
you
don't believe in the knife edge, you should look at K+R+R vs. K+R+N or
K+Q+N vs. K+R+B+N.  There are many positions which are, for example, a 
win
for the stronger side, but only after perfect play for several hundred
moves, and on almost every move the slightest misstep by the stronger 
side
leads to a draw and the slightest misstep by the weaker side shortens 
the
win significantly.  The "reasons" for why the unique best move works 
and
the others don't are completely inscrutable.  I would say that this is 
in
fact typical, and not exceptional, for endgames where there is a small
material imbalance between the two sides.

Even in cases where the endgame theory was worked out before computers
(and was not later overturned), it wasn't easy to master.  Anyone who 
has
made a serious effort to master K+R+P vs. K+R knows that very delicate
positions can arise in practice, that can be handled perfectly only if
you've memorized a lot of special positions and variations.

Having said that, I grant that it's possible that the initial position 
in
chess is so "dead drawn" that these knife edges never arise and don't
matter, if all you care about is the value of the game starting from 
the
initial position.  So maybe, as you suggest, checkers is a better 
analogue
to chess than Othello is.
**************
________________________________________________________________________
AOL now offers free email to everyone.  Find out more about what's free 
from AOL at AOL.com.