Author: Uri Blass
Date: 21:13:13 05/14/01
Go up one level in this thread
On May 14, 2001 at 17:49:17, Dann Corbit wrote: >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. If you have enough memory 2^3000 is not relevant because the relevant number is the number of logical chess positions that is less than 10^50 and in this game even smaller than chess. If you try to construct the 32 piece tablebases in the game when it is illegal to play moves that give the opponent a simple win then it is enough. You can also ignore the 50 move rule for the case that you prove that chess is a draw. In this case proving that there is no win in 6500 without the 50 move rule is enough to prove that there is no mate in chess with the 50 move rule because every game of 13000 plies is a draw by the 50 move rule. In this case the number of iterations is not a problem. I believe that chess even without the 50 move rule is a draw. My idea to solve chess in 2050 or 2100 is the following idea: 1)Generate all the leagl positions in the game when the sides have no right to let the opponent a win without doubt(you should construct an evaluation to define a win without doubt and it should be something that you can compute in a relatively short time like 0.01 seconds on today's hardware In order to do it you generate all the possible positions in games of x plies when x<13000(the number can be even slightly smaller than 13000 but I am lazy to calculate or to find it) I do not know if the number of these positions is smaller or bigger than 10^25 It may be 10^30 and may be 10^20. It means that if you are optimistic you may get 10^20 possible numbers when everyone of them is of 192 bits or even less bits if there is a simple way to represent chess positions by numbers. You can sort all these numbers so it will be easy to find the place of every position in your array. 2)Calculate tablebases for all the positions that you found. The tablebases will give you for every position if it is a win in n moves for n<6500. A win in n moves does not mean mate in chess but mate in the game similiar to chess when it is illegal to play moves when the opponent gets a position that is evaluated as a win without doubt. Uri
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.