Author: Uri Blass
Date: 23:33:42 08/31/00
Go up one level in this thread
On August 31, 2000 at 23:44:39, Vincent Vega wrote: >On August 31, 2000 at 16:41:22, Uri Blass wrote: > >>On August 31, 2000 at 15:54:16, Frederic Friedel wrote: >> >>>But we don’t need to do that in order to solve chess (in the Thompson endgame >>>sense). The number of possible legal chess positions is far smaller: between >>>10^53 and 10^55. > >It is easy to see that the number of legal positions is less than 10^51 with >just a few simple rules (1 king per side, at most 16 pieces per side, no pawns >on 1st or 8th row). > >> >>The number of possible legal positions is really smaller and my counting program >>found that it is smaller. >> >>3.7010630121207222927827147741452119115968e46 is the upper bound that my program >>found(not considering side to move and castling or en passant rule). >>Ratko v.tomic improved it to a smaller bound but not clearly smaller. >> >>I guess that the real number of positions is between 10^43 and 10^45. > >I think this estimate is probably close to the truth. En passant and castling >won't add a significant number of positions because they require very specific >board setups. > >> >>It is possible to get an estimate for this number by the following steps. >>1)counting the exact number of pseudo-legal positions(I will call it x). >>2)generating 10000 of random pseudo-legal positions. >>3)counting the number of the real legal positions out of the 10,000 pseudo-legal >>positions(I will call it L). >>4)get the estimate x*L/10000. >> >>We must be careful that x will not be too big(otherwise we may get a very small >>number in step 3 and in this case the estimate cannot be trusted). >>An extreme case is the case when L=0 and the estimate in step 4 is 0. >> >>If we get L>30 we can know that we found a good estimate. >> >>This is a hard work to do it and I am not going to try it unless I find somebody >>to pay me for this job(at least 10000$). >>Checking the 10000 positions is a hard work(If I need 6 minutes to decide for >>every position if it is legal then I need 1000 hours only to do step 3). >> >>I do not believe that I will find somebody who wants to pay for this job so I am >>not going to try to do this job. >> >>Uri > >Why do you think that the process of checking if a pseudo-legal position is >legal can't be automated? I think one could devise an algorithm that would look >at all the things a human could possibly check. It is not so simple. You can prove that a position is illegal by automatic algorithem(for example if both kings are in check) but in order to prove that a position is legal you have to construct a game that is leading to the position and I do not know about a program that can do it. You are right that it is possible to save time by automatic checking and checking manually only the undecided positions. Uri
This page took 0 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.