How to store Ongoing chess games in SQL

[tzvika.b...@gmail.com]

Hi all

I'm building a JAVA application that lets users play asynchronous
(a.k.a correspondence) chess games with each other. The basic use case
is that a user logs in once a day, sees that 3 of her games are
waiting for her to move, views the board as it was after the last
opponent move, makes a move and goes on to the next game.

I'm trying to come up with an efficient way to store the games in an
SQL database. this design should support both ongoing and completed
games. The standard way of storing games is called PGN, and it
enumerates move after move - but this means whenever i load the game
page, i need to "re-run" all the moves. surely there is an efficient
way of storing the current state, not just how we got there? but can
this be done without duplicating data and breaking normalization
rules?

I'm sure I'm not the first bozo who tackles this problem. I would
appreciate links to other discussions/solutions, or general ideas on
how to go about it.

thx in advance
Tzvika

[Uri Dimant]

Tzvika, shalom
I don't know that it;s what you are looking for but take a look at
http://www.databaseanswers.org/data_models/chess_tournaments/index.htm

<tzvika.b...@gmail.com> wrote in message
news:1185701855....@r34g2000hsd.googlegroups.com...

[Erland Sommarskog]

tzvika.b...@gmail.com (tzvika.b...@gmail.com) writes:
> I'm building a JAVA application that lets users play asynchronous
> (a.k.a correspondence) chess games with each other. The basic use case
> is that a user logs in once a day, sees that 3 of her games are
> waiting for her to move, views the board as it was after the last
> opponent move, makes a move and goes on to the next game.
>
> I'm trying to come up with an efficient way to store the games in an
> SQL database. this design should support both ongoing and completed
> games. The standard way of storing games is called PGN, and it
> enumerates move after move - but this means whenever i load the game
> page, i need to "re-run" all the moves. surely there is an efficient
> way of storing the current state, not just how we got there? but can
> this be done without duplicating data and breaking normalization
> rules?

I will have to admit that I have never considering data-modelling a
chess game before, but there is an obvious contradiction between
efficiency and avoiding duplication, given that is requirement is show
all moves in the game as well as the current position. If you store
the position as such, then there is a risk that an inconsistency could
arise, so that the moves do not give the stored position.

But that does not say it would be wrong to do so. The system I work with is
for securities administration, and a core table is a table that tracks
all transactions that all customers have performed. From this table
it's perfectly possible to compute the cash balance or the stock position,
either the current standings or for a day in the past. Nevertheless,
we have separate tables where you can retrieve these values. The reason
for this is simply efficiency. With tens of million rows in this table,
we don't want to compute the sum every time.

One problem with redundant storage, is that it makes updates difficult.
But in our case, once a transaction has been registered, you cannot change
it or delete it. If a transaction was incorrect, you need to book a cancel
transaction and a new transaction. And the same applies to your chess
game. You can't say "wait, I want to change draw 25 so that I move the
king to H1 and not H2."

So I don't see any problem with storing the moves as well as the current
position.

--
Erland Sommarskog, SQL Server MVP, esq...@sommarskog.se

Books Online for SQL Server 2005 at
http://www.microsoft.com/technet/prodtechnol/sql/2005/downloads/books.mspx
Books Online for SQL Server 2000 at
http://www.microsoft.com/sql/prodinfo/previousversions/books.mspx

[Baz]

I'm no chess expert, but IIRC the standard notation for chess moves clearly
indicates where the piece was moved to. So, if you have a "moves" table
which includes not only the position of the piece after the move, but also a
column indicating the sequence of the moves (a column containing the
date/time of each move would do it, as would a SQL Server identity column)
then it would be pretty easy to produce a query which returned the most
recent position of each piece, which, in effect, gives you the current state
of the entire game (even easier if you "initialise" a game by writing the
starting position of each piece at the beginning of the game to the moves
table).

So, the moves table might look something like this:

move_identifier (identity column)
game_identifier
piece_identifier
start_position
end_position

And the query might look something like this:

SELECT
M1.game_identifier,
M1.piece_identifier,
M1.end_position
FROM
moves M1
WHERE
M1.move_identifier = (
SELECT
Max(M2.move_identifier)
FROM
moves M2
WHERE
M2.game_identifier = M1.game_identifier
AND
M2.piece_identifier =
M1.piece_identifier
)

<tzvika.b...@gmail.com> wrote in message
news:1185701855....@r34g2000hsd.googlegroups.com...

[Alex Kuznetsov]

On Jul 29, 4:37 am, "tzvika.barenh...@gmail.com"

Tzvika,

To record the current state, I would store positions of all the pieces
as follows:

CREATE TABLE Pieces(Piece VARCHAR(30))
--- populate it with 'White King', 'White Queen', 'White Pawn 1', ...

CREATE TABLE PiecePositions(
GameID INT,
Step INT,
--- because there are 32 pieces,
Piece VARCHAR(30) REFERENCES Pieces(Piece),
PositionRow CHAR(1) CHECK(PositionRow BETWEEN '1' AND '8'),
PositionCol CHAR(1) CHECK(PositionRow BETWEEN 'A' AND 'H'),
PRIMARY KEY(GameID, Step, Piece),
UNIQUE(GameID, Step, PositionRow, PositionCol))

Of course, recording the whole game as a sequence of states is
possible too. It is easy to guarantee that each game begins with step
1, that at step 1 all pieces are at correct positions, and there are
no gaps between steps - a few constraints can do that. Making sure
that transitions from step to step are valid is probably very complex.

Alex Kuznetsov, SQL Server MVP
http://sqlserver-tips.blogspot.com/

[--CELKO--]

>> I'm building a JAVA application that lets users play asynchronous (a.k.a correspondence) chess games with each other. The basic use case is that a user logs in once a day, sees that 3 of her games are waiting for her to move, views the board as it was after the last opponent move, makes a move and goes on to the next game. <<

I hope this is just for a programming exercise, Otherwise, you can
get open source software for this -- and games like GO or Chinese
chess as well. There are some standards for file exchange too.

>> I'm trying to come up with an efficient way to store the games in an SQL database. this design should support both ongoing and completed games. The standard way of storing games is called PGN, and it enumerates move after move - but this means whenever i load the game page, i need to "re-run" all the moves. surely there is an efficient way of storing the current state, not just how we got there? <<

Why do you think that is a bad thing? Most games will last less than
50 moves, so you can make a little animation of the game from the
start to bring the player up to current situation.

However, look up "Forsyth notation" which records the current board
arrangement and not the moves. White pieces are in uppercase single
letters, black in lowercase. Consecrative vacant squares are shown as
numerals, new rows are separated by a /. The rows start with the
black rook and are scanned left to right, top to bottom (8a to 8h, 7a
to 7h, etc). The starting position would be
"rsbqkbsr/pppppppp/8/8/8/8/PPPPPPPP/RSBQKBSR"

CREATE TABLE Games
(game_nbr INTEGER NOT NULL,
white_player_id INTEGER NOT NULL
REFERENCES Players (player_id)
ON DELETE CASCADE
ON UPDATE CASCADE,
black_player_id INTEGER NOT NULL
REFERENCES Players (player_id)
ON DELETE CASCADE
ON UPDATE CASCADE,
CHECK (white_player_id <> black_player_id),
PRIMARY KEY (white_player_id, black_player_id, game_nbr),
board_forsyth CHAR(64) NOT NULL,
board_date TIMESTAMP DEFAULT CURRENT_TIMESTAMP NOT NULL

CREATE TABLE Players
(player_id INTEGER NOT NULL PRIMARY KEY,
player_email VARCHAR(255) NOT NULL,
etc);

Now just update each game after a player makes a move and this should
give you the smallest possible representation, but no history of
moves, no comments, etc.

[tzvika.b...@gmail.com]

Thanks a lot everyone. I do need to keep the history (games can be
"replayed") so I think what I'll do is implement a solution along the
lines Baz and Alex suggested. What remains now is to decide whether
to keep an additional (and redundant) Forsyth notation string for each
game in order to allow the current position to be loaded quickly. If I
can't figure a way to write a constraint that verifies the consistency
of the current position with the moves that lead to it, I'll probably
live without it.

Thanks again
Tzvika

P.S: To Mr. Celko: I hate to be picky, but in your solution, the Games
table would probably need a 'boolean'-like column for whose turn it
is.
P.P.S: Yes, I do know boolean is not standard. a char with a
constraint that can be 'W' or 'B' will do :-)

[tzvika.b...@gmail.com]

On Jul 30, 5:16 pm, "tzvika.barenh...@gmail.com"

P.P.P.S: It just occurred to me that there is more info missing in
Forsyth than I first thought - not just whose move it is, but also who
can castle, how many moves since last capture, right to en passant -
and maybe even more obscure rules that I am missing still.

Of course, these are chess-related particulars, not SQL issues. I just
added them here for completeness. in SQL it would be trivial to add a
couple more columns for this.

Thanks again and excuse the pettiness.
Tzvika

[Tom Cooper]

<tzvika.b...@gmail.com> wrote in message
news:1185805018.7...@g4g2000hsf.googlegroups.com...

> Thanks a lot everyone. I do need to keep the history (games can be
> "replayed") so I think what I'll do is implement a solution along the
> lines Baz and Alex suggested. What remains now is to decide whether
> to keep an additional (and redundant) Forsyth notation string for each
> game in order to allow the current position to be loaded quickly. If I
> can't figure a way to write a constraint that verifies the consistency
> of the current position with the moves that lead to it, I'll probably
> live without it.
>
> Thanks again
> Tzvika
>
> P.S: To Mr. Celko: I hate to be picky, but in your solution, the Games
> table would probably need a 'boolean'-like column for whose turn it
> is.

And you need other information that doesn't come from just the position of
the pieces on the board, like can White castle king-side? (that is has
White's King or King Side Rook moved previously in this game?), or is there
an en passant capture available? or has it been 50 moves since a piece was
captured or a pawn moved?

[ML]

These can be calculated, can't they?

ML

---
Matija Lah, SQL Server MVP
http://milambda.blogspot.com/

[--CELKO--]

>> I do need to keep the history (games can be "replayed") so I think what I'll do is implement a solution along the lines Baz and Alex suggested. What remains now is to decide whether to keep an additional (and redundant) Forsyth notation string for each game in order to allow the current position to be loaded quickly. <<

With the Forsyth notation, I would use a counter rather than a flag.
You can deduce whether Black or White is to move next by odd/even
tests and not destroy that extra information. But I like the idea of
seeing the game take shape like a re-play of a DVD and it should not
take that long to load,

>> If I can't figure a way to write a constraint that verifies the consistency of the current position with the moves that lead to it, I'll probably live without it. <<

That would be a bit hard to put into a CHECK() wouldn't it?

>> It just occurred to me that there is more info missing in Forsyth than I first thought - not just whose move it is, but also who can castle, how many moves since last capture, right to en passant - and maybe even more obscure rules that I am missing still. <<

You can add a column for 0-0, 0-0-0, ?, ?? and the other comment
notations, but some of the rules like pawn promotion, Castling king
side, Castling queen side, en passant moves, etc. might require that
you model the state of each piece.

That is starting to get a little messy for SQL. Think about starting
with a bishop on white diagonals, a bishop on black diagonals. I
cannot just test for two bishops; I can lose one or both of them in
play; I can promote pawns to bishops and have up to ten of them on the
board at once (in theory).

>> Thanks again and excuse the pettiness. <<

Considering how picky I can get, this is nothing.

[Tom Cooper]

Yes, of course, if you have a history of all the moves in this game (which
would be my preference). If you are only keeping the current position, then
you need the additional information.

Tom

"ML" <M...@discussions.microsoft.com> wrote in message
news:D4349301-C524-47AC...@microsoft.com...

[ML]

Reality itself is a set of events. No history, no reality. :) Why would a
chess game be an exception?

[Tom Cooper]

Agreed,. I was just commenting on Celko's suggestion that

"However, look up "Forsyth notation" which records the current board
arrangement and not the moves. White pieces are in uppercase single
letters, black in lowercase. Consecrative vacant squares are shown as
numerals, new rows are separated by a /. The rows start with the
black rook and are scanned left to right, top to bottom (8a to 8h, 7a
to 7h, etc). The starting position would be
"rsbqkbsr/pppppppp/8/8/8/8/PPPPPPPP/RSBQKBSR"

He then gave a database schema which only included the position of the pawns
and pieces. I was pointing out that this is insufficient. Celko also
independently later realized that this was insufficient.

I agree, the correct way to store the status of a game is the series of
moves. However, there are other cases where all you are concerned about is
the position. If your newspaper prints a chess problem (you know, here's a
position, White to play and win in two moves), the paper will just print the
position, not a series of moves to get you from the start of a chess game to
that position.

Tom

"ML" <M...@discussions.microsoft.com> wrote in message

news:59F5F641-0509-4C20...@microsoft.com...

[ML]

A particular position can be derived from the series. It would require a few
additional reads from the table, but would not delay the printing of the
newspaper. :)

[Baz]

Hardly. Past and future don't exist, the only reality is now.

"ML" <M...@discussions.microsoft.com> wrote in message

news:59F5F641-0509-4C20...@microsoft.com...

[ML]

Prove it.

[tzvika.b...@gmail.com]

On Jul 30, 7:33 pm, --CELKO-- <jcelko...@earthlink.net> wrote:

> >> If I can't figure a way to write a constraint that verifies the consistency of the current position with the moves that lead to it, I'll probably live without it. <<
>
> That would be a bit hard to put into a CHECK() wouldn't it?
>
>

Extremely hard. But maybe if I can get Itzik B-G to treat it as a
puzzle, I am sure he will come up with something :-)
Tzvika

[Baz]

OK, I'm sure you did something recently which you wish you hadn't or could
have done better. Why not just pop back and do it again?

While you're at it, could you just pop round to tomorrow please and tell me
the headline on the Times.

"ML" <M...@discussions.microsoft.com> wrote in message

news:16D9524C-EB53-45FB...@microsoft.com...

[ML]

Can you touch the surface of the moon with you bare hand this very minute and
tell me how it feels?

Just because something is out of reach that doesn't mean it doesn't exist. :)

[Baz]

I know the moon exists, I can see it every night. I can't see the past, all
I have is memories, which are not the past. I can't see the future, all I
have is expectations, which are not the future.

Of course, you could argue that the moon doesn't exist right now because
it's broad daylight and so I can't see it, but if you do argue that you are
arguing for global scepticism i.e. that nothing exists outside of one's own
conciousness (and arguably not even that), but I wouldn't go there because
in losing everything you will lose the past and future.

"ML" <M...@discussions.microsoft.com> wrote in message

news:67345ECB-3AB8-4CD5...@microsoft.com...

[ML]

Remember: I said everything exists, unless proven otherwise. No scepticism
here. :)

We should continue this discussion over a beer or two cases... :)

[Baz]

Ahhhh, I knew there were fairies at the bottom of my garden...

"ML" <M...@discussions.microsoft.com> wrote in message

news:C196DC07-E5C4-4B6D...@microsoft.com...

[Jason Lepack]

A good chess application will be able to import as well as export PGN
format.

http://en.wikipedia.org/wiki/Portable_Game_Notation

Cheers,
Jason Lepack

On Jul 29, 5:37 am, "tzvika.barenh...@gmail.com"

[ML]

Well, what else could have been there?

[Alex Kuznetsov]

On Jul 31, 4:17 am, "tzvika.barenh...@gmail.com"

To use check constraints, you need to store columns from both previous
and current state in one row. Google up Joe Celko's article on
transitional constraints. I would not apply this technique in your
case - too complex.

[fat bold cyclop]

Just few words:
1. FEN stores also the info about en passant and castling (
http://en.wikipedia.org/wiki/Forsyth-Edwards_Notation)

2. Try looking at Jose sources (http://jose-chess.sourceforge.net/) --
great open source chess database, or post your question there.

3. Don't be afraid to duplicate data. It all depends what You want your
software to do. For example, if You want it to be able to search the
games for a given move sequence (Nf3+ ... NxQ) You probably need to
additionally store gamestates (is the king in check? is a given piece
attacked? etc.).

Good luck,
Fat Bold Cyclop

*** Sent via Developersdex http://www.developersdex.com ***

[tzvika.b...@gmail.com]

On Aug 2, 7:55 pm, fat bold cyclop <fat.bold.cyc...@gmail.com> wrote:
> Just few words:

> 1. FEN stores also the info about en passant and castling (http://en.wikipedia.org/wiki/Forsyth-Edwards_Notation)

>
> 2. Try looking at Jose sources (http://jose-chess.sourceforge.net/) --
> great open source chess database, or post your question there.
>
> 3. Don't be afraid to duplicate data. It all depends what You want your
> software to do. For example, if You want it to be able to search the
> games for a given move sequence (Nf3+ ... NxQ) You probably need to
> additionally store gamestates (is the king in check? is a given piece
> attacked? etc.).
>
> Good luck,
> Fat Bold Cyclop
>
> *** Sent via Developersdexhttp://www.developersdex.com***

Thanks FBC. My app will be play-driven, not db-driven (i.e. it will
compete with redhotpawn.com, not chessbase - though of course it never
will compete with either). So the focus is not going to be on these
advance searches, but on showing games in progress and moving them
forward.

T