bob wrote:Depends on your definition of "incomplete plies". If you mean a ply where you terminated due to a search time-out, you NEVER store those results, lest you plant the seeds from which a blunder will eventually grow.
I am not trying to be confrontational, I am just confused. Why wouldn't I use partial results from a search?
Let's ignore aspiration search for a minute. Imagine I am searching at depth d and I have explored only 5 moves of the 40 moves available when I run out of time. The first move I explored is of course the move that was considered best after the depth d-1 search, and the third move I searched happened to score higher. I have just proven that at depth d the third move that is better than the one I found at depth d-1. Why wouldn't I play that move?
Or perhaps when you are using aspiration search the situation is different? (I don't see why.)
matthewlai wrote:What kind of improvements are people getting with PVS compared to good old alpha-beta (with aspiration window)?
Always felt PVS was obviously useful without an aspiration window but when added the added complexity is not really worth it ontop of all the already null window searches of nullmove too. Which become a significant part of the search space as you search deeper.
Then again I'm doing iterative search in my engines and researches are always hard on the eye to code and I hate them. Even adding nullmove breaks my heart.
bob wrote:Depends on your definition of "incomplete plies". If you mean a ply where you terminated due to a search time-out, you NEVER store those results, lest you plant the seeds from which a blunder will eventually grow.
I am not trying to be confrontational, I am just confused. Why wouldn't I use partial results from a search?
Let's ignore aspiration search for a minute. Imagine I am searching at depth d and I have explored only 5 moves of the 40 moves available when I run out of time. The first move I explored is of course the move that was considered best after the depth d-1 search, and the third move I searched happened to score higher. I have just proven that at depth d the third move that is better than the one I found at depth d-1. Why wouldn't I play that move?
Or perhaps when you are using aspiration search the situation is different? (I don't see why.)
Suppose your search plays QxP at ply = N, and for some reason, the best reply (the move that completely refutes QxP) gets ordered last at the next ply. If you get half-way through that search, and time out and store it in the ttable, you have a REALLY incorrect score. You think you are winning a pawn in that position when you are really losing a queen for a pawn. If you use that bogus score on the next search, you can easily choose a bad move.
A partial result at ply=1 is different. You should play the best move you have, but you do have to realize that it might not be the best move available, since you have not searched all of them. Most reasonable programs today seem to try to complete the current iteration before timing out to avoid exactly this situation.
I was talking about nodes internal to the tree. Not at the root where I would always play move 3 if it produced a better score than move 1, even though I know that moves 4 through 35 might be better.
bob wrote:
I was talking about nodes internal to the tree. Not at the root where I would always play move 3 if it produced a better score than move 1, even though I know that moves 4 through 35 might be better.
Oh, that was the source of the confusion. I was talking about the root only. Of course the score of any partial search should be discarded.
bob wrote:First, you are testing incorrectly. PVS works when the first move is best and move ordering is working as expected. IE in the normal chess positions you encounter in games.
WAC is a bunch of positions where the goal is to find a non-obvious move that works by some tactical trick. By definition you are going to have to change your mind to the correct move, once you get deep enough, and that re-search when you get the null-window fail high, then the PVS fail high, and then finally reset the aspiration beta value and start again, is the thing that hurts. HERE. But PVS is about the average case, not about the worst case. And yet WAC is nothing but "worst cases".
PVS is a "calm water" algorithm. Don't try to sail it into a hurricane, it will sink. But in calm water it works flawlessly. As Gene Amdahl used to preach, "design for the common case, not the exceptional one" if you want to make something better.
I did find out about that as well. It's an improvement for mlmfl (positions after common opening lines).
But that begs the question - if that's the case, does PVS actually help?
On positions where we don't change the PV, PVS allows us to search deeper, but if we aren't changing our mind anyways, searching deeper is just wasting time.
On positions where we do change the PV, PVS seems to be slower in my case, which means it will miss deeper tactical lines.
So it seems to me like PVS makes the search faster where it doesn't matter, and slower where it does matter?
Think about this: You search N plies deep and start iteration N+1. You search the first move and get a score and now search the remainder using a null-window. If you fail high, you JUST found a better move at reduced cost, compared to what it would have taken you to just search with original aspiration beta value as the upper bound. But when you get lots of "mind changes" PVS falls a bit flat. It just doesn't happen that frequently, except in positions that are highly tactical where every new iteration exposes some new tactic and screws up move ordering for those branches at the same time...
I guess that means I have to start using results from incomplete plies. Right now I only use the result of a ply if it actually finishes.
Otherwise, it doesn't really matter that we get to the fail high faster in iteration N + 1, since iteration N + 1 will take longer to complete anyways due to the re-search.
Depends on your definition of "incomplete plies". If you mean a ply where you terminated due to a search time-out, you NEVER store those results, lest you plant the seeds from which a blunder will eventually grow. If you mean a ply where you fail high, that is not "incomplete". You searched all that was required to prove that the previous move (previous ply) was a mistake that is refuted by at least this move if not others. That is a complete ply also, just like a ply where you search everything and discover alpha was unchanged after you finished.
That makes sense. I'll have to think about how to implement that. Right now I never use anything from an iteration that doesn't finish.
Disclosure: I work for DeepMind on the AlphaZero project, but everything I say here is personal opinion and does not reflect the views of DeepMind / Alphabet.
matthewlai wrote:That makes sense. I'll have to think about how to implement that. Right now I never use anything from an iteration that doesn't finish.
Assuming you search root move by root move and keep your best move at the front of the list of root moves, it does not make sense not to use information gained by completely searching individual (but not all) root moves.
Suppose you have completely finished iteration 10 and only searched two moves in iteration 11. If the second root move searched to depth 11 turned out to be better than the first root move searched to depth 11 (i.e. the move that was best when searched to depth 10), then clearly that second root move should be played and not the first root move. (If the second root move overtook the first root move due to the first root move dropping in eval, then it would be good to allocate more search time and try finishing the iteration, but that can be implemented as a further improvement.)
matthewlai wrote:That makes sense. I'll have to think about how to implement that. Right now I never use anything from an iteration that doesn't finish.
Assuming you search root move by root move and keep your best move at the front of the list of root moves, it does not make sense not to use information gained by completely searching individual (but not all) root moves.
Suppose you have completely finished iteration 10 and only searched two moves in iteration 11. If the second root move searched to depth 11 turned out to be better than the first root move searched to depth 11 (i.e. the move that was best when searched to depth 10), then clearly that second root move should be played and not the first root move. (If the second root move overtook the first root move due to the first root move dropping in eval, then it would be good to allocate more search time and try finishing the iteration, but that can be implemented as a further improvement.)
Yes it makes sense. It's just a little tricky to implement for me since I do not have a separate root search routine.
All I am doing is calling regular search on the root node, and essentially retrieving the best move from the transposition table.
Disclosure: I work for DeepMind on the AlphaZero project, but everything I say here is personal opinion and does not reflect the views of DeepMind / Alphabet.
v = -Search(-alpha-1, -alpha, depth-R-1, ...)
if ((!R && v > alpha && v < beta) || (R && v > alpha))
v = -Search(-beta, -alpha, depth-1, ...)
i.e. you shouldn't trust the v < beta score when R > 0...?