Evaluation of material imbalance (a Rybka secret?)

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.
Alessandro Scotti

Evaluation of material imbalance (a Rybka secret?)

Post by Alessandro Scotti » Thu Dec 06, 2007 9:21 pm

Like many, I think, I have often wondered what could be the secrets of Rybka. One particular feature that was often hinted at and seems to be indirectly confirmed by the fact that Larry is now part of Rybka's team, is the precise evaluation of material imbalances.
The original article by Larry Kaufman, a highly recommended reading, is here:

http://mywebpages.comcast.net/danheisma ... alance.htm

A short while ago, I decided to do some investigation on my own and tried to reproduce Kaufman's experiment, but this time with the help of some tool. For me, modifying Kiwi was an obvious choice since I know the code well and Kiwi includes a robust PGN parser.

What I'm trying to do: analyze and collect data for material imbalances over a large collection of games, and use the data for... something! :-) Ideally, a chess engine will use the data to properly evaluate the material situation on the board, rather than relying on values that are good but only "on average".

But first, the data. I have put everything on this page:

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

Interpreted data, statistics and source code. Sorry to put on external link but the HTML page alone is well over 100K.

Now for the help request! :-) I have several questions...
1) what do you think of this approach?
2) can you spot some mistake or need more information?
3) if the approach is good, what could be a good way for an engine to use this data?

Of course all of this is free to use in any engine, I really hope we can make this approach work!

Karlo Bala
Posts: 300
Joined: Wed Mar 22, 2006 9:17 am
Location: Novi Sad, Serbia

Re: Evaluation of material imbalance (a Rybka secret?)

Post by Karlo Bala » Thu Dec 06, 2007 10:04 pm

Alessandro Scotti wrote:Like many, I think, I have often wondered what could be the secrets of Rybka. One particular feature that was often hinted at and seems to be indirectly confirmed by the fact that Larry is now part of Rybka's team, is the precise evaluation of material imbalances.
The original article by Larry Kaufman, a highly recommended reading, is here:

http://mywebpages.comcast.net/danheisma ... alance.htm

A short while ago, I decided to do some investigation on my own and tried to reproduce Kaufman's experiment, but this time with the help of some tool. For me, modifying Kiwi was an obvious choice since I know the code well and Kiwi includes a robust PGN parser.

What I'm trying to do: analyze and collect data for material imbalances over a large collection of games, and use the data for... something! :-) Ideally, a chess engine will use the data to properly evaluate the material situation on the board, rather than relying on values that are good but only "on average".

But first, the data. I have put everything on this page:

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

Interpreted data, statistics and source code. Sorry to put on external link but the HTML page alone is well over 100K.

Now for the help request! :-) I have several questions...
1) what do you think of this approach?
2) can you spot some mistake or need more information?
3) if the approach is good, what could be a good way for an engine to use this data?

Of course all of this is free to use in any engine, I really hope we can make this approach work!
Excellent work!!!
I tried something similar by hand and found that it is too painful. I think that only missing thing is material correction for corresponding imbalance.
Abs(X) ~ mat + Correction(mat)
Best Regards,
Karlo Balla Jr.

Laszlo Gaspar
Posts: 64
Joined: Thu Mar 09, 2006 10:07 am
Location: Budapest, Hungary

Re: Evaluation of material imbalance (a Rybka secret?)

Post by Laszlo Gaspar » Fri Dec 07, 2007 7:03 am

Nice work, Alessandro! I will try to use your data in my program and report the result.

Thank you!
Regards,
László

User avatar
Ross Boyd
Posts: 114
Joined: Wed Mar 08, 2006 8:52 pm
Location: Wollongong, Australia
Contact:

Re: Evaluation of material imbalance (a Rybka secret?)

Post by Ross Boyd » Fri Dec 07, 2007 8:44 am

Hi Alessandro,

Nice work!

I'm attempting to do a similar thing in TRACE 2.

So far I have the internal structure in place which I call MIM... Material Imbalance Matrix.

It is basically an array indexed by the number of pieces of each type and colour.

The array covers all the usual combinations of pieces/pawns.
There can be 0 to 8 pawns for either side.
WN,WB,WR,WQ,BN,BB,BR and BQ are limited to a max of 2 - to keep the array size reasonable - otherwise it just returns MIM_UNKNOWN and I let the eval handle it impartially.

The array is by nature symmetrically redundant for white and black - I haven't yet worked out how to take best advantage of this fact - and thus reduce the memory/cache overhead. (I think you would solve this issue quickly.)

Each individual record contains:
1. a favourability factor (this is the 'hard to tune' part)
2. a recognizer constant eg KNNKP, KPPKP - so I can directly call a custom eval routine for simple endings.
3. who can win flags... to recognize dead draws and/or draw boundaries
4. a drawishness factor.

I don't keep track of bishop square colour yet although I know I should as this is very important in material imbalances. But, its 'early days', and its not hard to modify the structure to include it.

Its kind of funny that we have worked in exact reverse - you have completed the PGN analysis and I've done the internal representation.
We were collaborating without knowing it :D

I don't normally share code (because people would laugh at it) but you are welcome to my mim.h and mim.cpp modules. Just drop me a line.

BTW, my wife Trace ___loved___ her trip to Italy in April this year - love is just not a strong enough word, I have the photos to prove it... we are now both bonified Limoncello aholics. Anyway! Back on topic....

Conceptually, MIM should work well as long as the eval doesn't duplicate the effects of the material imbalances... ie. by applying bonuses twice by mistake... for example the two bishops would already be rewarded in the mim favourability factor...

As to your questions...
Now for the help request! Smile I have several questions...
1) what do you think of this approach?
2) can you spot some mistake or need more information?
3) if the approach is good, what could be a good way for an engine to use this data?
1. I think you are a genius. :D
2. Maybe human GM games would be a more reliable source of MI knowledge. Maybe not.
3. As mentioned, the MIM matrix would be a brilliant approach, sublime for its simplicity, excellent for its elegance, and ingenious for its ingenuity.

Erm, yes, I'm a complete idiot at the best of times.

Hope this helps you, cheers!

Ross

Harald Johnsen

Re: Evaluation of material imbalance (a Rybka secret?)

Post by Harald Johnsen » Fri Dec 07, 2007 9:58 am

Nice work Alessandro !
Alessandro Scotti wrote:Now for the help request! :-) I have several questions...
3) if the approach is good, what could be a good way for an engine to use this data?
Convert the probability back to a material value :

Code: Select all

abs_X = lookup_table[material_signature];
new_material_value = (abs_X - 0.5) * queen_value;

Et voila.

HJ.

mjlef
Posts: 1420
Joined: Thu Mar 30, 2006 12:08 pm
Contact:

Re: Evaluation of material imbalance (a Rybka secret?)

Post by mjlef » Fri Dec 07, 2007 11:24 am

Alessandro Scotti wrote:Like many, I think, I have often wondered what could be the secrets of Rybka. One particular feature that was often hinted at and seems to be indirectly confirmed by the fact that Larry is now part of Rybka's team, is the precise evaluation of material imbalances.
The original article by Larry Kaufman, a highly recommended reading, is here:

http://mywebpages.comcast.net/danheisma ... alance.htm

A short while ago, I decided to do some investigation on my own and tried to reproduce Kaufman's experiment, but this time with the help of some tool. For me, modifying Kiwi was an obvious choice since I know the code well and Kiwi includes a robust PGN parser.

What I'm trying to do: analyze and collect data for material imbalances over a large collection of games, and use the data for... something! :-) Ideally, a chess engine will use the data to properly evaluate the material situation on the board, rather than relying on values that are good but only "on average".

But first, the data. I have put everything on this page:

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

Interpreted data, statistics and source code. Sorry to put on external link but the HTML page alone is well over 100K.

Now for the help request! :-) I have several questions...
1) what do you think of this approach?
2) can you spot some mistake or need more information?
3) if the approach is good, what could be a good way for an engine to use this data?

Of course all of this is free to use in any engine, I really hope we can make this approach work!
Great data. My program has had a kind of material imbalance array since the early 1990s...but deciding what to put in the array is the hard part!

One question: does "count"refer to the number of games where a material signature was found, or the number of total postions it was found in? Example. lets say it got down to KRP vs KR, and this happened 50 times in a row in the same game, does that count 50 times, or just once for that game? One more question: material difference seem to set the bishop pair at 50, is that right?

If anyone makes a comma delimeted version for easier import into other stats programs, I would like a copy. Otherwise I will make one myself tonight.

As a method of using this stuff, a simple linear fit of the averages (win probabilities versus "classic" materail imbalance) is a good start. Then you can just take the slope of the line (how match material is worth how much of a win percentage change). Then for any data points off the line, you can calculate a fractional material difference to correct for the varying win percentage. A quick look at the date says -300 is close ot a win percentage of 0, and +300 a win percenatge of 300. So a 1% win percentage change is about 6/100th a pawn. If I can feed this all into a spreadsheet I could make some pretty useful stuff of this. In fact, I have also been gathering very similar percentages.

Mark

User avatar
Steve Maughan
Posts: 1061
Joined: Wed Mar 08, 2006 7:28 pm
Location: Florida, USA
Contact:

Re: Evaluation of material imbalance (a Rybka secret?)

Post by Steve Maughan » Fri Dec 07, 2007 1:54 pm

Harald,
Harald Johnsen wrote: Convert the probability back to a material value :

Code: Select all

abs_X = lookup_table[material_signature];
new_material_value = (abs_X - 0.5) * queen_value;
So you're saying that a material advantage of a queen has a probability of winning of 100%? It's probably a good starting point but intuitively it seems a little high. Having watched thousand of comp v comp games over the years there are *very* few that end in a draw when one side shows a score of >+4.00 pawns. So I would start at a value of 6 pawns.

When I think about it couldn't someone zip through a couple of million games and get an idea of the winning probability distribution as a function of material difference? We could then make a better estimate of the scaling for Harald's formula.

Best regards,

Steve

Harald Johnsen

Re: Evaluation of material imbalance (a Rybka secret?)

Post by Harald Johnsen » Fri Dec 07, 2007 4:32 pm

That was just a simple start. Note that it's not a queen value but only one half (around 5 pawns) since the probability is between 0 and 1. Nearly what you suggest indeed.

HJ.

Edit:
if you don't fully trust the statistics (or are nervous of using the oracle as is) you can also use an average between the real material value and the one that comes from the statistic tables.

Alessandro Scotti

Re: Evaluation of material imbalance (a Rybka secret?)

Post by Alessandro Scotti » Fri Dec 07, 2007 6:44 pm

Karlo Bala wrote:I think that only missing thing is material correction for corresponding imbalance.
Abs(X) ~ mat + Correction(mat)
Hi Karlo, yes that's missing but I still don't know how to relate abs(X) to mat! :?

Alessandro Scotti

Re: Evaluation of material imbalance (a Rybka secret?)

Post by Alessandro Scotti » Fri Dec 07, 2007 6:53 pm

Ross Boyd wrote:I'm attempting to do a similar thing in TRACE 2.

So far I have the internal structure in place which I call MIM... Material Imbalance Matrix.
Hi Ross, nice to hear from you! MIM sounds good... I have something similar in Hamsters and I think the best approach to this is the one used in Fruit, i.e. a small hash table indexed by material. This table basically contains MIM entries and avoids the need for a large table, while still adding little overhead to the program (both in terms of memory and CPU).
Ross Boyd wrote: 2. Maybe human GM games would be a more reliable source of MI knowledge. Maybe not.
3. As mentioned, the MIM matrix would be a brilliant approach, sublime for its simplicity, excellent for its elegance, and ingenious for its ingenuity.
2. The statistics could definitely use more quality games, I'll try to add what I find around...
3. Agreed! :-)

P.S. Drop me a note next time you come to Italy, even if we remain strictly in the same domain Limoncello is only the tip of the iceberg! :D

Post Reply