Symbolic: Status Report 2007.05.11

[sje]

Symbolic: Status Report 2007.05.11

Work has continued on Symbolic's Lisp based checkmate search. There has been significant progress on making threat and refute selection more efficient, although an early attempt at this caused most threats and refutes to be tried twice instead of just once. There has been some difficulty with debugging as most problems tend to appear only on longer and more complicated positions.

One rather annoying bug has been identified and fixed. On some long running analyses, the Lisp interpreter thread would hang up in a strange idle state. A clue to finding the cause came when it was noticed that the fault would occur on the same input position on different machines after a different number of nodes and different CPU time consumptions, but at roughly the same wall clock elapsed search time. It turned out that the C++ timer events passed to the Lisp interpreter thread and then to the mate search could not be safely postponed as was previously thought. After about thirty thousand of these piled up at a 10 Hz rate, the pipe / pthread / mutex share mechanism said "Enough is enough!" and froze everything. With these timer events now correctly processed by the search, the program nows runs for hours at a time with no failures.

It appears that the recent addition of force status propagation is working. The idea here is that a node is a forced lose if the active mover is checkmated or if the node is fully expanded and all immediate subnodes are forced mates. Likewise, a node is a forced mate if at least one immediate subnode is a forced lose. Forced draw status is also handled correctly. The mate search now ends on one of three conditions: 1) A forced result of any kind at the root is detected; 2) The threat generation try count is exceeded; 3) No further mate threats can be found.

Related to the force status improvements, the mate search now also knows about second repetition and transposition status.

To decrease the chance of C++ stack overflow in the interpreter's recursive descent evaluator, the toolkit's thread creator routine now hands out a two megabyte stack allocation, twice the original level of generosity. I might double this again before the cognitive search goes online.

I had hoped to get the cognitive searcher running on FICS, but more testing is needed and I've only had a few hours in the past week or so to work on things.

--------

Mate threat generation raises several interesting issues. The two basic topics here are the severity of a threat and the likelihood of a threat. The first issue is an estimate of how damaging a variation is to the defender and is roughly a guess about how soon a checkmate might arrive after the threat move. The second issue deals the probability that a threat variation will have some bearing on move selection, and this is trickier than measuring severity as it strongly depends on what the defender may chose as intermediate moves.

Consider the probability P(node_N), the chance that the given node N will appear in the predicted variation. It is the product of the probabilities of each of the moves leading to the node. From the view of the search, the first mover (Symbolic) can assign certain probabilities of zero or one to any of its moves, but the second mover's probabilities can only be affected indirectly. There is a cyclic process where successive additions to the search tree change earlier likelihood estimates and so threat generation has to take global information into account. My idea here is that there's a concept of a "best permissible threat" where the defender will actively work against moving into subtrees where the opportunities are too good for the attacker. Selection of the next best permissible threat is (at this time in the development) based on a second global minimax. This is a minimax of the threat space, somewhat similar to a standard minimax of the position evaluation space.

The threat search space is not the same as the search tree, but is rather the set of all current potential moves from first mover nodes that are not fully expanded. Merely looking at threat severity is insufficient as it doesn't really consider the defenders evasion potential on intermediate moves in a potential threat variation. So, at each first mover node there needs to be a best permissible threat for the node and its subtree (each second mover node has an inverse "most tolerable threat"), and the metrics of these are minimaxed accordingly. Considering the potential of many, many possible threats, there needs to be an incremental update method for generating and maintaining these metrics. And that's what I'm working on at the present.

[Dann Corbit]

Is your estimate on the current threat based on probability (e.g. Bayesian model of some kind) or is it purely heuristic?

[sje]

At the moment, there's no need to assign explicit probability estimates other than the zero and one special cases; only relative rank is important. This will change.

[sje]

The incremental update for the global threat minimax is proving harder to do than I had anticipated. But it's worth the effort as it promises a big speed up.

There is no need for a similar mechanism for the defend/refute side of things; a refutation generation is always made by considering only second mover nodes starting at the threat node and working back to the root as needed. The situation is a subset of the conditions faced by the defense in Paradise: it's known in advance that there are no winning attacks for the defensive side, so there's no need to look for any. Obviously, there needs to be a lot of work before a more general player can be implemented.

--------

My idea of posting an automatically generated web page after every search may need some modification. Tests with my current ISP and web host show that the uplink just isn't fast enough for real time posting of the search narrative or the tree/node dump. Having a fiber link would likely solve the problem, but I checked and the only provider isn't doing installations in my local area.