Multiplicative piece-square tables

[hgm]

The following idea occurred to me, in connection with King Safety. It is particularly easy to apply to Xiangqi, where the King is trapped in the palace, but similar techniques might work in Chess after castling.

The problem I perceive (from watching games) is that my Xiangqi engine lets the opponent sneak up on his King fortress with two Horses or Pawns, perhaps supported from a distance by Rooks or Cannons. (Even if they are not, they usually can be within one or two moves, as Rooks and Cannons are very mobile pieces, and in Xiangqi there are many open files even in the opening position.) And when he has amassed enough material in fromt of the gate, suddenly the checkmate gets within the horizon, no matter what you do, as the opponent sacs some of the seige material for the Guards and Elephant defenders to expose your King, after which you are dead meat.

The moral lesson is: don't let him approach with slow-moving pieces like Horses and Pawns; if you keep those at bay, there is little he can do to your King fortress faster than you can react by summoning heavy pices to your defensive aid. This can be done by piece-square tables, giving H and P lying in seige just in front of the palace a high value.

But this does not quite do what you want. Considering the gravity of the threat, two H or P there should already carry an enormous weight; if you ignore the threat by trying to grab material elsewhere on the board rather than stopping such advance, no matter how valuable that material, you will likely be checkmated. Putting PST values that are high enough to cause unconditional attention does result in the unwanted effect that they also would stimulate hopeless solo attacks of a single Horse or Pawn without any backup, which is doomed to fail, while you might have sacrificed material to acheive it, or, (in the case of a Pawn, which cannot be retreated) is likely to cost you the wreckless attacker in the long run.

Furthermore, although high PST values for the attackers would stimulate you to prevent their approach (possibly at large cost), they would not stimulate equally valid (and perhaps less costly) modes of defense, like blocking them when they are on the highly valued squares (XQ Horses can be blocked), or defending your Guards or Elephants with heavy material, so your fortress gets unassailable. Giving high PST values for your own heavy pieces on good defensive squares would have the very detrimental effect of causing very passive play, tying up your own pieces in defense even when there are no attackers at all.

In short, you would want to give a huge penalty when a gang of pieces appears in front of your palace, a penalty far higher than the sum of the pieces there in isolation (which might even be negative), and you want to award defense only if there are attackers. Such conditional penalties and bonuses suggest multiplication rathr than addition. E.g. if I would award a distant Pawn a factor 1, and a Pawn at the point of entering the palace a factor 7, and would multiply the factors of all Pawns and treat the product as a'pawn-storm bonus' in centi-Pawn, a single Pawn storming my palace would contribute a meaningless 7 cP, (compared to an 'all-clear' value of 1cP), which I could even offset with a 20-cP penalty in the normal PST. But a pack of 3 Pawns doing the same would contribute 7*7*7 = 343 cP, (perhaps offsetted by 3*20 = 60cP in normal PST eval), which is good enough to create a panic reasonably well in adance of the checkmate that is likely to ly beyond the horizon. And an extra defender (say a Horse on a square where it defends the Guard in front of my King) could contribute a factor 1/3, reducing the threat of 3 storming Pawns to a manageable 114 cP, and reducing a pair of them to the 'insignificant threat' level.

Of course you don't actually want to do any multiplications or divisions, but this can be avoided by accounting the logarithm of the pawn-storm bonus. This can be done in the same way as normal PST scoring, except that before adding the actual bonus to the total evaluation score, you would have to exponentiate it (which you do by lookup from a small table). So you would get two additional sets of PSTs: one that has the (square-dependent) values for attackers (positive) and defenders (negative) of the white fortress, another set doing the same for black. The differential update of this during MakeMove() could be done for free, by piggybacking them on the normal PSTs in SIMD fashion, e.g. as low-order bits (putting the normal differential evaluation in the high-order 16 bits, with two 8-bit log(pawnStormBonus) values in the two low-order bytes. These two low-order bytes would each be used as indexes in the exp table to undo the log, and then are added / subtracted to the high-order 16 bits to produce the total evaluation. Very cheap.

Are there programs that do use this approach to King Safety?

[bob]

The following idea occurred to me, in connection with King Safety. It is particularly easy to apply to Xiangqi, where the King is trapped in the palace, but similar techniques might work in Chess after castling.

The problem I perceive (from watching games) is that my Xiangqi engine lets the opponent sneak up on his King fortress with two Horses or Pawns, perhaps supported from a distance by Rooks or Cannons. (Even if they are not, they usually can be within one or two moves, as Rooks and Cannons are very mobile pieces, and in Xiangqi there are many open files even in the opening position.) And when he has amassed enough material in fromt of the gate, suddenly the checkmate gets within the horizon, no matter what you do, as the opponent sacs some of the seige material for the Guards and Elephant defenders to expose your King, after which you are dead meat.

The moral lesson is: don't let him approach with slow-moving pieces like Horses and Pawns; if you keep those at bay, there is little he can do to your King fortress faster than you can react by summoning heavy pices to your defensive aid. This can be done by piece-square tables, giving H and P lying in seige just in front of the palace a high value.

But this does not quite do what you want. Considering the gravity of the threat, two H or P there should already carry an enormous weight; if you ignore the threat by trying to grab material elsewhere on the board rather than stopping such advance, no matter how valuable that material, you will likely be checkmated. Putting PST values that are high enough to cause unconditional attention does result in the unwanted effect that they also would stimulate hopeless solo attacks of a single Horse or Pawn without any backup, which is doomed to fail, while you might have sacrificed material to acheive it, or, (in the case of a Pawn, which cannot be retreated) is likely to cost you the wreckless attacker in the long run.

Furthermore, although high PST values for the attackers would stimulate you to prevent their approach (possibly at large cost), they would not stimulate equally valid (and perhaps less costly) modes of defense, like blocking them when they are on the highly valued squares (XQ Horses can be blocked), or defending your Guards or Elephants with heavy material, so your fortress gets unassailable. Giving high PST values for your own heavy pieces on good defensive squares would have the very detrimental effect of causing very passive play, tying up your own pieces in defense even when there are no attackers at all.

In short, you would want to give a huge penalty when a gang of pieces appears in front of your palace, a penalty far higher than the sum of the pieces there in isolation (which might even be negative), and you want to award defense only if there are attackers. Such conditional penalties and bonuses suggest multiplication rathr than addition. E.g. if I would award a distant Pawn a factor 1, and a Pawn at the point of entering the palace a factor 7, and would multiply the factors of all Pawns and treat the product as a'pawn-storm bonus' in centi-Pawn, a single Pawn storming my palace would contribute a meaningless 7 cP, (compared to an 'all-clear' value of 1cP), which I could even offset with a 20-cP penalty in the normal PST. But a pack of 3 Pawns doing the same would contribute 7*7*7 = 343 cP, (perhaps offsetted by 3*20 = 60cP in normal PST eval), which is good enough to create a panic reasonably well in adance of the checkmate that is likely to ly beyond the horizon. And an extra defender (say a Horse on a square where it defends the Guard in front of my King) could contribute a factor 1/3, reducing the threat of 3 storming Pawns to a manageable 114 cP, and reducing a pair of them to the 'insignificant threat' level.

Of course you don't actually want to do any multiplications or divisions, but this can be avoided by accounting the logarithm of the pawn-storm bonus. This can be done in the same way as normal PST scoring, except that before adding the actual bonus to the total evaluation score, you would have to exponentiate it (which you do by lookup from a small table). So you would get two additional sets of PSTs: one that has the (square-dependent) values for attackers (positive) and defenders (negative) of the white fortress, another set doing the same for black. The differential update of this during MakeMove() could be done for free, by piggybacking them on the normal PSTs in SIMD fashion, e.g. as low-order bits (putting the normal differential evaluation in the high-order 16 bits, with two 8-bit log(pawnStormBonus) values in the two low-order bytes. These two low-order bytes would each be used as indexes in the exp table to undo the log, and then are added / subtracted to the high-order 16 bits to produce the total evaluation. Very cheap.

Are there programs that do use this approach to King Safety?

I do this kind of thing in Crafty. And. contrary to urban legend, multiplies are not bad in terms of performance, nor are divides. But in any case, this is commonly called a "second-order" evaluation term. So that small things don't add up for a single piece. In Crafty's king safety, we compute a term that is zero for a good king shelter, up to something like 15 for a king with no friendly pawns in front of it. We then factor in the closeness of the attackers, where sliders are looked at to see if they attack squares close to the king rather than being physically close. These two terms are effectively multiplied (done thru a table lookup in a 2d array to give us more precise control over the final value) to give a king safety numerical score.

second-order terms capture more of the complexities of the game, because they depend on coordinated pieces rather than just single pieces. This could be carried quite a bit further, and in our case, we are planning on doing so.

[Tord Romstad]

Are there programs that do use this approach to King Safety?

Something similar, yes -- except that I don't use piece square tables, but instead consider whether each individual piece attacks a square adjacent to the king.

Each piece type has a constant "attack weight":

Code: Select all

  const int QueenAttackWeight = 5;
  const int RookAttackWeight = 3;
  const int BishopAttackWeight = 2;
  const int KnightAttackWeight = 2;

For each color, I have two local variables in the evaluation function, an "attack weight" and an "attack count". When I evaluate each piece for the attacking side, I check if the piece attacks a square adjacent to the enemy king. If it does, I increment the attack count by one, and the attack weight by the piece's attack weight constant (5 for a queen, 3 for a rook, etc.).

The attack weight and count are used as the basic ingredients in my king attack evaluation. I multiply the attack count by the attack weight, which gives me a number of "attack units", as I call them. On top of this, I add or subtract some additional attack units based on other factors (number of safe checks, mate threats, number of attacked/defended squares around the king, the pawn shelter, etc.).

Finally, the number of attack units are used as the index to a lookup table which contains the king attack scores.

Tord

[hgm]

So basically the number of attack units grows as the square of the number of attackers where Queens are weghted a little more than lighter pieces. Is there any particular function that this lookup table represents (e.g. exponetial, arctangent), or is it just hand-tailored values?

In Chess precisely figuring out the attacked squares does make sense, but in Xiangqi a simple PST amount to nearly the same thing: becaue the King is confined to the 3x3 palace, attacking the central square of the palace automatically means attacking a square next to the King. And if you have a Rook attacking along, say, the d-file, it does not matter much if the King is on the e-file or f-file, as in both cases it is equally restricted in it movement: on the e-file by the Rook, on the f-file because the g-file is outside of the palace. The Rook might not seem to contribute much to the danger if the Kinfg ws in the f-file, but a first check can chase it to the e-file, and than it makes all the difference that it can be checkmated more easily there.

[Tord Romstad]

So basically the number of attack units grows as the square of the number of attackers where Queens are weghted a little more than lighter pieces. Is there any particular function that this lookup table represents (e.g. exponetial, arctangent), or is it just hand-tailored values?

By default, it's a quadratic function, but it can be changed to a linear function through a UCI parameter. There are also parameters for adjusting the coefficients of the quadratic or linear function.

In Chess precisely figuring out the attacked squares does make sense, but in Xiangqi a simple PST amount to nearly the same thing: becaue the King is confined to the 3x3 palace, attacking the central square of the palace automatically means attacking a square next to the King. And if you have a Rook attacking along, say, the d-file, it does not matter much if the King is on the e-file or f-file, as in both cases it is equally restricted in it movement: on the e-file by the Rook, on the f-file because the g-file is outside of the palace. The Rook might not seem to contribute much to the danger if the Kinfg ws in the f-file, but a first check can chase it to the e-file, and than it makes all the difference that it can be checkmated more easily there.

As far as I can see, you don't take into account blocking pieces between the rook and the palace, but as the board is less crowded than in chess, and pawns capture forward, this may not be very important in practice. I agree that piece square tables should work better for this in xiangqi (and in shogi, where there are few sliding pieces) than in chess.

Tord

[hgm]

So basically the number of attack units grows as the square of the number of attackers where Queens are weghted a little more than lighter pieces. Is there any particular function that this lookup table represents (e.g. exponetial, arctangent), or is it just hand-tailored values?

By default, it's a quadratic function, but it can be changed to a linear function through a UCI parameter. There are also parameters for adjusting the coefficients of the quadratic or linear function.

In Chess precisely figuring out the attacked squares does make sense, but in Xiangqi a simple PST amount to nearly the same thing: becaue the King is confined to the 3x3 palace, attacking the central square of the palace automatically means attacking a square next to the King. And if you have a Rook attacking along, say, the d-file, it does not matter much if the King is on the e-file or f-file, as in both cases it is equally restricted in it movement: on the e-file by the Rook, on the f-file because the g-file is outside of the palace. The Rook might not seem to contribute much to the danger if the Kinfg ws in the f-file, but a first check can chase it to the e-file, and than it makes all the difference that it can be checkmated more easily there.

As far as I can see, you don't take into account blocking pieces between the rook and the palace, but as the board is less crowded than in chess, and pawns capture forward, this may not be very important in practice. I agree that piece square tables should work better for this in xiangqi (and in shogi, where there are few sliding pieces) than in chess.

Tord

I was not planning on using this for Rook positioning, but only for Rook presence. (I.e. the Rooks would have a flat king-safety PST, at a facor > 1, making any attack by the leapers (H+P) more dangerous by the mere fact they are on the board. I could make an exception for squares where the Rooks are in contact with the palace, so it is obvious they cannot be blocked by anything, or that they are so far advanced that they could not be blocked by enemy Pawns (i.e. on rank 0-3).)

The idea was that attack by Rooks is not a strategic feature, but a tactical feature that can easily change from one move to the next. If the Rook is not yet in position, but there is a Rook on the board, you can bet that it will be there one or two moves later. In Xiangqi you have much less control over your own half of the board as in Chess, as King, Advisors and Elephants practically defend no squares at all outside the palace, Cannons are useless at close range, and Pawns are too far advanced from the beginning. So you basically depend on the Rooks and Horses to control your own turf, which is just too much for them. This means pieces like Rooks pretty much roam the board with impunity, and if you cannot attack the palace from the front, over the open d- or f-file, you do it from one of the sides, penetrating through the open b- or h-file.

An alternative method could be to keep extra Zobrist tables in stead of extra piece-square tables, defining keys only for pieces as far as they are relevant for the attack or defense of one of the palaces. (e.g. if it is relevant to kow if a Rook is blocked, but not by what, all blockers could get the same Zobrist random for that square). And then use them to access a hash table that lists the King-Safety score. And perhaps even a move that has to be extended by 2 ply, to bring the mate within the horizon. The problem is of course tat you would somehow have to fill that hash table.