If you look behind logic programming at what powered deduction engines, you will find that its core is very much tree search algorithms like depth-first backtracking search or iterative deepening, which IIUC, is also central in chess engines.

The rest is basically regular programming in that its largely bound by how well the programmer models. For a large number of things, the scope of what a human can consider lags an optimization process. In chess, it at first seemed like this might be the case there too, but latest performance points to maybe not this time.

By classical here I simply meant non-connectionist methods in general.

I guess I've never thought of search as being either connectionist or non-connectionist. It's self-evident that people search (eg look up in books) things that aren't in local memory.

I think the distinction is how the looked-up knowledge is integrated.

The non-connectionist, classical, symbolical aspect is not so much "search" per se, but the fact that MCTS performs a form of look-ahead, which requires manually encoding the rules of the game in some fashion.

Determining what the legal moves in a state are, and what state results from a given move, is not something the AI would learn by itself, but is programmed into the system by a human expert.

I do not believe this is still true in MuZero, where no rules are ever explicitly encoded, beyond what leaks in from the reward function?

Indeed, in this latest iteration the network learns a model of the game by itself. Note however that it still uses MCTS and performs a look-ahead, i.e. it is still being "told" by the programmers how to do search (planning), only now it is left to the system to determine how it wants to represent states/actions/policies internally.