Can principal variation search be worth no Elo?

[mvanthoor]

Thanks

But keep in mind that if I remember correctly, you added PVS after you had TT move ordering, TT Cuts, and MVV-LVA, and gained ~56 Elo. The 39 Elo I gained was just with using MVV-LVA and TT-Cuts. If my TT move ordering was playing nice with PVS, I think 15-20 Elo more would be realistic. Not to mention killers.

Yes; most people add killers, history, and often many evaluation terms before they add a TT, but I wanted to beat TSCP with the least amount of features possible. Because TSCP is a one-trick pawn-pony, I added the TT first, because it massively helps in pawn endgames. (Because pawns don't have a lot of moves, they cause many TT hits.)

While I'm glad I found the culprit of this bug, it's such an odd bug. Both the killers and the TT add significant speed, node reduction, and Elo gains to the engine, but when PVS is added to the mix, it just makes things worse. But take them away, and then all of sudden PVS is a strength gaining feature again? Huh? I honestly have no clue what might be at play here, but I have a couple of theories, so I suppose I'll just go from there.

Just add the TT ordering first, by giving the TT-move a higher score than the highest MVV-LVA score, and test again. Then add the killers below the lowest MVV_LVA score and test again.

And I've noticed what you mention with regards to Rustic being stronger against certain engines versus others, although Blunder's improvements are usually optimizations and whatnot. This is now why I always try to pair self-pay with gauntlet testing, which I know you do as well. Seems to be the best way to good an accurate estimate of what the engines Elo will end up being on the CCRL.

Yes. I have had several speed improvements in the current development version, which in total added about 50 Elo (but as the margin is +/- 24, it could also be around 25 or 75). Against some engines in the gauntlet Rustic's performance rating increases (so it wins more games against said engine than it did before the optimizations), while against other engines, nothing seems to have changed. Against two engines rated 2130 and 2160 Rustic only manages 50% score in a head-to-head match, which would put the engine at 2140-2150 level. However, against two engines rated ~2100, Rustic scores +150 Elo for a rating of 2250... and against one 2260 engine, it scores -50 for a rating of 2210.

So... depending on which engines CCRL chooses, the newest Rustic version might be rated 2150, but it could also be 2200 or even higher.

It seems that some engines have, for example, evaluation features that cause them to exploit gaps in Rustic's knowledge. (It only counts material and PST's), and extra speed doesn't fix this. Maybe I should test those two 2130 and 2160 engines against the 2260 engine, to see if that 2260 engine also scores poorly against them; because I know that that engine also only uses PST's and material counting.

I'm not mentioning the specific engines to make sure CCRL doesn't get any idea's about which engines to put in the gauntlet to make it an interesting tournament. I don't want to stack the deck against my own engine, not in favor of it, but also not disadvantaging it.

[mvanthoor]

The latter method since it's more efficient. And currently, I score my moves by making sure the TT move always has the highest score, then the MVV-LVA values, and then finally the killer scores are always below the MVV-LVA values. I think the exact values are something like 60, 56-11, and 10.

Quickly looked over my own code again. As far as I can see, there's no bug in ordering the killer moves. I thought the "value == 0" might make it miss one of the killers, but it doesn't. My engine can use more than 2 killers if I wanted to, and the "value == 0" just makes the loop over the killer array stop as soon as the move in the move list has been found in the killer array and scored. Then the next move in the move list is scored.

So if it's any help, you can take a look at Rustic's move ordering code. (The file is erroneously still called "sorting.rs".)

[algerbrex]

The latter method since it's more efficient. And currently, I score my moves by making sure the TT move always has the highest score, then the MVV-LVA values, and then finally the killer scores are always below the MVV-LVA values. I think the exact values are something like 60, 56-11, and 10.

Quickly looked over my own code again. As far as I can see, there's no bug in ordering the killer moves. I thought the "value == 0" might make it miss one of the killers, but it doesn't. My engine can use more than 2 killers if I wanted to, and the "value == 0" just makes the loop over the killer array stop as soon as the move in the move list has been found in the killer array and scored. Then the next move in the move list is scored.

So if it's any help, you can take a look at Rustic's move ordering code. (The file is erroneously still called "sorting.rs".)

Thanks.

For now to see if I can stomp out the move ordering bug, I copied your code from Rustic verbatim with only the killers and MVV-LVA, and then made PVS and non-PVS versions of Blunder and will run another SPRT test session to see if the improvements from PVS still hold up (or increase).

[mvanthoor]

Thanks.

For now to see if I can stomp out the move ordering bug, I copied your code from Rustic verbatim with only the killers and MVV-LVA, and then made PVS and non-PVS versions of Blunder and will run another SPRT test session to see if the improvements from PVS still hold up (or increase).

I'll be interested to see if this improves matters.

Also take into account that you'll need an MVV_LVA-offset. You need to raise all your scores if the lowest MVV_LVA value is something like 10 or so (as is in my implementation). While you can put the killers at 9 and 8 for example, at some point you'll want to implement the history heuristic, and those values can become large because they're often calculated like "depth * depth". Even though they're capped, you'll quickly hit values over 100, even in a simple engine (more so if you have null move pruning already), and the history heuristic needs to be ordered BELOW the killers. You have to have some space there.

[emadsen]

The latter method since it's more efficient. And currently, I score my moves by making sure the TT move always has the highest score, then the MVV-LVA values, and then finally the killer scores are always below the MVV-LVA values. I think the exact values are something like 60, 56-11, and 10.

Is 60 enough range to ensure proper sort order of moves? Is there a reason you're calculating an integer value for move priority versus using bit-shifting? Bit-shifting seems less prone to move priority bugs.

[mvanthoor]

...

You're giving both killers the same score:

Code: Select all

if search.killers[ply][0].Equal(*move) {
    move.AddScore(KillerMoveScore)
} else if search.killers[ply][1].Equal(*move) {
    move.AddScore(KillerMoveScore)
}

I'm ordering killer[0] higher than killer[1] because it's newer. You're ordering them above the non-ordered quiet moves, but apart from that, the order in which the killers are tried are the one they are generated in. In my case, the newest killer in killer[0] is tried first.

Code: Select all

value = MVV_LVA_OFFSET - ((n as u32 + 1) * KILLER_VALUE);

I don't know if it would actually make a difference; if the newest killer is always the better one to try first.

I might actually try and see if simplifying my killer move setup to 2 moves only makes a speed difference because there's no looping and calculating. Over the weekend... And I might reduce the TT buckets to 2 and remove the loop there as well.

[algerbrex]

Thanks.

For now to see if I can stomp out the move ordering bug, I copied your code from Rustic verbatim with only the killers and MVV-LVA, and then made PVS and non-PVS versions of Blunder and will run another SPRT test session to see if the improvements from PVS still hold up (or increase).

I'll be interested to see if this improves matters.

Also take into account that you'll need an MVV_LVA-offset. You need to raise all your scores if the lowest MVV_LVA value is something like 10 or so (as is in my implementation). While you can put the killers at 9 and 8 for example, at some point you'll want to implement the history heuristic, and those values can become large because they're often calculated like "depth * depth". Even though they're capped, you'll quickly hit values over 100, even in a simple engine (more so if you have null move pruning already), and the history heuristic needs to be ordered BELOW the killers. You have to have some space there.

Well, from some quick preliminary testing, PVS + Killers still seems to be stronger, not sure by how much yet. But PVS + Killers + TT move is still a loss, so there's something still buggy about how I'm dealing with TT moves.

[algerbrex]

The latter method since it's more efficient. And currently, I score my moves by making sure the TT move always has the highest score, then the MVV-LVA values, and then finally the killer scores are always below the MVV-LVA values. I think the exact values are something like 60, 56-11, and 10.

Is 60 enough range to ensure proper sort order of moves? Is there a reason you're calculating an integer value for move priority versus using bit-shifting? Bit-shifting seems less prone to move priority bugs.

Interesting. I've never thought about using bitshifting, but I'm not opposed to doing that. Integer values are what I used originally and what seemed most natural when I started. And as long as the TT move is sorted above MVV-LVA and killers then from my understanding things should be fine, which should be the case with setting the value at 60.

[algerbrex]

...

You're giving both killers the same score:

Code: Select all

if search.killers[ply][0].Equal(*move) {
    move.AddScore(KillerMoveScore)
} else if search.killers[ply][1].Equal(*move) {
    move.AddScore(KillerMoveScore)
}

I'm ordering killer[0] higher than killer[1] because it's newer. You're ordering them above the non-ordered quiet moves, but apart from that, the order in which the killers are tried are the one they are generated in. In my case, the newest killer in killer[0] is tried first.

Code: Select all

value = MVV_LVA_OFFSET - ((n as u32 + 1) * KILLER_VALUE);

I don't know if it would actually make a difference; if the newest killer is always the better one to try first.

I might actually try and see if simplifying my killer move setup to 2 moves only makes a speed difference because there's no looping and calculating. Over the weekend... And I might reduce the TT buckets to 2 and remove the loop there as well.

Right. I tested scoring the 0th killer better than the 1st killer in this new dev version of Blunder, and it was actually a loss, so I removed it. But now it seems to be a win again, so for now I'll score them differently again.

[mvanthoor]

Well, from some quick preliminary testing, PVS + Killers still seems to be stronger, not sure by how much yet. But PVS + Killers + TT move is still a loss, so there's something still buggy about how I'm dealing with TT moves.

I just pass the TT-move to the scoring function and when I find find the TT move in the move list, I score it with a score higher than the highest MVV_LVA score. That's basically all.