Re: How long would it take a computer to completely "solve" chess?

From: Guy Macon (http://www.guymacon.com)
Date: 09/14/04 

Date: Tue, 14 Sep 2004 09:11:50 -0700

(I will be starting a hot project later this week and will be limiting
my newsgroup usage to reading selected posts and an occasional reply.)

Sean O'Leathlobhair <jwlawler@yahoo.com> says...

>But if we do any pruning, can we be sure that we have not missed some
>very obscure trick? We may have solved the game for all practical
>purposes but if we have pruned anything, could we really say that we
>have theoretically solved chess?

Yes. Yourvobjection is valid for the normal runing that chess
programs do, but there are other ways to prune which have zero
chance of missing something subtle like throwing away two rooks
and a queen in order to set up a forced mate in 49. Here is how:

Imagine that you are a program searching the entire move tree,
looking to find wins, losses and draws.

Now add a modification; if you see a position that has a king and
a rook against a king, search one ply farther to rule out stalemate
or losing the rook, mark it as a win for the side with the rook,
and stop searching that branch. Why? because there exists an
algorithm that wins every time from that position. You just pruned
without any chance of missing something subtle.

Now imagine a thousand years of humans and computers searching
for more algorithms that will reduce the size of the search...

It's not just that RK vs K position that you can prune at either;
yiu can prune at any position that has 6 men on the board (soon it
will be 8); we know the result from every such position already.

Relevant Pages

  • Re: How long would it take a computer to completely "solve" chess?
    ... >> a rook against a king, search one ply farther to rule out stalemate ... >> and stop searching that branch. ... the tree will get to the same position (with same ... A position that has a known algorithm for winning. ...
    (sci.math)
  • Diagonal vectors for BSP trees
    ... I was reading the paper "Refinements to nearest-neighbor searching in k ... He mentions that using planes of arbitrary direction speeds up nearest ... "An Optimal Algorithm for Approximate Nearest in Fixed Dimensions", ...
    (comp.graphics.algorithms)
  • Re: How long would it take a computer to completely "solve" chess?
    ... > a rook against a king, search one ply farther to rule out stalemate ... > and stop searching that branch. ... I can see that this sort of pruning is safe. ...
    (sci.math)
  • Re: [newbie] Best way to search for binary data
    ... [string searching ... ... > searching random bytes. ... algorithms are usually preferred to the Knuth-Morris-Pratt algorithm. ... void init_search(const char *string) ...
    (microsoft.public.vc.language)
  • Re: "Algorithms" in Molecular Biology?
    ... provided now includes its own refutation, continuously evading any test to ... for refuting my point is to provide a definition of Algorithm which all ... Is searching not an answer in and of itself. ...
    (sci.bio.evolution)