Magic SEE

[hgm]

I wonder if anyone ever tried this:

There are ony 144 material combinations that could attack a square: 0-1 Kings, 0-1 Queens, 0-2 Rooks, 0-3 minors, 0-2 Pawns. That makes 144^2 ~ 20K combinations of attackers and protectors. So it should be easy to tabulate the amount of material you lose in optimal play when you enter a certain square with the cheapest piece that attacks it, as a function of the material combinations that attack and protect that square. I.e. make a table loss[attackers][protectors]. The loss can be zero (e.g. if the piece first entering the square is sufficiently protected there), but never negative (as the opponent could always refrain from capturing it, and stand pat immediately).

This table could be used to help calculating the more general SEE when you enter an occupied square with a chosen piece, i.e. for an arbitrary capture. You just add the value of the occupant of the square to it (i.e. value[victim] - loss[attackers][protectors] to know what happens when you would capture it starting with your lowest piece. This would quantify the threat to that square. If you would capture with a piece that is not the lowest attacker you could caluclate the result as

victim - Max(0, capturer - loss[protectors][attackers - materialWeight[capturer]])

This is a pretty cheap way to get SEE provided you have the material combinations. And it only requires a 20KB table, as the SEE results range from 0-10, and thus fit in a single byte. In fact you could pack two of them in a byte.

I wonder if the table cannot be shrunk further by smart hashing, as is done for the move tables with magic bitboards. There are only 11 different outcomes of SEE, so many (attackers, protectors) combinations will have the same outcome. Like in magic bitboards occupied squares on the ray become don't cares beyond the first occupied squares, extra attackers of defenders become don't cares here if the opponent has run out of material. So I could imagine that there could be a small table of just 2 or 4KB, that in combination with cleverly chosen hash keys for each type of piece (assuming we use an additive key, and not an XOR key, to allow multiple pieces of the same type), would allow you to hash all SEE results to the small table such that only combinations that need the same result will collide.

[Rebel]

I have somthing like this since the early 80's.

http://www.top-5000.nl/authors/rebel/chess840.htm#HW

Source code: http://rebel13.nl/efs/index.html

Works with a [12][256][256] table [piece type][attackers][defenders]

[D Sceviour]

One problem is calculating the number of attackers, and the number of defenders on a square. That is where the bulk of the calculation would take place. These types of tests miss some of the most crucial errors including exposed pins, double discharged checks, interpositions and piece forks. Do not forget, it is possible to have nine queens on the board attacking the same square.

Perhaps it might be used to determine whether to explore a sub branch after the first combination has been tried, and all the attackers and defenders have been pre-calculated. That is, after the first exchange in the move list has been tried and the position has been tested for king safety problems. Normally the first exchange would be the heaviest piece to try to reduce the size of the sub-tree.

If the first try came back fail-low then it is an indication of a losing exchange combination. However, the hidden possibility of other unknowns would never be explored.

[Rebel]

It's good enough for 95+% (or so) of all cases. It's mostly used for move ordering anyway.

[hgm]

Yep, that would be faster, if cache size was no concern. But 768KB is a bit large. This is why I was hoping for a magic version of it that would only need 4KB or so. The overhead of removing the piece you are actually trying to capture with from the attackers set and then calculate it the other way around is probably well worth it for shrinking something used that often to make it fit into L1. Many of the more complex combinations (say with more than 3 pieces on each side) would probably occur so infrequently that it would have no impact whatsoever when you got them completely wrong. Deep SEE is an inherently unreliable estimate, as burning up so many pieces will have so many unconsidered side effects in terms of discovering attacks and withdrawing protectors that it would almost never be right even if you calculated it formally correct.

With only 3 pieces you could have material combinations:

-, K, Q, R, m, P, KQ, KR, Km, KP, QR, Qm, QP, RR, Rm, RP, mm, mP, PP, (19 so far)
KQR, KQm, KQP, KRR, KRm, KRP, Kmm, KmP, KPP, (+9 = 28)
QRR, QRm, Qmm, QmP, RRm, RRP, Rmm, RmP, RPP, (+9 = 37)
mmm, mmP, mPP (+3 = 40)

If you got those 40x40 = 1600 right, you would not care too much about the rest.

More important would probably be to distinguish direct and 'hindered x-ray' attackers, e.g. where B or R attack through Q.

[hgm]

The best way to keep track of x-rays is to record them as 'boosted Queens': instead of 2 Queen states (0 or 1) you would get 5 (0, 1, Q+xB, Q+xR, Q+2xR). This would drive up the number of attacker and protector combinations from 144 to 360. A 360 x 360 table starts to get uncomfortaly large, however.

Perhaps a multi-level lookup would be possible. In SEE you can often cancel like pieces against each other. E.g. R with N attacker and Q protector is the same as with NNB attackers and NNQ protectors. If you write victim + protector values on the one hand, and attacker values on the other in ascending order, identical terms in a corresponding position will cancel:

Code: Select all

R N N Q
 N N B

after the NxR you get just 2 extra Knight trades before the QxB recapture. A bordering pair of equivalent pieces can be ignored.

To make use of that you could you could keep track of the attacking material in separable parts, like Pawn + minor + Rook attacks and (x-ray-boosted) Queen + King attacks. The former would have 3*4*3 = 36 states, the latter 5*2 = 10 states. So you could combine the low attackers with the low protectors for a lookup in a 36x36 table to reduce away canceling pieces, and be left with a unique code for the remaining 'irreducible' combination of attackers and protectors. This code could then be used together with the Q+K attackers and protectors to access a 3d table, to finally get

see[combi[attackerPMR][protectorPMR]][attackerQXK][protectorQXK]

I wonder how much this could reduce the table size; this is not very easy to calculate. It might be only a factor 4.

[mvk]

I wonder if anyone ever tried this:

Tried that and still doing it. But not with a perfect hash. The hit rate for the imperfect hash of attacks^defenders is good enough, where attackers and defenders are just the linear combination of the piece counts, each of 12 bits if I recall correctly.

Code: Select all

#define EXCHANGE_LIST_PAWN              (1)             /* 1 */
#define EXCHANGE_LIST_MINOR             (1*3)           /* 3 */
#define EXCHANGE_LIST_ROOK              (1*3*12)        /* 36 */
#define EXCHANGE_LIST_ROYAL             (1*3*12*11)     /* 396 */

I have a second table for as long as there are pawns involved and the target square is on the last rank.

I err on the safe side if a queen is in front of a bishop or rook: In the defender list I promote the weaker piece to a queen in that case, and in the attacker list I demote the queen.

[hgm]

I have a second table for as long as there are pawns involved and the target square is on the last rank.

I err on the safe side if a queen is in front of a bishop or rook.

Ah yes, promotion makes a difference.

I am still dwelling on the two-stage approach. It is not only that you can cancel equal trades. Many of the outcomes are totally decided in the P+minor+R part, and never get to the stage where you would involve Q or K. In particular when there are more low-valued protectors than attackers. E.g. no attacking Pawns and two Pawn protectors (already represent 1/9 of the possibilities) always lose you the initial capturer, and thus end on -3 or -5 irrespective of the Q and K attackers and protectors.

It is true that it is a bit wasteful to store the same value in the table for 10*10 different QK combinations, but as there can only be 10 different outcomes of SEE, this wastes at most 1000 table elements. When there are more P/minor/R protectors than attackers, the only case where it would ever help to involve an attacker Q is when there is one more low protector than low attacker, the low-protector set contains 2 Rooks (one ending on the square, the other protecting it, because the attacker initiates the exchange). Q x R-protected-by-R could conceivably bring a +1 (if Q=9 and R=5, which could be a reason to set Q=10, as then even the 2-Rooks case can achieve nothing).

Similarly, all cases where there are 2 more attackers than protectors only require Q-involvement by the protector when the attacker has 2 Rooks (or never with Q=10). Only the cases low attackers = low protectors (220 cases) and low attackers = low protectors + 1 (202 cases) require wide-spread (or any) Q+K involvement.

[hgm]

I wrote a quick program to generate all combinations of atackers and protectors without X-rays (i.e. 144 x 144 ~ 20K combinations), and calculate SEE for entering an empty square with your lowest attacker on each of those. For each combination of P/minor/R attackers and protectors, I made a 4x4 array of the SEE values depending on the Q/K attackers and protectors.

Then I counted in how many of the 20K cases the 4x4 array was not constant, and how many different such 4x4 arrays there were. The result surprised me; there were only 308 cases were the result of the SEE depended on the involvement of Q or K. And there were only 27 different such 4x4 array (where one would expect 10 different 4x4 for all the KQ-independent cases, as SEE only can have value 0-9). So if I did not mess up the 308 KQ-dependent cases map onto only 17 different 4x4 matrices that specify how K and Q affect the result. (Very often this is to just provide the last capturer.)

That allows a much larger compression than I expected. The 3d table with SEE values would only need 27 x 4 x 4 = 432 entries, the table that specifies which of the 27 layers you need as function of the P/minor/R material requires 36 x 36 = 1296 entries. The whole table requires less than 2KB!

With x-rays I do not expect the number of layers to grow very much larger, but instead of 4x4 each layer would have to be 10x10 to handle the occasional case where an x-ray participant would matter. So the totally required table space would be only slightly above 4KB.

[hgm]

One problem is calculating the number of attackers, and the number of defenders on a square. That is where the bulk of the calculation would take place.

My preference goes out to a design where this information would be present at all time in an attack map. Most likely it would be in a form where a 64-bit int would contain 4x16 flags representing the attackers to 4 equal-valued victims. (And another int64 would similarly contain the protectors.) Due to LVA ordering the bits for attackers to one square would not be contiguous, but scattered through the word with a stride of 4 bits. They can be easily made contiguous by a mask, multiply and shift. In principle you could look for a magic multiplier that hashes them in a unique way to an acceptable number of bits, so that you could use that as an index into a table that tells you the number of attackers of various types. You still would need a way to figure in the x-rays, however.

A more simplistic design would simply run the move generator for the stm and (usually as part of the null move search) for the opponent, and for each occupied square hit by a move add the piece weight to a counter for that square. That would give you the attackers as an almost free side effect of move generation. For hits of slider on similarly moving slider you would have to continue the move to get the X-ray, which is only slightly more expensive (as such hits occur rarely). A smart move generator would be aware of pins, and avoid moving of pinned pieces off their pin line, so you would not get any false attackers from that. And the legality of King moves is basically checked by the SEE itself.