Author: Steven Edwards
Date: 16:06:00 04/10/05
Symbolic: Status report 2005.04.10 Inside the toolkit, I completed the work with implementing fractional ply extensions. The quantum is 1/16 of a ply and can be easily adjusted to any negative integral power of two. One of the extension heuristics is to extend a little extra in a reply to check when there are only two replies available. Another is to extend on passed pawn motion proportionally to the advancement of the pawn. Testing of the above was going smoothly until running the MES suite. Here is position MES.0890: [D] 4k3/n1P1p2R/p3p2P/4P1bN/4K1p1/8/1p6/8 w - - 0 1 The best move is 1. Rh8+ and the toolkit finds that quite rapidly. But somewhere in the eighth iteration, the program crashed with a bus error. After too many hours of debugging I figured out that the extension limiting was not always working too well and the search thread's stack smashed into its heap at a point some 400 ply deep. (Because the toolkit search doesn't have a ply limit as it has no ply indexed tables, there is no ply overflow check.) The crash was not immediately caused by an obvious allocation error; instead, it had an access fault when the overloaded RSA (PowerPC Register Save Area on the stack) was written to by the standard routine entry register content save protocol. After I fixed the extension limit problem, the bus error disappeared. This new version of the toolkit is now operating on ICC for the amusement of all. Fooling around with the various extensions could take months with ever diminishing returns. I don't have the patience or time for this, so it's not going to happen. Also, it is not directly related to the success of the cognitive search, so I'm going to suspend all future toolkit extension work. -------- I'm making the occasional effort to work on my geocities web site: http://www.geocities.com/chessnotation I wanted to upload the test suites, but their file manager prohibits a file name with an "epd" extension. (The "pgn" and "fen" extensions are also not supported.) I made a request for them to fix this, but I'm not holding my breath. -------- I've come to a near final decision on plan representation, generation, and exploration. This has been a tricky task as there are numerous interdependencies among the plan representation and the structure of the knowledge sequencers that access plans and the position search tree. A plan in Symbolic is a directed acyclic graph (a tree), something like a position search tree. A big difference is that the branches in a plan are goals instead of moves. All but one of the goals is a name for some concept like "MateAttack" and each of these can be elaborated (via productions) into sequences of other goals. Eventually, the elaboration task tries to map a general concept goal into the only terminal goal: "PlayMove". When a PlayMove goal is executed, it causes a move (given in the attribute list associated with the partcular instance of the PlayMove pattern) to be played and the plan explorer moves to a new node in the position search tree. Goals defined so far: PlayMove: the only terminal goal; causes a move to be played in the search. BestMove: the top level goal that is posted once at the start of a cognitive search. BestMoveAlt: a goal used as a syntactic placeholder during BestMove elaboration. MateAttack: one of a number of secondary high level goals that may be produced from elaborating a BestMove goal; also, from following up from an earlier MateAttack plan. In turn, it can be elaborated into one of more subplans, each starting with a suggested mating attack move (via PlayMove) that itself is followed by some defensive goal. TabsMove: a goal that is rewritten into a PlayMove goal at the time of exploration; it is present only as a patch until more of the cognitive search chess knowledge is added. SpecMove: A move specification that can match zero or more actual moves that are available at the time of elaboration. It is used (mostly) to indicate which subplan should be explored in response to a move by the opponent. SpecMoveAlt: a goal used as a syntactic placeholder during SpecMove elaboration. Continue: a goal used as a syntactic placeholder at the end of an incomplete plan during plan generation; it tells the productions that a plan may still need more work before it can be explored. -------- Some pseudo code for KsSelector, the knowledge sequencer invoked to return an analysis (PV, score, etc.): 1. Invoke KSQuickSelector to come up with an obvious move with a termnal analysis; this will in turn call a number of other sequencers to help. Most of the time it won't return with a usable move. If it should work, then KsSelector returns immediately with the KSQuickSelector analysis. 2. If KSQuickSelector doesn't help, then KsSurveyor is called to comment upon the current position. It makes its comments by posting Theme pattern instances in the current IDB (Instance Data Base). 3. KsPlanner is then called. It posts the initial plan using instances of the PlanPoint, PlanBranch, and Goal patterns. (PlanPoint and PlanBranch instances are used to describe the topography of a plan.) The only goal at first is a BestMove goal. After this initialization, high level planning productions examine the Theme instances posted earlier and attempt to elaborate the BestMove/BestMoveAlt goals into secondary thematic goals. Further planning productions are tried and eventually a plan, likely including nested subplans, is formed. 4. The KsExpPlan sequencer is called with the current IDB and its plan's root PlanPoint instance as actual parameters. It returns an analysis from exploring the plan. -------- Some pseudo code for KsExpPlan, the knowledge sequencer invoked to return an analysis from exploring a point in a plan: 1. If the input plan point is the end of a plan, then KsExpPlan calls KsExpPlanTerm and returns its analysis. 2. Otherwise, KsExpPlan generates a list of all current immediate goals at the current plan point. 3. The first/best goal is removed from the current immediate goal list. If none exist, then control transfers to step 6. 4. If the goal is not PlayMove (hence, non-terminal) then the elaboration productions are called to re-write the goal and the results (if any) are reloaded onto the current immediate goal list. Control transfers to step 3. 5. The PlayMove goal is executed by KsPlayMove which returns an analysis. This analysis is A/B minimaxed with earlier KsPlayMove results. Control transfers to step 3. 6. The best KsPlayMove analysis is returned. -------- Some pseudo code for KsPlayMove, the knowledge sequencer invoked to return an analysis from playing a move in a plan: 1. If the given move is illegal, an empty analysis is immediately returned; otherwise the move is played. 2. If the resulting position can be quickly and certainly evaluated (e.g., checkmate, threefold repetition) then that analysis is returned. 3. Otherwise, a local pointer into the current plan is advanced to the end of the PlayMove branch, and KsPlayMove calls KsExpPlan to complete the exploration; its resulting analysis is returned. -------- Some pseudo code for KsExpPlanTerm, the knowledge sequencer invoked to return an analysis at the terminal point in a plan: 1. KsExpPlanTerm first decides on whether or not the current position and search state require more planning. 2. If more planning is needed, then KsSelector is called to do the work; its analysis is returned. 3. If more planning can be avoided, then a quiescence analysis is returned. -------- More to come.
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.