From: | Alban Hertroys <haramrae(at)gmail(dot)com> |
---|---|
To: | Sidney Cadot <sidney(at)jigsaw(dot)nl> |
Cc: | pgsql-general(at)postgresql(dot)org |
Subject: | Re: Searchable chess positions in a Postgress DB |
Date: | 2012-04-11 09:14:11 |
Message-ID: | CAF-3MvOUrNxF5BptjMuu-S5ii0V9Et49Cd-1F+FnOHJih41otA@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-general |
On 11 April 2012 09:15, Sidney Cadot <sidney(at)jigsaw(dot)nl> wrote:
> Dear all,
>
> As a hobby project, I am toying around with a database containing
> about 5 million chess games. On average, these games have about 80
> positions (~ 40 moves by both black and white), which means there are
> about 400 million chess positions in there.
>
> I have written code to extract these positions, and now I want to put
> them into a Postgres database. Specifically, I want to do this in a
> way that allows *fast* lookups of positions, e.g. "give me all
> positions that have a White King on c4 and either a Black Bishop or
> White Knight on f7".
>
> Currently, my "Positions" table looks like this:
>
> Column | Type | Modifiers
> -------------------+---------+-----------
> gameindex | integer | not null
> plyindex | integer | not null
> pseudofenboard | text | not null
> fenside | text | not null
> fencastling | text | not null
> fenenpassant | text | not null
> possiblemovecount | integer | not null
> isincheck | boolean | not null
> Indexes:
> "positions_pkey" PRIMARY KEY, btree (gameindex, plyindex)
> Foreign-key constraints:
> "positions_gameindex_fkey" FOREIGN KEY (gameindex) REFERENCES
> games(gameindex)
>
> The "PseudoFenBoard" field currently holds a string describing the
> position. For example, the starting position of chess looks like this:
>
> "rnbqkbnr/pppppppp/________/________/________/________/PPPPPPPP/RNBQKBNR"
>
> This design allows me to formulate the kind of positional queries that
> I want (by using regular expression matching), but executing them will
> involve a slow, linear traversal of the 400M table rows, which is not
> desirable.
>
> I am toying around with the ugly idea to make a "Positions" table that
> has a single field for each of the squares, e.g.
>
> CREATE TABLE Position2 (
> GameIndex INTEGER NOT NULL,
> PlyIndex INTEGER NOT NULL,
> a1 "char" NOT NULL,
> a2 "char" NOT NULL,
> -- (60 fields defs omitted)
> h7 "char" NOT NULL,
> h8 "char" NOT NULL
> );
>
> This would allow the creation of indices on each of the 64 fields
> separately, which should help to achieve near-instantaneous position
> query performance, especially after gathering proper statistics for
> all the field-specific indices.
>
> I realize that this design is quite ugly, so I would be interested to
> hear if there are nicer alternatives that can perform equally well.
>
> Also, above I use the 1-byte "char" type. Is this the only type in
> PostGres that is guaranteed to be just a single byte, or are there
> better alternatives?
No, you're using the unlimited length "char" type. You probably mean
to use either char(1) or varchar(1).
It wouldn't hurt to make those chars a foreign key to a chess-piece
table, so that you both define what a certain code means on the
chess-board and constrain which codes are available.
You could possibly take that a bit further by finding a constraint
that limits the number of each piece on the board (exactly 1 white
king, up to 2 white towers, up to 8 white pawns, etc), but I have no
ready idea of how you could achieve that...
> A 13-state enum would be best (listing the 6
> white pieces, 6 black pieces, and 'empty' states for every square on
> the board) but as I understand from the documentation, enums always up
> take 4 bytes per entry.
> Any ideas for improvement would be greatly appreciated.
Well, since a chess-board is a matrix, it seems to make sense to
describe it as a two-dimensional array of varchar(1)'s. I don't know
off the top of my head what the storage requirements for that are
though.
--
If you can't see the forest for the trees,
Cut the trees and you'll see there is no forest.
From | Date | Subject | |
---|---|---|---|
Next Message | Gavin Flower | 2012-04-11 09:24:53 | Re: Searchable chess positions in a Postgress DB |
Previous Message | Kuba | 2012-04-11 09:09:47 | OS authentication on Windows |