Author: Steven Edwards
Date: 11:19:32 02/13/04
A brief comparison of the two knowledge based chess programs implemented in Lisp: Paradise and Symbolic: Author (Paradise) David Wilkins of Sunny California. Author (Symbolic) S. J. Edwards of Frozen New England. Date (Paradise) operational in 1979. Date (Symbolic) begun in 2003, planned completion in late 2004. Implementation language (Paradise) MacLisp from MIT Implementation language (Symbolic) ANSI C++ for the underlying chess toolkit package, ASNI C++ for the ChessLisp (by Edwards) interpreter, and ChessLisp for the knowledge based chess program itself. ChessLisp is a comprehensive subset of Common Lisp with the addition of chess specific support. Implementation hardware (Paradise) Digital pdp10 (36 bits, Multics OS) Implementation hardware (Symbolic) Any 32 or 64 bit platform supporting ANSI C++ and POSIX; currently using a mixture of Apple Macintoshes (OS X/OpenBSD), a 400 MHz AMD K6 (Linux), and a dual 1.13 GHz Intel P3 (Linux). Data structure primitives (Paradise) Lisp atoms and lists. Data structure primitives (Symbolic) Lisp atoms and lists. ChessLisp has more than a hundred primitive chess specific operations that access chess specific structure types for atoms; these types include moves, boards, bitboards, bitboard databases, positions, trees, and nodes. About a dozen chess specific enumeration types (including squares, pieces, and directions) also have built in support. Data structure operations (Paradise) MacLisp operations. Data structure operations (Symbolic) ChessLisp operations. Computationally expensive operations on chess structures are performed by the chess toolkit routines as activated by the ChessLisp implementation of chess specific operations like Generate, Execute, Retract, and ExpandNode. Property list usage (Paradise) The usual Lisp property list usage. Property list usage (Symbolic) The usual Lisp property list usage. Various chess specific structure types have extensive property lists initialized by access to the underlying toolkit. Domain (Paradise) Any chess position with emphasis on complex tactical middlegame positions. Domain (Symbolic) Any chess position; support included for an opening book and for tablebases. Search rate (Paradise) Highly variable, approximate mean of 20 seconds per node. Search rate (Symbolic) Too early to tell. Simple movepath enumeration run from ChessLisp is about 100,000 nodes per second on a 1 GHz PowerPC Macintosh. Knowledge based search will be much, much slower; the target rate is 20 (yes, only 20) nodes per second. Search paradigms (Paradise) Extensive pattern matching produces a pattern instance database; specialized knowledge sources contribute to pattern matiching; a plan generator produces tactical plans in a Plan Language; plans are tested via search. A specialized causality facility and quiescence search are also used. Search paradigms (Symbolic) As with Paradise, Symbolic will have extensive use of pattern matching and planning operations; the intent is to have the underlying C++ chess toolkit to provide relatively high speed pattern matching and possibly plan formation. Symbolic also has the capability to retain the entire annotated search tree available throughout an entire search and so be able to revisit nodes as needed. A similarity facility, something like a causality facility, will be used. The toolkit will support a few fast but very specific mini-searches like mate-in-3 and simple pawn races. Learning (Paradise) None. Learning (Symbolic) One idea is to deploy an incrementally improved plan library facility. This will be entirely implemented in Lisp and consist of recognizer/template entries that have proven merit. A possible library entry generation mode is to take a position of interest, generate the entire full width search tree to sufficient depth, identify the nodes that contribute to top level move selection, construct patterns that distinguish those nodes from others, and finally build a recognizer and associated plan template from those patterns. EPD test suites can automate this process. Status (Paradise) Completed; last paper presented in 1981. Status (Symbolic) 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.