Material imbalance/bad trade and borrowing code

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Evert
Posts: 2924
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Material imbalance/bad trade and borrowing code

Post by Evert » Sun Jan 30, 2011 4:34 pm

Roman Hartmann wrote: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
Cool, very interesting!
Thanks.

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

Re: Material imbalance/bad trade and borrowing code

Post by Evert » Sun Jan 30, 2011 4:58 pm

bob wrote: 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...
Thanks. :)
So, a few questions about the tuning that goes into that table.
Clearly, because of symmetry, only half of the numbers in the table are independent. The majority of the numbers are saturated at +/-126, but of course it doesn't matter when R=+2, n=0. Quite apart from the fact that you're never going to take 10 pawns to make up the nominal 1000 points of difference, the imbalance is large enough that it's probably decisive. The interesting elements are those that are supposedly near equal. The off-equal elements R=+/-1,n=0 and n=+/-1,R=0 effectively modify the value of a single rook or single minor with respect to pawns (to rook~600, minor~400). Apart from those, there are 9 numbers left, 7 of which (including those along the diagonal) are +/-42 and and two (that put rooks against a superior number of minor pieces) are +/-84.
Which of those numbers were tested and tuned most thoroughly? I would expect the block immediately besides R=n=0 and the R=+/-2/n=-/+3 combinations, is that correct?

Just trying to get a feel for where I'd start if I wanted to re-tune some of those numbers, since I don't have the computational resources (not for computer chess anyway) to vary all of them extensively.
I'll probably take the fact that the modified rook/minor vs. pawns value come out at 600/400 as a hint that this value is fairly good, since it seems to work well across a number of different chess programs, and try varying the other elements of the table first.
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...
Thanks again. :)
It's one thing to look at someone else's code (or description) and re-use an idea that's interesting, but I never really understood the point in copying other people's code verbatim. Technical complications aside, it doesn't seem any fun to me...

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

Re: Material imbalance/bad trade and borrowing code

Post by Evert » Sun Jan 30, 2011 5:05 pm

Gian-Carlo Pascutto wrote: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.
It's something a lot of people get very worked up about though (which is fair enough); clearly there's a line somewhere that says what is ok and what isn't.
I was also fairly sure on which side of that line this would fall (especially since it's about the idea more than the code), but I wanted to make sure and maybe get a more general idea of what people consider acceptable and what not.

bob
Posts: 20643
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Material imbalance/bad trade and borrowing code

Post by bob » Sun Jan 30, 2011 5:15 pm

Evert wrote:
bob wrote: 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...
Thanks. :)
So, a few questions about the tuning that goes into that table.
Clearly, because of symmetry, only half of the numbers in the table are independent. The majority of the numbers are saturated at +/-126, but of course it doesn't matter when R=+2, n=0. Quite apart from the fact that you're never going to take 10 pawns to make up the nominal 1000 points of difference, the imbalance is large enough that it's probably decisive. The interesting elements are those that are supposedly near equal. The off-equal elements R=+/-1,n=0 and n=+/-1,R=0 effectively modify the value of a single rook or single minor with respect to pawns (to rook~600, minor~400). Apart from those, there are 9 numbers left, 7 of which (including those along the diagonal) are +/-42 and and two (that put rooks against a superior number of minor pieces) are +/-84.
Which of those numbers were tested and tuned most thoroughly? I would expect the block immediately besides R=n=0 and the R=+/-2/n=-/+3 combinations, is that correct?

Main cases were +/-1 minor, which is knight/bishop vs 3 pawns sort of issue, then R vs 2 minors (bad for R) and Q vs 3 minors (bad for Q). There is also the R=1, minor=-1 (exchange) that was tested thoroughly. We then just folded those values into the table, because the table is faster than a bunch of if-tests...




Just trying to get a feel for where I'd start if I wanted to re-tune some of those numbers, since I don't have the computational resources (not for computer chess anyway) to vary all of them extensively.
I'll probably take the fact that the modified rook/minor vs. pawns value come out at 600/400 as a hint that this value is fairly good, since it seems to work well across a number of different chess programs, and try varying the other elements of the table first.
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...
Thanks again. :)
It's one thing to look at someone else's code (or description) and re-use an idea that's interesting, but I never really understood the point in copying other people's code verbatim. Technical complications aside, it doesn't seem any fun to me...
I agree completely. But obviously there are plenty that don't, based on the number of clones/derivatives that exist.

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

Re: Material imbalance/bad trade and borrowing code

Post by hgm » Wed Feb 09, 2011 6:47 pm

In Spartacus I incrementally update a material index, which is intended to index a material table containing the non-additive parts of the material evaluation. Such as the Bishop pair bonus (currently the only thing in the table), and a bonus for simplifying when ahead. Other things that could be put in there are this bad-trade business, discounting of a material advantage when you have no Pawns, discounting of material advantages that have no mating potential (e.g. KBK = 0 = KNNK).

The problem is that I have to tinker a bit with the index, to prevent the table from becoming excessively large. Rather than 'perfect hashing', which would define a 1:1 mapping between all possible material combinations and integers, I would be satisfied with a kind of 'magic' mapping that maps cases that have to be treated similarly (i.e. receive the same discount or bonus) to the same index. And I would not be concerned at all if extremey imbalanced material combinations, where the game is aready totally decided, would map wrongly.

Because of the Bishop pair I am kind of forced to make an exact count of the number of Bishops for each side (0, 1 or 2, as Spartacus does not consider underpromotion to Bishop). I can do that by counting 1 for each white Bishop, and 3 for each black one, for 9 possibilities. I aso have to count Pawns (to make sure I detect the loss of the last one), 0-10, so 11 possibilities for each side. That already makes 9x121 = 1089 in total.

To implement a trading gradient, the index must be sensitive to total amount of material. I can use a count for that which counts N=R=1 and Q=A=C=2. Pawns and Bishops are already counted explicitly, and do not have to be incorporated. So the count can run up to 10 for each side (2N+2R+Q+A+C), 21 possibilities in total.

Finally, to decide on the sign of the discount, the index must be sensitive to who has the advantage. For this I could use an index that counts imblances; minors as 3, R=5 and A=C=Q=10. Then each index value can only be obtained in a very limited number of ways:

0 = equal or RR-Q (or RR-C or C-A etc.; for Q below also read C or A)
1 = BB/BN/NN-R or Q/RR-BBN/BNN
2 = R-B/N (the exchange)
3 = B/N-nothing (a minor)
4 = BBN/BNN-R
5 = R-nothing or Q-R (a Rook)
6 = BB/BN/NN-nothing (two minors)
7 = Q/RR-B/N

Of course it can also be negative, if black has the advantage. Larger advantages would no longer be meaningful. So the index would run from -7 to 7, 15 possibilites.

The material table could then conceptually be seen as a multi-dimensional array matTab[whiteP][blackP][whiteB][blackB][totalMaterial][advantage]. The size would be 3x3x11x11x21x15 ~ 350kB. The order of theindicescould be chosen such that extreme advantges would overflow into entries with a different number of Pawns.

'Bad trade' cases, like minor for 3 Pawns or 2 minors vs R+P can be easily distinguished from simple cases like being an exchange ahaed, and can receive a penalty.

Post Reply