6
$\begingroup$

Player A and Player B are playing a turn-based game. At the beginning of the game there are $N(N \ge 3)$ points in a plane. In each turn one of the players chooses exactly $3$ different points and he connects them with a closed curve line (He can leave as many points as he wants inside/outside of the closed curve). The only other restriction of the game is that none of the line should intersect or touch each other (Therefore you can't choose a point that's already lying on a curve). After finite number of moves it's not possible to choose $3$ different points without violating the rules, hence the game ends. The player who drew a closed curve last is the winner. For which $N$ Player A can be sure that he will win, no matter how Player B plays?


I've managed to partially solve this problem, as I have proved that for every odd number, the Player A can always win the game. The strategy is to choose $3$ random points and connect them with a closed curve such that the number of point encircled by the curve is the same as the number of line outside of the curve. After that in each turn Player A repeats what Player B does, so because of the symmetry he's garanteed to finish last and hence win.

On the other hand this strategy doesn't work for even numbers. By brute-force and checking every possible game situation, I found out that Player A can't win when $N=8,14,20$ (I did this up to 20, as the calculations get more complicated as the number of points grows). This makes me conjecture that Player A can't win when $N=6k+2$, unless Player B makes a mistake.

On each turn the dots are split into two new "disjoint" sets. Actually after $K$ turns we have $K+1$ "disjoint" sets, albeit some of them can be empty. This sets of point can be treated as separate games, but the problem is that sometimes is better to lose in some of those separate games, in order to win in the last one.

$\endgroup$
  • 1
    $\begingroup$ Ugh, it's a tough one... Let me reformulate the problem. You have a list of number. Each player pick a number greater than 3, remove 3 from it and separate the remaining value into two values. Now, playing on a losing state $L$ automatically brings a winning state $W$. And playing on a losing have always the possibly to bring a wining state $W$ a losing state $L$. So list $[L L]$ is losing because either you cannot play or you must play to bring something like $[W L]$, which is winning since you can bring it to a $[L L]$ state. The problem is with $[W W]$ states. $\endgroup$ – Lærne Feb 29 '16 at 11:43
4
$\begingroup$

Disclaimer: A lot of this post was copied from my answer to a similar sort of game.

Summary

It turns out that this game is very closely related to the Octal Game with code "0.007". Using the Sprague-Grundy Theorem combined with a winning strategy for Nim, it is relatively straightforward to analyze small games like this (e.g. your game for small $n$), and there are theorems which give efficient algorithms to learn about this in the medium range. Some Octal games can be efficiently solved even in large cases, but this particular game is not one of them.

It turns out that $B$ has a winning strategy for $N={0, 1, 2, 8, 14, 24, 32, 34, 46, 56, 66, 78, 88, 100, 112, 120, 132, 134, 164, 172, 186, 196, 204, 284, 292, 304, 358, 1048, 2504, 2754, 2914, 3054, 3078, 7252, 7358, 7868, 16170}$ and $A$ has a winning strategy in all other cases up to $2^{28}-1$. But I believe the general result is still open.


Connecting this game to existing theory

First note that you shouldn't be able to draw a curve through points as then drawing a curve through all of the points would be a winning move all of the time. To connect this game to existing general theory, we can reconceptualize it in the way that Lærne did: After you draw a curve, you remove three points from a component, and split the remainder into two components (where one or both of those may be empty). That is traditionally encoded in a "number" with Octal digits. In this case, the code is $0.007$, where the $0$s indicate that you can't remove only one or two points, and the three bits of the $7$ indicate that you can leave zero or one or two components when you remove three points from a component.


Who wins?

Since the original question was "who has a winning strategy?", rather than "what is the winning strategy, I won't re-present an introduction to the relevant theorems in detail.

If you don't already know about the strategy for Nim or the Sprague-Grundy Theorem and how they can be applied to similar games, you can read one or more of the following:

Very briefly, positions in games like this act in combinations like single heaps of Nim, where the size of the corresponding Nim heap is the least number that's not a size of a Nim heap corresponding to a position you can move to. The strategy for Nim tells you that combining games with known equivalent Nim boils down to bitwise XOR (aka "adding in base $2$ without carrying").

Because of the strategy for Nim (how Grundy values combine), and a position in this game is a combination of separate components, it suffices to know the Grundy/Nim values for a single "heap" (in our context, a single component of points). There are tricks to make this calculation more efficient than the naive method, some of which are covered in the graduate textbook "Combinatorial Game Theory" by Aaron N. Siegel. For some similar games, the Nim values are known to be eventually periodic (by a theorem that says they will be if they look periodic long enough), but according to Flammenkamp, for $0.007$, $2^{28}$ values have been calculated with no periodic behavior, although the values $N$ for which $B$ wins appear to stop at $16170$.

Aaron Siegel's program Combinatorial Game Suite allows efficient calculation of middling values (but probably wouldn't get up to $2^{28}$. For example, the lines hr:=game.heap.HeapRules.MakeRules("0.007") and hr.NimValues(100000) takes about a minute and a half on my machine to produce the list of Nim values for $N=0$ to $N=99999$.

For example, the Nim values from $N=0$ to $N=499$ are as follows (remember that $N=0$ corresponds to a win for $B$) $0,0,0,1,1,1,2,2,0,3,3,1,1,1,0,4,3,3,3,2,2,2,4,4,0,5,5,2,2,2,3,3,0,5,0,1,1,1,3,3,3,5,6,4,4,1,0,5,5,6,6,2,7,7,7,8,0,1,9,2,7,2,3,3,3,9,0,5,4,4,8,6,6,2,7,1,1,1,0,5,5,9,3,1,8,2,8,5,0,1,1,12,2,2,7,3,3,9,4,4,0,11,3,3,3,9,2,2,8,1,3,5,0,9,12,2,6,13,13,5,0,1,1,4,11,7,7,10,3,4,1,4,0,5,0,3,3,6,7,2,14,13,10,4,12,9,2,2,3,3,6,9,9,1,16,4,8,3,3,2,15,1,1,4,0,5,5,16,6,6,6,8,0,16,5,4,4,17,2,2,7,14,6,10,12,1,0,16,13,3,6,2,7,7,8,1,0,5,17,2,12,15,3,11,0,19,18,12,4,16,17,2,2,21,6,9,4,19,5,5,17,10,3,6,19,2,7,8,4,1,9,12,7,2,13,6,3,19,5,9,4,8,8,17,17,2,15,18,1,1,8,5,21,16,21,3,19,19,13,5,18,1,4,17,7,2,7,6,3,19,12,5,5,16,16,6,17,19,7,7,18,1,4,17,0,9,16,3,3,14,13,22,0,1,15,24,17,2,6,18,3,4,19,19,0,8,21,16,3,15,7,26,18,13,1,1,17,9,2,21,2,6,22,19,9,5,16,4,16,20,3,7,18,23,22,8,20,5,16,21,15,6,10,19,18,18,18,4,4,17,17,7,2,3,23,19,9,5,0,16,16,3,17,30,2,18,18,8,4,17,17,9,27,6,10,19,19,14,9,9,4,20,17,14,11,7,18,6,19,19,5,13,16,16,10,6,19,19,23,18,4,4,17,12,12,14,10,6,3,19,5,9,5,21,16,20,6,7,7,18,30,13,13,17,12,21,15,10,3,19,22,18,8,4,32,17,17,11,14,6,26,24,12,5,9,16,16,6,7,7,7,18,18,8,4,17,20,7,16,10,10,22,19,22,9,23,4,13,17,20,7,11,23,23,4,5,9,5,16,16,10,17,10,22,18,23,8,4,17,17,20,16,32,13,19,19,33,5,5,24$

$\endgroup$
  • $\begingroup$ Wow! What an insightful answer. It seems that at the moment this Octal game isn't solved. Anyway you don't have to change the rules, as the rules of my game are equivalent to Lærne's. The curve passes through exactly 3 points (the one we've chosen). Also I was wondering how can I calculate the Nim values. I mean you said we'll use the Nim values for single heaps, but the Nim value for a single heap with size $m$ is simply $m$. $\endgroup$ – Stefan4024 Mar 1 '16 at 18:15
  • $\begingroup$ @Stefan4024 The relevant use of the word "heap" is in scare quotes. A "heap" in the octal game 0.007 corresponds to a collection of points in the same component in your game. In addition to the 8 or so resources I mentioned that explain the correspondence between positions and heaps of Nim, and one way to compute the Nim values, I also just added a couple sentences on the subject. For example, a component with 6 points in your game happens to act like a Nim heap of size 2 in combinations since you can move to 3 pts (Nim 1), 1pt and 2 pts (Nim 0). $\endgroup$ – Mark S. Mar 2 '16 at 2:55
3
$\begingroup$

This problem intrigued me, so after spending (too) much time on it, I wrote a little python script to compute winning and losing states. Accordingly to it, 20 is a winning state. but 24 isn't. It's a funny little problem.

I reformulated the problem in term of ordered list of element greater than 3 for simplicity. Basically each section of the plane separated by curves is a cell, with the number in the cell, the number of free points in that section of the plane. Thus, each player pick a number greater than 3, remove 3 from it and separate the remaining value into two values (or one, when you prune out values at 0, 1, or 2).

here is the code :

def mkstate( state ):
    return tuple( sorted( filter( lambda x : x >= 3, state ) ) )

def childrenForNumber( n ):
    if n < 3:
        return

    n_3 = n - 3
    if n_3 == 0:
        yield ( 0, 0 )
        return

    children = set()
    for i in range( 0, n_3 ):
        yield ( i, n_3-i )

def childrenForState( state ):
    children = set()
    for k in range(len(state)):
        previous = state[:k]
        after = state[k+1:]
        for childForNumber in childrenForNumber( state[k] ):
            child = mkstate(previous + childForNumber + after)
            if child not in children:
                children.add( child )
                yield child

statesWinFlagStore = { tuple():False }

def isWinningStates( state ):
    if state in statesWinFlagStore:
        return statesWinFlagStore[state]
    else:
        onlyWinningChildren = True
        for child in childrenForState( state ):
            childIsWinning = isWinningStates( child )
            onlyWinningChildren = onlyWinningChildren and childIsWinning
        statesWinFlagStore[ state ] = ( not onlyWinningChildren )
        return ( not onlyWinningChildren )


def print_1dstates( bound ):
    for i in range( 0, bound+1 ):
        print( [i], ":", "W" if isWinningStates( (i,) ) else "L" )

def print_2dstates( bound ):
    from sys import stdout
    stdout.write("   ")
    for j in range( 0, bound+1 ):
        stdout.write("%02d "%j)
    stdout.write("\n")
    for i in range( 0, bound+1 ):
        stdout.write("%02d "%i)
        for j in range( 0, i+1 ):
            b = isWinningStates( (i,j) )
            stdout.write( " W " if b else " L " )
            pass
        stdout.write("\n")
        stdout.flush()

def print_tree( state, shift=0 ):
    s = " " * shift
    print( s, end='' )
    print( "[%s]" %",".join(map(str,state)), ":", "W" if isWinningStates( state ) else "L" )
    for child in childrenForState( state ):
        print_tree( child, shift=shift+3 )


if __name__ == '__main__':
    print_2dstates( 40 )

And here are the results for states of the form [i,j]:

   00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 
00  L 
01  L  L 
02  L  L  L 
03  W  W  W  L 
04  W  W  W  L  L 
05  W  W  W  L  L  L 
06  W  W  W  W  W  W  L 
07  W  W  W  W  W  W  L  L 
08  L  L  L  W  W  W  W  W  L 
09  W  W  W  W  W  W  W  W  W  L 
10  W  W  W  W  W  W  W  W  W  L  L 
11  W  W  W  L  L  L  W  W  W  W  W  L 
12  W  W  W  L  L  L  W  W  W  W  W  L  L 
13  W  W  W  L  L  L  W  W  W  W  W  L  L  L 
14  L  L  L  W  W  W  W  W  L  W  W  W  W  W  L 
15  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  L 
16  W  W  W  W  W  W  W  W  W  L  L  W  W  W  W  W  L 
17  W  W  W  W  W  W  W  W  W  L  L  W  W  W  W  W  L  L 
18  W  W  W  W  W  W  W  W  W  L  L  W  W  W  W  W  L  L  L 
19  W  W  W  W  W  W  L  L  W  W  W  W  W  W  W  W  W  W  W  L 
20  W  W  W  W  W  W  L  L  W  W  W  W  W  W  W  W  W  W  W  L  L 
21  W  W  W  W  W  W  L  L  W  W  W  W  W  W  W  W  W  W  W  L  L  L 
22  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  L  W  W  W  W  W  W  L 
23  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  L  W  W  W  W  W  W  L  L 
24  L  L  L  W  W  W  W  W  L  W  W  W  W  W  L  W  W  W  W  W  W  W  W  W  L 
25  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  L 
26  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  L  L 
27  W  W  W  W  W  W  L  L  W  W  W  W  W  W  W  W  W  W  W  L  L  L  W  W  W  W  W  L 
28  W  W  W  W  W  W  L  L  W  W  W  W  W  W  W  W  W  W  W  L  L  L  W  W  W  W  W  L  L 
29  W  W  W  W  W  W  L  L  W  W  W  W  W  W  W  W  W  W  W  L  L  L  W  W  W  W  W  L  L  L 
30  W  W  W  W  W  W  W  W  W  L  L  W  W  W  W  W  L  L  L  W  W  W  W  W  W  W  W  W  W  W  L 
31  W  W  W  W  W  W  W  W  W  L  L  W  W  W  W  W  L  L  L  W  W  W  W  W  W  W  W  W  W  W  L  L 
32  L  L  L  W  W  W  W  W  L  W  W  W  W  W  L  W  W  W  W  W  W  W  W  W  L  W  W  W  W  W  W  W  L 
33  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  L  L  W  W  W  W  W  W  L 
34  L  L  L  W  W  W  W  W  L  W  W  W  W  W  L  W  W  W  W  W  W  W  W  W  L  W  W  W  W  W  W  W  L  W  L 
35  W  W  W  L  L  L  W  W  W  W  W  L  L  L  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  L 
36  W  W  W  L  L  L  W  W  W  W  W  L  L  L  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  L  L 
37  W  W  W  L  L  L  W  W  W  W  W  L  L  L  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  W  L  L  L 
38  W  W  W  W  W  W  W  W  W  L  L  W  W  W  W  W  L  L  L  W  W  W  W  W  W  W  W  W  W  W  L  L  W  W  W  W  W  W  L 
39  W  W  W  W  W  W  W  W  W  L  L  W  W  W  W  W  L  L  L  W  W  W  W  W  W  W  W  W  W  W  L  L  W  W  W  W  W  W  L  L 
40  W  W  W  W  W  W  W  W  W  L  L  W  W  W  W  W  L  L  L  W  W  W  W  W  W  W  W  W  W  W  L  L  W  W  W  W  W  W  L  L  L 

I hope it somehow helps.

$\endgroup$
  • $\begingroup$ The code is really nice and it gives even more interesting results. It seems that there isn't a particular pattern, as for $N=8,14,24,32,34$ Player B can always win by playing the right way. Which probably makes the problem even more difficult, as we will have troubles to generalize a proof for all those numbers. Also I wonder whether there are infinite amount of numbers $N$ for which B can always win. $\endgroup$ – Stefan4024 Feb 29 '16 at 20:33
  • $\begingroup$ You made a good observation about reinterpreting the game. +1 It turns out that after that observation, much is already known about this game/relevant algorithms. See my answer for more details. $\endgroup$ – Mark S. Mar 1 '16 at 13:55

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.