Negamax with alpha-beta pruning bug on depth 0

Question

I'm programming a negamax with alpha-beta pruning. However, it only works if the "BAD" LINE is removed but I don't know why. I've based my code on this pseudo-code. Is it correct? Most implementations call negamax inside a loop (on a separate function for the root node), should I do that? Why?

private static double AlphaBetaWithMemory(Board board, int player,
        int depth,
        int max_depth, double alpha, double beta) {


    double eval = Double.NEGATIVE_INFINITY;
    List<Integer> moves;
    if (depth == max_depth
            || board.gameOver()) {
        double h = board.heuristic(player);
        return h;
    } else {
        movs=board.getMoves();
        for (Integer m : moves) {
            if (depth == 1) {
                double val = -AlphaBetaWithMemory(
                        board.move(m), (player + 1) % 2,
                        depth + 1,
                        max_depth, -beta, -alpha);
                if (val > eval) {
                    best_mov = m;
                    eval = val;
                } else if (val == eval) {
                    if (Math.random() > 0.5) {
                        best_mov = m;
                    }
                }
                alpha = Math.max(alpha, val); //"BAD" LINE
            } else {
                double val = -AlphaBetaWithMemory(
                        board.mover(m), (player + 1) % 2,
                        depth + 1,
                        max_depth, -beta, -alpha);
                eval = Math.max(eval, val);
                alpha = Math.max(alpha, val);
                if (alpha >= beta) {
                    return beta;
                }
            }
        }
   }
   return eval;

Answer 1

The problem was:

else if (val == eval) {
      if (Math.random() > 0.5) {
            best_mov = m;
      }
}

To solve this (and keep the randomness) I just needed to shuffle "movs". I know that sorting "movs" will be more efficient.