I've been thinking of a variant of hex, where instead of the two players making moves alternately, each turn a player picked at random makes a move. How hard is it to determine the chances for each player winning? This problem is obviously in PSPACE, but can't it to be NP-hard, much less PSPACE-complete. The difficulties come from how the randomness makes it impossible for a player to be forced into making a choice among options; if that player is lucky he gets enough moves two take both options, and if the player is unlucky the opponent gets enough moves to block both options. On the other hand, I can't think of any polynomial-time algorithms for this.
You might want to look at the paper "Random-Turn Hex and Other Selection Games," by Yuval Peres, Oded Schramm, Scott Sheffield, and David Wilson. From the introduction:
"Random-Turn Hex is the same as ordinary Hex, except that instead of alternating turns, players toss a coin before each turn to decide who gets to place the next stone. Although ordinary Hex is famously difficult to analyze, the optimal strategy for Random-Turn Hex turns out to be very simple."
So indeed, your intuition was right: this will be in BPP (or maybe P).