Evaluation of material imbalance (a Rybka secret?)

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

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

Post by Alessandro Scotti » Sat Dec 08, 2007 10:35 pm

diep wrote:hi Scotti, If you're so interested, why don't you do it the Frans Morsch/Chrilly Donninger way?
Hi Vincent,
and what would be the point of going that way?!? :?

User avatar
pedrox
Posts: 995
Joined: Fri Mar 10, 2006 5:07 am
Location: Basque Country (Spain)
Contact:

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

Post by pedrox » Sun Dec 09, 2007 8:23 am

mjlef wrote:
diep wrote:hi Scotti, If you're so interested, why don't you do it the Frans Morsch/Chrilly Donninger way?

Vincent
What is the "Frans Morsch/Chrilly Donninger way"? I am sorry if I missed something.
Perhaps refers to look at the code assembly other programs?

Thomas Gaksch

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

Post by Thomas Gaksch » Tue Dec 11, 2007 1:43 pm

Hi Alessandro!
wow, great work. I think your research is a very good starting point.
I personally believe that Rybka and/or Fritz are going one step further. I think they have not only informations about the "pure" material imbalance but additional informations about the pawn structure (or something else). For example you have calculated the probability of the RPP against RPP (rel(w)=1.02, abs(w)=0.51, rel(X)=1.00, abs(X)=0.50, mat=0, count=4156, R=1.00 / RPP rpp ()) as a draw. But if white for example has a double pawn and black has a connected passed pawn then the probability that black wins is much greater. So if it would be possible to calculate such relations and store them in a big hashtable it would be a great improvement for the evaluation.

Thomas

Edmund
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

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

Post by Edmund » Tue Dec 11, 2007 4:44 pm

Thomas Gaksch wrote:Hi Alessandro!
wow, great work. I think your research is a very good starting point.
I personally believe that Rybka and/or Fritz are going one step further. I think they have not only informations about the "pure" material imbalance but additional informations about the pawn structure (or something else). For example you have calculated the probability of the RPP against RPP (rel(w)=1.02, abs(w)=0.51, rel(X)=1.00, abs(X)=0.50, mat=0, count=4156, R=1.00 / RPP rpp ()) as a draw. But if white for example has a double pawn and black has a connected passed pawn then the probability that black wins is much greater. So if it would be possible to calculate such relations and store them in a big hashtable it would be a great improvement for the evaluation.

Thomas
The Database would probably become quite big:

Already just Material would take a database with
(3*3*3*3*9)^2 = 531.441 Entries

*2 ^2 if you want to store for each color whether it has connected pawns

and another

*2 ^2 if you want to store for each color whether it has passed pawns

= 8.503.056


... well ok .. if it just takes 1 byte per position, a 8 MB Hash-table would be possible.

But there are some other factors to be considered as well, parts of which have been mentioned in this thread before (e.g. square color of Bishops, pawn advance, pawns connected)

Thomas Gaksch

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

Post by Thomas Gaksch » Tue Dec 11, 2007 7:19 pm

Hello Edmund,
i am just doing a little bit brainstorming. Nothing is really elaborated.
First of all i think the information must not be perfect. This hashtable is not a bitbase or tablebase where you have for every position the exact information if you win/lose or draw. It only should give a probability so i think some informations could be missing (e.g. pawn advance....). The search function of an engine can compensate this lack of information. And if you would be able to consider all factors you would have the perfect information and engine and that is still not possible.
You can reduce the size of the hastable if you store only "positions" (or should i say "relations of pieces") which are not clearly won/lost or draw. Furthermore you can only store endgame "positions" with 6-10 pieces.
But that is only blindfold brainstorming. I have no idea if this could be done in practice.

Thomas

Edmund
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

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

Post by Edmund » Tue Dec 11, 2007 8:13 pm

You are right .. some information can be compensated by the evaluation function. But obviously, the more acurate the information in the tables is, the smaller and faster can be this function.

I think it would be better in this case to build a tablebase like database. A hashtable would not be so efficient (would require more space, due to the index - ca. 4 Byte extra per entry). Maybe we can rather find a nice index-scheme, to only store relevant(which are not clearly won/lost) piece configurations.

I like your point on the endgame positions. The Information in the tables will be much more acurate for positions with less pieces on the board, than in the starting positions, where it is all about development and not so much about material advantage.

Edmund

Thomas Gaksch

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

Post by Thomas Gaksch » Tue Dec 11, 2007 11:15 pm

Hello Edmund,
it would be great if someone (eventually you) could do some research concerning this topic. Tablebases and bitbases are very nice, but it is profen that they do not help very much in playing strength. Except you are able to produce 10 men bitbases :-)

Thomas

Alessandro Scotti

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

Post by Alessandro Scotti » Wed Dec 12, 2007 11:21 am

Thomas Gaksch wrote:Hi Alessandro!
wow, great work. I think your research is a very good starting point.
I personally believe that Rybka and/or Fritz are going one step further. I think they have not only informations about the "pure" material imbalance but additional informations about the pawn structure (or something else). For example you have calculated the probability of the RPP against RPP (rel(w)=1.02, abs(w)=0.51, rel(X)=1.00, abs(X)=0.50, mat=0, count=4156, R=1.00 / RPP rpp ()) as a draw. But if white for example has a double pawn and black has a connected passed pawn then the probability that black wins is much greater. So if it would be possible to calculate such relations and store them in a big hashtable it would be a great improvement for the evaluation.
Hi Thomas,
I'm not sure those exceptions can be properly analyzed in a statistical way, unless the number of games sampled is really huge (or some method is used to produce more samples for the "interesting" configurations). Some experts in statistics would be able to answer better though, when I first heard of Monte Carlo I could only think of the F1 GP! :-)
For now I think it's difficult enough to figure out how to improve evaluation of material, which is the main goal of this research. Exceptions like doubled pawns or connected passers can be accounted for in the evaluation function so this information is usable in all situations. In fact, at present I have only generated statistics about 1100 or so imbalances, not a very big number.

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

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

Post by mjlef » Wed Dec 12, 2007 1:36 pm

Alessandro Scotti wrote:
Thomas Gaksch wrote:Hi Alessandro!
wow, great work. I think your research is a very good starting point.
I personally believe that Rybka and/or Fritz are going one step further. I think they have not only informations about the "pure" material imbalance but additional informations about the pawn structure (or something else). For example you have calculated the probability of the RPP against RPP (rel(w)=1.02, abs(w)=0.51, rel(X)=1.00, abs(X)=0.50, mat=0, count=4156, R=1.00 / RPP rpp ()) as a draw. But if white for example has a double pawn and black has a connected passed pawn then the probability that black wins is much greater. So if it would be possible to calculate such relations and store them in a big hashtable it would be a great improvement for the evaluation.
Hi Thomas,
I'm not sure those exceptions can be properly analyzed in a statistical way, unless the number of games sampled is really huge (or some method is used to produce more samples for the "interesting" configurations). Some experts in statistics would be able to answer better though, when I first heard of Monte Carlo I could only think of the F1 GP! :-)
For now I think it's difficult enough to figure out how to improve evaluation of material, which is the main goal of this research. Exceptions like doubled pawns or connected passers can be accounted for in the evaluation function so this information is usable in all situations. In fact, at present I have only generated statistics about 1100 or so imbalances, not a very big number.
Can someone suggest a nice, freeware stats package that can do coorelation analysis,and curve fitting? The data is really great, and in tests my program finds a match with specific material imbalances in around 20% of positions searched. I suspect many of the other positions have such a huge material difference that they are not important, but it would be nice to figure out how to best use this data. I would love to do some coorelations, so let me know what you think would work best. Come on all you statisticians!

Mark

User avatar
David Dahlem
Posts: 900
Joined: Wed Mar 08, 2006 8:06 pm

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

Post by David Dahlem » Wed Dec 12, 2007 3:36 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!
This link does not work for me, i get a "not available" error message ...

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

Regards
Dave

Post Reply