strategy - Dots and Boxes- Best Move in Given Position

In the following game of Dots and Boxes, it is your move.

Your opponent is a computer who will play perfectly. What is the best move, and why?

Answer

Playing the first move in any of the blue spots will let you gain 8 squares with further optimal play, whatever the computer does. On the other hand, playing in any of the red spots will only let you win 6 squares with further optimal play.

Since there were exactly 32 empty spaces, I tried to push the ability of my computer and enumerate the best possible move starting from all $2^{32}$ states. For each state, the code finds the maximum number of squares you can get more than your opponent.

In a few minutes, the code found that the best result is -9. That is, whatever you do, you cannot win the game. Here is the code:

const long long lim=1ll<<32;
char best[lim];
//best[i] is the maximum number of extra squares you can win more than your opponent starting from state i
//A state is represented by a 32-bit bitmask. Edge i (defined below) has been already played iff bit i is 1


int main()
{
  //Number the empty positions from 0 to 31 from top to bottom, breaking ties from left to right
  //Every edge borders at most 2 boxes, and because of the state of the board, there exist at most 2 other edges whose existence is necessary to fill those boxes
  //Essentially, Adding edge i results in a box for you if match[i][0] and match[i][1] were already filled; and another box for you if match[i][2] and match[i][3] were already filled
  //if match[][] is 32 it means that current edge is at the boundary of the box and there is only one neighbouring box
  int match[32][4]={
    { 5, 0,32,32},{ 6, 1,32,32},{ 7, 2,32,32},{ 4, 3,32,32},
    { 3, 4, 8, 4},{ 0, 5,10, 5},{ 1, 6,11, 6},{ 2, 7,12, 7},
    { 4, 8, 9, 8},{ 8, 9,13, 9},{ 5,10,14,17},{ 6,11,15,11},

    { 7,12,15,18},{ 9,13,16,20},{10,17,32,32},{11,15,12,18},
    {19,16,13,20},{10,14,21,22},{23,18,12,15},{16,19,23,19},
    {25,20,13,16},{17,22,32,32},{24,22,17,21},{18,23,19,23},
    {22,24,26,30},{20,25,28,25},{29,26,24,30},{28,27,31,27},
    {25,28,27,28},{26,29,32,32},{24,26,32,32},{27,31,32,32}
  };

  for(long long i=lim-2;i>=0;i--)
  {
    best[i]=-25;

    for(int j=0;j<32;j++)
    {
      //If jth edge has already been played, you cannot play it at this move
      long long cur=(1ll)<      if((i&cur)!=0)continue;

      //Check how many boxes are filled by the current move
      long long mask=i^cur;
      int cnt=0;
      if((mask&(1ll<
      if((mask&(1ll<
      //If no boxes were filled in current move, you pass to opponent and they will do their best move
      //If at least one box was filled, you have to make another move
      char thismove;
      if(cnt==0)thismove=-best[mask];
      else thismove=cnt+best[mask];

      //Does playing this edge do better than any previously seen edges?
      if(thismove>best[i])best[i]=thismove;

    }
  }

  //Now let us consider the moves from the empty board
  //Playing edge j, the best you can do is -best[1ll<  for(int j=0;j<32;j++)
  {
    long long mask=(1ll)<    char thismove=-best[mask];
    printf("%d %d\n",j,(int)thismove);

  }
  printf("Best : %d\n",(int)best[0]);
  return 0;
}