Author: Ratko V Tomic
Date: 07:09:33 11/10/99
Go up one level in this thread
> It is possible to calculate a good estimate of the number of legal > positions by choosing 1000 random positions and counting the number > of positions that you can prove that they are legal. You would need much more (and many more) than a 1000 positions to get beyond the simplest back-of the envelope estimate (such as figures of type 10^50 or other rough estimates). Namely, for sampling to work here at all, in order to generate a "fair sample" of positions, you would have to have a good _model_ of what a "fair sample" here is, i.e. how much material of which kind should you put in. For example, it's not enough to pick a uniform odds for counts for pieces (within a range of 0-max counts for each piece type i.e. P 0-8, Q 0-9, R 0-10, etc), since as you well know, the different Material Contet (MC) states generate a widely different number of individual placements. And to get these kind of estimates for the "fair sample" model (which you need before you apply sampling to a given domain), you would end up enumerating MC states and counting their placement permutations (before getting even near the subtle illegalities issues of the positions) and that's how we both got our more accurate figures to start with. Highly irregularly constrained combinatorial problems, like chess or many other strategy games, are notorious for defying any poorly chosen "fair samples" (otherwise playing programs could simply "fair sample" a 1000 of "random" nodes or some such and play a good game). To get anywhere near of what "fair sample" is to be, you end up calculating much more in the problem domain than it would be worth for estimating this kind of bulk figure (which itself would be a simple byproduct of such model creation, in the first place). In case of chess to get sampling to work, you would probably need to sample separetely placements within separate MC states (e.g. around 58 million MC states that my generator produced), and for each of them, or for a "fair" sample of them (which means counting how many placements each have, i.e. getting the number you are looking for to "measure"), performing a sampling among the placement permutations for a given MC, with say a 1000 placements for each, so the total tests needed may involve as many as 60 billion positions, and still leave greater uncertainty than what we already have (or could get with simple refinements). And finally, you still wouldn't know whether you could, with certainty encode any position in a given number of bits (such as 155 bits for the basic position, the material & its placement, or a few more if one also keeps castle and ep status).
This page took 0.01 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.