Algorithms to play randomized game
From your explanation I assume that the game is not episodic, but sequential: each move outcome is dependent on the previous moves.

The Minimax algorithm modification you explained is called Expectimax and is generally a standard approach for such problems as far as I know. In order to avoid the big branching factor you can try some variation of the Monte Carlo algorithm. This way you will be able to explore deeper the game tree and still take into consideration the randomness.