Author: Steven Edwards
Date: 16:46:19 04/29/04
Symbolic: Status report 2004.04.29 I've been giving a lot of thought to the problem of time allocation during the move selection process. With a TABS (Traditional Alpha Beta Searcher), time allocation is in part supported by taking an iterative approach and deciding after each iteration whether or not to try another iteration. Alas, there is no simple analog to this technique in a knowledge based, pattern recognizer program like Symbolic. In Wilkins' knowledge based program Paradise, the time allocation problem was handled by ignoring it entirely; instead, a hard limit of forty-five minutes of processor time on a pdp-10 was enforced. Obviously, this is not suitable for a competitive program like Symbolic. Furthermore, an integrated approach of time management must be taken prior to design of the major structural sections of Symbolic to avoid the inevitable hacks of grafting time control afterwards. How best to do this? As with many other aspects of this project, nearly all of the computer chess literature is unhelpful. But there are some hints in the psychological studies of human chess move selection. These are: 1. A human chess player seems to retain all of his/her plans and search tree in memory during the selection process. 2. A human chess player seems to revisit some plans and search nodes during the selection process; sometimes with the same purpose and sometimes with different purposes. 3. A human chess player seems to work in part by having uncertainty reduction as a major goal in the selection process. Symbolic, unlike all TABS and nearly every other program, retains its entire tree in memory during move selection. Also, it is able to revisit nodes as needed and can retain previously generated information about those nodes. With these features in mind, attacking the problem of uncertainty reduction can also be used to attack the problem of time management. So here's my idea: 1. Design and implement a sufficient number of KSes (KS = Knowledge Source, a traditional AI buzzword) in Symbolic. Each KS is a big wad of Lisp code that takes a query (in a somewhat standardized format) and provides an answer (also in a somewhat standardized format). Each KS specializes in some topic like attacking, exchange evaluation, quiescence, etc., and one KS may invoke others to help answer a question. In this, a KS in Symbolic is similar to a KS in Paradise. 2. Unique to Symbolic, as far as I know, is the inclusion in the somewhat standardized KS query format of an effort parameter. This effort parameter is an integer value that gives the KS an idea of how hard it should try to reduce the uncertainty of the answer to the query. 3. Also included in the query format is a location parameter (usually a search tree node symbol) that specifies the context in which the question is being asked. This is needed (obviously) to tell the KS where various input can be found. 4. Access to the KS barnyard is gated by the KSM (KS Manager). The KSM provides a convenient debugging trace point, but much more importantly it also tracks (and caches) queries and their answers. Using its history, the KSM can at times provide a savings by recalling instead of recalculating answers. The KSM is also used to terminate the search gracefully if a hard time limit is exceeded. 5. Given all of the above, Symbolic can perform time management by using a monotonically increasing function that generates effort parameter values that are provided to queries submitted to the KSM. Symbolic will continue analysis until the overall uncertainty of the selection is suitably reduced relative to the time available on the chess clock. For more efficiency, a KS can be designed to take an additional parameter: its own prior analysis to the same query for a lesser effort parameter value. An example: The KS named Exchanger performs exchange analysis on the position associated with its input node. Called with an effort parameter value of zero, it does a relatively simple static exchange evaluation and returns a list of exchange squares with material delta scores for each of them. With higher effort values, it will examine additional factors like pins, discoveries, and checks. With even higher values, it will spend time reducing uncertainty by calling itself and possibly other KSes on positions resulting from partially executed exchange sequences. (These sequences can be cached for future references.) And at even higher values of its input effort parameter, Exchanger can invoke the Selector KS to start an internal subsearch. Any KSes called this way get their own effort parameter values, suitably calculated from the value of the effort parameter provided to the initial call to Exchanger. If this sounds a bit like a human applying a process of successive refinement, well, that's the idea. -------- Developing the KSes seems to be a reasonable approach to the current task agenda. The functionality of the KSes is needed in any case, so there's less risk of doing unproductive work if the overall design (i.e., the plan and pattern production system) changes. Ideas for KSes: 1. CandidateSelector: The main KS; select a move among the ply zero candidates. (Probable related KSes: ContigencySelector [picks a candidate very quickly with minimal analysis to have a valid reply in time control crunches], Selector [works at any node], SingletonSelector [only one reply is available], TablebaseSelector, BookSelector, CertaintySelector [where all or all but one subnodes have certain score bounds], KludgeSelector [starts an internal A/B search; used only during development; to fill knowledge gaps].) 2. Surveyor: Identify and rank salient positional themes to assist with planning. 3. Planner: Produce plans for a node. (Probable related KSes: PlanRanker, PlanRepairer, PlanLibrarian.) 4. Explorer: Apply a plan to a node and return an analysis. (Probable related KS: Scout, a lightweight Explorer using move suggestions instead of plans.) 5. Exchanger: Perform exchange analysis for the position associated with a node. 6. Terminator: Determine node quiescence. Hasta la vista, subtree. 7. Attacker: Suggest useful attacking moves and move sequences. (Probable related KSes: MateAttacker, MultiAttacker, CounterAttacker.) 8. Defender: Suggest useful defending moves and move sequences. (Probable related KS: MateDefender.) 9. DejaVu: Apply causal analysis to eliminate unnecessary search. 10. Quickshot: Detect an obvious reply move (e.g., simple recapture) to avoid branching. 11. Watcher: A meta-KS of sorts that tries to detect patterns in KS invocation. The idea here is to prevent the selection process from getting bogged down if it's doing nearly the same work repeatedly without productive results. 12. Micro: Perform a evaluation of positional factors for a quiescent position. (The underlying toolkit reports scores using thirty-two bit micropawn values, hence the name.) Unlike other KSes, this one ignores the value of its input effort parameter. -------- I've decided to punt on the Trapped instance recognizer for the moment as an accurate analysis needs more processing than I'd like to see in a bootstrap pattern recognizer. -------- The project directory tree was reorganized in order to take better advantage of Apple's Xcode development environment and to improve access, backup, and cross platform operations. The new tree has a Documents subtree to hold status reports, project documentation, and test suite files. Future work in this area will include support for better automation of Linux tasks such as a real Makefile; at the moment I just use: g++ -O3 -pipe -Wno-deprecated -lpthread -O Symbolic *.cpp and that takes several minutes to slog through all the C++ source. The pipe option is based on the superstition that using it just might speed up compilation. The "no deprecated" option is needed to silence warnings about an obscure include reference problem in Linux that is not a problem in OpenBSD. And the Posix thread library gets searched because of Symbolic's dependence on portable multithreading. -------- On the hardware front, I have had to deploy a spare USB keyboard on the main development machine, my 400 MHz PPC G4 Macintosh. This was needed after discovering that a standard US$60 Apple Professional Keyboard is unable to withstand an unexpected (and unobserved) application of feline urine. And because I have two house cats, I can assign neither blame nor the appropriate behavior modification treatment. -------- I had hoped to get Symbolic finished, or nearly so, by late 2004. Given health issues, wayward cats, and the current rate of progress, it may be mid 2005 before all of the primary goals are met. Again, the road is long.
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.