SEE Improvement Idea

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.
Post Reply
mjlef
Posts: 1361
Joined: Thu Mar 30, 2006 12:08 pm
Contact:

SEE Improvement Idea

Post by mjlef » Mon Jan 04, 2010 3:09 pm

In an attempt to improve the SEE used in programs for pruning moves or selecting move order, how about applying material imbalance rules in the SEE? An example. A program might calculate that PxP PxP is an "even" exchange, but if the first side was left with merely a lone Bishop, it could be much worse than doing the exchange. Often exchanges are better or worse than expected, and this could detect them sooner than waiting for the search and ful eval to get there.

mcostalba
Posts: 2679
Joined: Sat Jun 14, 2008 7:17 pm

Re: SEE Improvement Idea

Post by mcostalba » Mon Jan 04, 2010 4:13 pm

mjlef wrote:In an attempt to improve the SEE used in programs for pruning moves or selecting move order, how about applying material imbalance rules in the SEE? An example. A program might calculate that PxP PxP is an "even" exchange, but if the first side was left with merely a lone Bishop, it could be much worse than doing the exchange. Often exchanges are better or worse than expected, and this could detect them sooner than waiting for the search and ful eval to get there.
You mean that if you have PxP PxP and the side to move remains with just a bishop you consider see negative and discard or postpone the move (because at the end that's what see is used for) ? hmmmmmmm

Ferdy
Posts: 3620
Joined: Sun Aug 10, 2008 1:15 pm
Location: Philippines

Re: SEE Improvement Idea

Post by Ferdy » Mon Jan 04, 2010 4:35 pm

mjlef wrote:In an attempt to improve the SEE used in programs for pruning moves or selecting move order, how about applying material imbalance rules in the SEE? An example. A program might calculate that PxP PxP is an "even" exchange, but if the first side was left with merely a lone Bishop, it could be much worse than doing the exchange. Often exchanges are better or worse than expected, and this could detect them sooner than waiting for the search and ful eval to get there.
There is also a possibility that the resulting exchange could be a draw, it all depends on positions. But of course we will try to check also the remaining and type of pieces of the opponent.
The idea is interesting and can be improved of course :) .

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

Re: SEE Improvement Idea

Post by hgm » Mon Jan 04, 2010 4:46 pm

This is an issue that also came up in normal search utility pruning. Capturing the last Pawn in (say) KBPK , this is not futile when eval - alpha = -200, as the Pawn effectively is worth 400. In Xiangqi, where material evaluation cannot be approximated by simple additive function in any case, this is also an important issue.

The implementation of this is not extremely expensive: in stead of adding the captured material to a differential eval, you add a code for that material to a differentially updated material index, that you then use to access the material table to get the new eval. This can be done both in search and in SEE.

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

Re: SEE Improvement Idea

Post by mjlef » Mon Jan 04, 2010 6:55 pm

Exactly. Mnay programs have either a material imbalance table, or hashed material signatures so looking this up would be very fast. And it should improve things everywhere (not just endgames)sinc eit would correct for the various exchange possibilities. It could scre up a bit with the SEE aqssuption that the next smallest attacker should capture first.

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

Re: SEE Improvement Idea

Post by hgm » Mon Jan 04, 2010 7:26 pm

Indeed, ordering could be a problem in SEE. Perhaps the material table could contain ordering hints, e.g. tabulate the lowest-valued piece. I don't know which reversals are possible in Chess: the obvious case is that with only one Pawn that Pawn might be more valuable than a Bishop or Knight. I don't think a Rook could ever be less valusble than a Pawn or a minor, and because an a Queen shoud always be worth more than Rook or Bishop because f upward compatbility. So perhaps a one-bit flag to indicate a Pawn should be tried after minors would be sufficient.

I don't think that non-additive effects in material eval are very important in Chess. The minor-without-pawns and two-kights cases is really the only heavy exception that comes to mind.

It might well be possible to get away with only partial material tables, not fully resolving any material combination. In my Xianqi engine, I use a material table indexed by defensive material of one side, and offensive material of the other. That lmits the number of combinations to 1458. In Chess it might be possible to ony use material of one side.

Post Reply