Author: Dann Corbit
Date: 14:49:17 05/14/01
Go up one level in this thread
On May 14, 2001 at 17:37:44, Uri Blass wrote: >On May 14, 2001 at 15:44:28, Dann Corbit wrote: > >>On May 14, 2001 at 14:51:16, J. Wesley Cleveland wrote: >>[snip] >>>I thought that is what we were discussing. If you have a hash table large enough >>>to store every position found in the search, then you do not need total path >>>information with each position, which means you could solve chess by considering >>>"only" about 10^25 positions. So, if Moore's law holds up, we could solve chess >>>by the end of the century, rather than by the end of the universe. >> >>Not a chance. Let's ignore the complication of things like the half-move clock >>for now. We shall also ignore the fact that you can ignore all the draw rules >>except for material count, and that it may be beneficial to do so at times. >> >>One of the fields of the hash position is depth. You will not know the answer >>to the true value of the position until the position has reached either >>won/loss/draw. Since chess has a depth of nearly 12000 plies, that implies a >>search so long and so deep that even if it were purely a binary choice you would >>never solve it. Just consider 2^10000 [about 2e3010] (which is absurdly >>smaller than the chess tree). Take the square root of that. Hmmmm. >> >>Having 10^50 positions in a hash table is useless unless you have analyzed them >>clear to the end. The end is so far away that it is laughable to consider that >>we might possibly get there. >I do not know if 10^25 is practically enough to solve chess but I am not sure >that it is not. >The point is that you may analyze only part of the legal positions in order to >solve chess. > >Instead of solving chess you can solve the following game that has the same >solution as chess but less positions. > >The rules are the same as chess with the following modifications: > >1)Moves that give the opponent to play a forced mate of at most 3 moves are >illegal. > >2)A side who has no leagl moves in this game and has legal moves by the chess >rules is losing the game. > >There are clearly less position in this game >(for example the position after 1.f3 e5 2.g4 is illegal byt the rules) > >Now you can replace the mate in at most 3 moves by the words a win without doubt >and you can say that moves that give the opponent a win without doubt are >illegal when win without doubt can be calculated in a short time. > >There are a lot of positions that can be described as a win without doubt. > >Example every position when the weaker side has only a king and no stalemate >chances when the stronger side has 2 connected pawns that the king has no chance >to capture. > >This no chance can be evaluated by a smart evaluation. > >The 50 move rule is not relevant because you need full 100 plies after you get a >position with only a king for the weaker side. This is a good idea to simplify analysis and surely it would be used. But suppose that in the tree there is a SINGLE trail through the tree where we have an average of two choices and goes only 1/4 of the way to the maximium depth. 2^3000 is still absurdly large. In short, the actual tree is truly enormous. Nobody knows how deep the darn thing is, even if we should say that everything close to a checkmate is dead. It might go the while 6000 plies and it might be much deeper if it turns out to be valuable to ignore draw rules for one party or the other. So, it could possibly be simpler. If so, nobody can say how much simpler. And it could also be much harder. In fact, the real tree could be absurdly deep.
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.