Author: Robert Hyatt
Date: 20:39:06 12/29/97
Go up one level in this thread
On December 29, 1997 at 22:16:25, Don Dailey wrote: >>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? my approach is simple. Suppose we followed a book line 20 moves deep. And suppose the score at the end of the line is -2. I take this -2 and propogate it over the entire book line, but in a uniform graduated way, so that the last book move gets a learned result of -2 (more on this number later). the next to last move (move 19) gets 19/20 of this score, all the way back to move 1 which gets 1/20 of this score. I don't ever play a book move with a learned value of -1 or worse, so I would not play the last 10 moves again, unless they had already been played. Next, each time crafty plays an opening, the learning has two components, the learned value and the learn count, which is incremented each time a book move is played, but limited to a max value of 255. Say a move has been played N times with a learned value of X. The new learned value is (N*X+new)/(N+1). If the learned value is very bad, I may "shrink" N to make the lesson a little more forceful. The "learned value" is the value I "discern" as key from the first 10 moves out of book, but is graduated based on search depth. I use 10 plies as "normal"... anything less than this reduces the learned value. I also take the opponent's rating into consideration, so that if crafty is rated higher than the opponent, good learned values are scaled back proportional to the rating difference, while bad results (against a weaker opponent) are scaled up in the same way. For players rated better than crafty, I scale good scores way up, but scale bad scores down since a better player should win most games. > >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. In my book, for each "position" (which is really a move since I generate moves, make 'em and look up the resulting positions) I store wins, draws, and losses for that side, plus the learned value and learn count as above. Crafty never plays a move with zero wins... and uses the counts in a statistical way to favor moves that were played most frequently, but it also factors in win/loss ratio and other things including the learned value... And my book can be culled so that it only contains moves played at least N times total, where N is a user-definable parameter when the book is originally parsed and built. > >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. I don't do this. I tried this (actually used it in Cray Blitz) but believe it gives false information. IE it sometimes takes many moves to see the benefits of a gambit. you will likely accept almost all gambits, and decline to play any doing this. But the bad side is accepting gambits that seem to hang a pawn, but which lead to a really bad bind of some sort.. > >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. > I have a ! (always play) and ? (never play) manual override. I also use a small "start book" so that it is easy to add your favorite line with !'s to make crafty play it, without having to rebuild the big book which can take a while... I have 16 user-definable flag characters that can be appended to any move (ie use a for gambit, b for closed, etc.) and when playing you can tell it to select (if available) any move with an "a" flag first, to make it play a gambit if possible... >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. A word of advice: *don't* try to choose book lines with a + eval. They are nearly impossible to find, and generally leave you in bad or drawish positions. I'd rather come out -.3 than anything, because Crafty has a chance to use it's search and knowledge to play chess, rather than coming out at +.05, in a dead drawn position... > >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. that is the *danger*. Just because you think you are doing good right out of book, doesn't mean you are doing good long-term. IE try the king's gambit against it. It can get into a world of hurt if the book doesn't help it give the pawn back. So as black you come out +, but likely won't stay there very long. This was why I tossed the minimax approach we used in Cray Blitz... the learning approach works much better... > >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. there is an alternative... *hundreds* of masters and IM's and GM's fine tuning your book, which is *exactly* what I have. It is a combination of book learning and the Internet Chess Club. :) > >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.