Material Tables and Indexing

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
CThinker
Posts: 388
Joined: Wed Mar 08, 2006 9:08 pm
Contact:

Re: Material Tables and Indexing

Post by CThinker » Tue Apr 22, 2008 1:00 am

bob wrote:There are two points here...

1. piece for 3 pawns is almost always bad. The opponent ends up with an extra piece, and can slowly overwhelm each and every one of your pawns since he has one extra piece to attack with.

2. On rare occasions, particularly in late middlegame positions, a knight for 3 pawns might not be bad at all, if the pawns are mobile and can move freely and quickly, Or if the piece for three pawns exposes the king to an attack by rooks/queen on the now-open files. But those cases are extremely rare.

For this reason, I have some very simple code in Crafty that simply tosses in a big penalty if piece for 3 pawns, or two minors for rook+pawn gets played on the board... And it works well in almost all cases. General rules will almost always have exceptions, but if they are rare enough....
I too have played with different ways of penalizing these types of imbalances. All the time, the engine plays worse against other engines, and plays too passive against humans (based on ICC games).

In the end, I don't have such code anymore. I'm sure I'm simply not doing it right.

Me, back to the drawing board now...

gladius
Posts: 567
Joined: Tue Dec 12, 2006 9:10 am
Full name: Gary Linscott

Re: Material Tables and Indexing

Post by gladius » Tue Apr 22, 2008 1:35 am

bob wrote:One note. I wrestled with this for almost 30 years. Without producing a satisfactory result. All by trying to manipulate positional scores and material values so that this kind of thing would not happen. I finally gave up and did what I do as a human... if I see a position where one side has a piece and the other side has three pawns, I immediately think "the side with the piece is probably winning..." and then I look more carefully to see if the side with the three extra pawns can mobilize them and turn them into an unanswerable threat before the opponent attacks them and turns them into lunch for the extra piece to eat...

Doing it the Crafty "bad trade" way (where I penalize the side that is down a piece for 3 pawns or down two pieces for a rook and pawn, and then let the normal scoring work. I adjust this single "bad trade" value based on lots of testing to produce the best overall result, and go with that...
Thanks Bob, I'll give that a try and see if I can get some good results from it. I wonder whether it's better to tie it to pawn weaknesses as well, so for example, if you have 2 weak pawns that bishop is going to be much more valuable than keeping the pawns around. So maybe my pawn scoring is not taking "weakness" into account enough.

CThinker
Posts: 388
Joined: Wed Mar 08, 2006 9:08 pm
Contact:

Re: Material Tables and Indexing

Post by CThinker » Tue Apr 22, 2008 8:09 am

mjlef wrote:I use a 16 bit value for each side, which has fields for the number of each piece type (other than king, of course):

QQQRRRBBBNNNPPPP

This handles up to 15 pawns, 7 bishops, 7 knights, 7 rooks and 7 queens. I know it is possible to have lots of promotions and end up with 10 rooks or something, but I just ignore that. When it comes time to apply the material table you can just use a test like this:

if (((pieces[white]& MagicMask)==0) && (pieces[black]& MagicMask)==0))
{
//add in the material bonus
}

You just set the bits in MagicMask to handle the cases where the material array would not handle them. Say more than one queen:

MagicMask = 0xc0000;

You can set other bits if you cannot hanlde say 4 rooks and 4 bishops and 4 knights, for example.

These bit fields have lots of uses in things like detecting specific endgames:

if (pieces[white]==RookPawn) .... handle rook and pawn ending...

just define RookPawn to be 0x401

Old NOW had a very small material bonus array, and only handled up tp 1 queen, 2 rooks, 2 bishops, 2 knights and 3 pawns. This was to keep it to 1024 elements (2^10) because it had to run in 640 k DOS. You can still pack a lot of endgame knowledge even in a small array like this. And if you do not want to use the Rybka/Strelka multiplication index, the array index can be quickly calculated from AND and shifts of these 16 bit materail words.

Mark
The Thinker code has exactly what you just described. I actually got the idea from Amy. But in Amy, its just 12 bits, instead of 32. Each bit simply tells you whether such a piece is present on the board.

In the 32-bit value, I call 'profile', the counts of the pieces are encoded just as you have described.

I use this in two ways:

1. To quickly detect obvious draws and wins. I just have a short table of known draw and win profiles. If the current board profile is there, no further eval is needed.

As a result, the endgame recognizer code is very short.

I don't have those complex code that compares the counts of minors vs majors vs pawns.

2. To hash material eval (PST, end-game values that may not be draw, etc). The material hash table is small, so I do an integer hashing of the 32-bit profile value and end-up with index to the material hash table.

The other good thing about this is that I don't need a 10-item array for keeping the piece counts. This 4-byte integer does the job.

Code: Select all

        #define MaterialProfile_Pawn    &#40;0x000f <<  0&#41;
        #define MaterialProfile_Knight  &#40;0x0003 <<  4&#41;
        #define MaterialProfile_Bishop  &#40;0x0003 <<  7&#41;
        #define MaterialProfile_Rook    &#40;0x0003 << 10&#41;
        #define MaterialProfile_Queen   &#40;0x0003 << 13&#41;

        #define MaterialProfile_Side&#40;color_) ( 0xffff << (&#40;color_) << 4&#41; )

        #define MaterialProfile_White    MaterialProfile_Side &#40;White&#41;
        #define MaterialProfile_Black    MaterialProfile_Side &#40;Black&#41;

        #define MaterialProfile_WhitePawn    ( &#40;0x000f <<  0&#41; << &#40;White * 16&#41; )
        #define MaterialProfile_WhiteKnight  ( &#40;0x0003 <<  4&#41; << &#40;White * 16&#41; )
        #define MaterialProfile_WhiteBishop  ( &#40;0x0003 <<  7&#41; << &#40;White * 16&#41; )
        #define MaterialProfile_WhiteRook    ( &#40;0x0003 << 10&#41; << &#40;White * 16&#41; )
        #define MaterialProfile_WhiteQueen   ( &#40;0x0003 << 13&#41; << &#40;White * 16&#41; )

        #define MaterialProfile_BlackPawn    ( &#40;0x000f <<  0&#41; << &#40;Black * 16&#41; )
        #define MaterialProfile_BlackKnight  ( &#40;0x0003 <<  4&#41; << &#40;Black * 16&#41; )
        #define MaterialProfile_BlackBishop  ( &#40;0x0003 <<  7&#41; << &#40;Black * 16&#41; )
        #define MaterialProfile_BlackRook    ( &#40;0x0003 << 10&#41; << &#40;Black * 16&#41; )
        #define MaterialProfile_BlackQueen   ( &#40;0x0003 << 13&#41; << &#40;Black * 16&#41; )

        #define MaterialProfile_WhiteNonPawns   ( MaterialProfile_WhiteMinors | MaterialProfile_WhiteMajors )
        #define MaterialProfile_BlackNonPawns   ( MaterialProfile_BlackMinors | MaterialProfile_BlackMajors )

        #define MaterialProfile_AllNonPawns     ( MaterialProfile_WhiteNonPawns | MaterialProfile_BlackNonPawns )

        #define MaterialProfile_WhiteMinors     ( MaterialProfile_WhiteKnight | MaterialProfile_WhiteBishop )
        #define MaterialProfile_BlackMinors     ( MaterialProfile_BlackKnight | MaterialProfile_BlackBishop )

        #define MaterialProfile_AllMinors       ( MaterialProfile_WhiteMinors | MaterialProfile_BlackMinors )

        #define MaterialProfile_WhiteMajors     ( MaterialProfile_WhiteRook | MaterialProfile_WhiteQueen )
        #define MaterialProfile_BlackMajors     ( MaterialProfile_BlackRook | MaterialProfile_BlackQueen )

        #define MaterialProfile_AllMajors       ( MaterialProfile_WhiteMajors | MaterialProfile_BlackMajors )

        #define MaterialProfile_AllPawns        ( MaterialProfile_WhitePawn   | MaterialProfile_BlackPawn   )
        #define MaterialProfile_AllKnights      ( MaterialProfile_WhiteKnight | MaterialProfile_BlackKnight )
        #define MaterialProfile_AllBishops      ( MaterialProfile_WhiteBishop | MaterialProfile_BlackBishop )
        #define MaterialProfile_AllRooks        ( MaterialProfile_WhiteRook   | MaterialProfile_BlackRook   )
        #define MaterialProfile_AllQueens       ( MaterialProfile_WhiteQueen  | MaterialProfile_BlackQueen  )

        #define MaterialProfile_AllMajorsAndPawns   ( MaterialProfile_AllMajors | MaterialProfile_AllPawns )

        #define MaterialProfile_Count_WhitePawn&#40;prof_)    ( ( &#40;prof_) >> (  0 + &#40;White * 16&#41; ) ) & 0x000f )
        #define MaterialProfile_Count_WhiteKnight&#40;prof_)  ( ( &#40;prof_) >> (  4 + &#40;White * 16&#41; ) ) & 0x0003 )
        #define MaterialProfile_Count_WhiteBishop&#40;prof_)  ( ( &#40;prof_) >> (  7 + &#40;White * 16&#41; ) ) & 0x0003 )
        #define MaterialProfile_Count_WhiteRook&#40;prof_)    ( ( &#40;prof_) >> ( 10 + &#40;White * 16&#41; ) ) & 0x0003 )
        #define MaterialProfile_Count_WhiteQueen&#40;prof_)   ( ( &#40;prof_) >> ( 13 + &#40;White * 16&#41; ) ) & 0x0003 )

        #define MaterialProfile_Count_BlackPawn&#40;prof_)    ( ( &#40;prof_) >> (  0 + &#40;Black * 16&#41; ) ) & 0x000f )
        #define MaterialProfile_Count_BlackKnight&#40;prof_)  ( ( &#40;prof_) >> (  4 + &#40;Black * 16&#41; ) ) & 0x0003 )
        #define MaterialProfile_Count_BlackBishop&#40;prof_)  ( ( &#40;prof_) >> (  7 + &#40;Black * 16&#41; ) ) & 0x0003 )
        #define MaterialProfile_Count_BlackRook&#40;prof_)    ( ( &#40;prof_) >> ( 10 + &#40;Black * 16&#41; ) ) & 0x0003 )
        #define MaterialProfile_Count_BlackQueen&#40;prof_)   ( ( &#40;prof_) >> ( 13 + &#40;Black * 16&#41; ) ) & 0x0003 )

        #define MaterialProfile_Count&#40;pbrd_,pc_type_,color_) \
            ( &#40;pc_type_) == Pawn ? (&#40;pbrd_)->material_profile >> (&#40;color_) << 4&#41;) & 0x0f &#58; \
                                   (&#40;pbrd_)->material_profile >> &#40;1 + ((&#40;pc_type_) - 1&#41; * 3&#41; + (&#40;color_) << 4&#41;)) & 0x07 )

        #define MaterialProfileInc_Piece&#40;pc_type_,color_) (&#40;1 << ((&#40;pc_type_) * 3&#41; - 2&#41;) << (&#40;color_) * 16&#41;) // only for Knight, Bishop, Rook or Queen

        #define MaterialProfileInc_Pawn    &#40;1 <<  0&#41;
        #define MaterialProfileInc_Knight  &#40;1 <<  4&#41;
        #define MaterialProfileInc_Bishop  &#40;1 <<  7&#41;
        #define MaterialProfileInc_Rook    &#40;1 << 10&#41;
        #define MaterialProfileInc_Queen   &#40;1 << 13&#41;

        #define MaterialProfileInc_WhitePawn    ( &#40;1 <<  0&#41; << &#40;White * 16&#41; )
        #define MaterialProfileInc_WhiteKnight  ( &#40;1 <<  4&#41; << &#40;White * 16&#41; )
        #define MaterialProfileInc_WhiteBishop  ( &#40;1 <<  7&#41; << &#40;White * 16&#41; )
        #define MaterialProfileInc_WhiteRook    ( &#40;1 << 10&#41; << &#40;White * 16&#41; )
        #define MaterialProfileInc_WhiteQueen   ( &#40;1 << 13&#41; << &#40;White * 16&#41; )

        #define MaterialProfileInc_BlackPawn    ( &#40;1 <<  0&#41; << &#40;Black * 16&#41; )
        #define MaterialProfileInc_BlackKnight  ( &#40;1 <<  4&#41; << &#40;Black * 16&#41; )
        #define MaterialProfileInc_BlackBishop  ( &#40;1 <<  7&#41; << &#40;Black * 16&#41; )
        #define MaterialProfileInc_BlackRook    ( &#40;1 << 10&#41; << &#40;Black * 16&#41; )
        #define MaterialProfileInc_BlackQueen   ( &#40;1 << 13&#41; << &#40;Black * 16&#41; )

        #define MaterialProfile_KQKP    ( MaterialProfileInc_WhiteQueen  | MaterialProfileInc_BlackPawn   )
        #define MaterialProfile_KPKQ    ( MaterialProfileInc_WhitePawn   | MaterialProfileInc_BlackQueen  )

        #define MaterialProfile_KRKP    ( MaterialProfileInc_WhiteRook   | MaterialProfileInc_BlackPawn   )
        #define MaterialProfile_KPKR    ( MaterialProfileInc_WhitePawn   | MaterialProfileInc_BlackRook   )

        #define MaterialProfile_KBKP    ( MaterialProfileInc_WhiteBishop | MaterialProfileInc_BlackPawn   )
        #define MaterialProfile_KPKB    ( MaterialProfileInc_WhitePawn   | MaterialProfileInc_BlackBishop )

        #define MaterialProfile_KNKP    ( MaterialProfileInc_WhiteKnight | MaterialProfileInc_BlackPawn   )
        #define MaterialProfile_KPKN    ( MaterialProfileInc_WhitePawn   | MaterialProfileInc_BlackKnight )

        #define MaterialProfile_KNPK    ( MaterialProfileInc_WhiteKnight | MaterialProfileInc_WhitePawn   )
        #define MaterialProfile_KKNP    ( MaterialProfileInc_BlackKnight | MaterialProfileInc_BlackPawn   )

        #define MaterialProfile_KRPKR   ( MaterialProfileInc_WhiteRook   | MaterialProfileInc_WhitePawn   | MaterialProfileInc_BlackPawn   )
        #define MaterialProfile_KRKRP   ( MaterialProfileInc_WhiteRook   | MaterialProfileInc_BlackRook   | MaterialProfileInc_BlackPawn   )

        #define MaterialProfile_KBPKB   ( MaterialProfileInc_WhiteBishop | MaterialProfileInc_WhitePawn   | MaterialProfileInc_BlackPawn   )
        #define MaterialProfile_KBKBP   ( MaterialProfileInc_WhiteBishop | MaterialProfileInc_BlackBishop | MaterialProfileInc_BlackPawn   )

        #define MaterialProfile_NONE    ( 0xffffffff )

        #define MaterialProfile_KPK     MaterialProfileInc_WhitePawn
        #define MaterialProfile_KKP     MaterialProfileInc_BlackPawn

        #define MaterialProfile_KRK     MaterialProfileInc_WhiteRook
        #define MaterialProfile_KKR     MaterialProfileInc_BlackRook

        #define MaterialProfile_KNK     MaterialProfileInc_WhiteKnight
        #define MaterialProfile_KKN     MaterialProfileInc_BlackKnight

        #define MaterialProfile_KNNK    &#40;MaterialProfileInc_WhiteKnight * 2&#41; 
        #define MaterialProfile_KKNN    &#40;MaterialProfileInc_BlackKnight * 2&#41;

        #define MaterialProfile_KBBKN   ( &#40;MaterialProfileInc_WhiteBishop * 2&#41; | MaterialProfileInc_BlackKnight )
        #define MaterialProfile_KNKBB   ( MaterialProfileInc_WhiteKnight | &#40;MaterialProfileInc_BlackBishop * 2&#41; )

        #define MaterialProfile_KQKQ    ( MaterialProfileInc_WhiteQueen  | MaterialProfileInc_BlackQueen  )
        #define MaterialProfile_KRKR    ( MaterialProfileInc_WhiteRook   | MaterialProfileInc_BlackRook   )
        #define MaterialProfile_KBKB    ( MaterialProfileInc_WhiteBishop | MaterialProfileInc_BlackBishop )
        #define MaterialProfile_KNKN    ( MaterialProfileInc_WhiteKnight | MaterialProfileInc_BlackKnight )

        #define MaterialProfile_KBPK    ( MaterialProfileInc_WhiteBishop | MaterialProfileInc_WhitePawn   )
        #define MaterialProfile_KKBP    ( MaterialProfileInc_BlackBishop | MaterialProfileInc_BlackPawn   )

        #define MaterialProfile_KK      0

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

Re: Material Tables and Indexing

Post by bob » Tue Apr 22, 2008 3:38 pm

gladius wrote:
bob wrote:One note. I wrestled with this for almost 30 years. Without producing a satisfactory result. All by trying to manipulate positional scores and material values so that this kind of thing would not happen. I finally gave up and did what I do as a human... if I see a position where one side has a piece and the other side has three pawns, I immediately think "the side with the piece is probably winning..." and then I look more carefully to see if the side with the three extra pawns can mobilize them and turn them into an unanswerable threat before the opponent attacks them and turns them into lunch for the extra piece to eat...

Doing it the Crafty "bad trade" way (where I penalize the side that is down a piece for 3 pawns or down two pieces for a rook and pawn, and then let the normal scoring work. I adjust this single "bad trade" value based on lots of testing to produce the best overall result, and go with that...
Thanks Bob, I'll give that a try and see if I can get some good results from it. I wonder whether it's better to tie it to pawn weaknesses as well, so for example, if you have 2 weak pawns that bishop is going to be much more valuable than keeping the pawns around. So maybe my pawn scoring is not taking "weakness" into account enough.
I think it is better to let your normal evaluation handle things. Give a big penalty for piece for 3 pawns. Then see if your normal passed pawn / king safety scoring can come up with enough compensation to make that still look attractive. Now you just tune this penalty for best overall results and you are done, whereas if you adjust piece values, you throw other things out of kilter and make the testing/tuning much more complex...

Edsel Apostol
Posts: 770
Joined: Mon Jul 17, 2006 3:53 am
Full name: Edsel Apostol
Contact:

Re: Material Tables and Indexing

Post by Edsel Apostol » Sun Apr 27, 2008 10:34 am

Thanks Lance.

Thinker now by the way is my favorite engine because of its playing style, though I would be more happy if you could support UCI.

Any hints or ideas on how to make an engine play just like yours? Maybe a suggestion in the line of "less prunings or reductions", etc..

CThinker
Posts: 388
Joined: Wed Mar 08, 2006 9:08 pm
Contact:

Re: Material Tables and Indexing

Post by CThinker » Wed Apr 30, 2008 5:29 pm

Edsel Apostol wrote:Thanks Lance.

Thinker now by the way is my favorite engine because of its playing style, though I would be more happy if you could support UCI.

Any hints or ideas on how to make an engine play just like yours? Maybe a suggestion in the line of "less prunings or reductions", etc..
From my experience, the style of play is more affected by evaluation, and less by search.

The "(Passive)Thinker" and "(Active)Thinker" only differ in the evaluation code. The rest are exactly the same for both. The 'Active' version scores a lot of things which the much simpler 'Passive' version does not.

Mabuhay!

Edsel Apostol
Posts: 770
Joined: Mon Jul 17, 2006 3:53 am
Full name: Edsel Apostol
Contact:

Re: Material Tables and Indexing

Post by Edsel Apostol » Thu May 01, 2008 9:34 am

I thought that search makes the engine play actively or passively. For example, if I reduce too much, the engine plays more speculative, it means more active but prone to lose more often.

Maybe that's why my engine is still not that strong. I will just try to make a solid search and an aggressive eval then, instead of an aggressive search and a solid eval.

Dann Corbit
Posts: 12000
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Material Tables and Indexing

Post by Dann Corbit » Thu May 01, 2008 7:07 pm

Edsel Apostol wrote:I thought that search makes the engine play actively or passively. For example, if I reduce too much, the engine plays more speculative, it means more active but prone to lose more often.

Maybe that's why my engine is still not that strong. I will just try to make a solid search and an aggressive eval then, instead of an aggressive search and a solid eval.
T20080404x is quite strong. It looks pretty good here:
http://www.husvankempen.de/nunn/phpBB2/ ... b62cafe0a8

Although UFIM cleaned your clock.
;-)

CThinker
Posts: 388
Joined: Wed Mar 08, 2006 9:08 pm
Contact:

Re: Material Tables and Indexing

Post by CThinker » Fri May 02, 2008 12:12 am

Edsel Apostol wrote:I thought that search makes the engine play actively or passively. For example, if I reduce too much, the engine plays more speculative, it means more active but prone to lose more often.

Maybe that's why my engine is still not that strong. I will just try to make a solid search and an aggressive eval then, instead of an aggressive search and a solid eval.
In the end, what eval says is a good score is what the search will pick.

In Thinker, what people consider as 'interesting' plays, are artifacts of a number of peculiar eval behavior.

For one, Thinker does not cap positional scores. It is, for example, possible to have more than 3 points of positional score. This means that the engine thinks that it is OK to be behind by 3 pawns as long as most of its pieces are mobile but the opponent's pieces are not.

Second, Thinker does not evaluate material balances. It is OK for the engine to trade materially equivalent pieces (e.g., a bishop or knight for 3 pawns). The absence of such complex code (and other complex/exotic) evaluation code, results in a small/compact code, and allows Thinker to get into interesting positions.

Third, Thinker gives a lot of bonuses for what I think are 'aggressive' behavior . An example of this, is a big bonus for the affinity of the King to the opponent's King. This causes the King to actually "attack" the opponent. This can easily backfire, as the King could end-up in the open or forego castling. But it is quite a sight to behold.

Edsel Apostol
Posts: 770
Joined: Mon Jul 17, 2006 3:53 am
Full name: Edsel Apostol
Contact:

Re: Material Tables and Indexing

Post by Edsel Apostol » Sat May 03, 2008 11:18 am

Hi Dann,

The latest betas are much stronger. Some of them could already reach 40%+ against Spike 1.2 in blitz in slow hardware using Noomen Test Suite 2007 as opening suite.

The latest release version has a too aggressive pruning and has a bug in the search concerning hash table cut-offs.

Twisted Logic will exact revenge soon. :twisted: :)

Post Reply