Author: Steven Edwards
Date: 14:15:52 05/13/04
[Running about ten days behind with posting] Symbolic: Status report 2004.05.03 I've implemented the basic routines that enable time management along with the protocol to transmit the nominal time allocation value from the toolkit to the ChessLisp code via the cognitive search class interface. I've decided to handle all time values as signed 64 bit integers interpreted as microsecond counts, and calendar values are expressed as elapsed microseconds from the beginning of the Thompson Epoch (1970.01.01 00:00:00 UTC). As ChessLisp uses a 64 bit representation for a numeric value, there's no extra penalty for the time representation and using signed values simplifies various comparison operations. Supporting the microsecond representation are two new ChessLisp intrinsic functions: usec_clock and usec_usage. The first gets the current wall clock time (in UTC) and the second returns the accumulated CPU usage. As Symbolic is to be a competitive program, it uses the wall clock times for setting response time limits. The usec_usage calls are needed to help calculate overall CPU utilization by dividing the CPU usage by the elapsed time; this value is reported in the narration. Interestingly, OpenBSD running on a PPC claims microsecond accuracy on wall clock times but only centisecond accuracy on CPU usage times. This is undoubtedly related to the 100 Hz timeslicing. At selection initialization time, Symbolic takes the microsecond count of the NominalUsec property of its input parameter symbol and the current wall clock and calculates three different clock values. These are the sums of the current clock and limits for fast select (0.5 * NominalUsec), nominal select (1.0 * NominalUsec), and hard select (8.0 * NominalUsec). Each of the three limits gets a set of ChessLisp functions that are used for testing the current elapsed time and help to determine when a search should be either continued or terminated. The fast and nominal limits are checked in the top level CandidateSelector KS that manages the root effort parameter generation. Combined with a certainty metric and records of usage for previous effort values, CandidateSelector performs some magic and decides on whether to end the selection process or to continue it with a higher effort. The hard limit is checked by the KS Manager and it will end the search gracefully if and when the hard limit is exceeded. I haven't put the standard catch/throw exception handling code in ChessLisp as it adds more complexity than what it's worth in increased functionality. The only drawback here is that following each call to the KS Manager (invoking a KS), Symbolic's Lisp code must have a check for search abort that leads to a prompt exit from the calling KS. This isn't too bad and personally I think it leads to clearer code. The operation of the CandidateSelector KS includes reporting of the predicted variation that may change after each result caused by propagation of a new (higher) root effort value. The PV is recovered by scanning the search tree starting at the root node and reporting the movepath for each node in the chain that has a non-nil IsEV property. (Symbolic internals: EV = Expected Variation; PV = Position Value.) The PV is not reported if the CandidateSelector KS has determined that the search was killed via the KS Manager due to a hard limit overflow. An outline of KsCandidateSelector: begin Effort := 1; KsContingencySelector(RootNode, (Effort - 1)); ReportPV(); Timeout := TimeCheck(); while (not HardAbort) and (not Timeout) begin KsSelector(RootNode, (Effort - 1)); if (not HardAbort) begin ReportPV(); Effort := Effort + 1; Timeout := TimeCheck(); end; end; end; Some adjustment of the time management code will likely be needed as directed by future testing. One minor issue here is the per move overhead of creating a new cognitive search object that in turn creates a ChessLisp object that in turn loads Symbolic's ChessLisp source. This takes about a second on a modest computer but will increase as more Symbolic's source grows. Also, the optional generation of the natural language narrative takes time, and the wall clock budget will have to be adjusted for this in those games where a narration is desired. -------- Next on the agenda is developing the KS Manager and formalizing the input and result parameter semantics for the various KSes.
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.