Material imbalance/bad trade and borrowing code

[Evert]

Given the fascination a large number of people here seem to have with copying someone else's code, I thought I'd ask about the following.

I've read various discussions on what base values should be used for the pieces and how one should deal with material imbalances. One approach is to make a huge table, indexed by piece counts from both sides and filling it up with appropriate values. That obviously lets you tune any sort of material imbalance you care to think about and it saves some special purpose code to detect material imbalances that change with, say, the number of pawns on the board.
At the same time, such a table is a bit opaque to me with respect to what's actually happening for any particular combination of material, and it doesn't seem like it's the sort of thing that should be necessary. I also don't have the resources to compile such a table for myself. In other words, I prefer to do something different.

I've seen people argue that rather than the more canonical 100/300/300/500/900 piece values, computer programs are better off using something like 100/400/400/600/1200. With these piece values, a minor for three pawns is calculated as a bad trade and it preserves exchange = two pawns and three minors = two rooks = one queen from the canonical values. That's useful, but at the same time, I don't really like the idea that much.

Enter the "bad trade" idea as implemented in Crafty. Superficially, this does more or less the same thing: by looking at the adjacent elements to the material balance, it effectively changes the value of a rook to 604 and the value of a minor to 413. Changing the base value of the pieces to those and recalculating would change the remaining elements of the table to be in the range 5-76 if we ignore the saturated elements far from the diagonal. So what it does is actually not very different from changing the piece values to the 100/400/400/600 scale. Nevertheless, I like this idea more because it seems a bit more clear what is going on.

So here's the question: I would like to use something similar in my own code, because I like the idea. However, there isn't much variation in how you could implement this (it's basically a 2-dimensional array indexed by number of minors and number of majors). At a stretch, it's possible to guess/calibrate the values in the table so they're different from the ones that are actually used in Crafty (which are probably not optimal for another program anyway), but that's about it as far as I can see.
To what extend is implementing this idea, inspired by Crafty, considered to be "copying"? Bearing in mind that any independent implementation is not going to be substantially different from the implementation in Crafty.

For reference, the relevant table in Crafty is this:

Code: Select all

/*
   This array is indexed by rook advantage and minor piece advantage.
   rook advantage is 4 + white rook equivalents - black rook equivalents 
   where a rook equivalent is number of rooks + 2 * number of queens.
   minor piece advantage is 4 + white minors - black minors.  

   The classic bad trade case is two minors for a rook.  If white trades
   two minors for a rook, rook advantage is +5 and minor advantage is +2.
   imbalance[5][2] gives a penalty of -42 for this trade.
*/
int imbalance[9][9] = {
/* n=-4  n=-3  n=-2  n=-1   n=0  n=+1  n=+2  n=+3 +n=+4 */
  {-126, -126, -126, -126, -126, -126, -126, -126,  -42 }, /* R=-4 */
  {-126, -126, -126, -126, -126, -126, -126,  -42,   42 }, /* R=-3 */
  {-126, -126, -126, -126, -126, -126,  -42,   42,   84 }, /* R=-2 */
  {-126, -126, -126, -126, -104,  -42,   42,   84,  126 }, /* R=-1 */
  {-126, -126, -126,  -88,    0,   88,  126,  126,  126 }, /*  R=0 */
  {-126,  -84,  -42,   42,  104,  126,  126,  126,  126 }, /* R=+1 */
  { -84,  -42,   42,  126,  126,  126,  126,  126,  126 }, /* R=+2 */
  { -42,   42,  126,  126,  126,  126,  126,  126,  126 }, /* R=+3 */
  {  42,  126,  126,  126,  126,  126,  126,  126,  126 }  /* R=+4 */
};

[michiguel]

Given the fascination a large number of people here seem to have with copying someone else's code, I thought I'd ask about the following.

I've read various discussions on what base values should be used for the pieces and how one should deal with material imbalances. One approach is to make a huge table, indexed by piece counts from both sides and filling it up with appropriate values. That obviously lets you tune any sort of material imbalance you care to think about and it saves some special purpose code to detect material imbalances that change with, say, the number of pawns on the board.
At the same time, such a table is a bit opaque to me with respect to what's actually happening for any particular combination of material, and it doesn't seem like it's the sort of thing that should be necessary. I also don't have the resources to compile such a table for myself. In other words, I prefer to do something different.

I've seen people argue that rather than the more canonical 100/300/300/500/900 piece values, computer programs are better off using something like 100/400/400/600/1200. With these piece values, a minor for three pawns is calculated as a bad trade and it preserves exchange = two pawns and three minors = two rooks = one queen from the canonical values. That's useful, but at the same time, I don't really like the idea that much.

Enter the "bad trade" idea as implemented in Crafty. Superficially, this does more or less the same thing: by looking at the adjacent elements to the material balance, it effectively changes the value of a rook to 604 and the value of a minor to 413. Changing the base value of the pieces to those and recalculating would change the remaining elements of the table to be in the range 5-76 if we ignore the saturated elements far from the diagonal. So what it does is actually not very different from changing the piece values to the 100/400/400/600 scale. Nevertheless, I like this idea more because it seems a bit more clear what is going on.

So here's the question: I would like to use something similar in my own code, because I like the idea. However, there isn't much variation in how you could implement this (it's basically a 2-dimensional array indexed by number of minors and number of majors). At a stretch, it's possible to guess/calibrate the values in the table so they're different from the ones that are actually used in Crafty (which are probably not optimal for another program anyway), but that's about it as far as I can see.
To what extend is implementing this idea, inspired by Crafty, considered to be "copying"? Bearing in mind that any independent implementation is not going to be substantially different from the implementation in Crafty.

For reference, the relevant table in Crafty is this:

Code: Select all

/*
   This array is indexed by rook advantage and minor piece advantage.
   rook advantage is 4 + white rook equivalents - black rook equivalents 
   where a rook equivalent is number of rooks + 2 * number of queens.
   minor piece advantage is 4 + white minors - black minors.  

   The classic bad trade case is two minors for a rook.  If white trades
   two minors for a rook, rook advantage is +5 and minor advantage is +2.
   imbalance[5][2] gives a penalty of -42 for this trade.
*/
int imbalance[9][9] = {
/* n=-4  n=-3  n=-2  n=-1   n=0  n=+1  n=+2  n=+3 +n=+4 */
  {-126, -126, -126, -126, -126, -126, -126, -126,  -42 }, /* R=-4 */
  {-126, -126, -126, -126, -126, -126, -126,  -42,   42 }, /* R=-3 */
  {-126, -126, -126, -126, -126, -126,  -42,   42,   84 }, /* R=-2 */
  {-126, -126, -126, -126, -104,  -42,   42,   84,  126 }, /* R=-1 */
  {-126, -126, -126,  -88,    0,   88,  126,  126,  126 }, /*  R=0 */
  {-126,  -84,  -42,   42,  104,  126,  126,  126,  126 }, /* R=+1 */
  { -84,  -42,   42,  126,  126,  126,  126,  126,  126 }, /* R=+2 */
  { -42,   42,  126,  126,  126,  126,  126,  126,  126 }, /* R=+3 */
  {  42,  126,  126,  126,  126,  126,  126,  126,  126 }  /* R=+4 */
};

In general, I find this table approach difficult to maintain (not to mention the memory it could consume).

I have several rules to estimate the material imbalance. This could become slow, but I use a hash table and the calculation becomes virtually free.

Miguel

[hgm]

I heard from Bob that Crafty has abandoned this bad-trade business, if I did not misunderstand him.

As I am mostly interested in variants, there is no way to make a material table based on empercal data from human games, so I usually rely on filling the table with formulas made up by educated guessing, and interpolation of extreme cases. E.g. to fit the fact that 3 Queens balance between 6 and 7 Knights, it is clear that you either need terms that are non-linear in the number of Queens and Knights, or cross terms between Queens and opposing Knights. And probably a bit of both. You can also include terms that encourage trading pieces when you have a winning advantage, and encourage trading Pawns when you have a losing disadvantage, etc. You can in general discount advantages with imbalances (e.g. if Queen balances exactly 3 minors, 2R+2B+N vs 2R+2B (a plain Knight advantage) should be better than 2R+Q vs 2R+2B) based on the assumption that unequal material makes the result more unpredictable.

In stead of an exhaustive table, which you initialie using formulas at startup, you could make it a hash table that you update during search. Such material hash has extremely high hit rate.

[bob]

I heard from Bob that Crafty has abandoned this bad-trade business, if I did not misunderstand him.

As I am mostly interested in variants, there is no way to make a material table based on empercal data from human games, so I usually rely on filling the table with formulas made up by educated guessing, and interpolation of extreme cases. E.g. to fit the fact that 3 Queens balance between 6 and 7 Knights, it is clear that you either need terms that are non-linear in the number of Queens and Knights, or cross terms between Queens and opposing Knights. And probably a bit of both. You can also include terms that encourage trading pieces when you have a winning advantage, and encourage trading Pawns when you have a losing disadvantage, etc. You can in general discount advantages with imbalances (e.g. if Queen balances exactly 3 minors, 2R+2B+N vs 2R+2B (a plain Knight advantage) should be better than 2R+Q vs 2R+2B) based on the assumption that unequal material makes the result more unpredictable.

In stead of an exhaustive table, which you initialie using formulas at startup, you could make it a hash table that you update during search. Such material hash has extremely high hit rate.

No. We abandoned the old fixed-case approach that said things like rook vs 2 minors is a bad trade for the side giving up 2 minors for a rook, or queen vs 3 minors is bad for the side giving up 3 minors for the queen. We now do it much more generally with the material imbalance table quoted above... Which seems to work pretty well. Tracy did this about 2-3 years ago if I remember correctly...

[Gian-Carlo Pascutto]

You could, like, just ask Bob Hyatt politely, you know?

[bob]

You could, like, just ask Bob Hyatt politely, you know?[/quote

Didn't think his post was impolite. But I noticed I did not answer it.

This "idea" is not a new one. And like all evaluation terms, I am afraid that if someone copies it directly, it will be significantly sub-optimal for their program. We did a lot of tuning to settle on the numbers we are using.

There are two parts to the code, one is a simple reference to the array/table using the two material imbalance terms that show which side has more of what or less of what (say +2 minors, -1 major, a rook for two minors exchange). That is such a simple bit of code no one could complain about that being copied at all. ie, "score += imbalance[majors][minors]. The table is also pretty simple and small enough to be irrelevant to the copying issue, IMHO. Particularly given that the numbers probably will only work well using the other numbers in Crafty's eval, of which there are hundreds...

It would be more of a problem if this was just one of many things that is copied, of course. But for this piece of code, where the table is 10 lines or so, + one line of executable code, I would not see a problem...

[Roman Hartmann]

You might want to read the following postings/links dealing with material imbalances in full depth:

http://www.talkchess.com/forum/viewtopic.php?t=18240

http://www.ascotti.org/programming/chess/mat_stats.html

Roman

[Gian-Carlo Pascutto]

You could, like, just ask Bob Hyatt politely, you know?

Didn't think his post was impolite.

For sure not, didn't want to imply that.

I was pretty sure you would be OK with what he is asking and wanted to point out that all the wondering about the "copying" could be easily avoided.

[jdart]

I used to have a fair amount of logic for this but I took most of it out just in favor of changing piece values. So for example Knight/Bishop now have values >3 pawns, which both helps more correctly evaluate the exchange (Rook for minor) and also discourages trading 3 pawns for a minor (generally bad). I'm sure I could do better with a more elaborate table lookup but I've actually noticed fewer bad trades since making this change - since I think the older code still had holes in it, despite covering many common cases.

--Jon

[Evert]

As I am mostly interested in variants, there is no way to make a material table based on empercal data from human games, so I usually rely on filling the table with formulas made up by educated guessing, and interpolation of extreme cases. E.g. to fit the fact that 3 Queens balance between 6 and 7 Knights, it is clear that you either need terms that are non-linear in the number of Queens and Knights, or cross terms between Queens and opposing Knights. And probably a bit of both. You can also include terms that encourage trading pieces when you have a winning advantage, and encourage trading Pawns when you have a losing disadvantage, etc. You can in general discount advantages with imbalances (e.g. if Queen balances exactly 3 minors, 2R+2B+N vs 2R+2B (a plain Knight advantage) should be better than 2R+Q vs 2R+2B) based on the assumption that unequal material makes the result more unpredictable.

I've wondered about variants as well, but it gets complicated by me wanting a generic evaluation function with weights for certain features that the program gets to sort out for itself based on a set of heuristics. No clear idea on how to make that work in general though.
At the moment, I test whether pieces are colour bound (or mainly colour bound) and give a bonus for having a pair, that could probably be generalised to a more general concept of colour weakness. But a more general evaluation of material imbalances for arbitrary pieces I'm not sure how to do.
I read recently (I don't remember where exactly, though I can probably find it) that a Ferz is slightly stronger than a Wazir despite being colour bound because it has two forward moves rather than one. That's not very intuitive to me.

In stead of an exhaustive table, which you initialie using formulas at startup, you could make it a hash table that you update during search. Such material hash has extremely high hit rate.

I've always wondered about that. At first glance it always seemed to me that calculating the hash signature and doing the table lookup would be more expensive than evaluating the imbalance. Obviously depends on how extensive the evaluation is. I'll have a look at that.