Ah, if the game can play infinitely, that does make MCTS seem like it might not be much better, sadly. You could add in a cutoff point, certainly. I don't know of any literature on it, though I expect some sort of discount factor for cut-off scores would make sense (as they are less certain than a full play through).

In the profiling, could you see down to the lowest levels? Sometimes being able to prevent memory allocations can buy you 100x speedups, for example. That could give you 2 extra ply on the tree, which isn't significantly deeper but might be significantly better. (Perhaps.)

And yes, I think we're talking about the same thing when I was saying that minimax should still work fine providing you look at it abstractly and instead of minimising and maximising the in-game scores, you minimise and maximise an external utility value that reflects the chance of winning the game.

I don't know if trying to roll ranking and score into the same function will be what you want, because it's an arbitrary blend between the two, and balancing that will be tricky. eg. In your example there, in a 4 player game a player cares more about moving from 4th place to 3rd by gaining 2 points than it would about having the 2 top players both drop 50 points while not changing the rankings. This might make sense in the end game (as ranking is key) but not at the start (because you presumably still have a chance of winning and want everyone to score less, not just your most immediate rank neighbour).

In your situation I might be tempted to try and create a more abstract, strategic approach. One that hinged upon spotting certain features of the game and working based on that. Or one which collapsed the game tree down into a smaller number of abstract move types, solved (or at least more thoroughly explored) that game tree, then expanded it out into a single concrete next move.

I just wanted to add - the other poster mentioned A, and you're worried about the search space. With A, if your heuristic is perfect and monotonic, the search should reduce to depth-first which should be fine in almost any search space. The main problem you have is that your heuristic is not monotonic, since your scores, and hence your distance to a solution state, can't be guaranteed to converge with each step. There might be a way out of that, but it would depend more on your game rules.