Ошибка утечки памяти в алгоритме min-max

Question

Я совершенно новый для программирования, я только что собрал C месяц назад в абсолютно случайной попытке закодировать собственный шахматный движок (моя цель - создать что-то, что может лучше всего. увлекательный.), поэтому, пожалуйста, постарайтесь быть максимально ясными с вашими ответами и, пожалуйста, просите разъяснения, когда мне не хватает объяснений.

В настоящий момент мой движок может анализировать около 0,5 до 0,8 миллиона позиций в секунду на моем процессоре 1,8 ГГц, любые идеи по этому поводу тоже будут приветствоваться, но в любом случае мне казалось очевидным, что единственный способ сделать мой движок быстрее чтобы попытаться перемещаться в фиксированном порядке, чтобы ошибки были исключены из поиска. Чтобы сделать это, я сменил свой код с передачи int переменных в проходящие int указатели. Моя идея заключалась в том, чтобы просто придерживаться оценки, которая породила его. Код по-прежнему работает, но растет по размеру. Я googled и попробовал некоторые инструменты утечки памяти, но они только говорят мне, где выделенная утечка памяти была выделена, что я уже знаю, но не тогда, когда адрес был потерян.

Я понял, что если я просто отправлю свой код, какой-то парень с опытом может сразу заметить утечку. Теперь, когда я попал в Интернет, ища помощь, я узнал, что мой код логически эквивалентен алгоритму, который существовал десятилетиями под названием минимакс с альфа-бета-обрезкой. Круто.

int evaluate(int *board, int capture) { ... return board evaluation; } 

int *Black(int *board, int depth, int *max, int *min) { 
    if (depth == 0) { 
     temp = malloc(20 * sizeof(int)); //eventually i will store 
    }     
    minlocal = malloc(20 * sizeof(int)); //moves next to the score 
    *minlocal = *min; //this is what i came up with so that min/max   
         //of a higher function call doesn't get changed 
    for (all moves) { 
     if (depth > 0) { 
      temp = whitemove(board, depth - 1, max, minlocal); 
     } else { 
      *temp = evaluate(board, capture); 
     } 
     if (*temp <= *max) { 
      ;free(minlocal); 
      return temp; 
     } 
     if (*temp < *minlocal) { 
      *minlocal = *temp; 
     } 
     if (depth > 0) { 
      free(temp); 
     } 
    } 
    if (depth = 0) { //<====== silly bug! 
     free(temp); 
    } 
    return minlocal; 
} 

int *whitemove(int *board, int depth, int *max, int *min) { 
    temp = malloc(20 * sizeof(int)); 
    maxlocal = malloc(20 * sizeof(int)); 
    *temp = -30000; 
    *maxlocal = *max; 
    for (all moves) { 
     v = blackmove(board, depth - 1, maxlocal, min); 
     if (*v > *temp) { 
      free(temp); 
      temp = v; 
     } else { 
      free(v); 
     } 
     if (*temp > *maxlocal) { 
      *maxlocal = *temp; 
     } 
     if (*temp >= *min) { 
      free(maxlocal); 
      return temp; 
     } 
    } 
    free(maxlocal); 
    return temp; 
} 

Чтение код, который вы, вероятно, заметили, что моя вещь может играть только белый и глубина может быть только четное число, это не имеет значения для меня сейчас.

Насколько я знаю, такой подход, который я принял, может быть абсолютно глупым, но он, кажется, не медленнее, чем раньше, и он должен иметь возможность хранить линии игры вместо простого первого хода. Любое мнение об альтернативах также приветствуется.

Answer 1

Вы, кажется, хорошо освоили навыки программирования на C за очень короткое время.

Тем не менее вам по-прежнему необходимо улучшить свой стиль: презентация очень важно, так как это помогает избежать многих глупых ошибок и делает ваш код более читаемым для обоих других программистов.

Также используйте все предупреждения, которые может произвести компилятор с соответствующими флагами, такими как gcc -Wall -Wextra.

Существует глупая ошибка в конце функции Black:

if (depth = 0) 

Если очевидно, читали

if (depth == 0) 

Это где вы никогда не освободит память.

Возможно, в других местах, где вы теряете дорожку выделенных блоков, а также места, где выделение не требуется, использование локального массива происходит намного быстрее, если вам не нужно возвращать его вызывающему. Передача указателя на локальный массив в качестве целевого массива также может уменьшить объем выделения памяти.

Answer 2

В общем, когда вы пишете код на C, всякий раз, когда вы выделяете память, вам нужно иметь в виду, что вам нужно правильно указать free, используя оператор double equals в вашем сравнении.В нашем случае у вас есть переменная с именем temp, которая будет использовать выделенную память, и при каждой инициализации для whitemove или Black вы выделяете для нее новую память без free ранее выделенной памяти, которая остается выделенной, но у вас больше нет ссылки для этого.

Ответ выше, ниже я дам вам несколько советов:

Это хорошо, что вы изобрели альфа-бета отсечение, не узнав об этом, но вы должны реализовать его элегантно. Например, у вас есть whitemove и функция Black. Почему вы называете Black «черным» вместо того, чтобы быть последовательным и называть его «черным»? Кроме того, когда вы пишете функцию, вам необходимо решить проблему как можно более широко. Как белый ход отличается от черного?

• они пытаются максимизировать оценку по отношению к различным направлениям
• они могут двигаться с различными частями

Теперь, если вы принять это во внимание, вы можете написать две функции, как единый функция. Вам не нужно возвращать большие куски памяти, потому что это не то, что мы хотим знать из шахматного движка. Вам нужно вернуть оценку и двигаться. Вы можете использовать один массив для хранения наилучшего варианта и другого массива для хранения текущего варианта. Всякий раз, когда вы находите лучшую вариацию, то тот, который раньше считался лучшим, затем заменил его. Но избегайте утечек памяти :)