Building the engine

Now let's build the engine. This is where we'll cheat take advantage of the wonderful world of open source.

Remember that what we want to do is take a PGN game that's in progress, and let dbacl complete the next move by picking all possible legal next moves and adding them in turn to the current game, then we let dbacl compute the most probable game under its model. We don't really know if dbacl's model is a good one for chess, and let's not even think about competing with Deep Thought here, but this procedure will at least give us a way to pick the move.

Unfortunately, computing legal moves is straightforward but tedious, so I looked around the internet for something useful, and found the SAN Toolkit (if the link doesn't work, get it here). This is an old freeware toolkit for chess which does everything we want, even though it was last updated in 1993 and probably no longer state of the art. It's written in C and we have to compile it, but most importantly we can use it directly in a Unix shell environment. Download it and place it in the chess directory.

% untar xfz san.tgz
% cd SAN
% cp SAN_DOC/Makefile SAN_SRC
% cd SAN_SRC
% make
% cd ../..

The documentation for this program is a little wanting, but it's not too hard to figure out, and the source code helps. Everything is calculated by the program san, which accepts commands. We'll write a script which accepts a PGN partial game and one of the dbacl categories we learned, and outputs the "best" move, meaning what dbacl thinks is closest to the category that was learned.

Let's try those ideas out before we proceed. We'll need a test PGN file.

% cat > test.pgn
1. e4 c5 2. Nf3 e6 3. d3 Nc6

% echo -ne "svop verb namd nabd napr\nlfer test.pgn\nenum 1\n" \
 | ./SAN/SAN_SRC/san > test.legal 2>&1
% head -10 test.legal
: : : Welcome to the SAN Kit.
Revised: 1993.05.16

Bd2             : 1
Be2             : 1
Be3             : 1
Bf4             : 1
Bg5             : 1
Bh6             : 1
Kd2             : 1

Okay, this looks promising! There are some pieces of text we'll have to remove, but the possible first moves are all there (the listing is cut after 10 lines). Let's build the game line.

% cat test.pgn | sed 's/[0-9]*\.[ ]*//g' > test.gameline
% cat test.gameline
e4 c5 Nf3 e6 d3 Nc6

Next, we complete this gameline with each possible move:

% cat test.legal | grep '^.* : 1$' | cut -f 1 -d ' ' | \
 while read move; do
	echo `cat test.gameline` $move
 done > test.complete
% head -10 test.complete
e4 c5 Nf3 e6 d3 Nc6 Bd2
e4 c5 Nf3 e6 d3 Nc6 Be2
e4 c5 Nf3 e6 d3 Nc6 Be3
e4 c5 Nf3 e6 d3 Nc6 Bf4
e4 c5 Nf3 e6 d3 Nc6 Bg5
e4 c5 Nf3 e6 d3 Nc6 Bh6
e4 c5 Nf3 e6 d3 Nc6 Kd2
e4 c5 Nf3 e6 d3 Nc6 Ke2
e4 c5 Nf3 e6 d3 Nc6 Na3
e4 c5 Nf3 e6 d3 Nc6 Nbd2

And of course, let's check what dbacl thinks of this:

% cat test.complete | ./dbacl/src/dbacl -n -c ./WhiteWinDraw -f 1 > test.scores
% cat test.scores
WhiteWinDraw  53.88 e4 c5 Nf3 e6 d3 Nc6 Bd2
WhiteWinDraw  52.93 e4 c5 Nf3 e6 d3 Nc6 Be2
WhiteWinDraw  52.16 e4 c5 Nf3 e6 d3 Nc6 Be3
WhiteWinDraw  53.11 e4 c5 Nf3 e6 d3 Nc6 Bf4
WhiteWinDraw  52.88 e4 c5 Nf3 e6 d3 Nc6 Bg5
WhiteWinDraw  54.64 e4 c5 Nf3 e6 d3 Nc6 Bh6
WhiteWinDraw  55.32 e4 c5 Nf3 e6 d3 Nc6 Kd2
WhiteWinDraw  54.82 e4 c5 Nf3 e6 d3 Nc6 Ke2
WhiteWinDraw  54.55 e4 c5 Nf3 e6 d3 Nc6 Na3
WhiteWinDraw  57.48 e4 c5 Nf3 e6 d3 Nc6 Nbd2
WhiteWinDraw  52.07 e4 c5 Nf3 e6 d3 Nc6 Nc3
WhiteWinDraw  54.69 e4 c5 Nf3 e6 d3 Nc6 Nd4
WhiteWinDraw  53.83 e4 c5 Nf3 e6 d3 Nc6 Ne5
WhiteWinDraw  60.95 e4 c5 Nf3 e6 d3 Nc6 Nfd2
WhiteWinDraw  56.18 e4 c5 Nf3 e6 d3 Nc6 Ng1
WhiteWinDraw  54.51 e4 c5 Nf3 e6 d3 Nc6 Ng5
WhiteWinDraw  55.05 e4 c5 Nf3 e6 d3 Nc6 Nh4
WhiteWinDraw  52.88 e4 c5 Nf3 e6 d3 Nc6 Qd2
WhiteWinDraw  53.56 e4 c5 Nf3 e6 d3 Nc6 Qe2
WhiteWinDraw  53.83 e4 c5 Nf3 e6 d3 Nc6 Rg1
WhiteWinDraw  48.60 e4 c5 Nf3 e6 d3 Nc6 a3
WhiteWinDraw  49.86 e4 c5 Nf3 e6 d3 Nc6 a4
WhiteWinDraw  49.73 e4 c5 Nf3 e6 d3 Nc6 b3
WhiteWinDraw  49.77 e4 c5 Nf3 e6 d3 Nc6 b4
WhiteWinDraw  48.51 e4 c5 Nf3 e6 d3 Nc6 c3
WhiteWinDraw  49.23 e4 c5 Nf3 e6 d3 Nc6 c4
WhiteWinDraw  47.56 e4 c5 Nf3 e6 d3 Nc6 d4
WhiteWinDraw  49.77 e4 c5 Nf3 e6 d3 Nc6 e5
WhiteWinDraw  48.33 e4 c5 Nf3 e6 d3 Nc6 g3
WhiteWinDraw  50.00 e4 c5 Nf3 e6 d3 Nc6 g4
WhiteWinDraw  49.23 e4 c5 Nf3 e6 d3 Nc6 h3
WhiteWinDraw  49.86 e4 c5 Nf3 e6 d3 Nc6 h4

First, you'll note that each line contains the current game, but ends with one of the legal moves. Just before each game sequence, there is a score for that sequence, and since the sequences are nearly identical, the scores are nearly identical too.

In the world of dbacl, these scores are the negative logarithm (base 2) of the probability of the sequence, based on the model WhiteWinDraw. It's best to think of these scores as a distance away from the category model, so the line with the smallest score is the most likely. If you want to know what probability each sequence has, it's 1/(2^54.73) etc., which is pretty close to zero! But that's normal with these kinds of models.

So what's the best move? Simply sort the lines in increasing order by score and print out the first line:

% cat test.scores | sort -k 2 -n | head -1
WhiteWinDraw  47.56 e4 c5 Nf3 e6 d3 Nc6 d4

% head -1 test.complete
e4 c5 Nf3 e6 d3 Nc6 Bd2
% head -1 test.complete | ./dbacl/src/dbacl  -nv -c ./WhiteWinDraw -f 1 -d
# categories: WhiteWinDraw 
# format: avg_score * complexity
    20.25 * 0.5         []e4[](1)
     2.91 * 1.0         []e4[]c5[](1)
     8.82 * 1.5         []c5[](1)
     4.55 * 2.0         []c5[]Nf3[](1)
     7.65 * 2.5         []Nf3[](1)
     3.15 * 3.0         []Nf3[]e6[](1)
     5.71 * 3.5         []e6[](1)
     3.21 * 4.0         []e6[]d3[](1)
     5.48 * 4.5         []d3[](1)
     4.34 * 5.0         []d3[]Nc6[](1)
     5.83 * 5.5         []Nc6[](1)
     4.31 * 6.0         []Nc6[]Bd2[](1)
     5.75 * 6.5         []Bd2[](1)