[computer-go] What is All-as-first-heuristic?

[Chrilly]

Thanks for the very clear explanation (and also to Don Dailey).

> My guess is that you as a chess programmer might find this to be a crazy 
> idea
> because movegeneration changes a lot for every ply played
Not at all. In chess something similar is done. Its called there History 
Heuristic. One counts the number of cutoffs a move has generated (or how 
many times the move was the best). Usually this is a counted weight. If the 
remaining search depth is d, possible weights are  d*d, or 8*d or 2**d.
The count is traditionally used for move-ordering. But the latest 
development is history pruning. In History pruning one calculates the 
success-statistics of a move. The Ratio of Move-Played/Move was a Cutoff. If 
this ration is below a given thresold, the depth is decremented by 1 Ply.
This statistic is usually only used for non-capturing moves. Also if the 
best move was a capture the non-capturing moves are not punished for being 
worse.
Chess is somewhat different, because e.g. before moving Nc3d5 the move Nb1c3 
must be made. A good history-value for Nc3d5 has no effect for move-ordering 
or pruning at the top of the search tree.

In Suzie I have first implemented a knowledge based selective search. But I 
have gone back to a simple History-Heuristic based selective search. I do 
some aggressive History-Pruning. And I had exactly the same question. 
Currently I do it in the chess way (only captures are not threated special), 
which is very similar to a weighted All-as-First-heuristic. I am not really 
happy with it. One should restrict it to levels. But one can not do it only 
for the same level/distance from the root. If the previous iteration was to 
depth 4, then in the next iteration the moves being 5 plies away from the 
root would have no ordering information. One way is to move up/down 2 plies. 
But this comes close to the All-as-First-heuristic, because Suzie searches 
in the moment only 5 Plies (plus Quiescence).

I think that the details of search are in Go not so important (no big news 
for Go-, but a shocking insight for a chess programmer). If the evaluation 
does something wrong, it goes wrong, no matter of the search details. The 
selective and the History-based version play rather similar and especially 
make practically the same bad mistakes. The computer chess law of Jan 
Louwman is fully valid: Faster search means only that the bad moves are 
found faster. Jan formulated this law when the search depths of the chess 
programms were rather low (5-7 plies). In the meantime there is Heli Weigels 
law: The evaluation determines the playing style, the search the playing 
strength. Maybe the computers are just by a factor 10000 too slow for Go.

Chrilly