I would like to learn about the difference between depth-first and breadth-first search in knowledge-based chess engines (that, of course, excludes alpha-zero). The difference isn't that clear-cut, but, to my knowledge, some engines prefer to go deeper than explore more options per move. It seems that depth-first search, as it is used in Stockfish, has prevailed for now, but I don't necessarily find that obvious. Can anyone point me to research which has been done in this area?
Strength in chess engines depends on speed and speed depends on how strongly you can prune the tree. That is, how many nodes you can discard without degrading the accuracy of your search result.
In principle you might be able to visit the same nodes using either BFS or DFS, so a priori it is not clear which would be better prunable i.e. faster.
In chess, however, DFS is better prunable because one strong countermove is enough to invalidate a move. Therefore, the value of a move depends more strongly on a small set of next countermoves and the value of these countermoves on a small set of next moves etc. So, Min-Max-Search naturally lends itself to better pruning with DFS.
There is no need for research. Breadth-first, by definition needs to traverse all nodes at a level before going to the next. It just doesn't work for chess, where the number of positions is too many and most of the positions are just stupid (e.g. dropping a queen). Chess engines always use deep-first.
One important point to consider is that BFS has a hugely higher space complexity than DFS.
- b = branching factor = number of moves per step, about 31 in chess
- d = minimum depth of tree till optimal solution (e.g. 10 if checkmate in 10 turns is possible)
- m = maximum depth of tree (e.g. 150 moves till draw)
Space complexity of BFS: O(b^d)
Space complexity of DFS: O(b * m)
Assuming that a position with b=31, d=10 and m=150 is evaluated and each node needs 24 Bytes of space, BFS would need about 20 Petabyte of space and DFS only 111 KB, making BFS infeasible. Also keep in mind that modern CPUs only have a few MB of cache (e.g. 16 MB for the i9-9900KS), so they could not even fit all nodes of BFS at the depth of d=4 (22MB).
With strong pruning (i.e. throw away very bad moves), the branching factor can be reduced to perhaps 5-10 good moves per step, but this does not solve the exponential space complexity of BFS.
In addition to the great accepted answer, I'll point out that engines do differ in the amount of breadth/depth they analyze, even though all of them do use depth first search because of alpha beta search (something you should research if you want to learn more, as all traditional engines use it) being much better optimized for it.
For example, Stockfish is very well known for aggressively getting rid of moves it has to consider through various pruning techniques, so it can consider the best few moves to extremely great depths because it doesn't need to calculate as many positions.