Author: Steven Edwards
Date: 15:30:32 02/24/05
Symbolic: Status report 2005.02.24 As referenced in the last status report, the ChessLisp primitive KingFlightBB (returns a bitboard value of flight squares for a given position value and king color value) has been implemented. Currently, this is being held in reserve for the upcoming cognitive mate attack processing. I may add flight BB primitives for other piece types to better support trapped piece detection. Symbolic's underlying chess toolkit had its time control allocation tweaked slightly to better handle time controls with increments. Testing against Gnuchess 5 shows a slight improvement and so the toolkit, by itself, scores about 40% against Gnuchess on equal hardware. This is not a particularly outstanding level of performance, but I believe it will be sufficient for the overall purposes of the project. Inside the ChessLisp interpreter, I've added support for connecting Lisp to the traditional A/B search provided by the toolkit. This is seen from Lisp as the TABS primitive that takes a position value, an iteration limit (zero indicates a basic quiescence search), a position hash history list, and a list of moves suggesting a predicted variation. Passed invisibly are a main and a pawn transposition table; the return value is a list containing a predicted variation and an expectation. What is the purpose of the ChessLisp TABS primitive function? After all, isn't it cheating to say that the program uses an intelligent search when it is really calling an old fashioned A/B search? Well, yes and no. The rationale behind the TABS function is to provide a plastering compound to patch holes in the knowledge base of the cognitive search. And with no doubt at all, the holes in the initial cognitive search are large indeed. But they will not stay that way, and as the holes are filled by real Lisp code with explicit planning and reasoning, the usage of the TABS call will decrease monotonically and will eventually disappear entirely. I've been spending most of my available time thinking about plan and goal representation and access. Symbolic, much like Wilkins' Paradise program, represents plans as a directed acyclic graph (a tree). Each node in the plan graph represents a search point which in turn represents a position or set of positions. Each plan graph arc represents a goal; this goal may be as simple as a single specific chess move, or it may be a complex higher order concept like "MateAttack". Symbolic's plans have the requirements of creation, transversal, growth, and (importantly) editing. Alas, there is no simple way in Lisp to do all of this with a simple Lisp-style nested list. The current Lisp code for plan representation is a plan graph root vector that contains, among other items a plan graph node vector (search points) and a plan graph arc vector (goals). Plan node and arc entries contain indexing information that in turn describe the topography of the entire graph. Housekeeping functionality including dynamic allocation and threading are handled by a collection of explicit, encapsulating Lisp functions. A plan graph dump function was written to help convince me that the plan graph subsystem works as advertised. A future plan graph dump function will output in natural language and the fervent hope is that this ability will greatly aid in development. Attention in Symbolic's planning tasks now turns to goal representation. My idea at this point is to represent each goal instance as a symbol (created via the Lisp gensym primitive) adorned with an extensive property list. Exactly what property types will be present is a question I've only started to ponder, put they must include descriptions of specifics of what a particular goal means to accomplish (also, what is to be prevented) along with entry/exit conditions and metrics of how well the goal is being handled within the actual search. This approach is essentially similar to that taken by the Paradise program; the main exception is that plans in Symbolic are intended to be symmetric with respect to attack and defense. In Paradise, the plans were always made with the first mover being the attacker and the second mover playing defense at each plan choice point. Goals in Symbolic's planner need to be generated as part of a static analysis much as is done by a production system in Paradise. Exactly how this will be accomplished is not very clear to me at the present, but it will surely entail some sort of pattern recognition. And above the goal formation level is the task of connecting goals into a plan graph. Once a plan graph generator is in place, there is the requirement of exploring plans. A plan exploration uses a plan graph to generate and move through a search tree of actual chess positions (nodes) connected by chess moves (arcs). The underlying ChessLisp primitives are already in place for this, but the actual explorer code is only in the rough conceptual stage. The guessing at this point is that a plan graph will contain from ten to a hundred arcs/goals and the resulting exploration chess position tree will have from a hundred to a thousand nodes. These speculations are within an order of magnitude of those in Paradise and I believe that they are within the count range of plans and search trees used by strong human players. Procedural control in Symbolic's Lisp source is via activation of high level knowledge sources, each a ChessLisp function taking parameters divided into common and source specific interpretations. Generally, these knowledge sources are mutually recursive and all have an effort parameter that suggests how hard the KS should work to solve a subproblem. Most KS routines return an analysis (a predicted variation and a score); some return other structures. This is an important difference between Symbolic and Paradise; in the latter a KS is a predefined subset of the two hundred or so pattern recognizers in Paradise's production subsystem. In Symbolic, there is a KS Selector (picks a move), a KS Surveyor (nested feature recognition and pattern instance formation), a KS Planner (makes a plan graph from the surveyor output), a KS Scout (called from the planner to verify guesses via quick position searches suggested by earlier instance output), and a KS Explorer that iteratively performs a best first search of the plan graph that includes the growing of a chess position tree. As with Paradise, Symbolic will (usually) generate a plan graph at the root chess position and also at various other chess positions where an earlier plan is exhausted by the exploration. All of the above framework is in place, but the details are yet uncoded. Yes, there is much to be done. I had once hoped to get nearly everything working by the end of 2004, but with problems due to medical disability, the revised date of late 2005 has come into serious doubt. I'm fortunate to average an hour or two each week overall, and so Symbolic is likely the slowest developed chessplaying program ever even though large chunks of its toolkit were stolen from my earlier program Spector. Also, I admit that it's certainly possible that some other researcher, starting a cognitive program effort from scratch, could beat me to the goal. But what else can I do? I've been bitten by the chess programming bug as much as any other researcher in the area; however, working on a traditional A/B searcher is too boring to me to endure. Additionally, I haven't the budget for expensive hardware needed to compete in the "speed is everything" arena of traditional programs; my main workhorse is a 700 MHz PowerPC single CPU notebook with a fraction of the raw capability available when compared with more modern systems. So, an alternative approach is indicated; thus, a cognitive searcher with modest hardware needs. Some recent toolkit games: [Event "Xboard game"] [Site "jenn.local"] [Date "2005.02.24"] [Round "1"] [White "Symbolic v2005.02.24"] [Black "GNU Chess 5.07"] [Result "1-0"] [Termination "Black is checkmated"] [TimeControl "G/1800+30"] [UTC "2005.02.24 11:46:14"] 1. d4 d5 2. c4 e6 3. Nc3 Nf6 4. Nf3 c6 5. Bg5 dxc4 6. e4 b5 7. e5 h6 8. Bh4 g5 9. Nxg5 hxg5 10. Bxg5 Be7 11. exf6 Bxf6 12. Bxf6 Qxf6 13. a4 Rh4 14. g4 b4 15. Ne4 Qf4 16. Bg2 f5 17. gxf5 exf5 18. Ng3 Kf7 19. d5 c3 20. dxc6 cxb2 21. Qb3+ Be6 22. Qxb2 Na6 23. O-O Nc5 24. Rfd1 Nb3 25. Rab1 Nd4 26. Rd3 Rc8 27. Rc1 Kg6 28. Rcd1 Nb3 29. Rd6 Nc5 30. R1d4 Qg5 31. Rxh4 Qxh4 32. Qc2 Qf6 33. Qxc5 Rd8 34. Qxb4 Qa1+ 35. Nf1 Qf6 36. Rxd8 Qxd8 37. Qb7 Kf6 38. Qxa7 Qd6 39. c7 Qd7 40. Ne3 f4 41. Nd5+ Ke5 42. Qb8 Qc8 43. Ne7 f3 44. Nxc8 fxg2 45. Nb6 Ke4 46. Qe8 Kf5 47. Nd5 Bc8 48. h4 Kg4 49. Qe4+ Kh3 50. Qf4 Be6 51. Qg3# 1-0 [Event "Xboard game"] [Site "jenn.local"] [Date "2005.02.24"] [Round "1"] [White "Symbolic v2005.02.24"] [Black "Crafty-19.13"] [Result "0-1"] [Termination "White resigns"] [TimeControl "G/1800+30"] [UTC "2005.02.24 18:31:55"] 1. d4 d5 2. Nf3 Nf6 3. c4 e6 4. Nc3 c6 5. e3 Nbd7 6. Bd3 dxc4 7. Bxc4 b5 8. Bd3 a6 9. e4 c5 10. e5 cxd4 11. Nxb5 Nxe5 12. Nxe5 axb5 13. Bxb5+ Bd7 14. Nxd7 Qa5+ 15. Bd2 Qxb5 16. Nxf8 Qxb2 17. Nxe6 fxe6 18. O-O O-O 19. Bf4 Rfd8 20. Be5 Rxa2 21. Rxa2 Qxa2 22. Bxf6 gxf6 23. Qg4+ Kf7 24. Qe4 f5 25. Qh4 Qa5 26. Qxh7+ Kf6 27. Qh6+ Ke5 28. Qg7+ Ke4 29. Rd1 Qc5 30. Qg3 Kd5 31. Re1 Qc4 32. Qe5+ Kc6 33. Qxe6+ Qxe6 34. Rxe6+ Kd5 35. Re1 d3 36. Kf1 Kc4 37. Ra1 Re8 38. Ra2 Kb3 39. Ra7 d2 40. Rb7+ Kc3 41. Rc7+ Kb4 42. Rb7+ Kc5 43. Rb1 Kd4 44. h4 f4 45. Ra1 Kd3 46. Ra3+ Kc2 47. Ra2+ Kc3 48. Ra1 Ra8 49. Rd1 Kc2 50. Rxd2+ Kxd2 51. g4 f3 0-1
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.