Author: Robert Hyatt
Date: 12:47:39 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. > >Uri That's why I said it was a hard problem. The only problem is I don't have any real estimate as to what percentage of positions fall into that category. I am afraid it might be too many to ignore however. In the case you gave, I can think of general rules that could catch it. IE rooks can't move farther up the board than the most distant file opening in the pawn chain. IE after e4, black could actually get a rook anywhere on the board if he plays e5 and leaves the other pawns alone for a while. But the rules might be fairly special-purpose and numerous as the bishops would have to treat diagonals the same way to catch that example you gave. Seems messy. I already have enough headaches trying to get the port done for the big alpha box. I don't have that many tylenol around. :)
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.