Author: J. Wesley Cleveland
Date: 11:04:38 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. And doing so will really open your eyes to >how hard this is to do. I think you could make a close approximation to A pretty easily. Generate "unmoves" for a few ply and if there are tens of thousands of different positions, assume that one of them is reachable, if at some ply, no new positions are reached, it is illegal, else call it "not sure".
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.