How can I reduce combinatorial explosion in an MCTS-like algorithm for program induction?
I think you may get some inspiration from the work on deterministic environments by Javier Segovia et al. See their paper Computing programs for generalized planning using a classical planner (2019).
If you don't have access to Elsevier's papers, I recommend that you check out the first author's profile on dblp.org. From there you will find links to open access versions of the conference paper that led up to the publication above.