Working notes: A similarity facility

[sje]

Working notes: A similarity facility

[Note: this is not something for those who value a high nodes/second metric above all else.]

A causality facility, implemented only by a very few chess playing programs, uses information backed up from a sub search to intelligently prune alternative moves at the sub search parent node. For example, if a move M1 at node N results in an unanswered threat T, then the causality facility can analyze moves M2, M3, etc., comparing them to move M1 to see if the sub search analysis supports pruning any or all sibling moves if they can't handle the threat T either.

Hard to say, and much harder to do. But there is a way of implementing a much less complicated technique that can still help minimize redundant searching. I've been working on this in the ChessLisp domain and am now moving some of the ideas into Symbolic's traditional A/B searcher. I call the technique a "similarity facility".

So far, it looks like this:

First, there is an C++ class (CTHunter) that corresponds to the ChessLisp Tracker object. This is a fairly simple class; its main job is to keep track of the chess men by a serial number instead of by location. An instance of the CTHunter class is initialized with the position at the start of a search and serial numbers from zero up to thirty-one are assigned to the pieces by scanning the occupied squares bitboard. (The order really isn't important as long as it's consistent.) The class supports a high speed bidirectional look-up that will map squares to chess man serial numbers (a.k.a., target IDs) and vice versa. The class also has update methods for move execute/retract along with an internal stack of target IDs of captured pieces. The Big Idea here is that the exact location of a man is not always as important as the man's tactical relationships with other men.

Second, there is a new C++ class "Target Bitmap" (CTTargetBM) that describes target IDs for a given target in much the same way a bitboard describes some square property for a given square. So a target bitmap is soft of like a 32 bit version of a bitboard (max 32 pieces; can't be used for illegal positions with more than 32 men on the board). As with bitboards, target bitmaps also avail themselves of fast parallel boolean operations and these operations can share bitboard look up tables.

Third, there is a new C++ class "Target bitmap database" (CTTargetBMDB) that includes a pair of 32 target bitmap arrays for a position. These arrays are an analogue to the AttackFrom[64] and AttackTo[64] arrays in a regular bitboard database. Actually, like the regular bitboard arrays, one array is just the transpose of the other. An instance of a target bitmap database can be built quite rapidly from a CTHunter object and the attack arrays of a bitboard database.

(The above have all been coded and tested.)

Fourth, the search is modified to have a Hunter and Target database object pair that tracks the position of the current search node. (Yes, this will slow things down a bit. And it gets worse.)

Fifth, at any given node, the (formerly) full width search takes the current position along with all the legal moves and constructs a separate Hunter and Target database instance for each position resulting from a move. With the use of parallel boolean operations, the search can figure out a rough estimate of two things: 1) how each new position differs tactically from the common parent, and 2) how similar (or not) the sibling positions are among themselves.

Sixth, the search can use the similarity data to extract hints as to:

1) which moves are worth searching to what depths,
2) a rough order in which to search the moves,
3) [most importantly] which moves to skip because they are similar to previously searched moves.

[Aleks Peshkov]

Interesting topic because it is rather different from most current threads on low-level technics.

Tactical similarity to reduce subtrees was known to be implemented by Kaissa's team in 1970-ties. Kaissa's team reported that node savings in reducing research similar tactical lines was relatively even to time overhead, but Kaissa engine did not use transposition tables.

Piece set oriented board representation is not new, it is only out of current main stream fashion. I am not sure that piece-sets are better then bitboards to detect position similarity. For example knights and rooks transpositions are frequent in chess. IMHO tactically important squares are more permanent positional features then piece-piece relations. Often piece trades around one square do not change the threat to occupy some important square. I personally trying to generalize killer moves heuristic to killer squares heuristic in the goal of improving move ordering.

[Gerd Isenberg]

Your idea seems a generalization or an abstraction of the Botvinnik-Markov extensions, considering "same" threats after consecutive null-moves.

Assume an knight exclusively defends an important square. Otherwise the opponent knight may fork my king and queen (or rook) - a "family" check. Thus almost each move with the defending knight would allow the fork and should be abandoned and pruned (except checks or other kind of counter attacks). Otherwise there may moves to over-protect that important square or to nullify the fork-threat by moving the king or queen.

How do your CTHunter, CTTargetBM and CTTargetBMDB objects interact with such a pattern - to recognize, to keep this important square defended? Or for the opponent, to deflect or attack the one and only defender?

Thanks,
Gerd

[sje]

As mentioned above, the work is still in an early stage. A target bitmap is only concerned about some boolean property of a set of targets like a bitboard is concerned with some boolean property of all the squares.

So if a target bitmap is concerned with a square, then it necessarily represents the set of targets that satisfies some boolean property associated with that square.

One neat thing about targeting is that it can be used in planning. A plan can identify a target in an initial analysis and later refer to that target regardless of which square it may later occupy after moving.

[sje]

The delta of a delta defines a parabola. This is true with simple polynomials and an analogous formulation can help with determining similarity among chess positions and moves.

Consider the CTTargetBMDB class mentioned above. Let an instance of this exist for the current search node and also for each position resulting from a move at the node. For each pair of (parent, child) instances, generate the set differences P-C and C-P. The first will give those target relationships that are preserved by a move and the second gives those changed by the move. These deltas in turn can be compared to the same deltas generated by applying the difference operation to the bitmap databases pairs for all the other moves. (Each target bitmap array is 32 x 32 bits, so an and/or/xor can be performed with only sixteen 64 bit operations.)

Looking at the deltas of the deltas, we can see which moves are similar to each other and by how much. We can also see which moves make the smallest or largest changes in the parent. This information in turn can be used to guide the search in various ways.

[Harald Johnsen]

Steven, do you think that your similarity facility could be used like equivalent cards are used in bridge in order to apply partition search ?

HJ.

[sje]

Well, it's possible. The idea should be applicable in any two player traditional game tree search, and those games with wider branching stand to benefit more.

[sje]

The four basic target relationships based on the single primitive AtkFrTo(t0, t1) are:

DefP0(a0, a1): Target a0 (active mover at ply 0) defends target a1

DefP1(p0, p1): Target p0 (active mover at ply 1) defends target p1

AtkP0(a0, p0): Target a0 (active mover at ply 0) attacks target p0

AtkP1(p0, a0): Target p0 (active mover at ply 1) attacks target a0

The idea is to organize the basic relationships using the concept of "active color at search start" instead of (say) "White" as the rest of the program uses the convention of "active mover" instead of "white-to-move".

Instances of a given basic relationship can be ordered. For example, from the viewpoint of the ply zero moving side (say Black in this case), the instance DefP0(BlackRook, BlackPawn) is not as good as DefP0(BlackPawn, BlackPawn). Also, orderings of instances of differing basic predicates can be established.

Idea: the ratio of total DefPx / total AtkPy gives a rough estimate of quiescence.

Idea: the change calculated over a series of moves of estimated quiescence can guide the search into or away from active regions.

Idea: iterating attack/defend analysis gives more interesting target bitmaps with relations like Pin(), Xray(), Battery(), etc.

Idea: three operand target relations can be represented by a 32 element target bitmap array.

Idea: target bitmaps can be used to communicate information back up the tree; example: targets that are lost, targets that are exchanged, etc. This can be used to try re-searches with different short term goals.