Author: Graham Laight
Date: 01:32:14 05/18/01
Go up one level in this thread
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
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.