SEE is not working for me. Any idea why?

[metax]

You still search them before the non-captures?

No, he does not:

I use exactly the same idea as above, except that I do not "toss" the SEE < 0 captures, I just defer them until after the good captures, killers, etc.

EDIT: Ah, I understand what you mean. No, I think the principle is to search the SEE<0 captures after everything else.

[bob]

And what about normal search? do you something similar or does you "SEEing" all captures and sort them before start the search at move 1?

I use exactly the same idea as above, except that I do not "toss" the SEE < 0 captures, I just defer them until after the good captures, killers, etc.

You still search them before the non-captures?

Sort of. Killers are non-captures and get searched first. But since the captures appear in the move list first, the losers will be the first thing searched after the hash move, good captures and killers are finished.

[metax]

Sort of. Killers are non-captures and get searched first. But since the captures appear in the move list first, the losers will be the first thing searched after the hash move, good captures and killers are finished.

Why not search them after the non-captures? Wouldn't that work better?

[bob]

Sort of. Killers are non-captures and get searched first. But since the captures appear in the move list first, the losers will be the first thing searched after the hash move, good captures and killers are finished.

Why not search them after the non-captures? Wouldn't that work better?

No idea, but generally if Crafty fails high, it fails high on the first move searched about 92% of the time. By the time we get to "the rest of the moves" ordering is irrelevant. Searching them "after" would require stepping over them first, which would cost a small amount of time...

Only done in normal search however, which is way less than 1/2 of the tree space searched, thanks to the q-search.

[Kempelen]

Here is what I do.

1. generate all capture moves.

2. Sort the moves in simple MVV/LVA order (easy idea is sort_value = captured_piece<<4 + capturing piece)

3. Start searching. As I prepare to search a capture, I ask the following question: "Is the capturing piece less valuable than the captured piece, which is a material winner?" If so, I search it. If the answer is no, I use classic SEE to compute an expected material loss or gain, and if this value is >= 0, I search the move, otherwise I discard it and move to the next one.

The reason for the order of the above steps is to save time. The idea is this. You are going to search in MVV/LVA order as that has been proven to be slightly faster overall than searching in pure SEE order. And since SEE is expensive, you only want to do it when necessary. PxN doesn't need a SEE score, it is not going to lose material according to SEE (which doesn't include pins, overloads, etc). So we only apply SEE when we are not so sure, such as in cases like QxR which might win a rook, or it might lose the queen for the rook, so we want more information before deciding to search that move or not.


Hope that helps.

And what about normal search? do you something similar or does you "SEEing" all captures and sort them before start the search at move 1?

I use exactly the same idea as above, except that I do not "toss" the SEE < 0 captures, I just defer them until after the good captures, killers, etc.

After testing this, for normal search, with 1500 games I have seen this work worse than my last implementation. The reason is that if I rank all captures wih MVV/LVA, and when searching if a captures is SEE<0 the send it to end of move list, then in this situation I am discarting a capture been a killer sorted(killer are usually sorted up of bad captures).

In my understanding, you are loosing tactical opportunities because possible bad-captures been killers are only probed after other killers and history has been done. Do you solve this in any way??

thanks.

[Sven]

Here is what I do.

1. generate all capture moves.

2. Sort the moves in simple MVV/LVA order (easy idea is sort_value = captured_piece<<4 + capturing piece)

3. Start searching. As I prepare to search a capture, I ask the following question: "Is the capturing piece less valuable than the captured piece, which is a material winner?" If so, I search it. If the answer is no, I use classic SEE to compute an expected material loss or gain, and if this value is >= 0, I search the move, otherwise I discard it and move to the next one.

The reason for the order of the above steps is to save time. The idea is this. You are going to search in MVV/LVA order as that has been proven to be slightly faster overall than searching in pure SEE order. And since SEE is expensive, you only want to do it when necessary. PxN doesn't need a SEE score, it is not going to lose material according to SEE (which doesn't include pins, overloads, etc). So we only apply SEE when we are not so sure, such as in cases like QxR which might win a rook, or it might lose the queen for the rook, so we want more information before deciding to search that move or not.


Hope that helps.

And what about normal search? do you something similar or does you "SEEing" all captures and sort them before start the search at move 1?

I use exactly the same idea as above, except that I do not "toss" the SEE < 0 captures, I just defer them until after the good captures, killers, etc.

After testing this, for normal search, with 1500 games I have seen this work worse than my last implementation. The reason is that if I rank all captures wih MVV/LVA, and when searching if a captures is SEE<0 the send it to end of move list, then in this situation I am discarting a capture been a killer sorted(killer are usually sorted up of bad captures).

In my understanding, you are loosing tactical opportunities because possible bad-captures been killers are only probed after other killers and history has been done. Do you solve this in any way??

thanks.

Many people do never store captures as killer moves. This could already solve it for you. But if you want to allow losing captures as killers then why not just ask whether it is also a killer before sending a SEE<0 move to the bottom?

Sven

[Kempelen]

Here is what I do.

1. generate all capture moves.

2. Sort the moves in simple MVV/LVA order (easy idea is sort_value = captured_piece<<4 + capturing piece)

3. Start searching. As I prepare to search a capture, I ask the following question: "Is the capturing piece less valuable than the captured piece, which is a material winner?" If so, I search it. If the answer is no, I use classic SEE to compute an expected material loss or gain, and if this value is >= 0, I search the move, otherwise I discard it and move to the next one.

The reason for the order of the above steps is to save time. The idea is this. You are going to search in MVV/LVA order as that has been proven to be slightly faster overall than searching in pure SEE order. And since SEE is expensive, you only want to do it when necessary. PxN doesn't need a SEE score, it is not going to lose material according to SEE (which doesn't include pins, overloads, etc). So we only apply SEE when we are not so sure, such as in cases like QxR which might win a rook, or it might lose the queen for the rook, so we want more information before deciding to search that move or not.


Hope that helps.

And what about normal search? do you something similar or does you "SEEing" all captures and sort them before start the search at move 1?

I use exactly the same idea as above, except that I do not "toss" the SEE < 0 captures, I just defer them until after the good captures, killers, etc.

After testing this, for normal search, with 1500 games I have seen this work worse than my last implementation. The reason is that if I rank all captures wih MVV/LVA, and when searching if a captures is SEE<0 the send it to end of move list, then in this situation I am discarting a capture been a killer sorted(killer are usually sorted up of bad captures).

In my understanding, you are loosing tactical opportunities because possible bad-captures been killers are only probed after other killers and history has been done. Do you solve this in any way??

thanks.

Many people do never store captures as killer moves. This could already solve it for you. But if you want to allow losing captures as killers then why not just ask whether it is also a killer before sending a SEE<0 move to the bottom?

Sven

Quite simple. Five minutes after sending the post I was thinking on do it that way... thanks.

[bob]

Here is what I do.

1. generate all capture moves.

2. Sort the moves in simple MVV/LVA order (easy idea is sort_value = captured_piece<<4 + capturing piece)

3. Start searching. As I prepare to search a capture, I ask the following question: "Is the capturing piece less valuable than the captured piece, which is a material winner?" If so, I search it. If the answer is no, I use classic SEE to compute an expected material loss or gain, and if this value is >= 0, I search the move, otherwise I discard it and move to the next one.

The reason for the order of the above steps is to save time. The idea is this. You are going to search in MVV/LVA order as that has been proven to be slightly faster overall than searching in pure SEE order. And since SEE is expensive, you only want to do it when necessary. PxN doesn't need a SEE score, it is not going to lose material according to SEE (which doesn't include pins, overloads, etc). So we only apply SEE when we are not so sure, such as in cases like QxR which might win a rook, or it might lose the queen for the rook, so we want more information before deciding to search that move or not.


Hope that helps.

And what about normal search? do you something similar or does you "SEEing" all captures and sort them before start the search at move 1?

I use exactly the same idea as above, except that I do not "toss" the SEE < 0 captures, I just defer them until after the good captures, killers, etc.

After testing this, for normal search, with 1500 games I have seen this work worse than my last implementation. The reason is that if I rank all captures wih MVV/LVA, and when searching if a captures is SEE<0 the send it to end of move list, then in this situation I am discarting a capture been a killer sorted(killer are usually sorted up of bad captures).

In my understanding, you are loosing tactical opportunities because possible bad-captures been killers are only probed after other killers and history has been done. Do you solve this in any way??

thanks.

The idea is that removing the largest piece first (MVV) reduces the size of the tree significantly compared to removing the piece with the largest material gain. So we are talking about a small efficiency issue. The difference between using normal SEE ordering and MVV/LVA ordering is very small. But, in the q-search, where you can toss out captures with SEE < 0, the gain can be more than 2x, which is where SEE is really useful.

[P. Villanueva]

I´m also trying SEE and having no good results.

I´ve searched your position with a plain PVS algorithm (no null-move, no transposition table, no futility pruning, no LMR). I used SEE for delaying losing captures in alfabeta search and skiping them in quiesce.
The move ordering was MVV/LVA, killer, promotions, history.
I get these results:

Code: Select all

# Ajedrez KMT Chess v2.0-alfa.
# Copyright 2009 - 2010 Paul Villanueva.
# Teclee ayuda para ver la lista de comandos.
# Belay: fen 1k1r3q/1ppn3p/p4b2/4p3/8/P2N2P1/1PP1R1BP/2K1Q3 w - -
 1    -45     0         2 d3b4
 1    -25     0        11 g2f3
 1    -20     0        26 e1c3
 1    -10     2        29 c1b1
 2    -30     2        89 c1b1 h8g7
 2    -25     2       230 e1b4 d7b6
 3     -5     2       422 e1b4 d7b6 c1b1
 3     65     3      1223 g2h3 h8g7 h3d7 g7d7 d3e5 f6e5 e2e5
 4     60     5      3618 g2h3 d7b6 d3e5 h8g7
 5     -5    11     15257 g2h3 h8g7 h3d7 g7h6 c1b1 d8d7 d3e5 f6e5 e2e5 h6h2
 6     -5    26    101360 g2h3 h8g7 h3d7 g7h6 c1b1 d8d7 d3e5 f6e5 e2e5 h6h2
 7    -15   126    651224 g2h3 d7b6 h3g2 b6c4 e1b4 c4d6 c1b1
 7     -5   203   1109153 c1b1 h8g7 g2h3 g7h6 h3d7 d8d7 d3e5 f6e5 e2e5 h6h2
 7     70   304   1789077 e1b4 d7b6 b4e4 c7c6 d3e5 f6e5 e4e5 h8e5 e2e5
 8     70   782   4863009 e1b4 d7b6 b4e4 c7c6 d3e5 f6e5 e4e5 h8e5 e2e5
 9     60  3816  21057382 e1b4 d7b6 b4e4 c7c6 d3e5 f6e5 e4e5 h8e5 e2e5 b6c4
NPS: 601019
Tiempo: 6000
Nodos: 36061184

Without SEE

Code: Select all

 1   -340     0        15 d3e5 d7e5
 1   -315     0        26 g2b7 b8b7
 1    -45     0        44 d3f2
 1    -25     1        47 g2f3
 1    -20     1        64 e1c3
 1    -10     1        67 c1b1
 2    -30     1       206 c1b1 h8g7
 2    -25     1       853 e1b4 d7b6
 3     -5     1      1967 e1b4 d7b6 c1b1
 3     65     1      3610 g2h3 h8g7 h3d7 g7d7 d3e5 f6e5 e2e5
 4     60     3      7689 g2h3 d7b6 d3e5 h8g7
 5     -5     6     36277 g2h3 h8g7 h3d7 g7h6 c1b1 d8d7 d3e5 f6e5 e2e5 h6h2
 6     -5    22    176226 g2h3 h8g7 h3d7 g7h6 c1b1 d8d7 d3e5 f6e5 e2e5 h6h2
 7    -15   140   1208919 g2h3 d7b6 h3g2 b6c4 e1b4 c4d6 c1b1
 7     -5   265   2365806 c1b1 h8g7 g2h3 g7h6 h3d7 d8d7 d3e5 f6e5 e2e5 h6h2
 7     70   349   3061885 e1b4 d7b6 b4e4 c7c6 d3e5 f6e5 e4e5 h8e5 e2e5
 8     70   770   6789137 e1b4 d7b6 b4e4 c7c6 d3e5 f6e5 e4e5 h8e5 e2e5
 9     60  3864  32465159 e1b4 d7b6 b4e4 c7c6 d3e5 f6e5 e4e5 h8e5 e2e5 b6c4
NPS: 853947
Tiempo: 6000
Nodos: 51236864

I got a noticeable reduction in nodes for each depth, but the terrible drop in terms of NPS avoid any profit.

[Sven]

I´m also trying SEE and having no good results.

I´ve searched your position with a plain PVS algorithm (no null-move, no transposition table, no futility pruning, no LMR). I used SEE for delaying losing captures in alfabeta search and skiping them in quiesce.
The move ordering was MVV/LVA, killer, promotions, history.
I get these results:

Code: Select all

[...]
 8     70   782   4863009 e1b4 d7b6 b4e4 c7c6 d3e5 f6e5 e4e5 h8e5 e2e5 
 9     60  3816  21057382 e1b4 d7b6 b4e4 c7c6 d3e5 f6e5 e4e5 h8e5 e2e5 b6c4
NPS: 601019
Tiempo: 6000
Nodos: 36061184

Without SEE

Code: Select all

[...]
 8     70   770   6789137 e1b4 d7b6 b4e4 c7c6 d3e5 f6e5 e4e5 h8e5 e2e5
 9     60  3864  32465159 e1b4 d7b6 b4e4 c7c6 d3e5 f6e5 e4e5 h8e5 e2e5 b6c4
NPS: 853947
Tiempo: 6000
Nodos: 51236864

I got a noticeable reduction in nodes for each depth, but the terrible drop in terms of NPS avoid any profit.

I would compare with and without SEE using a fixed depth search, not fixed time as you did. Otherwise you can't tell which version uses less time for the same number of iterations, which would be crucial in my opinion to judge whether SEE helps in your case (for that single position - see below) by returning the same result faster, and therefore being able to search somewhat deeper.

Second point is that doing a comparison based on only one test position is usually not sufficient to draw any conclusion from it. You should use a larger test set at least, but even better in my opinion would be to play a statistically significant number of games.

Also it is difficult for the reader to judge about your results since it is unknown at which point in time your program prints a new PV line:
a) immediately if a new root move improves the old PV, or
b) only at the end of each iteration.
I would assume you do a), which implies that the times that were needed for completing a whole iteration are not visible directly.

Sven