mvanthoor wrote: ↑Tue Mar 02, 2021 5:26 pmIt seems move sorting is going to be the be-all-end-all, next to raw speed, for engines that don't implement advanced pruning methods (yet).
It is even more important if you use such techniques because how else would you know that the move you are about to prune is likely prunable without having examined it?
There's one more feature that I can recommend if you get around to null move pruning: in case you don't get a fail-high, you may get a move back. This is the threat move that your opponent would like to do if you didn't do anything about it. One recursion level further down from where you are now, this threat move should be ranked rather high because the threat move is likely to refute quite some of the moves on this level, i.e. because these moves don't address the threat.
And a general hint for the part when entering QS from main search: I don't check with "if (depth == 0)". That may bite you once you use reductions. Using "if (depth <= 0)" will spare a either some bug hunting or extra code to check whether the reduction falls straight into QS.
Ras wrote: ↑Tue Mar 02, 2021 5:34 pm
It is even more important if you use such techniques because how else would you know that the move you are about to prune is likely prunable without having examined it?
That's also the reason why Alpha 3 is going to be nicknamed "Get your shit in order" If the hash table doesn't add enough, I might actually turn them around; do the ordering and release that first, and then the hash table.
There's one more feature that I can recommend if you get around to null move pruning: in case you don't get a fail-high, you may get a move back. This is the threat move that your opponent would like to do if you didn't do anything about it. One recursion level further down from where you are now, this threat move should be ranked rather high because the threat move is likely to refute quite some of the moves on this level, i.e. because these moves don't address the threat.
I understand, that a threat is going to come through if you don't do anything about it. But... "you might get a move back" is something I don't understand. Back from what? Where does it come from? The hash table? I'd have to save that move and then look it up in the next call to alpha-beta if I understand correctly.
And a general hint for the part when entering QS from main search: I don't check with "if (depth == 0)". That may bite you once you use reductions. Using "if (depth <= 0)" will spare a either some bug hunting or extra code to check whether the reduction falls straight into QS.
"If depth == 0" means you're in one of the leaf nodes. So you could actually reduce to such an extent that you're NOT going to go all the way down to the leaf nodes of the requested depth? I hope I can find some clear explanations about that when I get to coding these things.
mvanthoor wrote: ↑Tue Mar 02, 2021 5:47 pmBut... "you might get a move back" is something I don't understand. Back from what?
From the next level search. I always initialise the index of the "bestmove" with -1 so that I can check if the search even returns a move. It won't if it fails low on the next level because no move improves the alpha in the next level, for example. My QS doesn't return PVs or best moves either (speed...), only the main search does. So it can also be that due to null move reduction, the null move search falls straight into QS.
I'd have to save that move and then look it up in the next call to alpha-beta if I understand correctly.
Yes, and if you initialise that threat move with something invalid, you also cover the case where you don't have a threat move, for whatever reason.
"If depth == 0" means you're in one of the leaf nodes. So you could actually reduce to such an extent that you're NOT going to go all the way down to the leaf nodes of the requested depth? I hope I can find some clear explanations about that when I get to coding these things.
Let's assume you are at depth==2, and you happen to reduce by 3. Now the depth for the next level is -1. If you check for depth==0 at the next level, the program would hang and finally crash with a stack overflow. Or you could always check that despite reductions, you never reduce more than to 0, but that's extra code that you need in all places. It's easier and more robust to solve that with a depth<=0 comparison at the beginning of the main search where you decide to branch off into QS instead.
So perhaps it is good to stress this a bit: Rasmus' Search() routine doesn't just return the bestScore; it also returns the bestMove. For a move that fails low the move returned by the child will be the refutation of that move. Refutations of a (hypothetical) turn pass are known as 'threats'.
Question to Rasmus: how do you use the threat move in move ordering? If it is a non-capture, it would of course have become a killer, and it would automatically have been searched before other non-captures. But still after the captures. I suppose you still do it that way.
But what if the threat move is a capture? Captures refutations are often very specific to the preceding move. That the threat move was the best capture after null move doesn't mean that it also will be best against other moves; the opponent might put his Queen on an unsafe square, and it would be more advisable to take that. Therefore MVV/LVA gives for captures better result than having 'killer captures' borrowed from a sibbling move.
I can imagine that the threat move could be used for finding non-capture evasions; I did something like that in Joker. If the threat move captured piece X, I ordered a single non-capture of piece X to a safe square with the captures as if it was a capture of a piece X. That helped a bit. Problem was thet MVV/LVA ordering often doesn't identify the true threat. E.g. in positions where Queens are tradable, a PxB threat would still be cashed by playing QxQ first, and then PxB. So Joker then would try to 'rescue' the Queen, which of course would not help much against the PxB. My conclusion was that it would be better to detect LxH captures or captures of unprotected victims already on generation, and return the worst of those as threat move, rather than the cut-move of the search.
For move ordering in the sibblings I would actually be more interested in which captures were searched in vain before the cut-move was found. If RxR failed low (after null move), but PxN fails high (perhaps because the captured Knight was protecting the Rook), it seems more useful to have a kind of 'anti-killer' for the RxR. I would want to try PxN before it in the sibbling nodes, but not if there also is a BxQ I could try...
Ply 14 was started but did not finish in time. So bric finished ply 13 in 35 seconds.
I tried to understand your low branching ratio, so I had a look at your source code. And their does appear something unusual in there: if I understood the code correctly, you search cut-moves that have a QS score above beta not to the nominal depth, but reduce them by 2 ply. Only when they then fail low then, they are re-searched to nominal depth.
That is a pretty hefty reduction. E.g. when you would be searching e7e5 as alternative to d7d5 in the 13 ply search, d4 x e5 would gobble up a Pawn (so QS >= beta), an advantage which every subsequent non-blunder can easily retain. So in the remaining sub-tree, every other level of the remaining 12 would subtract 2 extra ply of the remaining depth, i.e. 4 ply for every 2 real ply, so that it is really searched for only 6 more ply! (So 7 ply in total, instead of 13.)
I am not saying that this is a bad thing to do. But it does involve the risk of leaving the beginning engine developers here with a completely unjustified sense of inferiority, when they compare the performance of their fixed-depth search (+QS) with this...
hgm wrote: ↑Tue Mar 02, 2021 7:00 pmQuestion to Rasmus: how do you use the threat move in move ordering?
If the move is present in the next lower level, it gets a static priority value that puts it up pretty high, but after PV or hash/IID moves - except of course if the threat move is identical to a PV, hash, or IID move. It's also distinct from depth killers, which would receive a lower priority after capture moves if they aren't also PV, hash, IID, or threat moves. It doesn't matter whether it's a capture or a quiet move. Note that the move doesn't have to be there, e.g. if the threat move comes from an opponent piece that I happened to capture in my turn, though that is not triggered by the threat move itself.
the opponent might put his Queen on an unsafe square, and it would be more advisable to take that.
Or the threat may be a mate where taking the queen doesn't matter. I think the actual gain comes from using the information at all. I don't use it for finding actual refutations to the threat - more like making moves and only then checking whether they have addressed the threat, i.e. as testing stone.
Well, I suppose you have empirically established that it helps. But it still seems risky to me; a rather mundane 'threat' could make the null move fail low when current eval is only slightly above beta, and for punishing opponent blunders that move would not be very good. If I could capture a Q that just moved I would expect that to be on average a better choice.
hgm wrote: ↑Tue Mar 02, 2021 9:11 pmBut it still seems risky to me
I don't see much risk here. Let's suppose the "threat" consists of some minor detail such as a NxL exchange that would cost my bishop pair if I don't do anything about it. Now instead of addressing that, I try some stupid queen move where the queen will get captured by a minor piece. In the next level (i.e. opponent search), there will either be a hash move to capture my queen, or IID will show the capture. At that point, the search fails high upon the first move and returns. The queen move has been refuted, but the threat move hasn't even been tried.
The main drawback is if there is no hash move to take the queen, and no IID either beause it's too close to the remaining depth limit. In that case, capturing the queen would not be the first move, but only the second one. Though that leads me to an idea - I could try wether some "capture the last moved opponent piece with your least valuable attacker if there is no hash or IID move" logic would bring some Elo.
I expect it would. I also expect 'blacklisting' captures that did not manage to refute the null move would bring some Elo.
It is true that hash moves / IID to a large extent hide the effect of this kind of move-ordering, so that the benefits it can bring will always be limited.
Ply 14 was started but did not finish in time. So bric finished ply 13 in 35 seconds.
I tried to understand your low branching ratio, so I had a look at your source code. And their does appear something unusual in there: if I understood the code correctly, you search cut-moves that have a QS score above beta not to the nominal depth, but reduce them by 2 ply. Only when they then fail low then, they are re-searched to nominal depth.
That is a pretty hefty reduction. E.g. when you would be searching e7e5 as alternative to d7d5 in the 13 ply search, d4 x e5 would gobble up a Pawn (so QS >= beta), an advantage which every subsequent non-blunder can easily retain. So in the remaining sub-tree, every other level of the remaining 12 would subtract 2 extra ply of the remaining depth, i.e. 4 ply for every 2 real ply, so that it is really searched for only 6 more ply! (So 7 ply in total, instead of 13.)
I am not saying that this is a bad thing to do. But it does involve the risk of leaving the beginning engine developers here with a completely unjustified sense of inferiority, when they compare the performance of their fixed-depth search (+QS) with this...
Hmm, I was not trying to fool anyone. So, I'm glad you pointed that out.
If the hash table doesn't add enough, I might actually turn them around; do the ordering and release that first, and then the hash table.
