Kalaha Solver: finding the marbles
The standard trick is to skip portions of the search space that cannot bring a better solution than the ones found so far. For this you need to:


Remember the best solution found so far (or several best solutions, if you want).
Estimate an upper bound on possible scores that can be achieved from a given game state.


Then, given a partial game state, you compare the estimated upper bound to the current best solution, and if it's lower, there is no need to process the game state. The better the estimate, the more unnecessary processing is skipped.

Depending on the game it's might or it might not be possible to make a precise estimate. If it's not possible, you can use approximate examples. But there is a trade-off: The less precise estimate the higher chance you'll miss the best solution (but most likely the returned solution would be good enough).