SQLChess - A tutorial on thinking in sets

By David Moloney on 14 May 2007 | Tags: Tutorials

Chess makes a fantastic game for programming examples. You will find hundreds of examples on the internet. Some dedicated to OO patterns, others to algorithms and so forth. Unfortunately, most of these examples do not use a database or if they do, treat the database as nothing more than a storage repository. In this series of articles we will use SQL Server and T-SQL to implement the game of chess with an emphasis on thinking in sets.

Modeling the board

Chess is played on an 8 by 8 grid represented by 64 unique squares. Each square has 2 properties that provide its location on the board. The nomenclature of chess uses an alpha-numeric designation for each square

a8 (1,8)	b8 (2,8)	c8 (3,8)	d8 (4,8)	e8 (5,8)	f8 (6,8)	g8 (7,8)	h8 (8,8)
a7 (1,7)	b7 (2,7)	c7 (3,7)	d7 (4,7)	e7 (5,7)	f7 (6,7)	g7 (7,7)	h7 (8,7)
a6 (1,6)	b6 (2,6)	c6 (3,6)	d6 (4,6)	e6 (5,6)	f6 (6,6)	g6 (7,6)	h6 (8,6)
a5 (1,5)	b5 (2,5)	c5 (3,5)	d5 (4,5)	e5 (5,5)	f5 (6,5)	g5 (7,5)	h5 (8,5)
a4 (1,4)	b4 (2,4)	c4 (3,4)	d4 (4,4)	e4 (5,4)	f4 (6,4)	g4 (7,4)	h4 (8,4)
a3 (1,3)	b3 (2,3)	c3 (3,3)	d3 (4,3)	e3 (5,3)	f3 (6,3)	g3 (7,3)	h3 (8,3)
a2 (1,2)	b2 (2,2)	c2 (3,2)	d2 (4,2)	e2 (5,2)	f2 (6,2)	g2 (7,2)	h2 (8,2)
a1 (1,1)	b1 (2,1)	c1 (3,1)	d1 (4,1)	e1 (5,1)	f1 (6,1)	g1 (7,1)	h1 (8,1)

If we swap the alphabetical characters with numbers (a=1, b=2, etc..) the square could be interpreted as a "Point" like structure represented as X (a..h) and Y (1..8) coordinates. Using this "Point" representation will allow us to perform basic maths against the board. One way to represent a Point is by creating an attribute (column) for each property. That gives us a basic table with X and Y attributes. This design allows us to leverage the indexing system in SQL Server.

To help us with the mapping from a "Point" to the chess nomenclature, we add another column named Square. I have chosen to implement the Square attribute as a computed (derived) column for no good reason other than to test the conversion formula between the "Point" and "Square" representation.

CREATE TABLE [dbo].[Board] (
	[X] [smallint] NOT NULL ,
	[Y] [smallint] NOT NULL ,
	[Square] AS (isnull(convert(char(2),(char((96 + [X])) + convert(char(1),[Y]))),'')) ,
	CONSTRAINT [PK_Board] PRIMARY KEY  CLUSTERED ([X],[Y]),
	CONSTRAINT [CK_Board] UNIQUE  NONCLUSTERED  ([Square]),
	CONSTRAINT [CHK_Board_X_Domain] CHECK ([X] >= 1 and [X] <= 8),
	CONSTRAINT [CHK_Board_Y_Domain] CHECK ([Y] >= 1 and [Y] <= 8)
) 
GO

We now have a simple table with basic constraints. Insert 64 unique rows using this script and the board representation is complete.

Consider the proposition that a piece can be anywhere and moved to anywhere but its original position. In other words, show all the "From Square" - "To Square" combinations. It is surprisingly easy to do this by using some basic SQL.

Select R.Square as FromSquare, O.Square as ToSquare
from dbo.Board R CROSS JOIN dbo.Board O
WHERE R.Square != O.Square 

--(4032 row(s) affected)

Examining this query we find 2 important features:

The CROSS JOIN multiples 2 tables together. In this case, 64 rows times 64 rows = 4096 rows. This is a PRODUCT in relational terms.
The WHERE applies the fact that a "move" requires the piece to actually move. This is a RESTRICTION in relational terms. (64 Rows)

Thus 4096 rows - 64 rows = 4032 rows. This very simple query shows the inherent power of manipulating sets. We will create a view (AllMoves) to encapsulate this statement for reuse.

create view AllMoves (X,Y,FromSquare, Xi, Yi, ToSquare)
as
Select R.X, R.Y, R.Square, O.X, O.Y, O.Square
from Board R cross join Board O
where R.Square != O.Square

I have used the column names Xi to and Yi to indicate the "To Square" and X and Y to indicate the "From Square". Obviously, there are "movements" in this view which are impossible in chess. By interpreting the rules of chess, we will RESTRICT this set (AllMoves) until only valid chess moves remain.

Basic Piece Movement

The Castle

Castles move in either a horizontal or vertical path along the board. When we look at the point representation of the board, we can see a pattern that must be followed: The X coordinate is constant OR the Y coordinate is constant

Select FromSquare, ToSquare
from dbo.AllMoves
where (X = Xi or Y = Yi) 

--(896 row(s) affected)

How simple was that? Enough said!

The Bishop

Bishops move in diagonals. Looking at the board we see another pattern that must be followed: The absolute difference between the X movements equals the absolute difference the Y Movements

Select FromSquare, ToSquare
from AllMoves
where ABS(X-Xi) = ABS(Y-Yi)

--(560 row(s) affected)

Still a very simple query. Incidentally, this query threw an overflow error in my initial design. Tinyint's aren't wide enough.

The Knight

Looking at the Board, we can see how easy it is to translate the knight movements into a set of all possible knight moves using the "One-Two" motion.

Select FromSquare, ToSquare
from dbo.AllMoves
where (ABS(X - Xi) = 2 AND ABS(Y-Yi) = 1) OR (ABS(X - Xi) = 1 AND ABS(Y-Yi) = 2)

--(336 row(s) affected)

When the castle, bishop and knights moves are added together, they represent the set of every possibly valid move:

Castle (896) + Bishop (560) + Knight (336) = 1792 Possibly Valid Moves

The king, queen and pawn movements are contained within these Possibly Valid Moves.

In relational terms it is very simple to add tables together using an addition (Plus) operation. In SQL, it is just as easy with a choice of UNION or UNION ALL. The "ALL" extension includes duplicates but in our case there are none and is irrelevant.

select X, Y, FromSquare, Xi, Yi, ToSquare
from dbo.AllMoves
where (X = Xi or Y = Yi) 
union all
select X, Y, FromSquare, Xi, Yi, ToSquare
from dbo.AllMoves
where ABS(X-Xi) = ABS(Y-Yi)
union all
select X, Y, FromSquare, Xi, Yi, ToSquare
from dbo.AllMoves
where (ABS(X - Xi) = 2 AND ABS(Y-Yi) = 1) OR (ABS(X - Xi) = 1 AND ABS(Y-Yi) = 2)

--(1792 row(s) affected)

This query can be re-written without the UNION operator and expressed entirely with RESTRICTION (WHERE):

select X, Y, FromSquare, Xi, Yi, ToSquare
from dbo.AllMoves
where 
	(X = Xi or Y = Yi) --Castle
OR ABS(X-Xi) = ABS(Y-Yi) --Bishop
OR ((ABS(X - Xi) = 2 AND ABS(Y-Yi) = 1) OR (ABS(X - Xi) = 1 AND ABS(Y-Yi) = 2)) --Knight

--(1792 row(s) affected)

The speed freak in all of us would prefer the later approach as only 2 scans of the table are taken versus 6. Just for a moment consider the simplicity of the above SQL. Not bad for a "storage repository"!

The Queen

The queen can behave like a castle or bishop. A simple UNION of the Castle and Bishop moves.

Select FromSquare, ToSquare
from dbo.AllMoves B
where ABS(X-Xi) = ABS(Y-Yi)
union all
Select FromSquare, ToSquare
from AllMoves C
where (X = Xi or Y = Yi)

-- (1456 row(s) affected)

The King

The king can move to an adjacent square or perform a "castling". The adjacent square rule can be expressed by restricting the absolute difference between the X movements and Y movements to less than 2. The castling rule applies positional restrictions on the Y and X elements

Select FromSquare, ToSquare
from dbo.AllMoves
where ABS(X - Xi) < 2 AND  ABS(Y - Yi)  < 2 
OR (Y = Yi AND X = 5 AND ABS(X-Xi) = 2 AND Y in (1,8))

-- (424 row(s) affected)

The Pawn

The pawns movement is slightly more complex than the others due to the "1 or 2 square" start move, plus the different attack move, but is still fairly straight forward.

Select FromSquare, ToSquare
from dbo.AllMoves
where  Y != Yi
AND 
(
	(ABS(X - Xi) < 2 AND  ABS(Y - Yi)  < 2) 
	OR
	(X=Xi AND ((Y = 2 and Yi  = 4) OR (Y = 7 and Yi  = 5)))
)

--(324 row(s) affected)

So far, we have found the set of all possibly valid moves for each piece. The simplicity of the code involved should demonstrate to you the power of set based processing. Before we start looking at the "deeper" chess rules in the next article we will continue with basic piece movement and examine the paths that pieces travel over when moving.

Author's Note: A special thankyou to Koji Matsumura and Developer Jim for pointing out a very serious bug in the Bishop calculation.