Author: Uri Blass
Date: 20:15:39 09/01/00
Go up one level in this thread
On September 01, 2000 at 18:36:17, Vincent Vega wrote: >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.)? No. My pseudo legal positions only avoided some illegal material configurations and assumed that the pawns are in the obvious 48 squares. Here are some examples: 1)White has 7 pawns+3 rooks+3 bishops is impossible. 2)White has 7 pawns 2 queens 2 rooks 2 bishops 2 knights+king is possible. The same for black but both things together is impossible because the number of promoted pawns of white can be at most twice the number of captures of white+the number of captures of black and in this case there were no captures. My program even considered some illegal material structures. Exampe: If the only captured piece is a black knight then it is clear that the number of promoted white pawns is at most 1 but my program let white to do 2 promotions for every capture and not only for captures of black pawns. V.tomic improved my bound by letting white to do one promotion for every capture of a piece and 2 promotions for every capture of a pawn and the opposite. There are still many illegal structures that my program considered like a2,a3,b2 because my program did not check nothing about the pawn structure except being in the 48 obvious squares. It is possible to improve my program not to consider many of the impossible pawn structures but in this case counting the number of positions will take more time. I do not see a way to avoid cases when both kings are in check or cases when the king is checked by a rook and a knight when the distance between the rook and the king is 2 in generating the pseudo legal positions. It is possible to build a program that proves that many of the pseudo legal positions are illegal but the more hard task is to build a program to build a game that lead to the legal positions because usually I can be sure that the strange pseudo legal position is legal only after seeing a game. 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.