Kempelen wrote:bob wrote:hgm wrote:bob wrote:1. how did you find the first 3 "best moves"? Not with a normal alpha.
Define "normal alpha". This obviously depends on if you are doing PVS or alpha-beta, if you do asipration or not.
For me, "normal" would be -INFINITY when you don't do aspiration, and score_of_previous_iteration - lowerMargin when you do. Of course you would use the score of the 3rd move in the multi-PV case.
2. Once you find the first "best 3" you absolutely set alpha "artificially low". Why? Because you are setting it _lower_ than the actual score for the third-best move, once you actually find the real 3rd best move.
Why on Earth would I do that? Once I actually find the real 3rd best move, alpha is of course set to the score of that. Why would you set it lower? Both in alpha-beta and PVS one usully increases alpha, when one finds a move with a better score.
Let me make it simpler.
There are 4 moves, A, B, C and D. A, B and D are the real best 4.
Once you have searched A, B and C, C is the 3rd best so far, and you are searching with its score as alpha. But D is the _real_ 3rd best move and has a higher score. So while searching all moves
after C, you are using C's score as alpha, and it is lower than the real 3rd best move's score.
So again, how is this supposedly superior to what I am currently doing?
Maybe I am confused also, but I agree with H.G.
why? As I understand the proposed system work like a normal root move search: first we try 1st move and its score it sets as new alpha, then we search the 2nd move and if is score is better than new alpha, we set that move as new best and its score as new alpha, then try again with 3nd and so on. The only difference with multiPV is that 3 first moves are -Infinite as alpha and after third is like a normal search as I have described. In both cases we are searching for "best moves than a previous one"
That's not what is happening. Let me run thru both choices for clarity.
In Crafty, at depth N I search normally. The first move will initially be the best move, and about 85% of the time it remains best. All the rest of the moves are searched with a null-window fail-soft search (fail soft means that I store HT entries with scores outside the alpha/beta bound, whatever gets backed up). I save it, remove it from the move list, and re-start the search with normal aspiration. Now, since the first move is missing, we find another "best move" which is initially the first move left in the list. And often this is really the second best move due to the move ordering by node count at the root. Most of the remaining moves (assuming this one is best) get dismissed instantly with hash hits or shallow searches. I repeat for the 3rd, and 4th etc.
The alternative is to do a normal search, but once you get a score for the best move, you artificially lower alpha enough to pick up the 2nd best (and other) moves. If you don't lower it enough, everythying fails low and you get nothing and have to do it again. If you lower it too far, other moves will fail high and have to be evaluated, just because their score is > alpha. Any search where alpha != beta-1 is very expensive to do. Once you get 3 best moves, you can set alpha to the smallest of the 3 scores, so that only moves that are better will fail high.
The issue is searching the 2nd, 3rd moves in the list with the offset alpha value just to get 3 "best moves". And then expending significant effort to prove that they are the best.
I see no way this is more efficient than what I am doing at present. The interesting case is not the one where the first 3 root moves really are best, but the case where the best N moves are scattered throughout the move list,
My preference for the way I do things in Crafty is simplicity.
Some sample data:
Code: Select all
19-> 52.81 -0.17 18. ... Bc7 19. Rac1 f5 20. Nd2 Kh8
21. Kh1 Rac8 22. e4 Nf6 23. exf5 Qd7
24. Nc4 Qxf5 25. Qe2 e4 26. dxe4 Qxe4+
27. Qxe4 Nxe4 28. Bd4
20 1:25 -0.15 18. ... Bc7 19. Rac1 f5 20. Nd2 Kh8
21. Kh1 Rac8 22. e4 Nf6 23. exf5 Qd7
24. Nc4 Qxf5 25. Qe2 Rfe8 26. Rfe1
Rcd8 27. Nxe5 Bxe5 28. Bxe5 Rxd3
20-> 1:29 -0.15 18. ... Bc7 19. Rac1 f5 20. Nd2 Kh8
21. Kh1 Rac8 22. e4 Nf6 23. exf5 Qd7
24. Nc4 Qxf5 25. Qe2 Rfe8 26. Rfe1
Rcd8 27. Nxe5 Bxe5 28. Bxe5 Rxd3
If you notice, the first (best) move takes about 35 seconds to complete, the remainder of the moves take 4 seconds. If we remove this move from the list, we repeat this process again with roughly the same time required. There are some efficiency issues related to choosing one of these algorithms:
(1) once you find the best move, remove it from the list, and start back over at depth 1 and find the best move and build up good move ordering information to help the search;
(2) at the final ply, lower alpha to force other best moves to pop to the top of the list, without good move ordering information which makes the search less efficient. Very similar to the idea of just starting at depth N rather than using an iterated search.
This appears to be the primary reason I was seeing better performance with the current way I do things, assuming you believe that an iterated search approach is better.
In this same light, many use the idea that when a move fails low at the root, you should completely re-start the search at depth 1 to find a new best move using something better than just starting a blind/deep search. Since the fail low hash entry should stick around, the old best move will fail low on each iteration and not become the best move again.
Complex topic, lots to test. I've been experimenting with the fail-low-at-root -> restart idea as well. It has some advantages...