hgm wrote:Actually I have seen several people claiming here that MVV/LVA-like schemes not using SEE were performing better than SEE-based ordering.
What works even better for me than the Glaurung ordering is:
1) Determine the victim value for each capture.
2) Discard all captures with unworthy victims (futility)
3) Upgrade the victim value of captures with the threatened piece or of the piece threatening it by the opponent's SEE score on this piece.
4) Replace this adjusted victim value by SEE score when (adjusted) victim < attacker or victim < highest threatened piece.
5) use this victim value / SEE score to sort the moves
6) in case of equality, lowest attacker goes first.
Step 3 or 4b are only relevant in nodes where the null move failed low because it was refuted by a good capture of the opponent. Usually this is not the case.
So QxQ with SEE=0 will be tried before PxN with SEE=+2 (like Glaurung does).
An additional advantage of this ordering is that you don't use SEE as often as with the Glaurung scheme.
However, you are _still_ not trying the best capture first, so I don't see how it could possibly be better. I'll give this a whirl today and report the results back...
And note that testing this with 200 games is not going to come anywhere near the truth. Probably 10,000 games won't cut it...
bob wrote: You have a _better_ score using SEE, yet you use a weaker algorithm (MVV/LVA) to order what SEE says are non-losing captures. Why would it be better to try a move like NxR (winning an exchange) before trying QxB winning a whole bishop?
I'll try to run this test this week as I can get some _very_ accurate resolution on whether it is better or worse and by how much.
Thanks.
Please test the original Glaurung version (without the per-square MVV/LVA), I have quite important hints it _should_ be better. And you shouldn't need a lot of games to prove it, at least according to my tests.
I think the reason is that in presence of a winning capture performs better first do the equal exchanges, then the winning capture.
This is a chess rule: a winning capture gives you a big advantage anyway, but the advantage is bigger if few pieces remain, so that has sense to do the equal exchanges before the winning one: the final position will be a won one and fewer pieces remain on board the better!
bob wrote: You have a _better_ score using SEE, yet you use a weaker algorithm (MVV/LVA) to order what SEE says are non-losing captures. Why would it be better to try a move like NxR (winning an exchange) before trying QxB winning a whole bishop?
I'll try to run this test this week as I can get some _very_ accurate resolution on whether it is better or worse and by how much.
Thanks.
Please test the original Glaurung version (without the per-square MVV/LVA), I have quite important hints it _should_ be better. And you shouldn't need a lot of games to prove it, at least according to my tests.
I think the reason is that in presence of a winning capture performs better first do the equal exchanges, then the winning capture.
This is a chess rule: a winning capture gives you a big advantage anyway, but the advantage is bigger if few pieces remain, so that has sense to do the equal exchanges before the winning one: the final position will be a won one and fewer pieces remain on board the better!
Marco
yes, but that is a +human+ concept. Alpha/Beta doesn't agree with that idea, it simply wants scores > beta or scores < alpha, and whenever you can raise alpha or lower beta, the tree shrinks. Winning captures will change the bounds where exchanges will not, and that should reduce the size of the tree.
More to come... I still suspect this difference will not be that large in terms of Elo, which will make a lot of games necessary. But we'll see... And I will try Glaurung's approach first. I assume we are talking about doing this _everywhere_ we order the captures, also, not just in q-search?
I am now running a test with "stock Crafty 22.6R01" which is 22.6 (identical with 22.5 at the moment) against Crafty 22.6R02, which does what Tord is doing with respect to move ordering. I use SEE to screen captures with SEE <0, but then order all captures that are left (including those where a small piece captures a big piece and doesn't need SEE to see it is a winning move) using normal MVV/LVA. I am making two runs with normal crafty, 32,000 games per run, to use for a baseline, and then will run two 32,000 game matches with the new ordering to see what effect (if any) this has.
I tried several tactical positions and found the usual behavior where some were faster with the new approach, some were slower. Overall over only 12 position, the new approach was slower overall but not by a huge amount. WAC #2 seemed to be the worst case where the new (MVV/LVA after SEE) was over 6x slower because the tree ballooned into something big...
more in a couple of hours. These matches take about one hour per 32,000 games, the second run with normal crafty is almost done so about 2 hours will have some results ready to post...
First run has completed. I have two "originals" and one "SEE - MVV/LVA" run so far.
Crafty-22.6R01 is normal Crafty. 22.6R02 uses the SEE + MVV/LVA ordering we were discussing. The -101 and -102 in the names is a meaningless tag I add to keep the runs separate. Here are the results so far. The 4th test is in progress. I'll post the entire thing so far.
Name Elo + - games score oppo. draws
Crafty-22.6R02-101 2595 4 4 31128 49% 2599 20%
Crafty-22.6R01-101 2588 4 4 31128 48% 2599 21%
Crafty-22.6R01-102 2587 4 4 31128 48% 2599 21%
So a bit of a surprise, but the two are within the error bar of each other so whether or not the difference is that significant is uncertain. 7Elo with a +/-4 range. Second run should be done in an hour. More then.
Name Elo + - games score oppo. draws
Crafty-22.6R02-101 2600 5 4 31128 49% 2604 20%
Crafty-22.6R02-102 2600 4 5 31128 49% 2604 21%
Crafty-22.6R01-101 2593 4 4 31128 48% 2604 21%
Crafty-22.6R01-102 2592 5 4 31128 48% 2604 21%
The new version checks in pretty reliably better, although I am still not certain exactly why this would be. The new version hits 2600 twice, the older version is between 2592 and 2593 twice. So 7-8 Elo, again remembering the error bar, but with a total of 62,000 games (which I could combine into two lines above if anyone wants) the error bar would be even smaller while the Elo numbers would not change.
bob wrote: You have a _better_ score using SEE, yet you use a weaker algorithm (MVV/LVA) to order what SEE says are non-losing captures. Why would it be better to try a move like NxR (winning an exchange) before trying QxB winning a whole bishop?
I'll try to run this test this week as I can get some _very_ accurate resolution on whether it is better or worse and by how much.
Thanks.
Please test the original Glaurung version (without the per-square MVV/LVA), I have quite important hints it _should_ be better. And you shouldn't need a lot of games to prove it, at least according to my tests.
I think the reason is that in presence of a winning capture performs better first do the equal exchanges, then the winning capture.
This is a chess rule: a winning capture gives you a big advantage anyway, but the advantage is bigger if few pieces remain, so that has sense to do the equal exchanges before the winning one: the final position will be a won one and fewer pieces remain on board the better!
Marco
The reason is different. If you exchange, say, QxQ first, you reduce the tree removing poweful pieces. If you take the pawn first, you will end up analyzing every single possible capture that the opponen queen has. The result is the same, but if you do QxQ, the tree will be smaller.
Name Elo + - games score oppo. draws
Crafty-22.6R02-101 2600 5 4 31128 49% 2604 20%
Crafty-22.6R02-102 2600 4 5 31128 49% 2604 21%
Crafty-22.6R01-101 2593 4 4 31128 48% 2604 21%
Crafty-22.6R01-102 2592 5 4 31128 48% 2604 21%
The new version checks in pretty reliably better, although I am still not certain exactly why this would be. The new version hits 2600 twice, the older version is between 2592 and 2593 twice. So 7-8 Elo, again remembering the error bar, but with a total of 62,000 games (which I could combine into two lines above if anyone wants) the error bar would be even smaller while the Elo numbers would not change.
michiguel wrote:The reason is different. If you exchange, say, QxQ first, you reduce the tree removing poweful pieces. If you take the pawn first, you will end up analyzing every single possible capture that the opponen queen has. The result is the same, but if you do QxQ, the tree will be smaller.
Miguel
Interesting, so capturing pieces that have a lot of capturing opportunities first is another way of trying this. MVV is cheap way of representing this though, so I'm not sure it would be worth doing the actual counting.
Name Elo + - games score oppo. draws
Crafty-22.6R02-101 2600 5 4 31128 49% 2604 20%
Crafty-22.6R02-102 2600 4 5 31128 49% 2604 21%
Crafty-22.6R01-101 2593 4 4 31128 48% 2604 21%
Crafty-22.6R01-102 2592 5 4 31128 48% 2604 21%
The new version checks in pretty reliably better, although I am still not certain exactly why this would be. The new version hits 2600 twice, the older version is between 2592 and 2593 twice. So 7-8 Elo, again remembering the error bar, but with a total of 62,000 games (which I could combine into two lines above if anyone wants) the error bar would be even smaller while the Elo numbers would not change.
One of those things that makes you go hmmmm.....
I am not surprised at all!
Miguel
I'm not that surprised, because the gain is very small. But I had expected it to be a very small loss, rather than a small gain. I will try this on some longer games as well to see if that changes anything at all... But when I saw WAC2 take 6x longer, I expected to see a loss, so it was a bit of a surprise. SEE is simply more accurate so I am not sure why using SEE to cull moves, and then mvv/lva to actually sort them is of any benefit. I'm going to study it to understand why, however, assuming this is not an artifact of playing fast games (these games were 10 seconds + 10ms increment per move...)
Probably the most interesting thing is that this takes a _lot_ of games to measure the benefit. It is very small. Which leads me to believe that many have depended on superstition and assumed that this works, since it is not so easy to measure...
