Author: Don Dailey
Date: 19:16:25 12/29/97
Go up one level in this thread
>IE, somehow you find a line that works against Crafty for most any time
>control, and ends up +3 in your favor. In that case, Crafty will follow
>that line *exactly* once, and will then vary somewhere earlier (maybe
>at the last point with a branch, or with a -3, it might even go back a
>branch or two earlier, believing the entire sub-tree is broken. But it
>won't play it a second time, *ever*.
Hi Bob,
This makes a lot of sense to me and I like it a lot. But I don't quite
understand how you determine which point to vary from? This paragraph
is ambiguious to me. Can you elaborate a little more?
Anyway, since you talked about getting positions culled from PGN files,
that is exactly what I do. Let me share my algorithm and some of
its justifications with you and everyone else:
First of all I do a frenquency of occurance count on every move played
in a large database of Master games. If the frequency is above some
arbitrary value, I store the position and every move ever played from
that position. I also flag the high frequency replies, but I don't
remember the exact algorithm. It's based somewhat on the percentage
each move was played but also has some minimum frequency count
requirement to be considered high frequency.
Then I sort this file of positions by depth, deepest first.
I search each position (in the order I sorted them) to some arbitrary
depth, the deeper the better! When the final score is returned at the
root node I place it in a permanent hash table which is active during
this whole procedure. In this fashion each search gets the benefit of
the previous searches of the children nodes. Of course the "regular"
hash table is also active but this special one never forgets a
position. By the time I search the opening position information has
propogated back from the deepest book positions.
Please note that the searches are normal searches except for the
benefit of the extra information that gets propogated forward.
I make a note of each move the computer selected and add this to the
database.
Now at this point we have this big database of positions with the
following information attached:
f) High frequency human moves.
l) Low frequency human moves.
c) computer selected moves.
h) see below
-) depth of "book" process search
-) score of position from book process
How do we use this information for the book selection process? We
follow these steps in this order:
1) If "cf" computer will play this move because it was high
frequency AND the computer chose it.
2) If the move is "cl" the computer will still play this move
because some master played it AND the computer likes it.
I have a comment on this a little later.
3) If the computer prefers a move not played at all by the
human masters, we avoid the move and pick a high frequency
human move at random.
4) If no high frequency master moves are available we avoid
the move altogether and are out of book.
We also have a provision for editing the book. We attach an "h" to
the move which means it was Human selected. This serves as an
override and we also use this to provide variety. With Larry
Kaufman's help I forced in a lot of moves very near the opening
position so it wouldn't just play 1 move from every position. Note
that there are cases anyway where it will play more that 1 move but
this is not sufficient to provide enough variety. For instance from
the opening position it would only play d4 so we asked it to play e4
also.
So now the modified algorithm is:
1. play an h move at random if available
2. play a cf move at random if available (will only be 1)
3. play a cl move at random if available (will only be 1)
4. play an f move at random if available
5. out of book
So how well does this work? I can't give you any scientific answer
but our "feelings" about it are very good. The main reason we went to
all this trouble was because we did not have time or access to a
master willing to go to the tremendous effort to hand build a book for
us. And last year at the Dutch Computer Chess championship we were
very unhappy with our opening book performance. In almost every
single game (there were 11 of them) we were very unhappy on the first
move out of the opening book and struggled in almost all of our games.
We managed to win the tournament but not with any help whatsoever from
the opening book.
If you carefully look at the procedure you can see it was an attempt
to solve this problem. Basically each move in our book is searched
and contains some information propogated back from the final positions
in our book!
But we think this procedure was pretty successful. Since we created
the book we have noticed a HUGE shift in the computers assesment of
the first positions out of book. Typically we are very happy with
white and very often even think we are better with the black pieces!
Also we have only been outbooked a couple of times in a large number
of games but I do not consider this a major benefit.
But of course we realize this is only the computers opinion, and does
not really mean we are better off (indeed that is sometimes the case.)
But then again we rarely ever feel the urge to shuffle our pieces
around right out of book (which has been a problem for us in the
past.) We are picking lines that if nothing else, are compatible with
the computers idea of what is good and bad.
I know I'm likely to get a slew of mail pointing out all the drawbacks
of this technique. I concede that it has some flaws and is not
perfect. For instance there are likely to be some refuted moves in
the database. Theory is full of cases where a once popular move gets
refuted and these moves might very well show up as "CF" moves in my
book. But at least the computer got to take a crack at it too!
Also note that this is not much worse than someone furiously typing in
moves somewhere without paying a whole lot of attention to them. At
least each move gets individual attention from a strong master (the
computer itself.)
But I do consider it a great starting point. I also concede that
there may be no good substitute for a strong master fine tuning your
book, but having this kind of book doesn't prevent this.
Another HUGE benefit of this procedure is that your book contains all
this great theory whether you use it or not! Our old book was
specialized so there was no information at all on lines that were not
selected. If we wanted to add a new move we would be required to add
all the subsequent variations that went with it. But that is no
longer a problem! Now we simply change a single move choice and the
computer will never miss a beat and take over gracefully, still trying
to maximize its final out of book score.
Now, concerning step 3:
3. play a cl move at random if available.
This one is a little more open to debate. Should the computer play a
move that few people have tried? I argue that if the orignal book
search depth is sufficient it will not matter anyway. Because if you
search a position to 20 ply before the competition and would only
search 12 ply during the competition, why not just play the 20 ply
pre-searched move? The original search depth might very well
determine whether to use this step or skip it.
There are some more ideas that go with this which I'll save for later.
Anyway, I thought I would share this with you guys. Does anyone have
any comments or better yet would anyone like to share some of their
automated procedures with us?
-- Don
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.