My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too. Or just jump to my GitHub repository.

       
#include <iostream>
       
#include <vector>
       
 
       
// uncomment to enable the slower algorithms
       
//#define BRUTEFORCE
       
//#define NIM_SUM

       
 
       
// return true if player to move wins on a board with numSquares (<= 64)

       
bool bruteForce(unsigned int numSquares, unsigned long long occupiedMask = 0)
       
{
       
  // try each position and call yourself recursively
       
  for (unsigned int pos = 0; pos + 1 < numSquares; pos++)
       
  {
       
    // two neighboring bits => 11 binary => 3
       
    const unsigned long long twoSquares = 3ULL << pos;
       
    // both bits empty ?
       
    if ((occupiedMask & twoSquares) == 0)
       
      // occupy both bits, if opponent loses then this is a winning move for the current play
       
      if (!bruteForce(numSquares, occupiedMask | twoSquares))
       
        return true;
       
  }
       
 
       
  // all moves are losing moves
       
  return false;
       
}
       
 
       
// analyze all boards and count how often the first player wins

       
unsigned int nimSum(unsigned int maxSquares)
       
{
       
  // https://oeis.org/A215721
       
  // https://math.stackexchange.com/questions/615242/game-involving-tiling-a-1-by-n-board-with-1-x-2-tiles
       
  // https://blog.plover.com/math/sprague-grundy.html
       
 
       
  unsigned int numLost = 0;
       
 
       
  std::vector<unsigned int> mex(maxSquares + 1, 0);
       
 
       
  // find maximum value created by xoring states
       
  unsigned int maxXor = 1;
       
  while (maxXor < maxSquares)
       
    maxXor <<= 1;
       
 
       
  // track numbers of xored states
       
  std::vector<bool> found(maxXor, false);
       
  for (unsigned int i = 2; i <= maxSquares; i++)
       
  {
       
    // empty squares on the left and right side after the first move
       
    int left  = 0;
       
    int right = i - 2;
       
 
       
    // remember the highest XOR value
       
    unsigned int lastXor = 0;
       
    while (left <= right)
       
    {
       
      auto xored = mex[left] ^ mex[right];
       
      found[xored] = true;
       
 
       
      // remember the largest state (to speed up the clean-up/reset)
       
      if (lastXor < xored)
       
        lastXor = xored;
       
 
       
      // slide one position to the right
       
      left++;
       
      right--;
       
    }
       
 
       
    // find smallest number which was NOT create during one of the XOR steps
       
    unsigned int unused = 0;
       
    while (found[unused])
       
      unused++;
       
 
       
    // finished computing current value
       
    mex[i] = unused;
       
 
       
    // first player only loses when mex[i] == 0
       
    if (mex[i] == 0)
       
    {
       
      numLost++;
       
      if (numLost % 100 == 0)
       
        std::cout << i << "\t" << std::flush;
       
    }
       
 
       
    // erase all values (much faster than creating a new shiny std::vector)
       
    for (unsigned int reset = 0; reset <= lastXor; reset++)
       
      found[reset] = false;
       
  }
       
 
       
  return maxSquares - numLost;
       
}
       
 
       
// super-fast algorithm: implement the pattern observed in nimSum()
       
// nextLostPosition(n) = nextLostPosition(n - 5) + 34
       
// except for the first 14 values { 1, 5, 9, 15, 21, 25, 29, 35, 39, 43, 55, 59, 63 }

       
unsigned int fast(unsigned int maxSquares)
       
{
       
  const auto Precomputed = 13;
       
  const char Initial[Precomputed] = { 1, 5, 9, 15, 21, 25, 29, 35, 39, 43, 55, 59, 63 };
       
 
       
  // store only the most recent 5 values
       
  unsigned int last5[5];
       
 
       
  unsigned int numLost = 0;
       
  while (true)
       
  {
       
    // a(n) = a(n - 5) + 34
       
    auto current = last5[numLost % 5] + 34;
       
    // except for the first 13 values
       
    if (numLost < Precomputed)
       
      current = Initial[numLost];
       
 
       
    // found enough
       
    if (current > maxSquares)
       
      return maxSquares - numLost;
       
 
       
    // store the least recent 5 values
       
    last5[numLost % 5] = current;
       
    numLost++;
       
  }
       
 
       
  return 0; // never reached
       
}
       
 
       
int main()
       
{
       
  unsigned int limit = 1000000;
       
  std::cin >> limit;
       
 
       
  // slowest algorithm
       
#ifdef BRUTEFORCE
       
  unsigned int won = 0;
       
  for (unsigned int n = 1; n <= limit; n++)
       
    if (!bruteForce(n))
       
    {
       
      std::cout << n << " " << std::flush;
       
      won++;
       
    }
       
  std::cout << won << std::endl;
       
#endif
       
 
       
  // idea based on OEIS algorithm
       
#ifdef NIM_SUM
       
  std::cout << nimSum(limit) << std::endl;
       
#endif
       
 
       
  // my fastest algorithm
       
  std::cout << fast  (limit) << std::endl;
       
  return 0;
       
}

This solution contains 26 empty lines, 34 comments and 6 preprocessor commands.