Author: Steven Edwards
Date: 09:50:46 01/23/04
Go up one level in this thread
On January 22, 2004 at 18:06:17, Tord Romstad wrote: >On January 22, 2004 at 13:05:57, Steven Edwards wrote: >>On January 22, 2004 at 11:52:47, Tord Romstad wrote: >>>On January 22, 2004 at 10:03:55, Steven Edwards wrote: >>> >>>>Here's some example code for the ChessLisp intepreter in my program Symbolic: >>>> >>>>;;;; emp.lsp: Enumerate movepaths >>>> >>>>(defun emp (theFEN theDepth) >>>> "Enumerate distinct movepaths from a FEN string to a depth" >>>> (cond >>>> ((not (string? theFEN)) >>>> "Error: first argument must be a FEN string") >>>> ((not (and (integer? theDepth) (nonnegative? theDepth))) >>>> "Error: second argument must be a nonnegative integer") >>>> (t >>>> (let ((thePos (PosFromFEN theFEN))) >>>> (if (null? thePos) >>>> "Error: invalid position" >>>> (emp-aux thePos theDepth)))))) >>>> >>>>(defun emp-aux (thePos theDepth) >>>> "Enumerate distinct movepaths from a position to a depth" >>>> (cond >>>> ((= theDepth 0) 1) >>>> ((= theDepth 1) (length (Generate thePos))) >>>> (t >>>> (let ((theSum 0) (theEnv nil) (theMove nil) (theML (Generate thePos))) >>>> (dolist (theMove theML) >>>> (Execute theMove thePos theEnv) >>>> (incf theSum (emp-aux thePos (1- theDepth))) >>>> (Retract theMove thePos theEnv)) >>>> theSum)))) >>> >>>From the code above, it looks like you generate moves into a list rather >>>than an array. Isn't this terribly slow? And another question: What >>>is the purpose of the (theMove nil) in the LET bindings of the EMP-AUX >>>function? Is this necessary because of some quirk in your Lisp dialect? >> >>1. Generating moves into a list is done by the C++ routines and is quite fast. >>Also, a list representation of moves enables writing a tail recursive verion of >>the abve routine if needed. I can always write a GenerateArray intrinsic if the >>need arises. >> >>I have not made any attempts to optimize the interpreter speed except for >>consing and garbage collecting (these it does quite quickly). Creating a new >>lexical closure at the present requires a call to the C++ new() routine, so this >>will be a target for optimization aftter I do more work on implementing the >>remainder of the function intrinsics. > >Using dynamic memory for any of the central data structures in a chess program >seems inefficient and unnecessary to me, but I guess you have good reasons to >do so. It's not so bad if the dynamic memory is allocated only once and then recycled in place. Indeed, it is faster this way if the allocated objects are more than twice as large as the pointers used to track the storage. Example: the size of an instance of the CTMoveNode class is 40 bytes, and each one comes into existence via a call to an overriden new() that calls malloc(). But once the storage is created, it is recycled from that point until the owning thread terminates and then it is freed. So, the frequency of calls to new() is high when a thread starts, but drops exponentially as time passes. Also, consider the difference between a program that needs a million nodes per search vs one that searches less than a thousand in the same time. The latter can easily take some extra time with the mechanical task of moving pieces on the board and it won't make a measurable difference in the result timing. My prediction is that Symbolic will be spending most of its time doing: 1. Consing/garbage collection (true of just about every Lisp interpreter), 2. Constucting lexical closures, 3. Internal runtime error checking (argument counts, object type checking), 4. Property list access, 5. Actual low level chess tasks (generation, execution, retraction, etc.) that are processed by the C++ code. >>2. Adding the binding for theMove (and also theEnv) in the let variable list is >>a stylism of mine and not strictly necessary. > >But unless your Lisp dialect is very different from Common Lisp, the "theMove" >inside your DOLIST loop is not the same as the "theMove" in the LET form around >it. In your code, you just initialize a lexical variable named "theMove", and >never >use that variable for anything. You are correct, it was a typo. Another typo was the use of "nonnegative?"; it should be "nonminus?".
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.