Root search

[lauriet]

Hey,

This maybe a dumb question BUT.........

Some source has seperate functions for searching the root moves.
Why ?


Laurie.

[elcabesa]

Usually the root move search is a little bit different than other nodes. So some programmer prefer to have a separate function.
For example it's usually the root move search that print the info at screen.

Other programmer prefer to have a single search function for every node

[Evert]

This maybe a dumb question BUT.........

Some source has seperate functions for searching the root moves.
Why ?

I've done both.
In Jazz I have a separate root-search function that generates legal moves, looks for book moves and then iterates over the moves before calling the recursive search function. The reason for this is partly historic: I originally started with the root search and a plain random mover, then replaced the random mover by a search to identify the "best" move.
In SjaakII and other engines, I simply call search from the iterative deepening/aspiration window loop.

The latter is a bit simpler, but the first allows you to be more creative with root move ordering without messing up the recursive search function.

Some things you might do differently in the root versus an interior node:

• Widen the aspiration window immediately if the first move fails low, rather than seeing if any of the other moves is better. This is better in Jazz, but I suspect your mileage may vary depending on whether aspiration windows do anything for you at all.
• Sort remaining moves by nodes searched rather than score. Can be dodgy due to transposition cut-offs and extensions/reductions. Is a small win for Jazz.
• Log detailed statistics about the move being searched, for debugging purposes.
• Use detailed result scores from tablebases and opening books.

[bob]

Hey,

This maybe a dumb question BUT.........

Some source has seperate functions for searching the root moves.
Why ?


Laurie.

1. You don't probe the hash table at ply=1, putting in a check for that costs a little time.

2. Most order and select moves differently at the root. Using just one search function requires a test again, which is slightly slower.

3. You don't want to do a null-move search at the root. Same issue.

4. Etc.

I used to have a separate search function, but do not today. Why? I found maintaining two separate pieces of code that were very close to identical was a good way to introduce a bug when you change one but not the other.

[Ras]

NG-Play (and thus the CT800) uses NegaScout in the normal search, but a stripped down NegaLight at the root.

The moves are generated, ordered per LVVV/MVA. In the CT800, but not in NG-Play, a first search at depth=1 plus quiescence is done for refining the move sorting. Doesn't cost much time and helps the next level of pre-search.

Then a shallow pre-search is done at depth 3 plus quiescence, using the NegaLight which is alpha-beta minimax without hash tables or refined pruning or internal iterative deepening. The movelist is sorted as per the resulting scores. The idea is that 3 plies simple search don't cost much, but having a better move ordering helps to cut down the time when the deeper search is started.

Plus that there is a threat assessment, basically a null move at the root position at depth=2 with quiescence. Again, hash tables, pruning and stuff don't make sense here. The idea is that the opponent may have a very good move which is likely to be a good answer move in most cases, so that this move is considered first as the opponent's answer when launching the full search.

A specialty in the CT800 is the "early draw avoidance": if this is a regular game and under 30 moves, starting from the initial position, then the move-presorting routine will purge repetition draw moves from the move list at root level if there are other moves with a score of at least -0.4.

On the PC, the time needed until now is up to 40 ms, mostly much less. On a Cortex-M microcontroller, this phase can already take up to about 2 seconds. Under very short time controls, the full search thus is not even started.

The actual full search then starts at depth 3 in case that there is still time left. Except if the pre-search detected a forced mate, or that there is only one legal move available, or that there is only one legal move that avoids being mated immediately, in which cases the full search is not done (with the exception of analysis mode, of course).

I did experiment with using the hash tables in the pre-search; it turned out that the pre-search is neglactable towards the endgame anyway. In the middlegame (see above), this can take up to 2 seconds, but using hash tables right before the quiescence level (i.e. at depth 3) yielded hit rates of only around 10%. That didn't really cut down the time.

The only hash tables that are also used in the pre-search are the pawn hash tables because they are part of the static eval, not of the search tree. The gained data are also useful for the full search.

[cdani]

Hey,

This maybe a dumb question BUT.........

Some source has seperate functions for searching the root moves.
Why ?


Laurie.

In Andscacs search_root is so different that is difficult to find something similar to the alpha_beta one.

Some examples. It prepares some thread stuff. It orders different at first iteration and even different at other iterations. It does things related to multi pv. It prints pv's. It reduces different. Sometimes forces a reanalisis of a move. Does different things for thread 0 and other threads. And not a few things more.

[lojic]

Hey,

This maybe a dumb question BUT.........

Some source has seperate functions for searching the root moves.
Why ?


Laurie.

1. You don't probe the hash table at ply=1, putting in a check for that costs a little time.

2. Most order and select moves differently at the root. Using just one search function requires a test again, which is slightly slower.

3. You don't want to do a null-move search at the root. Same issue.

4. Etc.

I used to have a separate search function, but do not today. Why? I found maintaining two separate pieces of code that were very close to identical was a good way to introduce a bug when you change one but not the other.

Sorry to resurrect an old thread, but I've recently finished coding my transposition table, and I noticed Bob's comment:

You don't probe the hash table at ply=1, putting in a check for that costs a little time.

Why is that? I currently read the TT at the beginning of my alpha-beta i.e. I'm not skipping it for the first ply.

[Sven]

As far as I remember, in Bob's engine Crafty ply=1 means root node, and there you don't need to probe the TT.

[hgm]

I don't really see any reason not to probe the TT in the root. You cannot get a hash cutoff there anyway, because the depth will never be sufficient: the root iprinciple asks for infinite depth (but aborted by time considerations).

[Sven]

I don't really see any reason not to probe the TT in the root. You cannot get a hash cutoff there anyway, because the depth will never be sufficient: the root iprinciple asks for infinite depth (but aborted by time considerations).

There a lot of search features that should not be used at the root node, e.g. null move pruning or other kinds of pruning, IID, or even endgame tablebase probing. TT probing is just one of them IMO. Also there is at least one thing you only do at the root node: printing a new PV that has just been found by raising alpha. So you need to know anyway whether you are at the root, so it is no additional penalty to also suppress the useless TB probing there.