4CPU and 4 different evals.

[bob]

Which do you think would be more accurate:

(1) search to depth D in the normal way.

(2) starting at the root, do some shallower searches until you get to depth D/2, then starting there, search to something like depth D/2 + N (where N is small).

(1) search to depth D in the normal way... but play out the pv line . Does it >=match your previous pv line evaluation score? or did it drop significantly?

Why can you not go back to the root if you force the pv line1,
and do another search and see it was a bad move at the same time?

Because PV + a few plies tacked on to the end of the PV is not anywhere near the same as searching PV a few plies deeper. If you add a few moves on to the end, how do you know that the moves at the end of the old PV can not be improved on? Without searching them?

Again, Greenblatt proposed this idea. Even back in the days when he did a pure 5 ply forward-pruned search. Several of us tried it and threw it out as badly flawed. Anyone can try the idea if they want, of course. I'd rather go one or 2 plies deeper along every branch, using the current forward pruning/reduction ideas, rather than going a few plies deeper at the end of the PV, with no opportunity to change any of the PV moves.

pv_line1+pv_line2,

pv1 = pv_line1;
pv1 = e2e4 e7e5 g1f3 b8c6 f1b5

pv2 = pv_line2;
pv2 = a7a6 b5c6 b7c6 0-0 g8f6

pv = pv1+ pv2;
pv = e2e4 e7e5 g1f3 b8c6 f1b5 a7a6 b5c6 b7c6 0-0 g8f6

Say your pv2 sees that pv1 was a bust. There are a couple ways that can be tried.

Take your pv1, e2e4 e7e5 g1f3 b8c6 f1b5,
and work backards from the last pv_line1 ply, f1b5.

Increment to the next move ordered in your list. Assuming you order them from best score to worse. Next being, f1c4.

pv1 = pv_line1;
pv1 = e2e4 e7e5 g1f3 b8c6 f1c4

pv2 = pv_line2;
pv2 = f8c5 b1c3 g8f6 0-0 0-0

pv = pv1+ pv2;
pv = e2e4 e7e5 g1f3 b8c6 f1c4 f8c5 b1c3 g8f6 0-0 0-0

Still a bust? No. If yes, goto next move in list. If all moves in list fail, goto pv_line1[-ply][inc next move in list].

pv1 = e2e4 e7e5 g1f3,... b8c6 would change to the next move.

Use one thread per root move per pv search is what I would suggest to start with. This way you are not restrictive to one root being searched, and you'll know sooner if there is a move too avoid.

Then it would be another search concurrently done at the same time.
The root would be pv1, but shouldn't be limited to no changes if it fails with pv2. Working backwards only happens when your search says, "Hey! I've looked into the future. Your orginal normal search sucked. Try a new move." Work back toward the root changing the last ply of pv1 if it fails with pv2's evaluation. 6 root moves = 12 threads.

In (1) if you discover something unusual, you can change your mind all the way back to the root. In (2) your options are way limited because you have 1/2 of the tree that is now static and can not be modified to include more moves, after you realize that the ones you included are no good...

This is forward-pruning at it's most dangerous. It has been tried.

Greenblatt used a very simple form of this, by first doing a normal search to establish the final PV, then going to the end of that PV and doing a very shallow search to refine that PV before you make it "the PV". This doesn't work. Several of us tried it and it leads to gross tactical mistakes.

Ordering the moves at the root of pv1 would be by the outcome of pv2 evaluation. SFSB, Step-Forward-Step-Back.
6 ply search instead of 3.
10 ply search instead of 5.
18 ply search instead of 9.
30 ply search instead of 15.
48 ply search instead of 24.

I am not sure I follow your math at all. I can do 24 plies in time N. how do you get to 24 plies in time N _and_ go another 24 using your idea, if you have zero seconds to do that. So somehow you have to get to 24 plies in N/2 or less. How?

As I said, try it if you want. That is so selective (you just doubled the total search depth for the same amount of time) something is getting overlooked. Seriously overlooked. Deep but highly inaccurate PVs are not better than shallow but accurate ones. The very reason why full-width search was resurrected in chess 4.0...

[jwes]

Which do you think would be more accurate:

(1) search to depth D in the normal way.

(2) starting at the root, do some shallower searches until you get to depth D/2, then starting there, search to something like depth D/2 + N (where N is small).

(1) search to depth D in the normal way... but play out the pv line . Does it >=match your previous pv line evaluation score? or did it drop significantly?

Why can you not go back to the root if you force the pv line1,
and do another search and see it was a bad move at the same time?

Because PV + a few plies tacked on to the end of the PV is not anywhere near the same as searching PV a few plies deeper. If you add a few moves on to the end, how do you know that the moves at the end of the old PV can not be improved on? Without searching them?

Again, Greenblatt proposed this idea. Even back in the days when he did a pure 5 ply forward-pruned search. Several of us tried it and threw it out as badly flawed. Anyone can try the idea if they want, of course. I'd rather go one or 2 plies deeper along every branch, using the current forward pruning/reduction ideas, rather than going a few plies deeper at the end of the PV, with no opportunity to change any of the PV moves.

Of course, but going 1 or 2 plies deeper takes 2 or 4 times as long, while extending PVs 2-3 plies only adds a few percent to the search.

[jhaglund]

Because PV + a few plies tacked on to the end of the PV is not anywhere near the same as searching PV a few plies deeper. If you add a few moves on to the end, how do you know that the moves at the end of the old PV can not be improved on? Without searching them?

You are searching as search1 arrives.

search1 -> search2

In Crafty, you have 1 search, ex: search.c...

Picture having 2 search.c's.

search1 passes it's info to search2 as it searches.

search2's root would be search1's pv_line.

Say you look at CM11k... it has a thinking board of what the computer is planning to play. Now, if you had the PV that came after the thinking line, you'd have about double the depth.

Or, say a GM thinks out 8 moves to play. He moves them on the board and thinks out 8 moves again, WHILE he's still thinking about the first 8 moves, writes out his 8 + 8 moves... Get it? So instead of ply 8 he's at ply 16.

Say before he arrived at his 8 moves... he had another idea. 4 moves, didn't play them out and two moves later he is in trouble. Luckily, he had Crafty handy and it said, "Wait! I played your moves out, and I see trouble with that idea later." Crafty traced back each move to your root move, so that needs to change. Now he has his better 8 move plan, and goes onto win.

If the GM sees his 16th move discovered a blunder, you trace/step back your PV toward the root seeking out a new route first before throwing out the plan. Most likely, you'll get to the root right away, but not always.

Where you spend more cpu time is up to you. I'd prefer for an i7 - 4 threads per search to start with.

I'd rather go one or 2 plies deeper along every branch, using the current forward pruning/reduction ideas, rather than going a few plies deeper at the end of the PV, with no opportunity to change any of the PV moves.

You'd still have your current search method(s). Of course there would be opportunity for the PV move to change. Either by working back towards the root, in search1 from the last pv ply,
pv[-ply][inc_move],
which is what I would suggest first, before just giving up and changing the root move. search2 tells it change. You'll have already done a "full-width" search so everything would would be in hash tables.

I am not sure I follow your math at all. I can do 24 plies in time N. how do you get to 24 plies in time N _and_ go another 24 using your idea, if you have zero seconds to do that. So somehow you have to get to 24 plies in N/2 or less. How?

Easy, the concurrent search.

If you play out your move or moves from your first search PV, with a second search, as you still search you spend N amount of time, either until you iterate to your next move, for X amount of time, or with a que/stack, etc.

Now, it may not be perfectly doubling your depth, due to tree explosions, etc., but you'll be continuing your search1 PV with a second search as it's passed to the search2. "Hey, play it out & check this move(s) for me." Again, working back towards the root, in search1 from the last pv ply,
pv[-ply][inc_move] if search2 says your search1 fails.

That is so selective (you just doubled the total search depth for the same amount of time) something is getting overlooked. Seriously overlooked. Deep but highly inaccurate PVs are not better than shallow but accurate ones. The very reason why full-width search was resurrected in chess 4.0...

Nothing would be overlooked, unless there is a flaw in search1. If you cannot trust your PV in search1, then there is something wrong with any pruning/reductions made in search1. search1 & search2 are your normal searches that you do now. Search2 is the step-forward&step-back to search1 if you see trouble on the horizon.

Anymore clear?