# Computer Chess Club Archives

## Messages

### Subject: Re: Counting & Encoding Any Chess Position in 157 bits

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).