Historically, the non-ML approach would be an expert system. This is typically a rules-based decision system, falling under the umbrella of symbolic AI.
These systems can have strong utility in limited contexts, but are generally "brittle" in that parameters not previously defined or accounted will produce no-compute or weak utility. Because the rules of a game are fully definable, the main concern is utility, which relates to the degree to which the game has been solved.
Informing a heuristic system in this case requires analysis of the game in in the sense of game theory and combinatorial game theory, since Catan involves both imperfect information and combinatorial elements. The complexity is high indeed, not only per imperfect information, branching factors, stochasticity, players > 2, but, as you note, the game board itself has a very high number of potential configurations, so solving the game is presumed to be extremely difficult to impossible. (Possibly NEXPTIME if finite and undecidable otherwise.)
The paper Game strategies for The Settlers of Catan suggests that the game tree for Catan is not surveyable b/c the options for trade negotiation in natural language aren't bounded:
One response to this is to develop a symbolic model consisting of heuristic strategies for playing the game. Developing
such models potentially has two advantages. First, a symbolic
model can in principle lead to an interpretable model of human
expert play ... Second, a symbolic model can provide
a prior distribution over which next move is likely to be
The paper mentions this second part to relation to machine learning, where "the posterior distribution over optimal actions acquired through training improves on the baseline prior distribution."
Especially where the game is unsolved and intractable, machine learning has demonstrated strong utility for an increasing number of games, so it is unlikely not to be an optimal component for truly strong play. However, such a system can be a combination of ML and domain specific knowledge, such as in informed search.
The Optimizing UCT for Settlers of Catan goes into this in detail, and also provides reference to prior work.
If your primary requirement is strong utility, some form of machine learning is likely optimal. But it can be fun to attempt to solve games and cobble together sets of heuristics.