If there was an accurate way to rate Dominion decks (see the forums for an attempt), a computer would still have to calculate several hundreds or maybe thousands of playthroughs for every decision. And this number increases really fast. If we start with a $5/$2 start and there are only $2 cards in the kingdom (no Young Witch or Black Market or Hinterlands-pre-shuffle-activation cards), a player can do 16 things with $5: Buy a Duchy/Estate/Curse, Silver/Coppper, any of 10 Kingdom cards or buy nothing. With his $2 he can still do 14 things. So that's 16*14 = 224 possible opening moves. Then there's the shuffling. With anywhere from 10 to 12 cards, there are already hundreds of shuffling probabilities. And for each of those shuffles, a computer would continue branching, buy nothing or something and shuffle again at the end of the deck. Even with pruning (not pursuing unfruitful branches), this takes immense calculation power.
I would not be so pessimistic, or better would think that "rating the deck" would indeed have to deal with all this, and find a way to give some simple numbers to include all these possiblities. It's not so much different from chess. In chess, you also can't compute the game to its end, but have to stop at some point and take a heuristic on "how good" the game state is. And in chess you also have lots of possibilities, a free Queen in the middle of the board can move to 27 positions.
A human player also does not rate the state of Dominion by thinking about all possible outcomes. But you rate your deck and your choices by some heuristics, like "importance" of a card, and "collision probabilites" (for good: Village-Smithy, or bad Smithy-Smithy). And you don't think that you have a 27.4% prob that you will draw 5-4-2 the nex tshuffle, and a 19.0% prob to draw 6-3-3 etc. But you will think about somethink like: "Ok, the next few turns, I should be able to buy a $5 card or a Gold, when I'm lucky it will be two, and 2 or 1 cards for $4--."
I'm not an expert of chess, but in Dominion I think the problem for a good rating is that there are lots of important variants how the deck in the end looks like, and so it's really difficult to rate how good a rate is at the moment. I guess in chess there is no strategy where it is really a good idea to sacrifice the Queen and two Bishops for nothing, but Dominion decks look really different.
There are lots of combos which rely on just two cards, and even don't want something different, like NV/Bridge, HP/Baron, lots of BM-trick but even if you exclude these, engines are build in very different ways, depending on which Village, which draw, even which +buy is on the board, if there are alternative VPs, if there is Workshop/Ironwork/HoP/Quarry/Talisman, which attacks threaten the engine, or want to be mixed into it...? And all these engines want to be built differently, and it's very difficult to find a single (or two or three) metrics that describe which buy is "good" for these engine in a given situation.
I think the randomness is not a great problem if you would solve that. Draw 100 samples per decision and that's it, to get a bot that plays as fast as a human you could even affort 10.000. That's more than enough to get a good approximation. You maybe will not look as far in the future as you can in chess, but in both cases you can't look until the end of the game, and the important part is to have a good heuristics there to rate the state of the game.