SEE problem

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.
Tord Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

SEE problem

Post by Tord Romstad » Sun Apr 13, 2008 10:10 am

This morning, I stumbled upon a symmetry bug in my evaluation function, in the following position:
[D]4r2k/pp4p1/2p1P3/2Q5/3p4/P2Br3/1PP4q/1K2R3 b - -
The reason turned out to be that the passed pawn on e6 is evaluated differently in the mirrored position. One of the factors considered by my passed pawn evaluation is whether the pawn can safely advance. I use the static exchange evaluator to test this. I discovered that in the above position, the pawn push e6-e7 is incorrectly classified as a non-losing move (SEE value 0), while in the mirrored position, the pawn push e3-e2 is correctly classified as losing (SEE value -1).

It's easy to see why this happens. My SEE function begins by finding the least valuable attacker. In the above position, there are only two attackers, and they are both of equal value (the rooks on e8 and e3). My SEE picks the rook on e3 first. Unfortunately, this means that the X-ray attack from white's rook on e1 gets uncovered, which causes in an incorrect SEE value. In other words, the SEE analyses the sequence e6-e7 Re3xe7 Re1xe7, and concludes that white is winning, and that e6-e7 is therefore a safe move.

Now, consider the mirrored position:
[D]1k2r3/1pp4Q/p2bR3/3P4/2q5/2P1p3/PP4P1/4R2K w - -
Here, my SEE picks the other rook first. The SEE analyses the sequence e3-e2 Re1xe2 Qc4xe2 Re6xe2 Re8xe2, and concludes that e3-e2 loses a pawn.

This is of course a highly annoying problem, and I see no elegant and efficient way to fix it. How do you make sure the correct attacker gets picked first in positions with X-ray-attacks?

Tord

Guetti

Re: SEE problem

Post by Guetti » Sun Apr 13, 2008 11:30 am

Hm, this is a unfortunate position. Probably most SEE will mess this up, which is not a major problem if you only use it for move sorting.

If you depend on the correctness of the SEE, this is different. One possible solution could be, in the case where you have 2 sliding attackers on the same file (because the covered attacker could also be a queen?), you could check for Xray attackers for both of them before choosing one, and then select the attacker that will not uncover other attackers first?

Gerd Isenberg
Posts: 2106
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: SEE problem

Post by Gerd Isenberg » Sun Apr 13, 2008 12:02 pm

Nice problem. Just another reason for me to keep the color-flipper approach and to evaluate only white to move positions ;-)

You may look for x-rays in advance to pick those same valuable attackers/defenders in following order:
  • 1. supported by own slider from "behind" (battery)
    2. don't discovers any indirect defense (x-Ray)
    3. remaining
To avoid bitscan related asymmetries, you may split all vertical and diagonal sliding attack-directions into two disjoint sets. Positive or negative directions aka intersect with (1<<sq)-1 versus 0-(1<<sq) to traverse the positive directions first if white to move - but negative directions first if black to move - or vice versa. But that seems already the half way to color-flip the board vertically after each make/unmake.

Gerd

Harald Johnsen

Re: SEE problem

Post by Harald Johnsen » Sun Apr 13, 2008 12:22 pm

I's a problem or discovered attacks and pins, nothing that can be solved by SEE. Put your white queen on d6 and the d3 rook on f6, SEE will give a positive score for the white pawn push. And this position has nothing special...

Perhaps it's time to look at super-soma ;)

HJ.

Aleks Peshkov
Posts: 849
Joined: Sun Nov 19, 2006 8:16 pm
Location: Russia

Re: SEE problem

Post by Aleks Peshkov » Sun Apr 13, 2008 2:33 pm

Crafty used (at least in past and at least in some specific situations) opposite bitscans for opposite sides.

But I think the source of the problem that in general dynamic things like SEE should not be comparable with static features.

IMHO search depth extensions on passed pawn pushes would lead to more precise evaluation of highly important and highly dynamic nature of passed pawns. Passed pawn push is a rare and irreversible move, so the search can not to explode.

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: SEE problem

Post by Zach Wegner » Sun Apr 13, 2008 9:07 pm

I handle this by only using is_attacked() in my passed pawn eval. No path-dependency problems, and also SEE doesn't really handle passed pawns correctly. Say white has a pawn on e6, and white and black both attack e7 with a bishop. SEE will say it's safe to advance, but I'd prefer to save the pawn.

CRoberson
Posts: 1966
Joined: Mon Mar 13, 2006 1:31 am
Location: North Carolina, USA
Contact:

Re: SEE problem

Post by CRoberson » Mon Apr 14, 2008 2:00 am

I've seen several positions that SEE doesn't handle properly, but
this one is rather neat.

A "try all orders" loop could be wrapped around SEE. However,
that doesn't fully solve the general problem. It does solve your
position, but the general problem is obviously recursive.

So, SEE needs to be modified s.t. this doesn't hapen anywhere
in the SEE process. This means a "try all orders" loop needs
to be internal to the process. This turns the previously iterative
algorithm into a recursive one which will increase the overhead
and could make it too expensive for general use. So, have two
SEE's. SEE1 is the standard one that is used in Qsearch and SEE2
is the new expensive one for your passed pawn decisions.

Tord Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Re: SEE problem

Post by Tord Romstad » Mon Apr 14, 2008 6:04 am

Hi Andreas!
Guetti wrote:Hm, this is a unfortunate position. Probably most SEE will mess this up, which is not a major problem if you only use it for move sorting.
I agree.
If you depend on the correctness of the SEE, this is different. One possible solution could be, in the case where you have 2 sliding attackers on the same file (because the covered attacker could also be a queen?), you could check for Xray attackers for both of them before choosing one, and then select the attacker that will not uncover other attackers first?
This would be possible, but I fear it would be too expensive.

Tord

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

Re: SEE problem

Post by Edsel Apostol » Mon Apr 14, 2008 6:06 am

I have encountered those problems before. One solution I think is to use LSB for white and MSB for black, but then I don't like that solution so I never used SEE anymore for my passed pawn evaluation.

I have tried to wrote an SEE algorithm for this before and I posted it here in this forum. It seems to give correct results for both sides but I didn't have time to test if it is indeed working correctly.

Would the experts here take a look at my code in this link and confirm if it is indeed working correctly. If it has bugs, maybe we could fix it and adapt it on our own engines also.
http://www.talkchess.com/forum/viewtopi ... 0bfa60e609

Tord Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Re: SEE problem

Post by Tord Romstad » Mon Apr 14, 2008 6:09 am

Harald Johnsen wrote:I's a problem or discovered attacks and pins, nothing that can be solved by SEE. Put your white queen on d6 and the d3 rook on f6, SEE will give a positive score for the white pawn push. And this position has nothing special...
I don't agree that thsi is a problem of pins and discovered attacks. Only the direct and indirect attacks to a single square is involved. It's a completely local problem, of the type that an SEE should be able to evaluate correctly.
Perhaps it's time to look at super-soma ;)
I haven't tried, but I find it hard to believe that super-soma is worth the expense in chess. Has anyone tried it?

Tord

Post Reply