'ab-initio' piece values

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
hgm
Posts: 23365
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

'ab-initio' piece values

Post by hgm » Fri Mar 30, 2018 2:06 pm

Trying to calculate piece values from the move pattern of pieces is a tricky business, but determining them empirically from materially imbalanced games can also be a daunting task. Especially if you have no idea where to start from. And for games with piece drops material imbalance is usually way too volatile for the initial imbalance to have much effect on game result.

I now cooked up a method to guestimate piece values (as a function of their location, so really piece-square tables). It is based on the idea that the instantaneous value is proportional to the number of squares the piece can move/capture to, plus a factor alpha (<1) times the value it will on average have after its next move (calculated the same way). This averaging does not take any account of the fact that a player would prefer moves to locations where the piece is most valuable, as these are also the moves that the opponent will try most vehemently to prevent. So all moves are weighted equally. In a formula:

value(fromSqr) = nr_of_moves(fromSqr) + alpha * (SUM value(toSqr))/nr_of_moves(fromSqr)

where the SUM runs over all toSqr reachable from fromSqr. This system of equations (one for each board square) can be solved by just starting with the value set to 0 everywhere, and applying the formula repeatedly until the values do not change anymore. (The fact that alpha < 1 ensures that this will converge.)

For sliders it is not obvious what the nr_of_moves is, as the distant moves can be blocked. For this reason I use a second parameter beta, which basically represents the fraction of the board that is empty; for each square we have to pass through to reach the toSqr, we pick up a factor beta. And the average over moves is similarly weighted.

As an example, with beta=0.7 (an early middle-game value) and alpha=0.8 (arbitrarily chosen; this would be an obvious choice for something to tune in games, with an engine that uses the generated PST), I get the following for the orthodox pieces on an 8x8 board:

Code: Select all

Knight
 25.24 26.44 27.31 27.87 27.87 27.31 26.44 25.24
 26.44 27.74 29.13 29.66 29.66 29.13 27.74 26.44
 27.31 29.13 31.18 31.66 31.66 31.18 29.13 27.31
 27.87 29.66 31.66 32.26 32.26 31.66 29.66 27.87
 27.87 29.66 31.66 32.26 32.26 31.66 29.66 27.87
 27.31 29.13 31.18 31.66 31.66 31.18 29.13 27.31
 26.44 27.74 29.13 29.66 29.66 29.13 27.74 26.44
 25.24 26.44 27.31 27.87 27.87 27.31 26.44 25.24

Bishop
 29.13 29.39 29.82 30.04 30.04 29.82 29.39 29.13
 29.39 31.07 31.67 32.04 32.04 31.67 31.07 29.39
 29.82 31.67 33.27 33.63 33.63 33.27 31.67 29.82
 30.04 32.04 33.63 34.78 34.78 33.63 32.04 30.04
 30.04 32.04 33.63 34.78 34.78 33.63 32.04 30.04
 29.82 31.67 33.27 33.63 33.63 33.27 31.67 29.82
 29.39 31.07 31.67 32.04 32.04 31.67 31.07 29.39
 29.13 29.39 29.82 30.04 30.04 29.82 29.39 29.13

Rook
 37.28 38.56 39.35 39.73 39.73 39.35 38.56 37.28
 38.56 39.99 40.86 41.28 41.28 40.86 39.99 38.56
 39.35 40.86 41.78 42.21 42.21 41.78 40.86 39.35
 39.73 41.28 42.21 42.66 42.66 42.21 41.28 39.73
 39.73 41.28 42.21 42.66 42.66 42.21 41.28 39.73
 39.35 40.86 41.78 42.21 42.21 41.78 40.86 39.35
 38.56 39.99 40.86 41.28 41.28 40.86 39.99 38.56
 37.28 38.56 39.35 39.73 39.73 39.35 38.56 37.28
This seems to give reasonable relative values for Knight and Bishop, the Knight suffering more from being on the edge or in a corner than the Bishop. (Which seems in agreement with common wisdom.) The Rook is a bit light in comparison, probably because the move-counting method does not take into account that covering orthogonally adjacent squares conveys some extra value.

My main reason for doing this was to get an idea for the piece values in Kyoto Shogi. This is a weird game (but popular in Japan), where pieces do not have the same move always, but alternate identity on each move. E.g. a Rook after moving becomes a Pawn, and a Pawn after moving then becomes a Rook. The calculation can handle this, by calculating Rook values from future Pawn values, and vice versa.

The value in Kyoto Shogi can be very different from square to square, because pieces can get stuck: a Rook moving to last rank, turning into a Pawn, would leave that Pawn without moves, and presumably thus without value. There are even pieces that must get stuck: a Gold General alternates with a Knight, and the latter in Shogi only has its two forward-most moves. So each time the Knight moves it advances two ranks, and a Gold General can at most retreat 1 step. So in the end you will be stuck with a Knight on one of the last two ranks, where it cannot move. Such pieces thus have an 'expiration date'. This makes their value decrease sharply as they advance towards the point where they become dead wood.

For example (again with beta = 0.7, and alpha = 0.6, again rather arbitrary, but chosen lower than with the Chess pieces, because in games with drops pieces tend to live quite short before they are captured) I get the following:

Code: Select all

Silver General &#40;alternating with Bishop&#41;
  7.48  8.08  8.48  8.08  7.48
  8.90 11.00 11.07 11.00  8.90
  9.19 11.20 11.55 11.20  9.19
  9.03 11.25 11.46 11.25  9.03
  8.06  9.31  9.65  9.31  8.06

Bishop &#40;alternating with Silver General&#41;
  9.02  9.25  9.55  9.25  9.02
  9.18 10.80 11.09 10.80  9.18
  9.57 11.25 12.65 11.25  9.57
  9.25 10.95 11.34 10.95  9.25
  9.00  9.34  9.64  9.34  9.00

Gold General &#40;alternating with &#40;Shogi-&#41;Knight&#41;
  2.00  3.00  3.00  3.00  2.00
  4.42  6.35  6.38  6.35  4.42
  5.25  7.18  7.28  7.18  5.25
  6.53  8.65  8.76  8.65  6.53
  6.16  8.30  8.34  8.30  6.16

&#40;Shogi-&#41;Knight &#40;alternating with Gold General&#41;
  0.00  0.00  0.00  0.00  0.00
  0.00  0.00  0.00  0.00  0.00
  2.80  3.50  3.80  3.50  2.80
  4.81  5.24  5.81  5.24  4.81
  5.31  5.76  6.31  5.76  5.31
We see that the Knight gets worthless on the last two ranks (as expected), and that this also strongly suppresses the value of the Gold General as it advances. The Bishop-Silver alternator is a healty piece, however; it can be worth somewhat more when it is a Bishop, but even that is not true on all squares.

brianr
Posts: 346
Joined: Thu Mar 09, 2006 2:01 pm

Re: 'ab-initio' piece values

Post by brianr » Fri Mar 30, 2018 3:11 pm

Already done by Reinhard Scharnagl. I can't easily find his old web pages going thru the derivation of his values, but perhaps wayback has them.

https://chessprogramming.wikispaces.com ... 0Scharnagl

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: 'ab-initio' piece values

Post by Evert » Fri Mar 30, 2018 9:34 pm

Nice. I like this.
I have used PST-values based on the number of moves from a given square for a while; they're not particularly great though. The second term could make a big difference here, particularly for the Knight.

Some thoughts: it probably makes sense to weigh forward moves and captures (for divergent pieces) differently. This could be another free parameter of course, but you don't want too many of those.

Empirically, the value of a slider (compared to a leaper) is determined by its second or third distant square, which is probably a fair guestimate for free space on the board. I've been thinking of building a piece value model around this observation, but I haven't found the time. Have you ever looked at lame leapers? They're a bit similar to sliders.

Your rook values look ok-ish for a middle-game position. In the end game the rook gains value because of its ability to undermine the enemy pawn structure, its ability to support pawns, and its ability to harrass the enemy king (not so much because it's a king, but because that's 275cp worth of attacking power the other side has trouble activating). There are probably too few datapoints to take that into account in a reasonable way. It's of course irrelevant for games with drops.

In SjaakII I use a slightly different metric, based on how dangerous a piece is at close range. This checks the attack pattern on a 3x3 and 5x5 area around the piece and combines these linearly. There is an ad-hoc correction for colour-bound pieces. I think it's reasonable for attack weights, but it's not ideal for piece values.

User avatar
hgm
Posts: 23365
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: 'ab-initio' piece values

Post by hgm » Sat Mar 31, 2018 9:24 am

Indeed, if you only pay attention to current mobility, a Knight in a corner would only get a quarter of its value. And a move with such a Knight would then gain you half a Knight's value in PST points. That seems way too much, so 'future mobility' has to be weighted in. In Kyoto Shogi that is extra obvious, as otherwise the fact that your Rook will turn into Pawn on the next move would not suppress the value at all compared to a 'persistent' Rook.

I guess the value of alpha is related to the number of moves you expect to do with a piece. In orthodox Chess the assumption that pieces will do ~5 moves, and Pawns ~2 seems reasonable, and would lead to an average game duration of 7*5 + 8*2 = 51 moves. So using alpha=0.8 seems reasonable.

When I set beta=0.9, corresponding to a 10% filled board (6-7 pieces), as in a typical late end-game, I get the following:

Code: Select all

Bishop
 38.21 37.86 37.73 37.64 37.64 37.73 37.86 38.21
 37.86 39.78 39.69 39.69 39.69 39.69 39.78 37.86
 37.73 39.69 41.74 41.73 41.73 41.74 39.69 37.73
 37.64 39.69 41.73 43.71 43.71 41.73 39.69 37.64
 37.64 39.69 41.73 43.71 43.71 41.73 39.69 37.64
 37.73 39.69 41.74 41.73 41.73 41.74 39.69 37.73
 37.86 39.78 39.69 39.69 39.69 39.69 39.78 37.86
 38.21 37.86 37.73 37.64 37.64 37.73 37.86 38.21

Rook
 55.37 56.07 56.53 56.76 56.76 56.53 56.07 55.37
 56.07 56.80 57.27 57.51 57.51 57.27 56.80 56.07
 56.53 57.27 57.76 57.99 57.99 57.76 57.27 56.53
 56.76 57.51 57.99 58.24 58.24 57.99 57.51 56.76
 56.76 57.51 57.99 58.24 58.24 57.99 57.51 56.76
 56.53 57.27 57.76 57.99 57.99 57.76 57.27 56.53
 56.07 56.80 57.27 57.51 57.51 57.27 56.80 56.07
 55.37 56.07 56.53 56.76 56.76 56.53 56.07 55.37
This gives a much more conventional ratio of the Rook and Bishop value. And the Bishop value is likely suppressed compared to the mobility calculation, bacause of its color binding. I.e. the mobility calculation should be interpreted as the value of a paired Bishop, where the color binding is not important, because the other Bishop takes care of the other color. The Bishop now seems unrealistically strong compared to a Knight, (whose value isn't affected by beta at all), however.

What still seems to be missing is the non-linearity I find empirically in the value of leapers, as a function of their number of moves N (value = 1.1*N*(30+5/8*N) cP). The method used here gives results strictly proportional to N. This could be caused by the fact that I am just averaging over all possible future mobilities rather than adding them. If a piece attacks 8 squares now, and no matter which of the 8 I move to, would also attack 8 squares from there, there must be some value in that I can choose which move I do, to selectively attack those 8 squares for which this is most profitable. Typically the number of squares reachable in 2 moves grows non-linearly with the number of moves a piece has. E.g. a Wazir has 4 moves, and can reach 12 squares in 2 moves (3 times as many). But a Knight has 8 moves, and can reach 32 in 2 moves (4 times as many). This gets even amplified if you assume that the two-move attacks are only worth something on squares that you don't already attack with a single move; that would be 8 for the Wazir (2x), but still 32 for the Knight (as it is a color alternator, so that there is no overlap between its 1-move and 2-move attack sets). The King, who also has 8 moves, does less well in this respect: it only gets 16 new 2-move targets.

User avatar
Ovyron
Posts: 2254
Joined: Tue Jul 03, 2007 2:30 am

Re: 'ab-initio' piece values

Post by Ovyron » Sat Mar 31, 2018 11:32 am

Can your method be used to guesstimate the value from some arbitrary new piece like, say...

The Cuttlefish

Moves like a Queen.

Captures like the captured piece captures, but without abandoning its attacking squares (like in Rifle chess). Can't capture pieces that capture in a similar fashion (like Ultima's Chameleon.)

I have no idea if such a piece would have much value, considering it can't even attack pawns without being captured by them.
Make someone happy today.

User avatar
hgm
Posts: 23365
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: 'ab-initio' piece values

Post by hgm » Sat Mar 31, 2018 12:57 pm

I wouldn't expect this method to work for anything but 'regular' chess pieces, i.e. those that capture by replacement to the same squares as they can move to (when empty). Even divergent pieces (using different moves for replacement capture than for moving to empty squares) would need extra parameters for weighting the importance of their captures and non-captures. (Empirical piece-value determinations suggest the captures should be weighted twice as much.) The method as described also doesn't take into account that forward moves in general contribute more to the value than sideway and backward moves.

For more exotic pieces, such as your Cuttlefish, the only value determination I would trust would be playing games starting from a position with a material imbalance of Cuttlefish vs other material. E.g. replace a minor in the FIDE position by a Cuttlefish, have an engine self-play a few hundred games, to see if Cuttlefish does better than Knight or Bishop. If it does, delete the f-Pawn of the player with the Cuttlefish, and play a new match from that position. If the side with the minor won, delete his f-Pawn, and try again.

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: 'ab-initio' piece values

Post by Evert » Mon Apr 02, 2018 9:57 am

I've been experimenting with your value model as well and so far I really like what comes out of it.
I added in a separate weight for forward moves, and also for capture moves (although I haven't tried it on divergent pieces yet). The formula I use is:

Code: Select all

value&#91;sq&#93; = &#40;moves&#91;sq&#93; + fw*fwd_moves&#91;sq&#93;) + sum_moves weight&#91;sq&#93;&#91;to&#93;*value&#91;to&#93; 
where

Code: Select all

weight&#91;sq&#93;&#91;to&#93; = alpha * beta^&#40;1 + between&#91;sq&#93;&#91;to&#93;) * &#40;1 + fw*fwd&#91;sq&#93;&#91;to&#93;) / &#40;moves&#91;sq&#93; + fwd_moves&#91;sq&#93;).
Here fwd[sq][to] is 1 or 0 depending on whether the move from sq to to is a forward move or not, and fw is the relative weight of forward moves. I have some normalisation factors in there that don't really matter. The parameter alpha is the relative importance of future moves, while beta is the likelihood that a square is empty.

Right now, I get the following output (alpha=0.8, beta=0.7, fw = 2.0):

Code: Select all

   Knight&#58;
   average&#58; 11.29 2.82
      8.99   10.96   12.89   13.33   13.33   12.89   10.96    8.99 
      9.32   11.48   14.08   14.47   14.47   14.08   11.48    9.32 
      9.77   12.65   15.62   15.96   15.96   15.62   12.65    9.77 
      9.76   12.64   15.60   15.98   15.98   15.60   12.64    9.76 
      9.37   12.24   15.20   15.58   15.58   15.20   12.24    9.37 
      8.73   11.55   14.56   14.77   14.77   14.56   11.55    8.73 
      6.42    7.41   10.23   10.46   10.46   10.23    7.41    6.42 
      4.03    5.10    6.02    6.19    6.19    6.02    5.10    4.03 
   Bishop&#58;
   average&#58; 16.25 4.06
     17.30   18.02   18.53   18.75   18.75   18.53   18.02   17.30 
     16.40   19.86   20.25   20.45   20.45   20.25   19.86   16.40 
     15.35   18.76   21.86   22.01   22.01   21.86   18.76   15.35 
     14.16   17.50   20.60   23.53   23.53   20.60   17.50   14.16 
     12.83   16.16   19.22   22.18   22.18   19.22   16.16   12.83 
     11.44   14.68   17.78   17.86   17.86   17.78   14.68   11.44 
      9.93   13.20   13.33   13.41   13.41   13.33   13.20    9.93 
      8.47    8.63    8.77    8.83    8.83    8.77    8.63    8.47 
   Rook&#58;
   average&#58; 20.20 5.05
     23.69   23.99   24.18   24.26   24.26   24.18   23.99   23.69 
     22.83   23.13   23.31   23.39   23.39   23.31   23.13   22.83 
     21.84   22.13   22.30   22.38   22.38   22.30   22.13   21.84 
     20.74   21.01   21.18   21.26   21.26   21.18   21.01   20.74 
     19.55   19.81   19.96   20.04   20.04   19.96   19.81   19.55 
     18.27   18.51   18.65   18.72   18.72   18.65   18.51   18.27 
     16.90   17.12   17.25   17.31   17.31   17.25   17.12   16.90 
     15.42   15.61   15.73   15.78   15.78   15.73   15.61   15.42 
   Queen&#58;
   average&#58; 36.23 9.06
     40.28   41.42   42.13   42.46   42.46   42.13   41.42   40.28 
     38.66   42.64   43.33   43.67   43.67   43.33   42.64   38.66 
     36.70   40.65   44.08   44.41   44.41   44.08   40.65   36.70 
     34.49   38.39   41.80   44.84   44.84   41.80   38.39   34.49 
     32.05   35.88   39.24   42.28   42.28   39.24   35.88   32.05 
     29.41   33.14   36.46   36.66   36.66   36.46   33.14   29.41 
     26.56   30.20   30.55   30.72   30.72   30.55   30.20   26.56 
     23.52   23.98   24.28   24.42   24.42   24.28   23.98   23.52 
   King&#58;
   average&#58; 12.18 3.04
      8.75   11.68   12.13   12.17   12.17   12.13   11.68    8.75 
     10.13   14.17   14.56   14.60   14.60   14.56   14.17   10.13 
     10.28   14.33   14.74   14.78   14.78   14.74   14.33   10.28 
     10.29   14.34   14.75   14.79   14.79   14.75   14.34   10.29 
     10.27   14.32   14.73   14.77   14.77   14.73   14.32   10.27 
     10.13   14.18   14.59   14.62   14.62   14.59   14.18   10.13 
      9.27   13.31   13.62   13.65   13.65   13.62   13.31    9.27 
      4.83    6.79    7.03    7.05    7.05    7.03    6.79    4.83 
   Pawn&#58;
   average&#58; 3.88 0.97
      3.73    5.08    5.28    5.31    5.31    5.28    5.08    3.73 
      3.72    5.08    5.27    5.30    5.30    5.27    5.08    3.72 
      3.70    5.05    5.25    5.28    5.28    5.25    5.05    3.70 
      3.64    4.99    5.19    5.21    5.21    5.19    4.99    3.64 
      3.48    4.84    5.02    5.04    5.04    5.02    4.84    3.48 
      3.08    4.41    4.58    4.58    4.58    4.58    4.41    3.08 
      2.00    3.33    3.33    3.33    3.33    3.33    3.33    2.00 
      0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00 
The second number after the "average" is just a scaled version of the first number, chosen so that a Knight will typically come out as 3, for easy comparison. The only real issue is that it overvalues the Bishop quite a bit, even taking into account that this is the value for a pared Bishop. Presumably though, the Bishop should come down a bit from elephantiasis, but I don't see that dragging it down from ~4 to the ~3.2-3.3 you'd expect on this scale.
I left the pawn in the above output because I find it amusing that the value comes out so well. I once calculated the value of a pawn in a game like Sittuyin or Makruk, just using different weighting for captures and forward moves, and you get a very decent value out of that (compared to a Ferz or Wazir), so perhaps it's not so strange that it comes out ok here. I wouldn't take it too seriously though.

User avatar
hgm
Posts: 23365
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: 'ab-initio' piece values

Post by hgm » Mon Apr 02, 2018 11:36 am

I am a bit puzzled that the Bishops comes out so much higher than the Knight, at beta=0.7.

Another thought: is it really that forward moves are worth more than other moves, or could it be that this is just a consequence of that some board squares are more important than other squares? I.e. if we would award moves that hit the enemy board half more than moves that don't, wouldn't this automatically lead to forward moves contributing more value than backward moves, for pieces starting at the back rank?

Note that the 'rule' that forward moves are worth twice as much as other moves was derived by me purely from measuring empirical values of short-range leapers. For a slider, moving backwards should not hurt so much, as it can undo the effect by simply moving one step further forward on its next move.

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: 'ab-initio' piece values

Post by Evert » Mon Apr 02, 2018 11:55 am

hgm wrote:I am a bit puzzled that the Bishops comes out so much higher than the Knight, at beta=0.7.
Agreed. I couldn't find anything wrong with the code though. I'll try to figure out where this value comes from.
Note that if I disable the extra terms, I don't get exactly the same values as you posted, but the difference is small (in the last digit) and so I figured it was just due to some small unspecified detail.
Another thought: is it really that forward moves are worth more than other moves, or could it be that this is just a consequence of that some board squares are more important than other squares? I.e. if we would award moves that hit the enemy board half more than moves that don't, wouldn't this automatically lead to forward moves contributing more value than backward moves, for pieces starting at the back rank?
I suspect it's more the latter than the former. There is nothing intrinsically good about going "forward" rather than "backward", so it must have something to do with controlling squares that are important to the other side.
Note that the 'rule' that forward moves are worth twice as much as other moves was derived by me purely from measuring empirical values of short-range leapers. For a slider, moving backwards should not hurt so much, as it can undo the effect by simply moving one step further forward on its next move.
Noted.
Perhaps there is something to be said for treating sliders (riders) and leapers completely separately, but as a starting point it's still useful to try to treat them in a similar way. In a sense sliders are compound long-range lame leapers anyway, so if there is a way to treat leapers and lame leapers, it sort-of gives you sliders too.

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: 'ab-initio' piece values

Post by Evert » Mon Apr 02, 2018 8:35 pm

These piece values are not robust with respect to small changes in some of the parameters and tweaks to the definitions.
Blindly weighing forward moves as more important benefits the Bishop relative to the Rook (the Bishop has more forward moves than a rook), but weighing moves to the enemy side of the board does weird things to the King on the last three ranks and Knights on the back rank (where all moves are on the enemy side).

Post Reply