Author: Vincent Diepeveen
Date: 08:19:46 03/09/00
Hello,
[if you react on this posting please send a copy also by email to
diep@xs4all.nl as i don't check CCC regurarly]
For hashing in 64 bits there are
2^64 possible outcomes.
That's not much compared to the number of
positions as estimated in an ICCAJ some time ago: 10^43
was that outcome.
Now for a few mathematicians the number of theoretical
positions will be interesting, but not for us all.
More interesting are different numbers:
- practical 'alfabeta with nullmove' number
- human number of acceptible positions
So in short, how many positions can i expect that a search of my program
can ever search, including the nonsense positions?
First i started with a simple experiment. Is it possible to have more
than 16 non-pawn pieces on the board?
Theoretical: yes
Practical: no, as when there are 2 queens on the board usual already some
captures have been done reducing the number of pieces first.
For example one leaf seen by DIEP is e4 d5 ed5 c6 dc (lot of different moves)
cb7 and then bxa8Q. So the most obvious 'ALL' nodes are not having 2 queens.
Any position having over 16 pieces can be proven a nonsense or artificial
position in advance. Lines like e4 d5 ed5 c6 dc6 and then capturing further
to queen is not smart to allow.
Even middlegambits from white side: e4 e5 d4 ed c3 dc3 Bc4 cb2 has bxb2 as
best move. Qd5 is a nonsense move because of bxc1Q
So there we have perhaps for the alfabeta tree a SINGLE position with
2 queens, but still not over 16 pieces, as we chopped off a piece at c1.
So far i haven't seen a single interesting over 16 piece position which is
derived from good moves of at least 1 side, without being cutoffed by
nullmove.
Obvoiusly a fullwidth search will simply search all chess positions.
Nullmove chops off all that nonsense quite drastically (lucky).
Yet if i start calculating how many chess positions there are, using next
scheme to store a position:
64 bits 1 = piece 0= no piece
We can do that for 32 pieces at maximum determining whether
they are a pawn or not a pawn and we already know the number of
pieces on the board, so when we miss a few pawns, then we can
risk having more than 16 pieces anyway:
32 bits (total 96 now) 1 = pawn 0 = not a pawn
32 bits (total 128 now) 1 = white 0 = black
We already know what are pawns. What we now need are
at maximum 16 pieces left. We know what pieces are
white. we know what pieces are black, so first we
describe the kings:
white king first: 3 bits (total 131 bits now)
black king second: 3 bits (total 134 bits now)
So now we have at maximum 14 pieces left with each
as possible value: queen,rook,bishop,knight. We
already know what color it is. So we can
describe that in 2x14 = 28 bits (total 134+28 = 162 bits)
So we can describe an entire position in 162 bits at
maximum using an extremely simple scheme.
Note that describing all positions can be done in not
many bits more by using 5 pieces and 5^max pieces,
so a smart mathematician can figure out that we hardly
need more than 162 bits for *any* chess position.
2^162 = 10^48
Now there was already an estimate of 2^43 on the total
number of positions. Yet there is an easier way which is
a lot harder to store though.
The basic stupidity in all these schemes is that they don't
take into account the limited number of squares that pawns
can be on.
Let's first do a naive calculation, only for pawns.
There are 48 squares and 8 white pawns and 8 black pawns
at maximum:
48! / (32!8!8!) = 2.9 * 10^16
this number is of course pure nonsense as it includes also white pawns
on a5..h5 and all black pawns at a4..h4, now i guess this is an illegal
to reach position, but many other theoretical perhaps
possible positions which practical never will happen are included.
Now we can reduce a lot less for the remaining 16 pieces.
However if we have all pawns on the board, then
we have only 48 squares left to put our pieces at.
If there are less pawns on the board, then the number will be higher, but
the total number of possible positions will be a lot less anyway.
48! / 32!(2!^6) = 7.3 ^ 10^23
If we multiply the 2 numbers then i get to something like 2 * 10^40
Now this is already a lot less than 10^43 as put in ICCAJ.
If i however do a 'human' estimation, then we talk about magnitudes less:
a king of mine can never be at about 48 different squares. i have at most
a few choices in opening/middlegame. Say 20 choices sounds like a fair
number?
All other squares are nonsense for my king for sure.
How many positions do we have with all white pieces behind all black pieces?
In other words: what is the maximum of pieces behind the enemy pieces that
we practical see in games?
3 perhaps?
How many white pieces go ever over the 4th rank?
Quite a number you'll say. Yes! But at most 1 at the time.
Actually, 10^30 already sounds like a nonsense number in my ears.
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.