Could this be an NP-Complete problem?
The sequence of losing positions can be found in the OEIS, A030193, as is the sequence of positions having Grundy value 1, A224839. The encyclopedia cites several relevant articles. Perhaps some of them discuss non-trivial algorithms for computing the sequence.