SEE implemented the wrong way?

[Steve Maughan]

You may find this post helpful:

http://www.chessprogramming.net/static- ... -in-chess/

Steve

[Daniel Anulliero]

Thanks to Denis and hg for your lights about my position
Thanks for the link Steve
SEE is that I thought... more complex than it seems ..

[flok]

Am I right that blind is not documented at the chessprogrammingwiki?

[hgm]

Could be. It is pretty simple to implement, though. For every capture in MVV/LVA order where the victim value is lower than the attacker value, postpone its search.

I usually determine the search order of captures by a 'priority key' stored in the upper byte of a 4-byte move (as the move itself only takes the lowest two bytes), and then extract the remaining move with the largest value whenever I have to search a new capture. With the simplified values 1,3,3,5,9 I can use priority key = 16*value[victim] - value[attacker] + 100 to get MVV/LVA order.

The +100 was not really needed for that, but allows me to deduct 100 for captures with a key above 100 to postpone them. So it becomes like this:

Code: Select all

1: identify largest move in not-yet-searched captures
2&#58; if key > 100 and value&#91;victim&#93; < value&#91;attacker&#93; && victim is protected
3&#58;   key -= 100
4&#58;   goto 1
5&#58; swap largest move to front of move list

This just postpones 'suspect captures', it does not prune them. Suspect captures need not be bad, R x protected P can be the move of choice when the only protector is a Rook, and there is a second R, Q or K attacker. If you don't have a second attacker on the same victim it would certainly have negative SEE, however. (Could still be good, though, if the protector was pinned on King or Queen.) As you are sorting your own generated moves, it should be easy to figure out if you have remaining captures to the same square.

The tricky thing is to know if the victim is protected. Depending on how you figure that out you might even know the value of the lowest protector. Then you can prune moves where victim + lowest protector together are worth less than attacker, as these would also certainly have negative SEE. In KingSlayer I don't have any special code to learn about opponent moves, however. I just made it possible for Search() to abort in the move-generation stage, similar to how it would abort when it detects it can capture a King. Basically I elevate the piece that just made a HxL capture temporarily to King status. King capture would return score +INF, but capturing the 'vulnarable piece' would return +INF+1, so that the caller can see that the move is not truly illegal, but only 'suspect', so that it can lower its key by 100 for rescheduling it.

Code: Select all

1: identify largest move in not-yet-searched captures
2: swap largest move to front of move list
3&#58; if key > 100 and value&#91;victim&#93; < value&#91;attacker&#93;
4&#58;      vulnerablePiece = attacker
5&#58; else vulnerablePiece = NONE
6&#58; MakeMove&#40;); score = -Search&#40;vulnerablePiece&#41;; UnMake&#40;);
7&#58; if score < -INF
8&#58;   key -= 100
9&#58;   goto 1

In Tenjiku Shogi I have to be really stingy w.r.t. what to search in QS. This because some non-captures can be far more profitable than capturing a single piece. Because they can fork multiple sites where they can blow up many pieces in one move. And most of the single captures trap the capturing piece, so that even when you cannot recapture them, attacking them through a non-capture would gain them back anyway.

So capture-only searches often completely miss the point. It thus seems best to spend as little time as possible on QS, so that the full-width search can go deeper. So my guiding principle will be to only try captures when you have good reason they will improve the score (making the stand-pat score incorrect). That is LxH captures, and capture of unprotected pieces. And the latter only into trapped situations (i.e. into the enemy camp) when the captured piece has a value of at least half that of the attacker. (So that you can sac it for a second piece when you cannot escape, and hopefully still get out positive.) I am not even sure if I should search equal captures. (Although with 42 different piece types the chances that a capture is truly equal are of course pretty slim.) The most efficient way to cash on a LxH threat, however, is first trade all higher victims (with which the opponent would otherwise launch desparate counter attacks). So I could make it dependent on the presense of gain opportuities: Scan through the victims collecting, but o searching equal captures until I encounter a LxH capture or sufficiently-valuable unprotected victim. If there is none, I can stand pat without searching the equal captures. And if I do encounter one, I can first search all the collected equal captures in MVV order before continuing with the LxH capture.

[flok]

Thanks for the elaborate reply.

Something odd is happening: if I don't postpone the blind-moves but instead prune them, then that gives me a 42 elo improvement (with 33347 games played at tc=40/5+0.125).

[pedrox]

You can use blind (for me fast SEE) to cut in quiesce and also to sort moves and perhaps can reduce the search depth of theses captures in the search, the gain of the latter will surely be much less. 42 points for only cut in the quiesce with blind seems somewhat high, at least compared to my engine.

In the quiescence before trying an expensive SEE, I use blind and delta prunning.