Author: J. Wesley Cleveland
Date: 15:03:59 05/18/01
Go up one level in this thread
On May 18, 2001 at 14:49:48, Uri Blass wrote: >On May 18, 2001 at 14:04:38, J. Wesley Cleveland wrote: > >>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". > >I disagree >By your logic you can assume that the following positions are legal. > >[D]8/8/8/8/3k4/2p1p3/2P1P3/3BK3 w - - 0 1 >[D]rn1qkbRr/p1p1pp1p/1p1p1np1/8/1PPP1PPP/P3P3/8/RNB1KBN1 w Qkq - 0 1 > >They are obviously illegal(the bishop at d1 in the first case and the rook at g8 >in the second case cannot jump into their square from the opening position) but >there is no problem of generating thousands of positions if you calculate >backwards. however, these positions are legal. [D]rnbqkbRr/p1p1pp1p/1p1p2p1/8/1PPP1PP1/P3P3/8/RNB1KBN1 w Qkq - 0 1 [D]8/8/8/8/3k4/2p1p3/2P1P3/3bK3 w - - 0 1 > >Uri Right. I should have said "First, eliminate all obviously illegal positions". I think you could catch nearly all of them with six cases: 1. illegal combination of material, e.g. 5 queens and 5 pawns. 2. illegal pawn structure, e.g. 6 white pawns on the a file, and black has more than a king. 3. bishop blocked by 2 pawns on 2nd or 3 pawns on 7th rank, either original or current position. 4. rook on other side of pawn wall, pawns on all files, none advanced more than one square and side with rook has all its pawns. 5. king behind opposing pawn wall, with no possible path without being in check (this seems the most difficult). 6. both kings in check. A first try would be to check for 1,2,3 and 6 and put all positions with pawns on all files, none advanced more than one square, and all positions where there are no paths from the kings' current positions to their inital positions that are not attacked by enemy pawns into "not sure". Another test might to be to "unmove" each piece to its initial position, "unmoving" opposing pieces only as necessary.
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.