# 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.

• Let S be n-bit binary string that represents which player is taking the turn. In the worst-case, you recover standard hex game if the random sequence is 010101... or 101010.... So, your problem is at least as hard as standard hex. Oct 21 '10 at 6:12
• There are two possible interpretations of this game. (1) Just before every turn, the players flip a coin to determine who goes next. (2) At the beginning of the game, the players flip a coin $n^2$ times (on a size $n$ board), and use this sequence for their turns. Turkistany seems to be assuming model (2); the original question is ambiguous, but from some of his wording I'd guess Itai is asking about (1), which might be easier than standard hex. Oct 21 '10 at 12:27
• Indeed, I mean the first interpretation, that the coin is flipped right before the move. Additionally, I noticed another ambiguity in my question: the precision in which I want to know the probability. While the impression I left when asking the problem is that I want to know the probability in complete precision, but I only want to know the probability in logarithmic precision. Like the difference between PP and BPP, the later seems more useful and natural. Oct 21 '10 at 21:28
• @Itai: Another question. Why do you claim that this is obviously in PSPACE? It seems to me that it is a refereed game, which would mean that the natural complexity-theoretic upper bound is EXPTIME. See Feige and Kilian, "Making Games Short." Oct 21 '10 at 22:43
• @tukistany Useless does NOT imply trivial! Oct 22 '10 at 1:59