Valgrind printing error when there isn't one?

Question

I'm building a chess program in C. I ran valgrind on the program and got:

==6683== Conditional jump or move depends on uninitialised value(s)
==6683==    at 0x405F23: getBestMove (MiniMax.c:318)
==6683==    by 0x403933: computerTurn (Chess.c:864)
==6683==    by 0x402947: runGame (Chess.c:579)
==6683==    by 0x403F66: main (Chess.c:981)



move_t* getBestMove(game_t game, int player, unsigned int depth)
{
  move_t *cur = NULL, *best = NULL;
  double alpha = INT_MIN, score = 0;
  firstMove = NULL;

  cur = getAllMoves(game, player);

  firstMove = 0;
  while (cur != NULL)
  {
    game_t copy;
    copyGame(game, &copy);
    makeMove(&copy, *cur);
    //root->game = copy;
    firstMove = NULL;
    score = -alphaBetaMax(-INT_MAX, -alpha, depth - 1, copy, !player);
    freeGame(copy);

    if (board_count > MAX_BOARDS)
      break;

    if (score > alpha) // line 318
    { 
      alpha = score;

      if (best != NULL)
      {
        best->next = NULL;

        free(best);
      }

      best = copyMove(*cur);
    }

    cur = cur->next;
  }

  freeMoves();

  if (board_count > MAX_BOARDS)
  {
    free(best);

    return 0;
  }

  return best;    
}

What I don't get is that both of the variables in the if (score, alpha) are initilized to (0,INT_MIN) respectively. So why is valgrind printing this error? Any help would be much appreciated!

Thanks for all the help so far, switching to DBL_MAX didn't affect the problem. Here's the code for alphaBetaMax:

static double alphaBetaMax(double alpha, double beta, int depthleft,
    game_t game, bool player)
{
  move_t *cur;
  double score = 0;
  bool did_move = false;

  cur = getAllMoves(game, player); // firstMove is a global list of all moves for current player
  firstMove = 0;

  while (cur != NULL)
  {
    game_t copy;
    if (depthleft <= 0 && !isCapture(game, cur))
    {
      cur = cur->next;
      continue;
    }
    did_move = true;
    copyGame(game, &copy);
    makeMove(&copy, *cur);
    firstMove = NULL;

    score = -alphaBetaMax(-beta, -alpha, depthleft - 1, copy, !player);

    if (board_count > MAX_BOARDS)
      break;

    freeGame(copy);

    if (score > alpha) // ln 278
      alpha = score;

    if (beta <= alpha) // ln 281
      break;

    cur = cur->next;
  }

  freeMoves();

  if (!did_move)
    alpha = evaluate(game) * (player * 2 - 1);

  return alpha;
}

Valgrind prints the same message regarding lines 278 and 281, which is hard for me to see why. Thanks for all the help!

Answer 1

You can get this error if alphaBetaMax returns a value that is dependent on uninitialized data.

E.g.:

int uninitialized;

int badStuff( bool val )
{
    if ( val ) return uninitialized;
    return 0;
}

void bestMove()
{
   int alpha = 5;
   int score = badStuff( getRandomBoolean() ); // valgrind sez: "this is a-ok."

   if ( alpha > score )   // valgrind sez: "but now you're playing with fire."
       doStuff();
}

Answer 2

Without seeing all the relevant parts of the code base, it's impossible to nail down exactly where the issue is. Chances are that the issue is related to your copyGame function which doesn't initialise game in all cases.

In order to illustrate how this error is possible consider the code snippet below which provides alternative implementations to the functions in use:

void copyGame(int input, int *output) {
    /* Not initialising output as expected, causes valgrind uninitialised value
     * error.
     */
}


int alphaBetaMax(int x, int y) {
    return y + x;
}


int main(int argc, const char* argv[]) {

    int game;
    int score;

    copyGame(10, &game);
    score = alphaBetaMax(2, game);

    if (score >= 15)   /* Line 22 */
        return 0;

    return 1;
}

This results in the following output from valgrind:

==29812== Conditional jump or move depends on uninitialised value(s)
==29812==    at 0x400503: main (main.c:22)

As you can see, the real error is that copyGame doesn't modify its output variable, resulting in game being used by the alphaBetaMax function with an uninitialised state.

If you consider all code paths you're likely to find a case where you have the same issue with game being uninitialised.

Answer 3

Valgrind has a commandline option --track-origins=yes which, when set, will tell you the source of the uninitialized value. As others have said, the likely cause in your case is somewhere in the alphaBetaMax() function.

When set to yes, Memcheck keeps track of the origins of all uninitialised values. Then, when an uninitialised value error is reported, Memcheck will try to show the origin of the value.

...

Performance overhead: origin tracking is expensive. It halves Memcheck's speed and increases memory use by a minimum of 100MB, and possibly more. Nevertheless it can drastically reduce the effort required to identify the root cause of uninitialised value errors, and so is often a programmer productivity win, despite running more slowly.