A game is played by two players on a $9\times 9$ board. At the beginning, one mark is placed on each square. As long as there are two marks on squares sharing a side, the first player picks one such pair of marks, and the second player chooses which mark to remove.
What is the maximum number of marks that the first player can remove, no matter how the second player plays?
The first player can remove $40$ marks by choosing non-overlapping pairs of marks. But it might be possible to remove more if she takes into account the second player's move, e.g. when a mark is removed, in the next turn choose a pair that contains the mark that is not removed from the last turn.