Game-winning strategy
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:
- Tom Ferguson's class notes on the subject
- MJD's notes in their tidy blog post about using this theory to solve the game in the question for $n$ up through $23$.
- Lim Chu Wee's series of blog posts which are also class notes building up the relevant theory (posts I through V)
- The lecture notes Misère Games and Misère Quotients by Aaron N. Siegel through page 10.
- My own long-winded series of blog posts building up the relevant theory (posts I.1 through I.6).
- Chapter 7 of the undergraduate textbook "Lessons in Play: An Introduction to Combinatorial Game Theory" by Albert, Nowakowski, and Wolfe (although a bit of reading of other chapters may be needed first).
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$
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.