Public forum discussion.
23 Sep 2012
I have a conjecture for Hex (or any maker-breaker game, for the matter). I have no idea if this is already a theorem (or proven false), but I have found no counterexamples yet after days of thought:
In a normal one-move-per-turn maker-breaker game, a winning strategy exists for a player if, at the beginning of their turn, their number of possible winning sets is greater than or equal to their number of possible losing sets.
Also, here is a theorem that I have proven:
Let P1 be the number of possible winning sets for a player before taking an element, and P2 be the number of winning sets for the same player after taking the element. Then:
P1 is greater than or equal to P2, which is greater than or equal to (1/2)P1.
I can type up have a proof of that one later if anyone is interested.
23 Sep 2012
Consider the following game. Players A and B alternately select a number from {1, 2, 3, 4, 5, 6}. A, who moves first, wins if he can get both 1 and 2, or both 3 or 4, or both 5 and 6. Otherwise, B wins. A has 12 winning sets out of the 20 possibilities, but B has a simple winning strategy, as 1 and 2 are miai, as well as 3 and 4, and 5 and 6.
23 Sep 2012
Of course this "game" is easily translated into a feasible Hex position.
23 Sep 2012
What is your precise definition of "winning sets"? The number of distinct game continuations (that result in a win for player X)? Or the number of distinct filled board configurations (in which player X wins)? Or the number of distinct board configurations (in which player X wins) that could be reached by legal play? Or what?
Is your conjecture meant to apply only at the beginning of a game? Or at any configuration that could be reached by legal play? Or when?
I looked once at some hex puzzles (which could be arrived at by legal play if the part of the board not involved in the puzzle is filled appropriately) in which the player to move has a winning strategy, but has nevertheless, IIRC, fewer winning sets by any of the definitions I noted above.
23 Sep 2012
Thanks! I don't know why I didn't think of that sooner :)
23 Sep 2012
The example given by T.D. shoots down both senses of "winning sets", as there are more for A regardless of through legal play or not. In fact, out of the 64 configurations, A wins in 37 of them.
24 Sep 2012
There is a reason he is called a devil ...