For which set A, Alice has a winning strategy?

MO456035.py

#!/usr/bin/pypy3

from functools import lru_cache

# Limit memory usage to 8GB
import resource
resource.setrlimit(resource.RLIMIT_AS, (8 * 1024**3, 8 * 1024**3))


"""
This is a pretty straightforward implementation which gets up to n=19 in the 8GB limit.
"""

def renumber_inc_lo(elts, x):
	return tuple(y + 1 if y < x else y for y in elts)


def renumber_dec_hi(elts, x):
	return tuple(z - 1 if z > x else z for z in elts)

@lru_cache(None)
def is_next_player_win(state):
	x, my_set, their_set = state
	assert my_set
	assert their_set
	if len(my_set) == 1 and my_set[0] > x:
		# I play and win
		return True

	# It's always an option to play 0, but doing so when x = 0 causes infinite recursion.
	# TODO Is it ever the right play? Seems unlikely.
	if x > 0:
		# Every number below x is incremented and numbers above it are untouched
		if not is_next_player_win((0, renumber_inc_lo(their_set, x), renumber_inc_lo(my_set, x))):
			return True

	for i, y in enumerate(my_set):
		if y > x:
			assert len(my_set) > 1
			# Can play y. We delete x, so decrement everything higher than it (which includes y by assumption).
			if not is_next_player_win((y - 1, renumber_dec_hi(their_set, x), renumber_dec_hi(my_set[:i] + my_set[i+1:], x))):
				return True

	return False

def count_first_player_wins(n):
	# Initially the sets are non-empty, which is why the range of mask is pulled in by 1 on each end.
	return sum(1 if is_next_player_win((0, tuple(1+x for x in range(n) if (mask >> x) & 1), tuple(1+x for x in range(n) if not((mask >> x) & 1)))) else 0 for mask in range(1, (1 << n) - 1))


"""
We can get further by using a more memory-efficient state representation for the LRU cache.
Here we pack the entire state as a ternary number, avoiding the overhead of tuple representations.
"""

def pack(x, my_set, their_set):
	n = max(x, max(my_set + their_set))
	my_set = set(my_set)
	rv = 0
	for i in range(n, -1, -1):
		rv = rv * 3 + (0 if i == x else 1 if i in my_set else 2)
	return rv


def unpack(packed):
	x = None
	my_set = []
	their_set = []
	i = 0
	while packed:
		packed, target = divmod(packed, 3)
		if target == 0:
			x = i
		elif target == 1:
			my_set.append(i)
		else:
			their_set.append(i)
		
		i += 1

	# If the top ternary digit is 0, x = i. This is why a ternary packing is safe.
	if x is None:
		x = i

	return x, my_set, their_set



@lru_cache(None)
def is_next_player_win_packed(state):
	x, my_set, their_set = unpack(state)
	assert my_set
	assert their_set
	if len(my_set) == 1 and my_set[0] > x:
		# I play and win
		return True

	# It's always an option to play 0, but doing so when x = 0 causes infinite recursion.
	# TODO Is it ever the right play? Seems unlikely.
	if x > 0:
		# Every number below x is incremented and numbers above it are untouched
		if not is_next_player_win_packed(pack(0, renumber_inc_lo(their_set, x), renumber_inc_lo(my_set, x))):
			return True

	for i, y in enumerate(my_set):
		if y > x:
			assert len(my_set) > 1
			# Can play y. We delete x, so decrement everything higher than it (which includes y by assumption).
			if not is_next_player_win_packed(pack(y - 1, renumber_dec_hi(their_set, x), renumber_dec_hi(my_set[:i] + my_set[i+1:], x))):
				return True

	return False


def count_first_player_wins_packed(n):
	# Initially the sets are non-empty, which is why the range of mask is pulled in by 1 on each end.
	return sum(1 if is_next_player_win_packed(pack(0, tuple(1+x for x in range(n) if (mask >> x) & 1), tuple(1+x for x in range(n) if not((mask >> x) & 1)))) else 0 for mask in range(1, (1 << n) - 1))



if __name__ == "__main__":
	from time import perf_counter
	for n in range(2, 30):
		start = perf_counter()
		print(n, count_first_player_wins_packed(n), "in", perf_counter() - start, "secs")

results.txt

2 2 in 6.959199890843593e-05 secs
3 5 in 0.0002845499984687194 secs
4 9 in 0.0009316479990957305 secs
5 20 in 0.0026305319988750853 secs
6 41 in 0.01599248500133399 secs
7 78 in 0.0315077459999884 secs
8 162 in 0.0659403999998176 secs
9 314 in 0.10611151400007657 secs
10 630 in 0.13074862199937343 secs
11 1254 in 0.11055787000077544 secs
12 2476 in 0.1055869990013889 secs
13 4971 in 0.13009591400259524 secs
14 9806 in 0.2424693790017045 secs
15 19670 in 0.46308021300137625 secs
16 38960 in 0.9932953210009146 secs
17 77907 in 2.1864521149982465 secs
18 154948 in 4.798909067998466 secs
19 309081 in 11.031438784000784 secs
20 616427 in 24.29949887100156 secs
21 1228104 in 60.07582182600163 secs
22 2452777 in 147.0375621409985 secs
23 4885494 in 397.6994510179975 secs