Questions on SMP search

[bob]

Best-first search is a good example of the correct use of the term "widening" as you can expand any node you want, at any time you want. Depth-first doesn't fit this description very well.

So, are modern chess programs best-first or depth-first searchers? Does the distinction even make sense, given that we all use the equation better=deeper when doing LMR?

I think it was proven already in 1996 (Aske Plaat) that it isn't...

It is purely depth-first. You do nothing until you go down the left-hand side of the tree and reach a terminal node. Also, depth-first has O(D) memory requirements (D = depth). Best-first has O(W^D) since you must store the entire tree.

So the two are completely different approaches, and since Berliner (and maybe conspiracy numbers search since his stuff) I have not seen anyone expand a tree in best-first form. Particularly since alpha/beta does not apply to best-first at all.

[marcelk]

So, are modern chess programs best-first or depth-first searchers? Does the distinction even make sense, given that we all use the equation better=deeper when doing LMR?

I think it was proven already in 1996 (Aske Plaat) that it isn't...

It is purely depth-first. You do nothing until you go down the left-hand side of the tree and reach a terminal node. Also, depth-first has O(D) memory requirements (D = depth). Best-first has O(W^D) since you must store the entire tree.

I would say modern programs are essentially best-first with a cloak of iterative deepening making it appear as depth-first. The tree is the hash table. Without hash table the LMR doesn't work, you need the work done in the previous iteration. Not for sorting for alpha-beta, but for tree shaping. The iterations drive both widening and deepening as others have explained very well above. Both widening and deepening are just as important.

[Gian-Carlo Pascutto]

So the two are completely different approaches, and since Berliner (and maybe conspiracy numbers search since his stuff) I have not seen anyone expand a tree in best-first form. Particularly since alpha/beta does not apply to best-first at all.

You *really* should read Aske Plaat's thesis. Aside from talking about MTD(f) (those parts you can skip), it proves that many instances of best-first algorithms applicable to chess can be rewritten as sequences of alpha-beta calls with a hashtable.

The nodes searched are equivalent. depth-first vs best-first is just an implementation difference.

Also, depth-first has O(D) memory requirements (D = depth). Best-first has O(W^D) since you must store the entire tree.

We call this "the hashtable". We already store the entire tree. Or at least the parts we care about.

[bob]

So, are modern chess programs best-first or depth-first searchers? Does the distinction even make sense, given that we all use the equation better=deeper when doing LMR?

I think it was proven already in 1996 (Aske Plaat) that it isn't...

It is purely depth-first. You do nothing until you go down the left-hand side of the tree and reach a terminal node. Also, depth-first has O(D) memory requirements (D = depth). Best-first has O(W^D) since you must store the entire tree.

I would say modern programs are essentially best-first with a cloak of iterative deepening making it appear as depth-first. The tree is the hash table. Without hash table the LMR doesn't work, you need the work done in the previous iteration. Not for sorting for alpha-beta, but for tree shaping. The iterations drive both widening and deepening as others have explained very well above. Both widening and deepening are just as important.

we have _got_ to use consistent definitions. Modern programs are no more best-first than they are human. Best-first is a _very_ explicit search paradigm. No alpha/beta. No following a path to the depth limit before scores start backing up, etc. Minimax is pure depth-first...

Any search widens and deepens, if it is searching a tree...

No current chess search is best-first however. I'd bet you can find good examples of best-first search via google, to see exactly how different it is from depth-first minmax/alpha-beta....

[bob]

So, are modern chess programs best-first or depth-first searchers? Does the distinction even make sense, given that we all use the equation better=deeper when doing LMR?

I think it was proven already in 1996 (Aske Plaat) that it isn't...

It is purely depth-first. You do nothing until you go down the left-hand side of the tree and reach a terminal node. Also, depth-first has O(D) memory requirements (D = depth). Best-first has O(W^D) since you must store the entire tree.

I would say modern programs are essentially best-first with a cloak of iterative deepening making it appear as depth-first. The tree is the hash table. Without hash table the LMR doesn't work, you need the work done in the previous iteration. Not for sorting for alpha-beta, but for tree shaping. The iterations drive both widening and deepening as others have explained very well above. Both widening and deepening are just as important.

we have _got_ to use consistent definitions. Modern programs are no more best-first than they are human. Best-first is a _very_ explicit search paradigm. No alpha/beta. No following a path to the depth limit before scores start backing up, etc. Minimax is pure depth-first...

Any search widens and deepens, if it is searching a tree...

No current chess search is best-first however. I'd bet you can find good examples of best-first search via google, to see exactly how different it is from depth-first minmax/alpha-beta....

[bob]

So the two are completely different approaches, and since Berliner (and maybe conspiracy numbers search since his stuff) I have not seen anyone expand a tree in best-first form. Particularly since alpha/beta does not apply to best-first at all.

You *really* should read Aske Plaat's thesis. Aside from talking about MTD(f) (those parts you can skip), it proves that many instances of best-first algorithms applicable to chess can be rewritten as sequences of alpha-beta calls with a hashtable.

The nodes searched are equivalent. depth-first vs best-first is just an implementation difference.

Also, depth-first has O(D) memory requirements (D = depth). Best-first has O(W^D) since you must store the entire tree.

We call this "the hashtable". We already store the entire tree. Or at least the parts we care about.

with best-first you must store everything... hashing isnt going to come close, and we can get by with storing nothing, with just a loss of performance. With best first, if you can't store everything, it won't work.

[Daniel Shawul]

Best-first search is a good example of the correct use of the term "widening" as you can expand any node you want, at any time you want. Depth-first doesn't fit this description very well.

Most best first searchs can be converted into equivalent depth first search, so it is just
an implementation difference. There is even an equivalent _depth first_ UCT search...
Even if that was not the case, I was getting the same effect by using LMR + depth first search before
I became familiar with UCT. So the widening effect is there in both cases, and is much stronger than
deepening in games with large BF.

For instance, for Amazons game with branching factor of ~2500 BF in the opening position
there is no way I can reach a depth = 7 search in 4-5 secs without LMR !
Evenif BF was 20000 (as in Arimaa), I still can reach the same depth in the same time since it widens
progressively. The key here is I always construct an _artificial_ branching factor no matter what which gets increased
as time goes on. The current modern chess engine's LMR reduction could be as high as 7 UNITS for the very
late moves, and 0 for the first move, so it has the same widening effect...

On board size of 19x19 progressive widening gives 100-200 elo improvement, but
on 9x9 board with lower branching factor I still can't get it to give any elo improvment...
It is very clear that iterative widening gives much better result on games of large branching factor,
but is doubltful on low BF games. This is also the case for many other Go engines.

[Daniel Shawul]

with best-first you must store everything... hashing isnt going to come close, and we can get by with storing nothing, with just a loss of performance. With best first, if you can't store everything, it won't work.

This is wrong as GCP pointed out. All the _relevant_ part of the tree nodes can be stored in memory, since UCT is a _very selective_ search. I never had problems with that and I don't even use tricks to control tree growth (f.i pruning nodes with low visits or win ratio). The standard way is to not "expand" (add children of the best move) on every visit to that node rather every 10 visits or so.
Also the fact that the qsearch is replaced with a MC playout helps in this regard since no nodes need to be stored during playout. So each node of a tree has a number of visits, from which the number of siblings to be considered at any time during the search can be calculated using a log formula.

This should not be confused with breadth first search which is much more memory intensive, which expands all moves instead of just the best moves as in best first. So we should make a distinction between depth first, best first and depth first.

[bob]

with best-first you must store everything... hashing isnt going to come close, and we can get by with storing nothing, with just a loss of performance. With best first, if you can't store everything, it won't work.

This is wrong as GCP pointed out. All the _relevant_ part of the tree nodes can be stored in memory, since UCT is a _very selective_ search. I never had problems with that and I don't even use tricks to control tree growth (f.i pruning nodes with low visits or win ratio). The standard way is to not "expand" (add children of the best move) on every visit to that node rather every 10 visits or so.
Also the fact that the qsearch is replaced with a MC playout helps in this regard since no nodes need to be stored during playout. So each node of a tree has a number of visits, from which the number of siblings to be considered at any time during the search can be calculated using a log formula.

This should not be confused with breadth first search which is much more memory intensive, which expands all moves instead of just the best moves as in best first. So we should make a distinction between depth first, best first and depth first.

Please listen again. For best first you have to store _everything_. I am not talking about UCT, minimax, alpha/beta, or anything else. The question was about best-first. It is completely unreleated to depth-first search as we use in chess programs.

Best-first is more human like, to be sure. But it has never approached depth-first in chess or checkers. Perhaps in GO or another game, who knows.

breadth-first is a variation of best-first and vice-versa. Because the tree grows in the same direction for either, although in theory best-first would be more efficient, as breadth-first would be pure full-width and slow. But best first is a breadth-first approach in general, and alpha/beta need not apply there...

[Daniel Shawul]

UCT with 0 exploration is effectively a best first search. Anyway lets not divert away from the discussion.With huge branching factor games , the widening effect becomes vivid best first or not. I get the same effect with depth_first + LMR. How do you think I can search depth=7 with a game of branching factor 3000 ? Please address that first and we will talk about best first search later.