Even more search questions

[Sven Schüle]

Hi,

I also would like to know the following:

3. When a timeout occurs and you decide which move to play, do you use the best move from the previous iteration (the last completed one) or from the current iteration (which is always incomplete but may already have a "best move" as soon as searching the first move - the best from previous iteration - has been completed)?

4. Does it hurt to sort the whole move list at the root node based on their subtree values of iteration i to determine the order of moves for iteration i+1? The alternative way is only to search the best move of iteration i as first move in iteration i+1, while leaving all other moves in the same ("random") order.

Sven

[Pradu]

Hi,

I also would like to know the following:

3. When a timeout occurs and you decide which move to play, do you use the best move from the previous iteration (the last completed one) or from the current iteration (which is always incomplete but may already have a "best move" as soon as searching the first move - the best from previous iteration - has been completed)?

I use the move that has raised the score the most so far for the current iteration.

4. Does it hurt to sort the whole move list at the root node based on their subtree values of iteration i to determine the order of moves for iteration i+1? The alternative way is only to search the best move of iteration i as first move in iteration i+1, while leaving all other moves in the same ("random") order.

Sven

[H.G.Muller]

I play BestMove, which is either still hanging there from the previous iteration, is the only move looked at in the current itersation (and then the same as the best of the previous, as that is always searched first), or a better move of the interrupted iteration.

If at the largest depth so far it is already determined that the best move of the previous iteration is not the best now, I don't see why you would ever prefer it to the one that is better at this largest depth. Even if the latter might not be best.

With 4 the problem is that almost all scores will be upper bounds only, and you might sort arbitrarily poor moves to second place. In Joker I only bring moves to the front of the list that did not fail low. (But in a stable search, there are none.) Otherwise, the static move ordering is probably more likely to give an early cut move when your original cut move is a bust at larger depth.

In fact it might be better to start searching moves at lower depth with the new window first, when your best move suffers a large score drop. Say you had +0.1 at 10 ply. Then all other moves will just have an upper bound somewhere slightly below +0.1, even the ones that bungle away a Queen. If at 11 ply you drop to -1 with your first move, it would be really helpful to know which moves scored better than -1 at 10 ply, but you just don't know.

In uMax I always only sort the best move in front, the others go in move-generation order. Even that seems to work quite well.

[Chan Rasjid]

Hello,

3. When a timeout occurs and you decide which move to play, do you use the best move from the previous iteration (the last completed one) or from the current iteration (which is always incomplete but may already have a "best move" as soon as searching the first move - the best from previous iteration - has been completed)?

I think there should not be any issue here - there never is any reason why the best move of iter-i is not the best move of iter-i+1 even before searching. The best move is played if none is better.

4. Does it hurt to sort the whole move list at the root node based on their subtree values of iteration i to determine the order of moves for iteration i+1? The alternative way is only to search the best move of iteration i as first move in iteration i+1, while leaving all other moves in the same ("random") order.

Root move-ordering does not matter if the best move does not change. But we don't know! I think your scheme here may be bad if the best move keeps changing.

Dr. Hyatt mentioned using number-nodes-searched for root ordering. I can't think of any better and just use it. I am not sure if this has any significant overhead. I only further take care that:-
1) all moves that have been "best" are sorted highest
2) then by number-nodes-searched
3) last are those that fail low and fail by a large margin

Rasjid

[H.G.Muller]

It might be an idea to keep record of the lowest upper bound each move had so far in any earlier iteration. If a move has -3.3 at 5 ply, but creeps up to -0.1 at 11 ply (still failing low) it is very likely that this is just a result of 'lazy refutation' by the opponent. Normal situation is that he would be able to hang on to the 3.3 advantage he had after 5 ply. He probably just gave it away by preferring a null move over the recapture of a piece somewhere deeper in the tree. So the -3.3 should be believed more than the -0.1, despite the fact that it is only at 5 ply. So a move is 'tainted' by an earlier poor upper-bound score, making it no longer an attractive candidate.

[Chan Rasjid]

Hello Muller,

PostPosted: Tue Jul 17, 2007 3:57 pm Post subject: Re: Even more search questions
It might be an idea to keep record of the lowest upper bound each move had so far in any earlier iteration. If a move has -3.3 at 5 ply, but creeps up to -0.1 at 11 ply (still failing low) it is very likely that this is just a result of 'lazy refutation' by the opponent. Normal situation is that he would be able to hang on to the 3.3 advantage he had after 5 ply. He probably just gave it away by preferring a null move over the recapture of a piece somewhere deeper in the tree. So the -3.3 should be believed more than the -0.1, despite the fact that it is only at 5 ply. So a move is 'tainted' by an earlier poor upper-bound score, making it no longer an attractive candidate.

It should be correct, but the most difficult part of a chess program is how to make it optimally strong.
Many things we add may just be adding more to the burden of computation with no benefit. I think the correct way is always about balance, priority and a bug-free program. That's how Fruit did it.

Rasjid

[Sven Schüle]

Hi Rasjid,

it seems as if "root ordering" is another area of potential improvement for me, so many thanks for your contribution.

Sven