16
$\begingroup$

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.

$\endgroup$
  • 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-Turkistany Oct 21 '10 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 Shor Oct 21 '10 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-Natan Oct 21 '10 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 Shor Oct 21 '10 at 22:43
  • 4
    $\begingroup$ @tukistany Useless does NOT imply trivial! $\endgroup$ – Jeffε Oct 22 '10 at 1:59
23
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ I'm just amazed that people have actually worked on this :) Nice reference ! $\endgroup$ – Suresh Venkat Oct 22 '10 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$ – Peter Shor Oct 22 '10 at 3:30
  • 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$ – Andy Drucker Oct 22 '10 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$ – Gil Kalai Nov 10 '10 at 3:11
  • 1
    $\begingroup$ 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 arxiv.org/pdf/0812.3677.pdf and 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.) $\endgroup$ – Andy Drucker Dec 15 '12 at 4:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.