Symbolic Status Report: 2007.04.07

[sje]

Symbolic Status Report: 2007.04.07

A nasty bug in the C++ code was found and fixed. The problem was related to a design error where there was a undetected case of order dependency of class constructor invocation for statically allocated objects. These are C++ routines that are called automatically by linker generated code prior to the call to the program's main routine. Unfortunately, there is no standard way of ordering these calls, so it's easy for a dependency to exist for a long time before a bug is triggered.

The fix in the above case came from removing the constructor code and placing it into an explicit initialization routine.

Sad to say, this was the second time this kind of problem occurred. My memory slips badly from time to time.

--------

Most of my limited development time has been spent on the Lisp based cognitive search as was planned. The work has been centered on the topic of score and predicted variation propagation in the whole tree retention search.

The fundamental idea with the cognitive search is to mimic human chess search, and this means keeping the entire search tree in memory instead of just a single variation at a time. A position value at a leaf node is determined via a static evaluation and an exchange analysis, while all other nodes are assigned values via standard negamax. As all nodes are given values immediately upon being attached to the tree, a new value assignment needs to be propagated upwards and this can change the values of some to all ancestor nodes. The idea is to do as little work as possible while getting all the numbers right.

A related task is to maintain a predicted variation at all nodes, and this depends on value maintenance. Again, the idea is to do the least processing.

Much testing was done on the value/PV work and I think I've got it right. There are some counter intuitive results: the root PV can oscillate between two unchanging PVs due to introducing new nodes in the tree. It took me a while to understand why this happens and I verified the phenomenon by writing a tree verification routine that does a whole tree check of all the negamax values and PVs. The program also includes an HTML output generator for dumping tree/node information, so I was able to make a visual overview of the detailed results.

Generated trees had node counts from about 400 to about 10,000. Average node processing time is less than 3 ms, so I've still got plenty of margin given the goal of 200 ms per node. Incidentally, when playing without an opening book the cognitive search thinks the three ply PV for the opening position is 1. e3 d5 2. Nc3.

A trickier topic is that of A/B window maintenance. Unlike traditional single leg A/B searchers, both bounds of a node's A/B window can change in either direction. While it's easy to generate a window update, it's harder to maintain all the node's windows efficiently, i.e., with minimal updates. I'm still working on this.

--------

There was one bug located in the ChessLisp interpreter. The intrinsic predicate "equal?" failed on some list pairs due to excessive cleverness when coding the equality testing routine.

--------

More to come.

[NKOTB]

Symbolic Status Report: 2007.04.--------

There was one bug located in the ChessLisp interpreter. The intrinsic predicate "equal?" failed on some list pairs due to excessive cleverness when coding the equality testing routine.

--------

More to come.

Hi Steven, The above is so true for so many programs. I have never seen it phrased that way, Excessive cleverness when coding.... Brilliant diction. Looking foward to Symbolic growing. Best of health.

[jswaff]

The fundamental idea with the cognitive search is to mimic human chess search, and this means keeping the entire search tree in memory instead of just a single variation at a time. A position value at a leaf node is determined via a static evaluation and an exchange analysis, while all other nodes are assigned values via standard negamax. As all nodes are given values immediately upon being attached to the tree, a new value assignment needs to be propagated upwards and this can change the values of some to all ancestor nodes. The idea is to do as little work as possible while getting all the numbers right.

Are you searching breadth first? It sounds like you're doing a tree search (of some kind), except, unlike a DFS your memory requirements will grow with the size of the tree. What is the benefit of keeping the entire search tree in memory?

--
James

[sje]

First, there's only a rudimentary search in place for testing purposes.

Eventually the search will expand that portion of the tree that will most likely to confirm or deny that the first move of the current predicted variation is the best move in the position.

The whole tree is kept in memory as that's the way humans search. Ideally, most searches will have well under a thousand nodes, so there's plenty of space. Also, the calculations at each node are rather elaborate, so there's no sense with doing them more than once. Finally, having the whole tree stored better enables the search to pick the order in which regions are explored.