Aimless behaviour

Compared to the earlier attempts, this change seems to have improved dbacl's tactics. However, we still have much aimless behaviour in the middle and end games. How do we address this?

Our biggest problem is possibly that dbacl is blind. It simply doesn't know or care about the true configuration of the board pieces, like a real chess engine would. Instead, everything it knows are the likely sequences of moves that it found in the training games.

Computer chess is an area which has been studied extensively for a long time, and while we could try to apply these methods to our little engine, we wouldn't learn anything new about chess or about dbacl. So instead, I am only going to try the kind of things that would not be out of place in spam filtering.

Deep in the dawn of spam filtering, people devised keyword rules to send unwanted email to the trash. Even today, this is a popular method to detect, for example, those messages which contain "VIAGRA" in the subject line, and automatically pick an action to take. Maybe we can detect some fixed text pattern in the gameline and use this to override the normal dbacl scores? Let's look at a typical game.

% head -1 ./gamefiles/BlackWin.txt | fmt
d4 Nf6 c4 e6 Nf3 b6 g3 Ba6  Qc2 c5 Bg2 Bb7 O-O Be7 Nc3 cxd4  Nxd4 Bxg2
Kxg2 Qc7 Qd3 O-O e4 d6  f3 Nbd7 b3 a6 Be3 Qb7 Rfd1 Rfe8  Bf2 Bf8 Nc2 Rec8
Ne3 Rab8 a4 Ne5  Qd2 Rc7 Rac1 Rbc8 Qe2 Nc6 Be1 Nd7  g4 Nc5 Qc2 Nb4 Qb1
Be7 Ne2 Nc6  Bc3 Ne5 Ng3 Bg5 Ngf1 Bf4 Bxe5 Bxe5  Rd2 Bf4 Rcd1 b5 axb5
axb5 Ra2 Nd7  Qd3 Nc5 Qc2 h6 Ra5 bxc4 bxc4 Nd7  Qe2 Ne5 Rb5 Qa6 Rb2
Nxc4 Nxc4 Qxc4  Rd3 Qc5 Ne3 Qg5 Qf2 Rc3 Rxc3 Rxc3  Nf1 Kh7 Rc2 Qe5 Ng3
Be3 Qe2 g6  Nf1 Bf4 Ng3 Kg7 Qf2 Be3 Qe2 Qd4  Nf1 Bf4 Ng3 Rxc2 Qxc2 Qd2+
Qxd2 Bxd2  Ne2 g5 Nd4 Kf6 Nb3 Bc3 Kf2 Ke5  Ke3 Bb4 Nc1 Bc5+ Ke2 Bg1 Nd3+
Kd4  h3 Kc3 Nc1 Bh2 Nd3 Bf4 Nf2 d5  exd5 exd5 Nd3 Be5 Nc1 Kd4 Nd3 Bf4  Nb4
Ke5 Nd3+ Kd6 Nb4 Ke6 Nd3 Bd6  Nb2 Ke5 Nd3+ Kf6 Nb2 Ke6 Nd3 h5  Nf2 f5 Nd1
fxg4 fxg4 hxg4 hxg4 Kf6  Nb2 Ke5 Kf3 Kd4 Nd1 Kd3 Nf2+ Kd2  Nh3 Be7 Nf2
Bc5 Nh1 Bd6 Nf2 Bf4  Nh1 Be3 Ng3 Kd3 Nh1 Bg1 Ng3 Kd2  Nf5 d4 Ng3 d3  0-1

Besides the normal moves that represent a change in position, the most obvious feature is that some of the moves above also contain an 'x', which means that this is a capturing move. Interesting! One of the problems with the dbacl engine so far is that often, an opportunity for capturing White's pieces is simply ignored. Can we devise a keyword rule which triggers on 'x' to force dbacl to capture an available piece instead of ignoring it?

Let's try it: first we'll need a gameline which includes an 'x' type move, since our previous test.gameline file doesn't. Note that we'll forget temporarily the underscore trick we used in the previous section, just to keep things simple at first.

If you look at the full game listed two paragraphs ago, you'll see that the last full move on the first line is "Nxd4 Bxg2", so if we use this line and delete the last full move, then the possible completions will contain at least "Nxd4" and we have a suitable test case.

% cat > test2.pgn
1. d4 Nf6 2. c4 e6 3. Nf3 b6 4. g3 Ba6 5. Qc2 c5 6. Bg2 Bb7 7. O-O Be7 8. Nc3 cxd4
% echo -ne "svop verb namd nabd napr\nlfer test2.pgn\nenum 1\n" \
 | ./SAN/SAN_SRC/san > test2.legal 2>&1
% cat test2.legal | grep '^.* : 1$' | cut -f 1 -d ' ' | \
 while read move; do
        echo `cat test2.gameline` $move
 done > test2.complete
% cat test2.complete | ./dbacl/src/dbacl -n -c ./WhiteWinDraw -f 1 > test2.scores

There are 48 different potential moves in the test2.scores file, and what we are interested in is the score (column 2) and the potential half move (column 21).

% cat test2.scores | sort -k 2 -n | cut -f 2,21 -d ' ' | head -25
129.08 h3
129.35 a4
129.89 a3
129.89 b3
129.89 e3
133.09 Qg6
133.36 Bf4
133.36 Bg5
133.36 Qa4
133.36 Rb1
133.36 Rd1
133.86 Be3
133.86 Bh3
133.86 Nb5
133.86 Ne4
133.86 Nh4
133.86 Qb3
133.86 Qd3
133.86 Qe4
137.87 Nxd4
154.68 e4
154.96 c5
155.77 b4
155.81 h4
155.95 g4

I've only listed the first 25 moves by score but it's clear that dbacl's model puts "h3" as the most likely move, and "Nxd4" way down in 20th position! Let's extract the capturing moves.

% cat test2.scores | grep 'x[^ _]*$' | sort -k 2 -n
WhiteWinDraw 138.73 d4 Nf6 c4 e6 Nf3 b6 g3 Ba6 Qc2 c5 Bg2 Bb7 O-O Be7 Nc3 cxd4 Nxd4 Bxg2 Nxd4
WhiteWinDraw 162.90 d4 Nf6 c4 e6 Nf3 b6 g3 Ba6 Qc2 c5 Bg2 Bb7 O-O Be7 Nc3 cxd4 Nxd4 Bxg2 Qxh7

Since there is more than one possible capturing move, the engine has to decide what it wants to play. By sorting the capturing moves by their scores, we let dbacl tell us which move it prefers. Obviously, "Nxd4" is this preferred candidate. It's also possible that for some gamelines, there is no legal capturing move; we'll have to use the full list of scores as before in that case.

Finally, we must decide how we are going to integrate this special handling of capturing moves into our chess engine. In spam filters, a keyword rule typically stops all other tests from happening afterwards, because the rule is trusted to override other decisions. Here, this means that we first score all the capturing moves if there are any, and use the best one regardless of other options. It's only if there are no capturing moves that we look at the remaining possibilities.

By using the explanations above, you can modify dce-basic.sh yourself, or try out dce-2.sh, which implements both the 'x' and "underscore" tricks together.

% chmod +x dce-2.sh
% xboard -fcp ./dce-2.sh