<p>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: </p>

<blockquote>
  <p>"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."</p>
</blockquote>

<p>So indeed, your intuition was right: this will be in BPP (or maybe P). </p>

CC BY-SA 3.0
2012-12-15T04:18:06.787Z
It turns out that there is a remarkable connection (due to David Richman) between random-turn games and *bidding games*, where the players bid for the next move; see http://arxiv.org/pdf/0812.3677.pdf    and http://users.math.yale.edu/~sp547/pdf/Discrete-bidding-games.pdf     This connection allows for essentially optimal play of bidding Hex, using the work of Peres et al.  I like this because bidding games are, at least ostensibly, luck-free, and I think bidding Hex would be more satisfying to play than random-turn Hex.  (Bidding every turn might be a maddeningly demanding task, however.)
Andy Drucker
CC BY-SA 3.0
2013-03-24T03:23:55.887Z
Bidding hex against people is indeed a lot of fun to play, there's a facebook app (though it doesn't seem to still work for me).  Against a computer playing an approximation to the optimal strategy it's not much fun because you will just get clobbered.
Noah Snyder
CC BY-SA 2.5
2010-10-22T03:24:37.927Z
I'm just amazed that people have actually worked on this :) Nice reference !
Suresh Venkat
CC BY-SA 2.5
2010-10-22T03:30:02.937Z
It's a really nice proof, too. I think I heard Scott Sheffield mention it in one of his talks (but then I completely forgot about it until it turned up on Google).
Peter Shor 
CC BY-SA 2.5
2010-10-22T15:23:32.923Z
Very nice result that should be better known. I am very surprised though that the optimal solution is not something very nice and symmetric. E.g. it seems true that the first move occupies the center of the board, why don't all the moves show some nice behavior? Is it an artifact of the probabilistic algorithm that they used or do we really get some random looking set colored black and white?
domotorp
CC BY-SA 2.5
2010-10-22T19:18:58.090Z
The algorithm these authors give is randomized and approximate; so, if there exists a strategy with value p starting from some given position, their strategy will win with probability at least (p - eps) for your choice of eps.  So, it might conceivably still be PSPACE-hard to play an exactly optimal strategy.
Andy Drucker
CC BY-SA 2.5
2010-10-22T19:20:51.410Z
Also, David Wilson's website actually has an application that allows you to play random-turn Hex (against their published strategy, I believe): http://dbwilson.com/#software
Andy Drucker
CC BY-SA 2.5
2010-11-10T03:11:54.197Z
In his last visit to Israel, inspired by the PSSW's paper, Oded Schramm and I played a quite a few rounds of random-turn-chess to realize that it is not a particularly interesting game.
Gil Kalai
CC BY-SA 2.5
2010-10-21T22:58:11.517Z
2010-10-21T22:58:11.517Z
Peter Shor 
<p>I've been thinking of a variant of <a href="http://www.hexwiki.org/" rel="nofollow">hex</a>, 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.</p>

CC BY-SA 2.5
2010-10-21T05:35:39.193Z
I don't know how hex is played. do you have a good link ?
Suresh Venkat
CC BY-SA 2.5
2010-10-21T05:44:57.693Z
There is a wiki on hex in www.hexwiki.org. There is a description of the rules in the "Rules" article.
Itai Bar-Natan
CC BY-SA 2.5
2010-10-21T06:12:12.890Z
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.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-21T07:52:40.090Z
So, the problem is PSPACE-complete
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-21T12:27:38.330Z
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.
Peter Shor 
CC BY-SA 2.5
2010-10-21T17:19:02.360Z
@turkistany: No, this doesn't prove the problem is PSPACE-hard.  In principle, it may be possible to compute the probability of winning without determining who wins with *any* particular sequence of coin flips.
Jeffε
CC BY-SA 2.5
2010-10-21T19:16:06.667Z
@JeffE, your interpretation makes the problem trivial since finding the the probability of wining is useless if we can't infer who actually won the game. BTW, How hard is it to find the probability of wining in standard hex (no randomness)?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-21T21:28:42.660Z
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.
Itai Bar-Natan
CC BY-SA 2.5
2010-10-21T22:43:49.890Z
@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."
Peter Shor 
CC BY-SA 2.5
2010-10-22T00:24:31.600Z
@Itai: Ignore that last comment. The coins are public, which means that it's in PSPACE.
Peter Shor 
CC BY-SA 2.5
2010-10-22T01:59:33.633Z
@tukistany Useless does NOT imply trivial!
Jeffε
CC BY-SA 2.5
2010-10-22T10:44:52.353Z
*"This problem is obviously in PSPACE"*: What is your input? I thought the game of hex begins with an *empty* $n \times n$ board? If your input is just the value $n$, do you assume unary or binary encoding of it?
Jukka Suomela
CC BY-SA 2.5
2010-10-22T12:47:19.763Z
@Jukka: For an empty board, the probability of winning is clearly $1/2$ by symmetry, giving a constant-time algorithm (and thus indeed *obviously* in PSPACE). This calculation is completely useless for determining which piece to play. For Itai's question, the input is a partially played game on an $n \times n$ board. For turkistany's interpretation (see my comment above), the correct input to consider is less clear.
Peter Shor 
<cc.complexity-theory><board-games>
Complexity of hex with random turn order.
Itai Bar-Natan
# Complexity of hex with random turn order.

(Asked by: username_0 on 2010-10-21)

I've been thinking of a variant of [hex](http://www.hexwiki.org/), 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.

**Tags:** cc.complexity-theory, board-games

> **Comments:**
> **username_1**: I don't know how hex is played. do you have a good link ?  
> **username_0**: There is a wiki on hex in www.hexwiki.org. There is a description of the rules in the "Rules" article.  
> **username_2**: 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.  
> **username_2**: So, the problem is PSPACE-complete  
> **username_3**: 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.  
> **username_4**: @turkistany: No, this doesn't prove the problem is PSPACE-hard.  In principle, it may be possible to compute the probability of winning without determining who wins with *any* particular sequence of coin flips.  
> **username_2**: @JeffE, your interpretation makes the problem trivial since finding the the probability of wining is useless if we can't infer who actually won the game. BTW, How hard is it to find the probability of wining in standard hex (no randomness)?  
> **username_0**: 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.  
> **username_3**: @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."  
> **username_3**: @Itai: Ignore that last comment. The coins are public, which means that it's in PSPACE.  
> **username_4**: @tukistany Useless does NOT imply trivial!  
> **username_5**: *"This problem is obviously in PSPACE"*: What is your input? I thought the game of hex begins with an *empty* $n \times n$ board? If your input is just the value $n$, do you assume unary or binary encoding of it?  
> **username_3**: @Jukka: For an empty board, the probability of winning is clearly $1/2$ by symmetry, giving a constant-time algorithm (and thus indeed *obviously* in PSPACE). This calculation is completely useless for determining which piece to play. For Itai's question, the input is a partially played game on an $n \times n$ board. For turkistany's interpretation (see my comment above), the correct input to consider is less clear.  

---

## 1 answers

### Answer by username_3 on 2010-10-21. Score: 23 | Accepted answer

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

> **Comments:**
> **username_1**: I'm just amazed that people have actually worked on this :) Nice reference !  
> **username_3**: It's a really nice proof, too. I think I heard Scott Sheffield mention it in one of his talks (but then I completely forgot about it until it turned up on Google).  
> **username_8**: Very nice result that should be better known. I am very surprised though that the optimal solution is not something very nice and symmetric. E.g. it seems true that the first move occupies the center of the board, why don't all the moves show some nice behavior? Is it an artifact of the probabilistic algorithm that they used or do we really get some random looking set colored black and white?  
> **username_6**: The algorithm these authors give is randomized and approximate; so, if there exists a strategy with value p starting from some given position, their strategy will win with probability at least (p - eps) for your choice of eps.  So, it might conceivably still be PSPACE-hard to play an exactly optimal strategy.  
> **username_6**: Also, David Wilson's website actually has an application that allows you to play random-turn Hex (against their published strategy, I believe): http://dbwilson.com/#software  
> **username_9**: In his last visit to Israel, inspired by the PSSW's paper, Oded Schramm and I played a quite a few rounds of random-turn-chess to realize that it is not a particularly interesting game.  
> **username_6**: It turns out that there is a remarkable connection (due to David Richman) between random-turn games and *bidding games*, where the players bid for the next move; see http://arxiv.org/pdf/0812.3677.pdf    and http://users.math.yale.edu/~sp547/pdf/Discrete-bidding-games.pdf     This connection allows for essentially optimal play of bidding Hex, using the work of Peres et al.  I like this because bidding games are, at least ostensibly, luck-free, and I think bidding Hex would be more satisfying to play than random-turn Hex.  (Bidding every turn might be a maddeningly demanding task, however.)  
> **username_7**: Bidding hex against people is indeed a lot of fun to play, there's a facebook app (though it doesn't seem to still work for me).  Against a computer playing an approximation to the optimal strategy it's not much fun because you will just get clobbered.  

---

