Randomized play

We've come a long way, so let's go back to the initial question. "Can a spam filter play chess?". To answer this question affirmatively, we need at least one example which can't be explained by random play. While dbacl undoubtedly makes some strange chess decisions sometimes, let's look at the following game fragment played against dce-3.sh:

Clearly, dbacl picked up the pawn defensive moves from the games archive, as this succession of moves is very unlikely to be random (all moves are on the same side of the board, and none of the moves are capturing moves, so cannot be explained by capture heuristics which partially override dbacl's natural choices).

So dbacl has definitely learned something about chess, at least in some tactical situations, and can probably hold its own against an average three year old. Mission accomplished!

Well, the title of this section is "randomized play", and there is one more thing to do. So far, the dbacl chess engine is deterministic: when faced with identical White moves, it will always play the same way. This gets boring very fast. What we would like is more randomized play, but which still uses the dbacl scoring system.

For randomized play, we can think of the scores as equivalent probabilities. Then we can pick not just the highest probability (lowest score) move as we've done so far, but instead any move according to its probability. Let's look again at the file test.scores that we created earlier:

% head -5 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

As I already mentioned, the dbacl model probabilities are related to these scores as follows: Prob[Bd2] = 2^(-53.88), Prob[Be2] = 2^(-52.93), etc. Unfortunately, these are all very small probabilities and we can't easily represent them as floating point numbers once the gameline becomes much longer, let alone pick them at random. So first, let's subtract the biggest common factor: If we sort the scores, then the top score is the factor we want:

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

We'll write an awk program to do the randomizing, so here's the first part:

% cat > renorm.awk
#!/usr/bin/awk -f
{
  if( cf == 0 ) {
    cf = $2
  }
  print $2 - cf, $0
}
% cat test.scores.prob | awk -f ./renorm.awk | head -5
0 WhiteWinDraw  47.56 e4 c5 Nf3 e6 d3 Nc6 d4
0.77 WhiteWinDraw  48.33 e4 c5 Nf3 e6 d3 Nc6 g3
0.95 WhiteWinDraw  48.51 e4 c5 Nf3 e6 d3 Nc6 c3
1.04 WhiteWinDraw  48.60 e4 c5 Nf3 e6 d3 Nc6 a3
1.67 WhiteWinDraw  49.23 e4 c5 Nf3 e6 d3 Nc6 c4

Okay, the first column gives the modified score and the rest is the original line. Since these are binary exponents rather than actual probabilities, we'll use a rejection sampler to pick the correct line and print it out. Here's the full randomizer:

% cat > randomizer.awk
#!/usr/bin/awk -f
{
  if( cf == 0 ) {
    cf = $2;
  }
  score[NR] = $2 - cf;
  line[NR] = $0;
}

END{
  # randomizer seeded by time of day
  # don't use more often than once per second.
  srand();
  while(1) {
    x = int(rand() * NR) + 1;
    t = -log(rand());
    if( log(2) * score[x] < t ) {
      print line[x];
      break;
    }
  }
}
% cat test.scores.prob | ./randomizer.awk 
WhiteWinDraw  48.33 e4 c5 Nf3 e6 d3 Nc6 g3
% cat test.scores.prob | ./randomizer.awk 
WhiteWinDraw  47.56 e4 c5 Nf3 e6 d3 Nc6 d4

Awk's randomizer is seeded by the time of day, so if you repeatedly run the randomizer.awk script in a fast loop, it will always output the same result. But for chess against people, we don't really care about the quality of the randomness involved.

I've added the randomizer to the final version of the chess engine, dce.sh, which also contains a few other improvements. If you feel like experimenting further with the dbacl chess engine, that script is probably the best starting point. Enjoy!

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