Complexity of hex with random turn order. 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).