Root search

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
lauriet
Posts: 162
Joined: Sun Nov 03, 2013 8:32 am
Contact:

Root search

Post by lauriet » Thu Sep 08, 2016 6:47 am

Hey,

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

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


Laurie.

elcabesa
Posts: 815
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: Root search

Post by elcabesa » Thu Sep 08, 2016 7:34 am

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

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Root search

Post by Evert » Thu Sep 08, 2016 7:48 am

lauriet wrote: 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
Posts: 20562
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Root search

Post by bob » Thu Sep 08, 2016 4:57 pm

lauriet wrote: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
Posts: 1160
Joined: Tue Aug 30, 2016 6:19 pm
Contact:

Re: Root search

Post by Ras » Thu Sep 08, 2016 5:40 pm

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.

User avatar
cdani
Posts: 2104
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Root search

Post by cdani » Fri Sep 09, 2016 4:29 pm

lauriet wrote: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.

Post Reply