Static tactics evaluator

[hgm]

Does anyone know what has been done in the area of statically (= without search) guessing the QS result and the move that would have to be played to achieve it? Something like SEE, but not just on a single square, but for the board as a whole. (Global Exchange Evaluation = GEE?)

Such an algorithm could start calculating the SEE on every occupied square, for each player, to determine what material is up for grabs. There are then two problems: how these results have to be combined, and that the SEE might not be independent of each other, and executing one exchange would affect the result of others.

As to combining, there are some simple cases. If the side to move has multiple profitable attacks, and no attacks against him, he can go on harvesting by performing the exchanges that leave him on move, until he collects one that leaves the opponent on move (such as capturing an unprotected piece, or two minors for a Rook); the opponent then presumably can resolve the attack on the next target in line, e.g. by moving that piece away, or arrange (extra) protection. Similarly, if the side to move has no profitable captures, but the opponent has, the move will be used to resolve the worst threat, after which the opponent would become side to move, and could combine any remaining SEEs as described above. The hard case appears to be where both sides have profitable attacks.

Dependence between different SEE typically occurs by capture of a piece involved in another SEE, using such a piece to capture, or using such a piece to block an attacker (i.e. a soft-pinned piece). The calculation of all SEE would start by generating moves for both sides, including friendly captures (protection) and x-rays, to create an attack map. (If such a map was not already available through incremental update.) For each piece we could then calculate the SEE from the attack map on its square.

We can then also calculate whether this result is critical, i.e. whether it would be the same if we lose a protector. E.g. a piece protected by two Pawns would be 'solidly protected' against attacks of any number of higher-valued piece, as even discarding one of these Pawns would make all of the captures SEE-negative. If there was only a single Pawn protector, the situation would be critical, a discarding that protector would make the piece hang. For every critical SEE we could mark the protectors as being essential for protecting that target, and how much it would cost you if that protector could not be used in the exchange.

If a piece gets marked as essential twice, it would be 'overloaded', and we might have to assign it to the exchange for which it matters most. (Not always, though. E.g. if a Pawn is protecting a Knight from a Rook attack, and a Pawn from a Queen attack, both SEEs would be so negative that not enough is gaint by 'distracting' the protector. If it had been a Rook instead of a Pawn under Queen attack, RxN would be possible, and the Pawn would be assigned to protecting the Rook. Overloading a protector is also no problem if the protected squares also have a common attacker.) The SEE to which the overloaded protector is not assigned must then be 'corrected' by ignoring that protector.

Similar correction would be needed if protection is 'undermined', by an essential protector being under attack itself. As with the overloading it depends how much has to be invested in eliminating the protector, compared to how much the SEE value on the square it protected would increase.

Potential soft-pins can be detected as x-ray captures through an enemy piece. The target of such an x-ray should be tested for another type of criticality: increase of the SEE value by adding the extra attacker. If there is such an increase, the x-rayed piece is soft-pinned, and can be marked the same way as a critical protector would be. An extra feature compared to the latter case is that if the SEE on the blocking piece itself is positive, solving that threat might not be so easy, as moving the piece away is no longer a free option.

An efficient implementation would of course get all the SEE values from a table indexed by the set of attackers and protectors; such a table could also indicate which protectors are critical, and which extra attackers would matter.

[Rebel]

Rebel (1980) started that way, never heard of QS in that time. It even evaluated checks for checkmate.

[towforce]

Rebel (1980) started that way, never heard of QS in that time. It even evaluated checks for checkmate.

Why did you stop?

My guess: faster CPUs => deeper search => less need for all types of tactical work in the eval

Also, the big picture (my favourite view!): you really need to know everything - not just the outcome of possible exchanges. Back in the day, the remedy for the need to know everything was to search fast and deep.

[hgm]

I don't want to use such a GEE for actual evaluation, but as a sort of 'policy network', to indicate which moves had better be reduced or pruned because they are poor and lose material. It is currently common practice to prune bad captures in QS, i.e. captures with SEE < 0. But such captures can be good, if a protector would be soft-pinned or overloaded, or the captures an essential protector of another square. R x protected N is the obvious move if that N was protecting an R attacked by a Q, and was not protected by another N. But it would be pruned in conventional QS, because it would lose the exchange, and that it gains a full Rook immediately afterwards would not be seen. Using GEE for the pruning decision would not have that problem.

[Rebel]

Rebel (1980) started that way, never heard of QS in that time. It even evaluated checks for checkmate.

Why did you stop?

Because QS gave more elo.

My guess: faster CPUs => deeper search => less need for all types of tactical work in the eval

Also, the big picture (my favourite view!): you really need to know everything - not just the outcome of possible exchanges. Back in the day, the remedy for the need to know everything was to search fast and deep.

[Rebel]

I don't want to use such a GEE for actual evaluation, but as a sort of 'policy network', to indicate which moves had better be reduced or pruned because they are poor and lose material. It is currently common practice to prune bad captures in QS, i.e. captures with SEE < 0. But such captures can be good, if a protector would be soft-pinned or overloaded, or the captures an essential protector of another square. R x protected N is the obvious move if that N was protecting an R attacked by a Q, and was not protected by another N. But it would be pruned in conventional QS, because it would lose the exchange, and that it gains a full Rook immediately afterwards would not be seen. Using GEE for the pruning decision would not have that problem.

Surely bad captures can be good, but in the end elo decides.

Perhaps you remember Don Beal playing in the WCCC 1986 with very extensive QS.

[towforce]

Perhaps you remember Don Beal playing in the WCCC 1986 with very extensive QS.

Don Beal wrote a paper about null-move quiescence in 1986 (it's discussed in this thread - link - where the consensus seems to be that it's not a good idea).

In the early 2000s, he also wrote two papers about learning from weak opponents and observing bad play, which are among the most memorable papers I've ever read (conclusion: you can learn from opponents who are weaker than yourself, but you have to put more time and effort into the learning. This applies outside of chess as well!).

[hgm]

Surely bad captures can be good, but in the end elo decides.

Sure, Elo decides whether being lame is highly superior to being blind. It doesn't tell you how to get healthy, though.

My favorite metaphor for this is 'fitting a circle with a square': suppose the game is to guess whether given event at coordinates (x,y) is within the unit circle. You could come up with the expression (fabs(x) < D && fabs(y) < D), and then empirically measure how often you are wrong, and make a carreer out of finding the best value for D. You could let 'Elo decide' whether D=1 (never any false misses) would be better than D=1/sqrt(2) (never any false hits), or you could tune. But even the best D you could find would perform dismally compared to using an octagon (fab(x) < D && fabs(y) < D && fabs(x+y) < E && fabs(x-y) < E). Even for the completely unoptimized choice D=1, E=sqrt(2), where the octagon entirely contains the circle. (Of course (x*x + y*y < 1) would do perfectly, but you would have to invent multiplication for that.)

Discriminating moves by SEE is just as inaccurate as treating a circle like it was a square; it classifies many captures that significantly up the score as 'bad', and many captures that waste material as 'good'. But as long as you don't have a more accurate classification (= GEE), there is no way to prevent erring in one direction or the other.

Of course QS is far more accurate than SEE, whether it prunes bad captures or not. It would see all these complications of overloading, undermining and soft-pinning. But it is also vastly more expensive. Trying to make it more accurate by searching additional moves makes it even more expensive, for very little potential improvement, because it already is so good to begin with. So that is not the way to go. Using a more accurate filter for which captures you prune (GEE instead of SEE), and in which order you should search them, doesn't necessarily make QS more expensive, though. In fact it could make it far cheaper. MVV/LVA + SEE is a rather primitive method of move ordering.

[chesskobra]

I am not sure if I understand the problem, but correct me if my formulation below is not what you are asking. But my formulation is piece based, not square based. But it can be made square based.

For any given board position, we define a directed graph or a 0-1 matrix M as follows. Index the rows of M by white pieces a_i and columns by black pieces b_j. Define m(i,j) = 1 if a_i can capture b_j, and 0 otherwise. Of course, M will possibly change after a move, and at the minimum if a_i captures b_j, then the j-th column will be removed. There might be modifications in other entries of M. We could create a tree of these matrices instead of full board positions, and do min-max on it. But you would like to make an estimate for the eval just based on M, is that right?

If my understanding is right, then I think it is an interesting algorithmic question. If my understanding is wrong, then I think I have an interesting question not relevant to your goal. In any case, if something is implemented based on the above matrix (whether full min-max or an estimate of eval), it could be useful for implementing strategies that are rule-independent.

[hgm]

You are spot on. The matrix you are defining is known as an attack map. Half of it can be obtained as a nearly free side effect of move generation. The other half would require move generation for the opponent, but could also be derived incrementally from the map in the parent node.

I want to use a somewhat extende version of the attack map, though, which also contains x-ray attacks. For the purpose of the tactics a Q attacg through an R or B is as good as a direct attack, as you would use it last anyway. But R or B attacking through Q would have to be treated special, as they break the usual capture order. And attacks through a K do not count at all.

The algorithm only has to work well for the most common (=simple) cases, as there always is the option to fall back on the usual MVV/LVA ordering if it judges the position too complex to handle. The SEE can be obtaied through two-level table lookup: the first level uses the attacks on a given square by one player obtained from the map to get a code that identifies the 3 or 4 lowest-value attackers (42 or 72 possible combinations). These codes are then used to index a 2-dimensional array that tabulates the SEE value (or contains some recognizable 'too complex' code) for the exchange after the first capture. To which the value of the occupant of the square then can be added to obtain the SEE.

To handle the case where both players heve a profitable capture, I am thinking of having a similar 2d table that contains a code for the combination of captures that would have to be made to achieve the SEE value. (It might not be profitable to continue the exchange beyond a certain point.) And two such codes could be used to index another 2d array to indicate the result of those both being possible. I still have to think some more on how to do that.