Author: Roger D Davis
Date: 16:54:14 04/10/05
Go up one level in this thread
On April 10, 2005 at 19:06:00, Steven Edwards wrote: >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. I love this, because you're kind of thinking outloud as you're keeping us informed of your progress, and it looks like really futuristic stuff. A question...I assume the toolkit itself can play a complete game, yes? If so, then the toolkit's performance becomes an important reference point for the success of the project. Let's say that the toolkit obtains an average rating of 2350 at some time control. Let's say that the whole project obtains an average rating of 2450. That means that the LISP code, architecture, etc., is yielding about 100 rating points over what the toolkit alone could achieve. What I'm saying is that the value of the LISP code, architecture, etc., can be judged by how much better the total project plays relative to the toolkit alone, right? Roger
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.