Author: Stuart Cracraft
Date: 20:17:28 05/16/98
Go up one level in this thread
On May 16, 1998 at 19:24:36, Ricardo Sant Ana wrote: >Hello All > > I ´ve been reading a lot about chess programs (engines), and I am a >little curious about how can one work in a chess program opening. >Could any of you chess programmers give me some light ? For instance, if >a friend of mine is working in a chess program, how can I improve it´s >chess book ? I listened that an opening could be good for humans but not >for a chess program, so , the one who is working in a chess program >opening should avoid it , but how can he/she kwew this ? >I think lot of people could enjoy this kind of information , and even >the programmmers, because if you (chess programmers) tell us (chess >program users) how can we work in YOUR chess program opening to make it >play better, we could give YOU back information about OUR progress :-) >So everybody would be HAPPY! :-) > >Well, if you could answer to the list and to my e-mail I would >aprecciate a lot. Of course I will answer in CCC. >Thanks in advance, Ricardo Sant´Ana (AKA Psy) I think you can get pretty complicated with a book. The most interesting opening book I heard of was Ken Thompson's minimaxed book for Belle. According to what I read that he wrote about it, it seemed to play everybody's favorite lines (instead of developing its own favorites), not particularly a great result but perhaps there is some more room for experimentation with minimaxed books. The main thing I remember is Thompson telling me to always do the book by position, not by moves or other methods. So when I wrote my code (various versions of it), this is what I did. Handles transpositions automatically so no special code. Pretty straightforward for these modern days of fancy stuff. I remember the Spracklens bumming lists of LISP-like expressions to create a beautiful-to-look-at opening file which could be very useful to a strong player organizing the book for the program but which looked pretty nasty to program. My own simple book is processed/generated/used by a small amount of code. One routine generates a binary sorted book.dat file based on a book.pgn file, which is a list of C structs containing 64-bits of hash and a score. This represents a position that is a "book position", found after some "book move." The pgn file source has pgn-format games or move lists (e4, e5, Nf3, etc.) The move list I chose was ECO's main lines in a preferred order (B, D, C, E, A, etc.) with supporting games at the end from various master tournaments. Pretty normal I'd expect unless you get really fancy. The book generator then simply scans all this stuff, takes the hash key created after each move made, sees if it is already in an in-memory buffer and if not, stores it there (with an additional hash key to help avoid collisions). When the buffer fills up, it writes out to the book.dat file. There is also an option where the program does a short quiescence search on each position before storing it. It scores it with its evaluation. This can be used to order the positions to give a "best N" randomness. The book reader is used as long as the program is not some N moves from the last book move. It then successively reads in buffers from the disk file into memory, scans for entries whose hash keys (combined) match the possible successor hashkeys for the current board position's successors. It builds a list from this. Based on the mode of the book, it may choose the first move found (ECO order), or in a random mode, or preferred (best score stored with position), or randomly amongst the best N or preferred N or randomly amongst the worst N or least preferred N in the overall list that it built. My current book is not large (less than 100k positions.) A single scan of all of these goes very quickly (less than 1 second on a Pentium 133mhz). To expand to many more positions I'd need to do a binary disk search or use a disk hashing method. I figure the current scheme would be good up to a few hundred thousand unique positions which would be the equivalent of many more than that in total opening lines as fewer and fewer unique lines get found since the positions tend to overlap and cancel out. I have no method for punishing positions that do poorly in practical play but this shouldn't be too hard as it would just involve an additional command to take a given position and rewrite the score with some user-provided number, a high negative meaning a position that should be avoided. Recall the score is written by the short quiescence search when the book is generated. An 80k position book with quiescence generates in fairly short order (an hour or two as I recall). An additional computer or background process could provide greater depth searches to be the basis for the score if preferred. I make no attempt to eliminate lines that don't fit the program's personality or style of play or more appropriately provide only lines that do fit its style which sounds like your original queston. To do this, I'd probably pay more attention to the score. One mode provided, called "preferred", does help somewhat avoid leaving the program in positions out of book that it doesn't like, which can avoid the problem of the program shuffling all its pieces around after leaving book to find an arrangement more suitable for its evaluation function. Storing all the positions is helpful because they might be useful for randomization and broader openings for more players to enjoy (for example on ICS). The choice of opening depends on what the program's evaluation considers important. Using an opening, other than providing pleasure to the human opponent, which contradicts the program's style is of course counter-productive. Most programs reward position features like open lines of play, central pawns, and so forth. If your program does, classical openings might be more appropriate, especially open or semi-open. If your evaluation function rewards other types of features more (control but not occupation of the center, fianchettos), perhaps closed and semi-closed openings should be favored. I think there has been more success with open and semi-open. Certainly this task has taken some of the best teams a lot of person-power. Entire groups have been dedicated to opening analysis for chess programs. Some very strong programs have lost a lot of points in practical play due to lack of adequate opening preparation. Another interesting opening book method would be the position-based learning approach to avoid opening errors but avoid having to dedicate so much to book support. Essentially a supplement to the book, I believe it is written to whenever the search indicates a big drop in evaluation during iterative deepening (or something along those lines.) There has been much controversy by this style of automatic booking up by commercial programs against their competitors, either to provide an artificially inflated win-count or an artificially inflated rating on the rating list. To start, I'd just suggest doing something simple that handles transpositions. This greatly simplifies your book code and anything that gives peace of mind in this business (or hobby) is worth its weight in gold. --Stuart
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.