Singular extension tests

[jwes]

For that +26 Elo reported previously, looks like +23 is a result of the hash move being preserved, and +3 for the speed gain. Before this was added, there was specific code in HashStore() that preserved the best move when storing an entry with the identical key but no best move. I removed that since this mechanism did the same thing. The optimization is definite, but quite small, in Crafty, for avoiding generating a move here and there. The biggest gain is avoiding losing the hash move when overwriting a position with a hash move by a table entry that is an UPPER entry (with no best move)...

To avoiding generating a move here and there you end up overwriting an already exsisting ttMove with a move from an ALL node ! Is this the "optimization" ?

Have you done any experiments showing how likely it is that a move that failed high before and currently fails low is to fail high again?

[Mangar]

Hi Bob,

in Spike we do something similar. We don´t call the move generator for hash-move and killer moves. On a fail low we store hash moves and moves found by IID but no other moves.

Maybe this saves the advantages without most disadvantages.

Greetings Volker

[Mangar]

Hi,

you sould at least not "delete" the hash move currently stored if the position that now fails low. Thus:

New_Hash_Move = FailLow? Old_Hash_Move : Best_Move.

I think that most if not all elo difference is coming from keeping the "old" hash-move as it has been the best move in some other search on the same position.

Greetings Volker

[mcostalba]

New_Hash_Move = FailLow? Old_Hash_Move : Best_Move.

I would think you mean:

New_Hash_Move = FailLow? (Old_Hash_Move ? Old_Hash_Move : Best_Move) : Best_Move

....anyhow I don't like it the same because it happens that New_Hash_Move could end up storing something that is not an "Hash_Move".

[bob]

For that +26 Elo reported previously, looks like +23 is a result of the hash move being preserved, and +3 for the speed gain. Before this was added, there was specific code in HashStore() that preserved the best move when storing an entry with the identical key but no best move. I removed that since this mechanism did the same thing. The optimization is definite, but quite small, in Crafty, for avoiding generating a move here and there. The biggest gain is avoiding losing the hash move when overwriting a position with a hash move by a table entry that is an UPPER entry (with no best move)...

To avoiding generating a move here and there you end up overwriting an already exsisting ttMove with a move from an ALL node ! Is this the "optimization" ?

No. If you read what I wrote, I save the _first_ move I search at any ply. If I finish without raising alpha, this is an ALL node. I save the first move I tried in the hash table entry for this position. If there was a pre-existing hash entry, it already had a best move, and that is always searched first. Which means it is going to end up as the move I save. I've always had this mechanism, except in a different place. I used to check on HashStore() to see if the current (to be stored) position matches an identical key. If so, If the current entry has no best move, and the one in the actual table does have one, I would add that move to the current entry to preserve it. The current approach does that, plus it adds one more minor optimization... If this is really an ALL node, and there was no hash entry to provide a hash move to search first, I simply take the first move I search and store it in this entry. Every now and then, this will cause a cutoff without doing a move generation. Most of the time it just gives me a first move to search that is joined by all the others since this is an ALL node. But when a bound changes due to some significant search finding, that ALL node may well become a CUT node and that hash move lets me find the fail high without generating moves.

As I said, a minor improvement, but it actually made the code easier to understand since both things are done in the same place now....

3 cases.

(1) PV node. When I store this, I take the move from the PV and store it in the hash entry.

(2) CUT node. When I store this, I save the move that caused the cutoff in the hash entry.

(3) ALL node. When I store this, I store the first move searched, which would be the hash move if there was one, else the first move generated by the move generator...

[bob]

Hi,

you sould at least not "delete" the hash move currently stored if the position that now fails low. Thus:

New_Hash_Move = FailLow? Old_Hash_Move : Best_Move.

I think that most if not all elo difference is coming from keeping the "old" hash-move as it has been the best move in some other search on the same position.

Greetings Volker

That is the effect of this approach. If there _was_ a hash move for this position, it is always searched first. So it would be the one that is stored in an ALL node, which is the only place this trick is used. If there was no hash move to suggest what to search first, I just use the first move searched, since that's a reasonable place to start (if I had no best move that is the same move I would start with since it is the first one produced by the generator).

[Desperado]

Hello everyone !

here is what i am doing (maybe wrong,if so pls let me know).

Independent on the node-type i have always a _bestMove_ available because my implementation looks like that.

Code: Select all

if( value > bValue)
	{ 
	 bValue = value;
	 bMove  = currentMove; !!! (independent on nodeType)

	 if(value > alpha)
		{
                 ...
		}
	}

The reasons (talking of an allNOde):


- if this is an allNode and we visit the Node again, we can save movegeneration at least.

- if the bMove would overwrite an existing _bestmove_ (which has all attributes of a cut node but insufficient depth for example) ,
this _bestmove_ is refuted here anyway. (so volker, why not overwrite ?)

- if all conditions are confirmed to fill the hashslot with information of this node
why should the _bestMove_ entry be empty ?!
why should i keep a now refuted _bestMove_ in the slot. (if _firstMove_
isnt anyway equal to _bestMove_=_currentHashMove_)
if in a failsoft frame another moves gets the "bestMoveFlag", i also
cannot see a problem.

i prefer and consider the _firstMove_ given by the sortAlgorithm as _bestMove_ in such
a case.

- if this is a _real_ allNode we can revisit it 1000 times and it doesnt play a role which move we examine first.

- maybe different argues for failSoft and failHard frame. but at the
end i think it doesnt play a role either.

of course i may have misunderstood what robert is doing, did i ?
if this is a bug for a reason i dont see at the moment, i would be
happy if some of you would tell me .

Michael

[bob]

Hello everyone !

here is what i am doing (maybe wrong,if so pls let me know).

Independent on the node-type i have always a _bestMove_ available because my implementation looks like that.

Code: Select all

if( value > bValue)
	{ 
	 bValue = value;
	 bMove  = currentMove; !!! (independent on nodeType)

	 if(value > alpha)
		{
                 ...
		}
	}

The reasons (talking of an allNOde):


- if this is an allNode and we visit the Node again, we can save movegeneration at least.

- if the bMove would overwrite an existing _bestmove_ (which has all attributes of a cut node but insufficient depth for example) ,
this _bestmove_ is refuted here anyway. (so volker, why not overwrite ?)

- if all conditions are confirmed to fill the hashslot with information of this node
why should the _bestMove_ entry be empty ?!
why should i keep a now refuted _bestMove_ in the slot. (if _firstMove_
isnt anyway equal to _bestMove_=_currentHashMove_)
if in a failsoft frame another moves gets the "bestMoveFlag", i also
cannot see a problem.

i prefer and consider the _firstMove_ given by the sortAlgorithm as _bestMove_ in such
a case.

- if this is a _real_ allNode we can revisit it 1000 times and it doesnt play a role which move we examine first.

- maybe different argues for failSoft and failHard frame. but at the
end i think it doesnt play a role either.

of course i may have misunderstood what robert is doing, did i ?
if this is a bug for a reason i dont see at the moment, i would be
happy if some of you would tell me .

Michael

Just a note. The "bValue" idea does not work on an all node. You can try setting bValue to -infinity and for each move searched at an ALL node, you can save the score/move if the score is > bValue (and of course any score is better than the -infinity). But the scores you get back are not real scores, and there is no way to say that one move is better than another at an ALL node.

All I am doing is when I store a hash entry after completing an ALL node, I store either the original hash move that I tried first at this ALL node, or simply the first move my move selection code proposed. Trying to figure out the best move at an ALL node is impossible within alpha/beta.

[bob]

Hi Bob,

in Spike we do something similar. We don´t call the move generator for hash-move and killer moves. On a fail low we store hash moves and moves found by IID but no other moves.

Maybe this saves the advantages without most disadvantages.

Greetings Volker

I haven't found a disadvantage yet, other than it might occasionally lead to an unnecessary ttSE extension if you are doing those. I am not, myself.

[Desperado]

hello robert,

well, of course we cannot get a best move in the sense that we know it is better
than all the other moves on that allNode.(impossible, like you said!)

BUT what i am speaking of is, that we dont need _any_(not even one statement) extra code to fill
the hashentry with a (best)move.

1.scenario

we have a tMove, so the move selector will pick it and we can do with
it what we want to do with it.
In this scenario the _firstmove_ is the same as the one picked from
hashtable.Now we loop all the moves and in 50% of all cases
the _firstmove_ == tMove keeps the move we store in transtable.
And the other 50% there will be picked another move from all outplayed moves.(due to failsoft)

(if that makes sense... -> imho)

2.scenario

we dont have a tMove available. So the move selector will decide what
the first move is.
Now exactly the same procedure as before. The value of the first move
picked is > -infinity, so marked as (best)move to store in transtable.

but again, because we use failsoft that can change again!.


3. imho

Now, i think the implementation is conform with the handling of pv and cut nodes.
It is straightforward, to use one code that works for all type of nodes including _allNodes_.
It cannot hurt to use this approach, so we "always" have a move to store.

Does it make sense to change the move we have already stored in scenario 1
if a failsoft returns a value > bValue ?
At the moment, i think yes. even if we cannot trust that move2 is better than move1
the value _indicates_ exactly that. Combined with the fact that we have nothing to lose
and the current tMove failed again, next time move2 gets the chance to be first move because
of its higher value. and normally the move selector is not that smart as the search.
And if i have to choose blindly between first move evaluated by move selector or
the _inicdicated_ move, i prefer the _indicated_ move.

I hope my logic is not totally broken...

regards Michael