Xiangqi piece value model

[Evert]

I went back and had a look at my old XiangQi program, which is in pretty dire shape (and weaker than SjaakII) and started thinking about how I could make a better program.

XiangQi has the unique feature that it has pieces that are solely useful for defense (Elephant and Adviser), while Pawns are only useful to attack (and the rest, Rook, Cannon and Horse, can do both but are better suited to attack). A simple linear material evaluation is inadequate because having a material advantage in defensive pieces does not directly help you win (however, being behind in defensive pieces does make it more likely that you lose). Perhaps the way to evaluate this is with a material table, but that still needs rules for how to fill it.

I came up with a model that may do well, but I have yet to try it out. I'm posting it here as a point for discussion (and so I can find it again later). For reference, a simple linear model gives something like R=9, H=C=4.5, E=A=2, P=1 (2 after crossing the river) with C>H in the opening and H>C in the ending.

In my model, E and A do not have a piece value as such, rather the value of R,C,H,P depend on the defensive material of the opponent (the simplest and probably good enough as a first guess is just the number of E+A, which ranges from 0-4). When the opponent loses a defensive piece, your own offensive pieces become more valuable, and so the evaluation sees a material advantage. The trading gradient should then be such that trading more defensive pieces increases the material advantage of the stronger side.
This seems reasonable, but there is a snag: if my Horse is now more valuable than yours, I should avoid trading it (which is correct). This depresses the value. It's not yet clear to me if this needs to be incorporated explicitly (probably you can just absorb this term in the tabulated piece values). A larger complication is that the piece values of at least the Horse and Cannon should scale with the total material remaining (a Horse has poor maneuverability on a crowded board, a Cannon needs a mount to attack).

Even if I assume that everything is somehow linear and I do some linear interpolation (as seems standard) for the "defensive phase" and "offensive phase", I get 4 different piece values that need to be set (tuned) for each piece. Apart from the increased computational complexity, does this seem like a reasonable approach?

[hgm]

In HaQiKi D I originally made a 'partial' material table, which was indexed by keys that were a combination of attacking material of one side, and defensive material of the other. That is only 3^5*6 = 1458 entries. That allows the devaluation of 'superfluous defenders'.

But it has many drawbacks. It cannot recognize specific end-games, for which you would want to have a recognizer (e.g. KRCKR). Or realize there is a huge difference between KRKAAEE (general draw) and KRKAAE (general win). Because if the defeding side would have an extra attacking piece, that missing E would be of no consequence at all.

So in the version I am preparing now I use a hashed material table, indexed by the full material composition (2M possible keys), where it calculates the material correction on the fly, rather than in advance, hoping that a high hit rate will completely mask the on-the-fly effort. As an initial approach I had this on-the-fly calculation just take the difference of the 1458-entry 'one-sided' tables. Then I started adding code to recogize specific total material combinations, such as Cannons without platforms, KRCKR and KRCdKR (which it could never win by itself). I also want to stick some tablebases in there. So the hashed material table either contains a score correction, or indicates a special end-game routine that must calculate a score based on the naive score or actual positioning of the pieces. (E.g. to top off a score with just K+C to 0, or recognize that KRCKR is draw with the defending KR in the central file.) The lengthy recognition of special end-game cases is then only done on a miss in the material hash, while the score calculation it specifies is done in the eval, only for cases where the material combination needed it.

I think that I can also discourage 'futile attacks' through such a table. E.g. when you only have a single Horse against full defense, or even against one E or two A, there is zero chance that Horse could achieve anything on the enemy half. So if you are behind (say against R or HH plus some P, and compromised defense), you'd better pull back that Horse to aid in the defense. This could be achieved by having the recognizer for this add a bonus dependent on the lone-Horse location to the naive eval, which draws the Horse towards your own Palace.

Recognizing futile attacker combinations (like two P against full defense) and basically compensating their contribution to the evaluation so it gets almost zero would also prevents it hangs on to such material and miss a chance to destroy the opponents winning material. E.g. in KRPAAEEKPPAAEE, with two crossed Pawns for black, and an uncrossed Pawn for white. Naively it would think the two crossed Pawns are worth more than a single uncrossed one, and avoid a trade even if he could make one. While KRAAEEKAAEE likely would have been a dead draw. If KRdKAAEE would have been recognized as a draw (as generally drawish end-game, or through a bitbase), it would not make that mistake.

[hgm]

Another consideration: it makes sense (and I think the Elephant-Eye evaluation actually uses this) that A or E possessions are not additive. Even if having 2A or 2E is roughly equivalent, having A+E is far worse, because they cannot protect each other. This is especially bad when defending against Rooks, who can attack and pin them at the same time. This can be translated to an increase in Rook value when the opponent does not have a complete set of A or E.

[phhnguyen]

This seems reasonable, but there is a snag: if my Horse is now more valuable than yours, I should avoid trading it (which is correct). This depresses the value. It's not yet clear to me if this needs to be incorporated explicitly (probably you can just absorb this term in the tabulated piece values). A larger complication is that the piece values of at least the Horse and Cannon should scale with the total material remaining (a Horse has poor maneuverability on a crowded board, a Cannon needs a mount to attack).

I think your problem is simply the lack of endgame knowledge. For example, in the game KRH vs KCAEE the Horse has higher value than the Cannon one (since the game closed to the end) thus your app may avoid trading H to C. However, KR vs KAEE is a sure win for the Rook side. If your app understands that endgame, the strong side will insist trading H-C whenever it could.

A bit different from (Western) chess, IMO, Xiangqi has higher speed of capturing / trading, thus, a typical game comes to the end significantly quicker. Thus endgame knowledge will be involved much sooner.

[Evert]

I think your problem is simply the lack of endgame knowledge. For example, in the game KRH vs KCAEE the Horse has higher value than the Cannon one (since the game closed to the end) thus your app may avoid trading H to C. However, KR vs KAEE is a sure win for the Rook side. If your app understands that endgame, the strong side will insist trading H-C whenever it could.

I think we just had another discussion about the merits of tossing a material advantage away to trade into a known win.
Joke aside, having specific end-game knowledge helps, of course, but it's a separate consideration from piece values, which are more general. In Western Chess, KNNK is a draw and so the two knights are worth considerably less than the pawns in KPPK. Or, in KBBP vs KNB trading into KBP vs KB with unequal bishops is a bad trade, but that doesn't affect the intrinsic value of the knight and bishops.

All of that said, in KRH vs KCAEE, H > C, but if you consider that the value of the Rook is depressed by the presence of the enemy Cannon this can make up for the difference and favour the trade of H for C (in honesty though, I don't think this effect is so large for a Cannon).

A bit different from (Western) chess, IMO, Xiangqi has higher speed of capturing / trading, thus, a typical game comes to the end significantly quicker. Thus endgame knowledge will be involved much sooner.

I'll have to take your word for it, because I have no way to judge this for myself. My impression, however, was that games last a similar number of moves?

[hgm]

I think your problem is simply the lack of endgame knowledge.

I can confirm this is very important. But that is not really different from Chess, where there also are many specific material combinations where the piece values do not work. E.g. a Knight would normally be worth far more than 2 Pawns, but in KNKPP you are not ahead, and only the side with the Pawns stands a chance to win. So the piece values are best tuned to the middle game, while specific end-game combinations are then recognized and evaluated by other means.

HaQiKi D originally used only a partial material table, which contained score corrections to the naive sum-of-piece-values for each of the 1458 combinations of attacking meterial and opponent defending material. This was good for discounting superfluous defenders, so that it would not make the mistake of giving up a Pawn rather than AAE when the opponent only had a Horse and it had AAEE left. But it was no good for recognizng specific end-game combinations. XQ had 2 million material combinations, and because that seemed a bit big for an exhaustive pre-coputed table, I made material hash table. This is supposed to have an extremely high hit rate, so it is not a problem if the scores in it have to be calculated on the fly in case of a miss.

Normally the table would contain a score correction, but I set aside a range of scores to indicate special treatment depending on the actual location of the pieces. (E.g. for KRCKR you would have to know if the defending King occupies the central file (draw) or the attacking King does that (sure win). Because it could not actually win the latter case at reasonable TC, I even had to recognize sub-goals based on Cannon location, and award bonuses for those.) For KRKAAEE I even put in a partial tablebase for all positions with the Rook on the opponent half, so that it can be probed also for all positions where the Rook side has additional defensive material behind its King. Positions that do not satisfy these criteria get a bonus for moving the King to the front of the Palace, but a reduction due to being a likely draw (and a bonus for being a sure win, if the oppnent did not have full defense).

[hgm]

For now I want to put the following knowledge into HaQiKi D (d or D means any number of A and E):

KRC vs KR won/draw based on file of defending King
KRCd vs KR sure win
KRd vs KAAEE drawish (EGT for KRKAAEE with Rook on enemy half)
KRd vs Kd (d<AAEE) sure win (EGT)
KRPd vs KAAEE sure win
KHd vs K or KA sure win
KHD vs Kd drawish when d>=E or d>=AA
KHPD vs Kd win/draw (d<=AEE, or d=AA), dependent on Pawn advance (EGT?)
KHd vs KP draw
KHPd vs KPd, d<=EE win (if not last-rank Pawn)
KHHd vs Kd sure win (EGT)
KHPPD vs Kd win (dependent on Pawn advance, EGT?)
KC, KCE or KCEE vs Kd draw
KCA vs KAA, KA or K sure win
KCD vs Kd with d>=E and D>=A drawish
KPd vs K win (if not last-rank P)
KPd vs Kd, d>0 draw
KPPD vs Kd
KPPPd vs Kd win (dependen on Pawn advance)

I also want to define the concept 'winning advantage', which would be one of the wins mentioned above, plus an extra identical major piece on each side (e.g. an extra Rook or Horse). This would get a bonus because the defending side cannot afford to trade the piece. This would provide an incentive to protect/destroy the winning advantage. E.g. in KRHPd vs KRPEE this would make the defending side sac crossed Pawn plus one Elephant for the remaining non-crossed Pawn of the strong side, because HP vs PEE is a winning advantage, while H vs E is not.

I guess EGTs with 3 attacking pieces could still be feasible. E.g. KHPP vs Kd would have ~10,000 combinations of attacking King file and defender positioning. If H and P are all confined to the enemy board half (45 squares), this would give a factor 45^3/2 ~ 45,000 (the division by 2 because of Pawn interchange). That would give it 450M positions.

[Evert]

For now I want to put the following knowledge into HaQiKi D (d or D means any number of A and E):

KRC vs KR won/draw based on file of defending King
KRCd vs KR sure win
KRd vs KAAEE drawish (EGT for KRKAAEE with Rook on enemy half)
KRd vs Kd (d<AAEE) sure win (EGT)
KRPd vs KAAEE sure win
KHd vs K or KA sure win
KHD vs Kd drawish when d>=E or d>=AA
KHPD vs Kd win/draw (d<=AEE, or d=AA), dependent on Pawn advance (EGT?)
KHd vs KP draw
KHPd vs KPd, d<=EE win (if not last-rank Pawn)
KHHd vs Kd sure win (EGT)
KHPPD vs Kd win (dependent on Pawn advance, EGT?)
KC, KCE or KCEE vs Kd draw
KCA vs KAA, KA or K sure win
KCD vs Kd with d>=E and D>=A drawish
KPd vs K win (if not last-rank P)
KPd vs Kd, d>0 draw
KPPD vs Kd
KPPPd vs Kd win (dependen on Pawn advance)

That's an interesting list. I was thinking of going through the list in Lau's book, which is slightly different. I can post those if you're interested.

I also want to define the concept 'winning advantage', which would be one of the wins mentioned above, plus an extra identical major piece on each side (e.g. an extra Rook or Horse). This would get a bonus because the defending side cannot afford to trade the piece. This would provide an incentive to protect/destroy the winning advantage. E.g. in KRHPd vs KRPEE this would make the defending side sac crossed Pawn plus one Elephant for the remaining non-crossed Pawn of the strong side, because HP vs PEE is a winning advantage, while H vs E is not.

That's an interesting idea. I've toyed with the idea of doing something like that for other variants, but never got around to doing it.

In other news, rather than messing around with my old Xiangqi program, I modified Postduif so it can play Xiangqi instead. It works, but play is awful because it still lacks any of the evaluation terms I was planning. I also haven't (yet) ported over the chase detection I have in SjaakII (which should be a little easier here since Postduif uses a piece list, so I can just compare a bitmask of chased piece IDs and don't need to track a piece as it moves). What struck me as a bit odd is that speed-wise (in terms of NPS) it's about equal to SjaakII at the moment, although SjaakII is bitboard while Postduif is mailbox (which I would have expected to be faster here).

Anyway, I had a rather interesting end-of-game from XBoard:

Code: Select all

133517 <second&#58; # Begin iterative deepening loop for position "2eakae2/2C6/9/9/9/p5E2/2p1c1p1P/5K3/3rr4/6E2 b 1 43"
133517 <second&#58;   2  15999      0         2  43. ... Pg2
133518 <second&#58; move g3g2
133518 >first &#58; time 6590
133518 >first &#58; otim 6806
book hit = &#40;NULL&#41;
133518 >first &#58; g3g2
133601 <second&#58; 0-1 &#123;Black mates&#125;
GameEnds&#40;27, Black mates, 6&#41;
result=27 sp=-3 move=86
GE&#40;26, False win claim&#58; 'Black mates', 6&#41; bare king k=5 color=0
133603 >first &#58; result 1-0 &#123;False win claim&#58; 'Black mates'&#125;
133603 >second&#58; result 1-0 &#123;False win claim&#58; 'Black mates'&#125;
133603 >first &#58; force
133603 >first &#58; ping 3
133603 >second&#58; force
133603 >second&#58; ping 2
133603 <first &#58; # Position '2eakae2/2C6/9/9/9/p5E2/2p1c3P/5Kp2/3rr4/6E2 w 44'
133603 <first &#58; 0-1 &#123;Black mates&#125;
133603 <first &#58; # Position '2eakae2/2C6/9/9/9/p5E2/2p1c3P/5Kp2/3rr4/6E2 w 44'
133603 <first &#58; 0-1 &#123;Black mates&#125;
133603 <first &#58; pong 3
133603 <second&#58; pong 2

Engine 2 is SjaakII, which mates and subsequently sends a result claim. XBoard rejects the claim (incorrectly) and sends the spurious result to the engines (the result is then apparently rejected in turn by Postduif, which claims black won).

[hgm]

Unfortunately XBoard has been broken for Xiangqi ever since I replaced the move generator in 4.8. The new mve generator allowed King and Advisers to leave the Palace. I discovered and fixed that for Adviser before the 4.9 release. But I discovered it for King only a few days ago, because of the failing mate detection. HaQiKi D does not claim, so when it mates the game just hangs when the King can move to a save square outside the Palace...

The required patch is this:

Code: Select all

--- a/moves.c
+++ b/moves.c
@@ -986,6 +986,13 @@ GenPseudoLegal (Board board, int flags, MoveCallback callback, VOIDSTAR closure,
 
             case WhiteWazir:
             case BlackWazir:
+		if(gameInfo.variant == VariantXiangqi) { // confine to Palace
+		    int palace = (piece == WhiteWazir ? 1 : BOARD_HEIGHT-2); // rank of Palace center square
+		    if(ff >= BOARD_WIDTH/2 && !SameColor(board[rf][ff-1]) callbackboard, flags, NormalMove, rf, ff, rf, ff-1, closure);
+		    if&#40;ff <= BOARD_WIDTH/2 && !SameColor&#40;board&#91;rf&#93;&#91;ff+1&#93;) callbackboard, flags, NormalMove, rf, ff, rf, ff+1, closure&#41;;
+		    if&#40;rf >= palace && !SameColor&#40;board&#91;rf-1&#93;&#91;ff&#93;) callbackboard, flags, NormalMove, rf, ff, rf-1, ff, closure&#41;;
+		    if&#40;rf <= palace && !SameColor&#40;board&#91;rf+1&#93;&#91;ff&#93;) callbackboard, flags, NormalMove, rf, ff, rf+1, ff, closure&#41;;
+		&#125; else
 		Wazir&#40;board, flags, rf, ff, callback, closure&#41;;
 		break;

(This assumes 3x3 Palace, which might not be how XBoard colors the squares when you overrule board size.)

The confinement code for Elephants was kept when rewriting the move generator, as was the blocking code for Horses and Elephants. So with this patch Xiangqi should be fully functional again.

[Evert]

The required patch is this:

Code: Select all

--- a/moves.c
+++ b/moves.c
@@ -986,6 +986,13 @@ GenPseudoLegal (Board board, int flags, MoveCallback callback, VOIDSTAR closure,
 
             case WhiteWazir:
             case BlackWazir:
+		if(gameInfo.variant == VariantXiangqi) { // confine to Palace
+		    int palace = (piece == WhiteWazir ? 1 : BOARD_HEIGHT-2); // rank of Palace center square
+		    if(ff >= BOARD_WIDTH/2 && !SameColor(board[rf][ff-1]) callbackboard, flags, NormalMove, rf, ff, rf, ff-1, closure);
+		    if&#40;ff <= BOARD_WIDTH/2 && !SameColor&#40;board&#91;rf&#93;&#91;ff+1&#93;) callbackboard, flags, NormalMove, rf, ff, rf, ff+1, closure&#41;;
+		    if&#40;rf >= palace && !SameColor&#40;board&#91;rf-1&#93;&#91;ff&#93;) callbackboard, flags, NormalMove, rf, ff, rf-1, ff, closure&#41;;
+		    if&#40;rf <= palace && !SameColor&#40;board&#91;rf+1&#93;&#91;ff&#93;) callbackboard, flags, NormalMove, rf, ff, rf+1, ff, closure&#41;;
+		&#125; else
 		Wazir&#40;board, flags, rf, ff, callback, closure&#41;;
 		break;

(This assumes 3x3 Palace, which might not be how XBoard colors the squares when you overrule board size.)

The confinement code for Elephants was kept when rewriting the move generator, as was the blocking code for Horses and Elephants. So with this patch Xiangqi should be fully functional again.

Thanks, but apparently the definition of SameColor has changed since the snapshot I have. The code fails to compile:

Code: Select all

moves.c:991:63: error: macro "SameColor" requires 2 arguments, but only 1 given
moves.c: In function ‘GenPseudoLegal’:
moves.c:991: warning: the address of ‘SameColor’ will always evaluate as ‘true’
moves.c:991: error: expected ‘)’ before ‘callbackboard’

and more of the same. Is there a version on your online repository that has the necessary changes?