Author: Uri Blass
Date: 07:08:06 05/18/01
Go up one level in this thread
On May 18, 2001 at 09:47:44, Robert Hyatt wrote: >On May 18, 2001 at 04:32:14, Graham Laight wrote: > >>On May 18, 2001 at 00:50:30, Robert Hyatt wrote: >> >>>On May 17, 2001 at 19:08:15, J. Wesley Cleveland wrote: >>> >>>>On May 17, 2001 at 05:44:03, Uri Blass wrote: >> >>>>>You need to write a special program to generate random board even if you want >>>>>only 20 samples because there is no easy way to choose a random position when >>>>>every position gets the same probability without a special program. >>>>> >>>>>Uri >>>> >>>>This seems overly complicated. If you have an encoding method, say, that encodes >>>>all positions into 168 bits, then generate random 168 bit numbers and see what >>>>percent of the corresponding positions are legal. >>> >>> >>>This is actually very difficult. IE for a position to be legal, you need to >>>prove the following: >>> >>>1. side on move is not in check; >>>2. pieces could actually reach the given position (ie if you have 3 pawns on a >>>single file, the opponent must be missing at least two pawns/pieces; >>>3. the side not on move actually could have made a legal move to get us to the >>>current position. >>>4. then the side on move actually could have made a legal move to get us to >>>that previous position. >>> >>>IE 3 and 4 are recursive and could be restated: >>> >>>3a. The position must be reachable from the opening position of the game. >>>That is yet another exponential problem. Or is that O(1) too. :) >> >>This isn't necessarily so (though I admit it might be) - because we're talking >>about statistical sampling here. >> >>In view of Bob's constraints 1. and 2. above, my approach would be to generate >>random positions and classify them in one of 3 ways: >> >>a) Obviously legal >>b) Obviously illegal >>c) Not sure >> >>Whether or not this simple approach works depends on the size of c). If it's >>relatively small, there's no problem. If it's relatively large, then it >>threatens the integrity of the exercise. >> >>-g > >A is _very_ hard to determine. Retrograde analysis is very interesting when you >have lots of time to spend on it. I agree that proving that a position is legal or illegal may take time but I believe that inteligent people can find usually after some hours in the worst case if the position is legal or illegal. There are a lot of cases when it can take a few seconds to see that a position is illegal(for example you can prove that you need at least 3 captures of black pieces to get the position when there are 14 black pieces on the board or if both kings are in check or if the king is in check from 3 directions). I think that most of the positions can be identified as obviously illegal easily. I believe that a significant part of the positions in classes a and c are legal positions and that humans usually can prove if they are legal or illegal if they use few hours per position so if humans start to check them they can evaluate the number of legal positions. Another point is that I read that there is a free program that can compose games for part of the legal positions so it is also possible to use it. 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.