A story about Python... sort of

[Russell Reagan]

"Bob Gailer" <bgailer at alum.rpi.edu> wrote

> Physically impossible? or impractical. If it can be solved by Turing
> machine computation then it is physically possible, even though it might
> take more time/resources than anyone cares to expend.

Or more time and resources than anyone has, which would make it impossible,
for now.

There are two ways to go about it. One is storing all of the positions and
their distance to a theoretical result (win in N plies, draw), using a
retrograde approach. This is how current endgame tablebases work. The other
is on the fly depth first search. Currently neither are anywhere close to
producing a practical solution. It's been said that there are more chess
positions than there are atoms in the universe, so no current technology
could possibly store the required information, even if we had the time to
generate all of those positions, which we don't. So that leaves it to the
search which requires only a tiny amount of information storage.
Unfortunately, the search increases exponentially as the depth increases.

A quick estimate, judging from the abilities of current programs and
estimated hardware in about 18 months (10GHz, Intel), it would take about
19,365,300,260,498,916 years to search to a depth of 60 ply (30 full moves),
and it is very unlikely that there is a forced win in the first 30 moves
anyway, with both sides playing perfectly. So, for now it's impossible and
impractical.