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.
$\begingroup$
$\endgroup$
13
-
4$\begingroup$ 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. $\endgroup$– Mohammad Al-TurkistanyOct 21, 2010 at 6:12
-
6$\begingroup$ 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. $\endgroup$– Peter ShorOct 21, 2010 at 12:27
-
2$\begingroup$ 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. $\endgroup$– Itai Bar-NatanOct 21, 2010 at 21:28
-
2$\begingroup$ @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." $\endgroup$– Peter ShorOct 21, 2010 at 22:43
-
4$\begingroup$ @tukistany Useless does NOT imply trivial! $\endgroup$– JeffεOct 22, 2010 at 1:59
|
Show 8 more comments
1 Answer
$\begingroup$
$\endgroup$
8
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).
answered Oct 21, 2010 at 22:58
-
4$\begingroup$ I'm just amazed that people have actually worked on this :) Nice reference ! $\endgroup$ Oct 22, 2010 at 3:24
-
1$\begingroup$ 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). $\endgroup$ Oct 22, 2010 at 3:30
-
2$\begingroup$ 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. $\endgroup$ Oct 22, 2010 at 19:18
-
1$\begingroup$ Also, David Wilson's website actually has an application that allows you to play random-turn Hex (against their published strategy, I believe): dbwilson.com/#software $\endgroup$ Oct 22, 2010 at 19:20
-
1$\begingroup$ 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. $\endgroup$ Nov 10, 2010 at 3:11