2

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?

4

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.

| improve this answer | |
  • I see, that makes sense. I'll take 'Min-Max search' as a starting point in order to improve my understanding of the subject matter. – postnubilaphoebus Apr 6 at 14:03
  • The usual term is minimax search. – TonyK Apr 7 at 0:31
3

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.

| improve this answer | |
  • 1
    Maybe it wasn't clear from my question formulation, but I didn't mean pure DFS or pure BFS. Instead, I simply meant comparing engines that go deeper but explore fewer options per position to engines that go less deep but explore more options per position. It would be very surprising to me if all engines automatically explored the same number of moves per position, on average. It could also be that my question is based on a fundamental misunderstanding. If so, I would be happy if you could point out what I'm missing. – postnubilaphoebus Apr 6 at 14:09
  • 2
    @postnubilaphoebus: I'm afraid you are misusing the terms then! Breadth-first search is qualitatively different from depth-first search. What you are talking about is simply a speed vs knowledge trade-off. – TonyK Apr 7 at 0:30
3

One important point to consider is that BFS has a hugely higher space complexity than DFS.

Notation:

  • 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.

| improve this answer | |
2

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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.