Archived from groups: rec.games.chess.computer (

More info?)

On Mon, 14 Mar 2005 23:08:09 +0100, "Stefan Renzewitz"

<Amarok@netcologne.de> wrote:

>

><cairpre409@yahoo.com> schrieb im Newsbeitrag

>news:1110836175.765118.96480@g14g2000cwa.googlegroups.com...

>> Any particular square can be occupied by K,Q,R,B,N,P of either color or

>> nothing. Thats 13 posibilites. 13 X 64 is 832. Lets double that again

>> since either side could be on move. 1664 The number of actual

>> positions is much less since as squares are occupied the true

>> possiblities decreases. In any event this is a much more managable

>> number than actual, or possible chess moves in a game. When designing

>> a chess database couldn't these 1664 be put in a table and all moves

>> and and all positions occuring in any game be simply referenced to that

>> table. This seems pretty simple and pretty fast. And would take up

>> less space than storing actual games. Each game record would be a set

>> of epd files that mearly referenced the positions table

>>

>> I am trying to teach myself something about database design, so I

>> wonder.

>> What is wrong with what I just said?

>

>This calculation (13 x 64 = 832 units of any storage type) only calculates

>the max. size you need to store ONE position (ignoring en-passent, castle

>and side to move info).

>The number of all possible positions is close to infinite (just think about

>all possible permutation and you will get something about 64^13 I think

This way to calculate the upper bound on the number of chess positions

should use the formula 13^64 (approx 2.0e+071) rather than the smaller

64^13 (approx 3.0e+023).

However there is another way to calculate an upper bound on the number

of poisitions:

There are at most 32 pieces to placed on the board). Order the

pieces. The first piece has 65 possibilities (64 squares + not being

on the board at all). The second piece has 64 possibilities for

placement (63 unoccupied squares + no being on the board at all). The

third has 63 possibilities and so on. So the total number of

possibilities is 65*64*63* ... *33 or (65!)/(33!) = approx 9.5e+053.

>though you have to reduce it by all non-regular positions) thus pre-storing

>all positions and then referencing moves to those positions doesn't work.

>Though you can reduce the number 13 by smarter storage system it remains a

>huge number. You also don't want to use raw FEN / EPD as this format is not

>the most compact way to store the keys for references (check hashing).

>

>Stefan

>

>

>