On Stealth Rocks: when there are unknown pokemon it may help to use some data on the usages of pokemon and leftovers to determine the amount it will lower the opposing pokemons score by (this score will then be moved up or down depending on what is revealed). The amount that it lowers the score by will be affected by things like typing, leftovers, and recovery moves, right?
Also, another problematic move may be taunt. It requires values of problematic battle effects, and it would really help to know the common sets of opposing pokemon (and distinguish between, say common leading sr's and other movesets that would be much more common if they are in other places in the team). It will also weight the chance that it makes the opposing move do nothing versus them using an attacking move, but that can just be done with probabilities.
Have you considered the possibility of making some killer moves to reduce the amount of nodes that have to be traversed? I feel that this could especially useful in the middle of the game when a lot about your opponents team is known, but not there are too many possibilities, so it can't just be brute-forced.
Finally, can you post the exact point values of some different types of moves/pokemon and some modifiers that you have so far (or just snippets of code)?