Author: Vincent Vega
Date: 15:36:17 09/01/00
Go up one level in this thread
On September 01, 2000 at 02:33:42, Uri Blass wrote: >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 I don't think writing a program that could create games to prove most positions legal would be too difficult. It would certainly be much more fun than doing these positions manually. I guess one could construct positions that would make it tough for such a program but I don't think these difficult ones would make up a large percentage of our randomly chosen sample. It'd be nice to get a lower bound on the number of total positions. BTW, did your pseudo-legal position generation avoid all the rules you could find (for example: if the king is double-checked by a knight and a rook, if the rook is within 2 squares of the king, the position is illegal (many other rules for double-checks); a side can't have 16 pieces if it doesn't have both light- and dark- square bishops; pawn structure and number of opponent's pieces determine max. number of possible promotions, etc.)?
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.