Theoretical background
For a game like this, there is only one theoretical idea from Combinatorial Game Theory we really need: The concept of "N-positions" and "P-positions". An N-position is a state where the Next player to move has a winning strategy. And a P-position is a state where instead the Previous player to move has one.
Two key facts:
- Note that at the end of the game when there are no moves available, the previous player had a winning strategy of "make the move that ends the game like this", so it's a P-position.
- In general, a position is a P-position when all of the moves are to N-positions. That is, any move (if one exists) would hand your opponent a win if they play perfectly. And, otherwise, the position is an N-position since a good move to make would be a move to a P-position.
If you prefer video, this idea is discussed at P-positions and N-positions: Introduction to Combinatorial Game Theory #2 by Knop's Course on YouTube.
Solution
(I will use "take" to mean "strike out".)
This game is probably just simple enough that it could reasonably be solved by hand with a decent amount of paper and time - just write out some branches of play, building up which states are N-positions or P-positions from below, until a promising line of play is found. But I used a program very similar to the Python mentioned below to analyze it.
The game is a win for the first player, who can win by taking any pair, or one of the triples $(1,6,8)$ or $(2,6,7)$.
It suffices to show that one of those moves is part of a winning strategy. For simplicity, consider the move of taking $(1,6,8)$, leaving $(2,3,4,5,7,9,10,11,12,13,14)$. Then there are seven things the opponent can take: $(2,13)$, $(3,12)$, $(4,11)$, $(5,10)$, $(2,3,10)$, $(2,4,9)$, and $(3,5,7)$.
- If they take $(2,13)$, the winning moves are $(3,12)$ and $(5,10)$. Either way, after one of those moves the remaining two moves are independent: $(4,11)$ and whichever is remaining of $(3,12)$ and $(5,10)$.
- If they take $(3,12)$ or $(5,10)$ one winning move is $(2,13)$ by the above. (Aside: $(4,11)$ is also a winning move.)
- If they take $(2,3,10)$, the only available move is $(4,11)$, leaving $(5,7,9,12,13,14)$, from which there are no more moves.
- If they take $(4,11)$, one winning move is $(2,3,10)$ by the above. (Aside: $(3,12)$ and $(5,10)$ are also winning moves.)
- If they take $(2,4,9)$ or $(3,5,7)$, the only winning move it to take the other of those triples, leaving $(10,\ldots,14)$ from which there are no more moves.
Python code
Since you mentioned Python, we can turn this idea of N and P positions into Python code. If moves
gives a list of reachable states starting from the state s
, then we can use #2 above to test if a state is an N-position:
def isNPosition(s): return not(all(map(isNPosition,moves(s))))
One way to define moves
is to use a set of numbers (so that striking out is easy), as in:
import itertools
def moves(s): return [s-set(x)\
for x in list(itertools.combinations(s,2))+list(itertools.combinations(s,3))\
if sum(x)==15]
Since the game is so short with not too much branching, this can evaluate whether any state (including the starting state) is an N-position very quickly.
import itertools
def moves(s): return [s-set(x)\
for x in list(itertools.combinations(s,2))+list(itertools.combinations(s,3))\
if sum(x)==15]
def isNPosition(s): return not(all(map(isNPosition,moves(s))))
print("The game is a win for the first player:",isNPosition(set(range(1,15))))
print("(1,6,8) would be a bad first move:",isNPosition(set(range(1,15))-set([1,6,8])))
#list which first moves are good/bad with "False"/"True"
for x in map(lambda s : ("The first move of:"\
,sorted(list(set(range(1,15))-s)),\
"leads to an N-position?",\
isNPosition(s)),\
moves(set(range(1,15)))): print(x)
Try it online!