Snake and Hunter

_Results.txt

     1   2   3   4   5   6   7   8   9  10  11  12  13  14
  +-------------------------------------------------------
1 |  0   1   2   3   4   5   6   7   8   9  10  11  ...
2 |      3   5   7   9  11  13  15  17  19  21  23  ...
3 |          8  11  14  17  18  23  24  27  28  31  32  35
4 |             15  19  23  25  29  33
5 |                 21  27  28
6 |                     31

MO244949.cs

using System;
using System.Collections.Generic;
using System.Linq;
using BITMASK = System.UInt64;

namespace Sandbox
{
    using STATE = System.ValueTuple<BITMASK, System.Byte, System.Byte>;

    // One way to formalise the snake constraint is to treat internal vertices as deleted.
    // Then the state consists of the set of vertices still in play (equiv. the set of deleted vertices)
    // and the two endpoints of the snake.
    // Since the deleted vertices must be contiguous, there are fewer than the implied N^2 2^N states
    // (where N^2 is the number of vertices).
    class MO244949
    {
        internal static int GameValue(int w, int h)
        {
            BITMASK one = 1;

            STATE state(BITMASK mask, int u, int v) => (mask, (byte)Math.Min(u, v), (byte)Math.Max(u, v));

            IEnumerable<int> neighbours(int xy)
            {
                int x = xy % w;
                int y = xy / w;
                if (x > 0) yield return xy - 1;
                if (x + 1 < w) yield return xy + 1;
                if (y > 0) yield return xy - w;
                if (y + 1 < h) yield return xy + w;
            }

            IEnumerable<STATE> successors(STATE s)
            {
                var (mask, u, v) = s;

                if (mask == 0)
                {
                    int xy = 0;
                    for (int y = 0; y < h; y++)
                    {
                        for (int x = 0; x < w; x++, xy++)
                        {
                            if (x + 1 < w) yield return state((one << xy) | (one << (xy + 1)), xy, xy + 1);
                            if (y + 1 < h) yield return state((one << xy) | (one << (xy + w)), xy, xy + w);
                        }
                    }

                    yield break;
                }

                foreach (var u2 in neighbours(u))
                {
                    if ((mask & (one << u2)) == 0) yield return state(mask | (one << u2), u2, v);
                }
                foreach (var v2 in neighbours(v))
                {
                    if ((mask & (one << v2)) == 0) yield return state(mask | (one << v2), u, v2);
                }
            }

            var layers = new List<ISet<STATE>>();
            layers.Add(new HashSet<STATE> { default });
            while (true)
            {
                var nextLayer = new HashSet<STATE>(layers[layers.Count - 1].SelectMany(successors));
                if (nextLayer.Count == 0) break;
                layers.Add(nextLayer);
            }

            // Evaluate.
            IDictionary<STATE, int> values = new Dictionary<STATE, int>();
            for (int layerIdx = layers.Count - 1; layerIdx >= 0; layerIdx--)
            {
                // Each state in the layer has a value which depends only on the values in the following state
                // and the parity of layerIdx.
                // If layerIdx is even we want to maximise; otherwise we want to minimise.
                var layer = layers[layerIdx];
                var nextValues = new Dictionary<STATE, int>();
                foreach (var s in layer)
                {
                    var successorValues = successors(s).Select(s2 => values[s2]).ToList();
                    if (successorValues.Count == 0) nextValues[s] = s.Item1.PopCount() - 1;
                    else nextValues[s] = (layerIdx & 1) == 1 ? successorValues.Min() : successorValues.Max();
                }

                values = nextValues;
            }

            return values[default];
        }
    }
}

Interesting results! Good start!