Практические советы по отладке глубокой рекурсии?

Question

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

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

Теперь я не буду спрашивать вас "где проблема в моем коде?" но я ищу общие советы, инструменты, визуализации, что-нибудь для отладки кода, подобного этому. Лично я занимаюсь разработкой на C #, но любые инструменты приветствуются. Хотя я думаю, что это может быть наиболее применимо к императивным языкам.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

Если вы настаиваете на отладке, иногда полезно исправить код с помощью операторов, которые проверяют заданное значение, чтобы вы могли прикрепить точку останова в это время и поместить в код:

  if ( depth = X && item.id = 32) {
     // Breakpoint here
  }

Answer 5

Однажды у меня была похожая проблема, когда я разрабатывал алгоритм ИИ для игры в тетрис. После многих попыток потерять ОЧЕНЬ много часов при чтении моих собственных журналов, отладке и включении и отключении функций, что мне помогло - написать быстрый визуализатор и протестировать мой код с ИСПРАВЛЕННЫМ вводом.

Итак, если время не является проблемой, и вы действительно хотите понять, что происходит, получите фиксированное состояние платы и ПОСМОТРИТЕ, что ваша программа делает с данными, используя комбинацию журналов отладки / вывода и своего рода собственные инструменты, которые показывают информацию о каждом шаге.

Как только вы обнаружите состояние платы, которая создает вам эту проблему, попробуйте точно определить функцию (и), где она начинается, и тогда вы сможете исправить ее.

Answer 6

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

Когда я проходил курс теории компиляции в колледже, мы использовали библиотеку программного обеспечения для визуализации наших деревьев; это также может помочь вам, так как это может помочь вам увидеть, как выглядит дерево. Фактически, вы можете создать приложение WinForms / WPF, чтобы выгрузить содержимое вашего дерева в элемент управления TreeView - это грязно, но оно выполнит свою работу.

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

Помните также, что интеллектуальная отладка с помощью Visual Studio может творить чудеса. Трудно увидеть, как состояние меняется в течение нескольких перерывов, но Visual Studio 2010 действительно должен помочь с этим.

К сожалению, не очень легко помочь вам отладить без дополнительной информации. Вы определили первую глубину, на которой это начинает ломаться? Это продолжает ломаться с более высокими глубинами поиска? Возможно, вы захотите оценить свои рабочие случаи и попытаться определить, чем они отличаются.

Answer 7

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

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

Answer 8

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

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

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