Database design (positons or moves)

G

Guest

Guest
Archived from groups: rec.games.chess.computer (More info?)

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?
 
G

Guest

Guest
Archived from groups: rec.games.chess.computer (More info?)

<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
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
 
G

Guest

Guest
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
>
>
>
 
G

Guest

Guest
Archived from groups: rec.games.chess.computer (More info?)

I think I may be asking a slightly different question than total number
of possible positions. I am really asking "how can I store and or
recreate any possible chess position. If for each square I ask " Is
this square empty?, does is have a white king, does it have a black
king, ..Queen...rook...knight...pawn. I repeat that for all 64 squares
Then I ask Is castling allowed and finally whose move is it.
Don't those 834 questions/ calculations allow me to store and recreate
any possible position? And by extention any game?

If I want to store or recreate a particular position I could use epd or
some other format.
Reading that file/entry would be 1 calculation. It might seem
inefficent to obtain the same information by performing 834
calculations. But it also seems that the actual size of the database
could be much smaller compared to storing each position/game.
And that might lead to more efficency. Also the length of time a
modern computer performs 1 calculation or 834 calculations of this type
is practically indistingushable to a human.

So is it better to store and retrieve each individual position/ game,
or to recreate it by performing the 834 calculations?
 
G

Guest

Guest
Archived from groups: rec.games.chess.computer (More info?)

On 14 Mar 2005 13:36:15 -0800, cairpre409@yahoo.com wrote:

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

Actually it is vastly greater. You are forgetting about the empty
squares. There are always at least 32 empty squares which may be
arranged in 32x31x30...x2 ways - an immense number. You are also
ignoring that pieces may be captured, so you have to consider all
positions with 32 pieces, all positions with 31 pieces, and so on.

Just take the two K's alone and you'll find that there are vastly more
positions than the 1664 you claim for the whole game!

Furthermore, you are ignoring the order in which the pieces are placed.
knNK is a different position than kNnK.

All in all you are ignoring just about every significan possibility.

The actual number of possible chess positions is usually estimated at
around 10^32, an immensly huge number.


Ed Seedhouse,
Victoria, B.C.
 
G

Guest

Guest
Archived from groups: rec.games.chess.computer (More info?)

On Mon, 14 Mar 2005 23:08:09 +0100, "Stefan Renzewitz"
<Amarok@netcologne.de> wrote:


>The number of all possible positions is close to infinite

Nonsense. It is infinitely far away from being infinite. Any actual
number, no matter how large it is, is also infinitely far away from
being infinite.


Ed Seedhouse,
Victoria, B.C.
 
G

Guest

Guest
Archived from groups: rec.games.chess.computer (More info?)

cairpre409@yahoo.com wrote:

> So is it better to store and retrieve each individual position/ game,
> or to recreate it by performing the 834 calculations?

This depends entirly on what kind of searches you are going to make.

You don't design a database from the bottom up: you do it from what
you are planning to use it for. It could easily be that the searches
you want to be fast will turn out to be expensive in terms of time or
space.

Get an idea of your requirements first - design the database once you
know.

Do you want to find games in which a particular position ocurred?
Exact position or fuzzy ('with ine white knight, but I don't care
where')? Straight? Mirrored? Rotated? with reversed colours?

Do you want one batch search (enter *all* of the search criteria,
and then wait while the database searches), or incremental (add
piece by piece, and see the hit list updated after each change)?
How long time are you prepared to wait in the first case? As long
time as it takes? Or wait for 30 seconds, and then get a partial
hit list to investigate while the rest of the search continues?
What is more important: search speed or database space?

It would seem more appropriate to store a position in a way
that allows you to easily find positions with a certain material
and also on certain squares. That is, a square by square
description as well as a RGB-code.

But until you actually have made up your mind about your
requirements, you don't really have a good foundation for your
question.

--
Anders Thulin ath*algonet.se http://www.algonet.se/~ath
 
G

Guest

Guest
Archived from groups: rec.games.chess.computer (More info?)

I think Bookup already does something like that, and some other
database systems that I'm less familar with do also.