Author: Ratko V Tomic
Date: 23:27:36 09/20/00
Go up one level in this thread
>I would expect a large position learning database, which continues to grow will >use more of the processor time to search this growing database to a point where >precious little time remains for the processor the execute much of the logic in >the program for any given move. Plus as this learning db will be so large it >will have to reside on disc, and so access times will be slower than hash >memory. > >It doesn't seem to be the right way to go in the short term. If a program has spent, say, 30 seconds analyzing a position in an earlier game, it is still much quicker to find the same position (and its associated decision) in a database than to spend 30 seconds evaluating it again. Database access, even on a slow disk, for any reasonable design and millions of positions would be well within 1 second. How many positions will you produce against the program? If you play at 30 sec/move, and play 4 hours a every day, in one year you will have around 175,000 positions (of which at least 15-20% would already be in the program's book; also some will be dupes or in the endgame tables). Finding a position in this order of magnitude database (or even ten times larger), using a well organized memory based hash/index tables and lookahead disk cache, might take on average under 1 ms or a few ms at most (I have done similar searches on DNS databases with millions of entries). In the simplest, but quite helpful from the customer's vewpoint, mode of use the program would simply check whether the current (actual, not from the search tree) position is in the database. If found, it would save user 30 seconds, if not, it would waste the time it took to establish that it didn't see such position before. The failed search would almost always terminate with RAM based hash/index table search (which would tell the program it didn't see the position before), wasting on average well under 1 ms. So, as long as more than, roughly, 1 in 30,000 positions repeats, it is a net saving of user's time. The search could also be greatly speeded up by noting that most of the repeats will occur right after the book lines. Thus by preloading into RAM a small subtree corresponding to the current opening line a program could decide hit or miss cases all in RAM, within microseconds. A bit improved program could also keep statistics of successfull searches across different opening lines and join such lines into the "related group" preload scheme. The 1 in 30,000 condition could improve by order of magnitude through well chosen preloading. Additional improvement would maintain the statistics on break-even game depth (i.e. at which depth in which openings, the net time gain turns into the time loss) and thus choose at which point, if any, it stops searching the database. That obviously depends on how prone to repeating positions the user is. From my games against programs, I would say I repeat around 1 in 1000 non-book opening or early middle game positions, so it would easily save me great deal of time and irritation watching a program think over for 30 seconds or more the same position and come up with the same decision it did few hours or few days earlier. As an option within this customer centered position learning (as opposed to the marketing hype centered, comp-comp oriented, "book-learning" of today), user could indicate that, when a position is found, the program should deepen its evaluation using the current time settings for the extra evaluations. Similarly, user could specify that the program should utilize the database during the search (e.g. if it is within the net-gain statistics accumulated for a given ply in the game; i.e. right after the opening book, and some plies beyond, it would certainly be a gain; the break-even point would come out of the past statistics). Further improvement of the scheme would be to let the program run overnight over the positions seen today and deepen the evaluations (again, it would have to judge based on past data how deep into the game, beyond its opening book, it is worth going). With an adaptible program which can decide (based on stats accumulated) when to deploy the database within the search, this option would improve its play. Additional option (and potential improvements/user's time savings) may be to join multiple databases (from many users of the program), e.g. via the manufacturer's web site. I would guess that within the next few years these kinds of user centered features, which save user's time and spare them from irritations, will be as common as the large opening books and the pretty screens are today. Another big hole in the current programs is the ability to "explain" to the user why some moves are made, but in the sense of a plan or strategy, not just as dump of a search tree (as is common presently). That one will take longer to become usable.
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.