Computer Chess Club Archives


Search

Terms

Messages

Subject: automated book generation in chess/checkers

Author: martin fierz

Date: 15:31:14 12/12/01


aloha,

there was a discussion about this, deep down in a thread about who is the best
chess programmer, so i decided share our experience here:

thomas lincke (lincke_at_inf.ethz.ch) has generated an opening book for my
checkers program with a technique called dropout expansion. he wrote a paper on
this, i think. for checkers it works very well, my book is very close to what
you expect from reading human opening books. the book has 1.1 million scored
positions in, which gives me about 200'000 book moves.

tom also used crafty as an engine to try and build a chess opening book. while i
do not know all details, i know he had at least a million nodes, and the book
was (if you ask me, 2200 rated) completely useless.

the big difference in performance for the two games is that checkers has a very
high percentage of losers in every position. chess on the other hand has lots of
positions where you can make nearly any move. take the opening position, i play
1. b2-b3. or even 1. h2-h3. these moves are not the best, but they don't hurt
too much either. so the problem is, you cannot discard these moves, and that is
what dropout expansion is about - test all moves to some depth and throw out all
which you think lose, and defer expansion of all slightly inferior moves, and
move on in the best nodes.

i thought maybe this technique would work in chess for some special variations,
where many moves are forced, so i suggested the dragon after about 15 standard
moves involving a pawn sacrifice for white - result: no use again. here's why:

1.e4 c5 2.Sf3 d6 3.d4 cxd4 4.Sxd4 Sf6 5.Sc3 g6 6.Le3 Lg7 7.f3 0-0 8.Dd2 Sc6
9.Lc4 Ld7 10.0-0-0 Tc8 11.Lb3 Se5 12.h4 Sc4 13.Lxc4 Txc4 14.h5 Sxh5 15.g4 Sf6

[D] 3q1rk1/pp1bppbp/3p1np1/8/2rNP1P1/2N1BP2/PPPQ4/2KR3R w - - 0 16

this was our starting position. i had hoped that in a sharp position as this,
dropout expansion would also work for chess. it didnt :-(
the problem was that crafty's main line went like 16. Qh2? h5? etc. the correct
answer to 16. Qh2? is Rxc3! which every dragon player will play in a slpit
second. the problem is that even if you can take the queens off with white now,
your position is bad. there have been too many discussions here about
"understanding", and i don't really want to say anything about it to avoid
further discussion. let me define "understanding" for this purpose as "does the
evaluation function know that this position is good or not", so that it "knows"
it *without* using the search? if a program's evaluation function does not
know/"understand" that the black position here is ok, it will never produce a
sensible main line, because the essential features of this position will not
change for a long time to come - black is an exchange down but has a pawn and
white's pawn structure is cripplede and his king is not safe. about all which
can change in the next 20 ply or so is that the queens come off, and even then
black is just fine.

so, to conclude this post, i believe in automated book generation for games with
few good moves/position but i don't believe in it for chess. tom also used it
for awari to good effect. i don't know enough about chinese chess, i played a
couple of times in beijing, but more for fun :-)

cheers
  martin



This page took 0.05 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.