Author: Don Dailey
Date: 15:10:19 05/17/98
Go up one level in this thread
On May 16, 1998 at 23:17:28, Stuart Cracraft wrote: > >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. So we are actually doing this in Cilkchess 1 and are happy with the results. We haven't done it for Cilkchess 2 yet and are using the book from Cilkchess 1. I don't know how Ken did it but here is how we are doing it now, it's actually simple: First, we start with a book that was constructed by culling half a million or so master games. We have some algorithm which I don't recall for determining which moves to keep based on frequency of occurance. We ended up with about 100.000 positions. Like Ken Thompson, we only think in terms of positions, not moves. And also like Ken, these openings contain everyones favorite lines, and some bad ones thrown in just for fun! Then we store the whole book in a special hash table, with depth and scoring information. To start out with, all positions have a depth of -1 which means no scoring information yet exists. Then we iteratively search each book position, starting at the positions furthest away from the leaf nodes, working our way all the way back up to the opening position. Each time we search a move we store the resulting perfect score in the book hash table. Also we reference this same hash table during all the searches. Other than this, the search is no different that any other search. We start with 1 ply, then 2 ply etc. We can continue this indefinitely. I think the current book was done to about 8 ply, and it did not take too long so we should be able to get at least 10 or 11 with some serious time on an Alpha. In principle we never have to stop. In any given position from our database of master games, there may be some moves played by the masters that are more popular than others. We note which ones these are by some criteria which we labored over for quite some time. I'll call these "popular" moves. So three cases have to be dealt with: 1. Computer likes a popular move 2. Computer likes a rarely played move 3. Computer likes a move never played. In case one, there is no problem, this becomes the book move. In case two and three we simply choose the highest scoring popular move. In cases where a popular move does not exist (usually near the leaf nodes of the book) I believe we trust the computers move if it has been played by humans. Otherwise we are out of book. To provide variety we have strong players add other selections near the opening position. We look at the scores returned from our mini-max procedure to help guide us, but our main goal is to provide some good variety. The nice thing about this method is that no matter what move we force the computer to play, it will be backed up with a mini-max book. It will make the best of whatever we choose for it. So the question remains, is this a worthwhile thing to do? I think it definitely is. There is no reason we cannot adjust the book manually so nothing is sacraficed with this method. In actual practice, my feeling is that this works quite well. We immediately noticed that the computer was suddenly comming out of book with positions IT liked. Almost always, these were good positions. Previously it would come out of book with position it didn't like, and we didn't like either (but its opponent loved!) I'll be the first to admit I have no concrete proof of this concept. It seems to work quite well. I am aware of the problems with this approach too, but the main principle is that the computer is choosing it's own moves, but from a preselected sample of tried and true moves selected by human players. So in my opinion its at least as good as a book chosen simply by frequency of occurance from human games. A project I'm interested in, is combining this with Bob Hyatt's approach which I think very highly of. Essentially, I can use the scores generated from my approach as a starting point and then apply Bob's method. If you do not know about this (Ricardo if your reading) I would definitely check it out. You will have to ask Bob or dig through some older posts where he explains it nicely. - 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.