Author: Don Dailey
Date: 21:41:29 06/01/98
Go up one level in this thread
On June 01, 1998 at 13:17:00, Lucien Okkes wrote: >Hello everyone, > >in the past months if have completed the 'body' of my own chessprogram. >It's called Warp version 3 (as all star trek fans know, warp 9 is the >maximum :-). I hope the body of the program is bug-free now. As you all >know, a chess program is not complete without an openingbook and an >endgame database. Although I was able to create a chess playing program >on my own, I stil have the feeling of a absolute beginner. So here is a >simple (?!) question: what is the best way to implement a openingbook >and an endgamedatabase? >Should I adopt an existing standard? Or is better to build a openingbook >myself, so that I can differentiate from other program's? How is an >openingbook organised? > >Greeting, > >Lucien Okkes Hi Lucien, I store my opening book as a database of positions. I use a hash table but have used a sorted table in the past combined with a binary search. There are many ways to do it, I will give you my way which is probably simpler than what others do. I store the positions as a simple text file of modified FEN positions. This is not necessary but I use the records for various things and I have tools that create fen records from games and so on. The details of how you store it are not important. With each fen record I also store a list of moves that the computer will play. Actually I have various codes to describe frequency of occurance and other information attached to each move too. I do not worry about how big this file is and it is stored on disk. When the program initializes, the big book file is read line by line, a hash key is generated and I store a pointer to the position in the file of each record. When the program moves, it first gets the key of the current position, looks in this index and finds out where the record is on disk, if it exists. It reads this record, parses it and chooses a move according to the rules I set up (based on the various codes etc.) Our book only has 109 thousand positions but that is enough to make the initial load take too long, since each record is parsed, converted into a position and other details performed. So when this index (or in memory hash table) is produced for the first time I write it out to disk in raw form. It will load next time from this table. The only time I rebuild is if I cannot find the index file. The rebuilding takes at least 30 seconds or more, but reading in an index file is almost instantaneous. There is no reason whatsoever the index file could not also be a disk file, I just happen to have it in memory. But finding a book move seems instant anyway. I do not yet have good tools for editing the book. It's a tedious process of finding the position using an editor, killing the index and starting up the program (to rebuild the index.) It's on my list of things to do and I could whip together a reasonable editor in no time. You can also store a book as move sequences. But I don't like this method because it will not see transpositions. Many times the program has been out of book and suddenly comes back in to book. This would not happen with move sequences. There are ways to search move sequences to make this possible but I believe storing the positions is actually simpler. There is also a cool trick with stored move sequences to help compress it. You store moves in 6 bits by using the offset into a move generator. Then you use 2 bits to represent groupings, something like: e4 (e5 (Nf3) (Nc3)) (c5 d4) which is equivalent to: e4 e5 Nf3 e4 e5 Nc3 e4 c5 d4 So you would never store a move twice like you might using move sequences. A simple stack structure will make this easy to deal with. The parenthesis are stored as one of the 2 extra bits in the move, one for left parenthesis and one for right. Double parenthesis can represent a special meaning which is encoded in the 6 bits normally used to store the move. Using 6 bits to store a move means that you cannot easily represent a move comming from a position with more than 64 leagal moves. Even though positions with 2 or 3 hundred moves are possible, in practice it's extremely rare to get more than 100 and perhaps a typical book would never exceed 64. There is no need to limit yourself to 8 bits but this is easiest to deal with and is the least number of bits that have a reasonable chance of being big enough. You might also choose to use a tree structure to store these moves. But I prefer simple implementations where possible and I think hashing or binary searching a list of positions is about as simple as you can get. I had older programs that stored only the hash key and some moves. I had no record of which moves were in the book, you just had to try it from the program. Years ago we gave this book to the Deep Thought team. Since we did not know what the moves were, I had to modify the program to "walk the book" to extract them as sequences of moves. The program ran all night and into the next day before I realized it was stuck in a recursive loop involving a draw by repetition series of moves. Even though I had a depth limit, the same draw positions were found hundreds or maybe thousands of times. There were several ways to play this sequence and several move orderings and it explored every single one of them. It was actually quite beautiful to me at the time and I was amazed at the output which formed nice patterns along the page! Just a few ideas for you, there are many possibilities. Opening books are not the most natural data to deal with, so they can be a bit of a pain doing right. - 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.