Consejos prácticos para depurar la recurrencia profunda?

Question

Estoy trabajando en un algoritmo de juego de mesa en el que un árbol grande se atraviesa mediante recursión, sin embargo, no se comporta como se esperaba. ¿Cómo manejo esto y qué experimentas con estas situaciones?

Para empeorar las cosas, usa la poda alfa-beta, lo que significa que nunca se visitan partes completas del árbol, y simplemente detiene la recursión cuando se cumplen ciertas condiciones. Tampoco puedo cambiar la profundidad de búsqueda a un número inferior porque, aunque es determinista, el resultado varía según la profundidad de búsqueda y puede comportarse como se espera a una profundidad de búsqueda más baja (y lo hace).

Ahora, no voy a preguntarte "¿dónde está el problema en mi código?" pero estoy buscando consejos generales, herramientas, visualizaciones, cualquier cosa para depurar código como este. Personalmente, estoy desarrollando C#, pero todas y cada una de las herramientas son bienvenidas. Aunque creo que esto puede ser más aplicable a los idiomas imperativos.

Answer 1

registro . Ingrese su código extensivamente. En mi experiencia, el registro es LA solución para este tipo de problemas. cuando es difícil averiguar qué está haciendo su código, iniciar sesión extensamente es una muy buena solución, ya que le permite generar desde su código el estado interno; en realidad no es una solución perfecta, pero por lo que he visto, funciona mejor que con cualquier otro método.

Answer 2

Normalmente probaría estos algoritmos con uno o más conjuntos de datos predefinidos que tienen resultados bien definidos. Por lo general, realizaría varias de estas pruebas en orden creciente de complejidad.

Si insiste en la depuración, a veces es útil para el médico el código con declaraciones que comprueban para un valor dado, para que pueda conectar un punto de interrupción en ese momento y el lugar en el código:

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

Answer 3

Una cosa que he hecho en el pasado es formatear los registros para reflejar la profundidad de recursión. Por lo tanto, puede hacer una nueva sangría para cada recurse u otro de algún otro delimitador. Luego crea un dll de depuración que registra todo lo que necesitas saber sobre cada iteración. Entre los dos, deberías poder leer la ruta de ejecución y con suerte saber qué está mal.

Answer 4

Sé lo doloroso que puede ser esto. En mi trabajo, actualmente estamos trabajando con una aplicación de terceros que básicamente se comporta como una caja negra, por lo que tenemos que idear algunas técnicas de depuración interesantes para ayudarnos a solucionar los problemas.

Cuando estaba tomando un curso de teoría de compilación en la universidad, utilizamos una biblioteca de software para visualizar nuestros árboles; esto también podría ayudarlo, ya que podría ayudarlo a ver cómo se ve el árbol. De hecho, podría compilar una aplicación WinForms/WPF para volcar el contenido de su árbol en un control TreeView; está desordenado, pero hará el trabajo.

Es posible que desee considerar algún tipo de salida de depuración, también. Sé que mencionaste que tu árbol es grande, pero quizás las declaraciones de depuración o las interrupciones en el punto clave durante la ejecución que tienes problemas para visualizar te echarán una mano.

Tenga en cuenta, también, que la depuración inteligente con Visual Studio puede hacer maravillas. Es difícil ver cómo el estado está cambiando en varios descansos, pero Visual Studio 2010 debería ayudar con esto.

Desafortunadamente, no es particularmente fácil ayudarle a depurar sin más información. ¿Has identificado la primera profundidad en la que comienza a romperse? ¿Continúa rompiéndose con mayores profundidades de búsqueda? Es posible que desee evaluar sus casos de trabajo y tratar de determinar cómo es diferente.

Answer 5

Dado que usted dice que el cruce no está funcionando como se esperaba, supongo que tiene alguna idea de dónde pueden salir cosas. Luego inspecciona el código para verificar que no has pasado por alto algo básico.

Después de eso, le sugiero que configure algunas pruebas unitarias simples. Si pasan, entonces continúe agregando pruebas hasta que fallen. Si fallan, reduzca las pruebas hasta que pasen o sean tan simples como puedan. Eso debería ayudarte a identificar los problemas.

Si desea depurar también, le sugiero que emplee puntos de interrupción condicional. Visual Studio le permite modificar puntos de interrupción, para que pueda establecer las condiciones cuando se debe activar el punto de interrupción. Eso puede reducir la cantidad de iteraciones que necesita observar.

Answer 6

Comenzaría por instrumentar la (s) función (es). En cada llamada recursiva, registre las estructuras de datos y cualquier otra información que sea útil para ayudarlo a identificar el problema.

Imprima el volcado junto con el código fuente, luego aléjese de la computadora y realice una agradable sesión de depuración en papel con una taza de café.

Answer 7

Quizás podría convertir la recursividad en una iteración con una pila explícita para los parámetros. La prueba es más fácil de esta manera porque puede registrar valores directamente, acceder a la pila y no tiene que pasar datos/variables en cada autoevaluación o evitar que se salgan del alcance.

Answer 8

Una vez tuve un problema similar cuando desarrollé un algoritmo de IA para jugar un juego de Tetris. Después de probar muchas cosas perdiendo MUCHAS horas leyendo mis propios registros y depurando e ingresando y saliendo de funciones, lo que funcionó para mí fue codificar un visualizador rápido y probar mi código con la entrada FIJA.

Entonces, si el tiempo no es un problema y realmente quiere entender lo que está pasando, obtenga un estado de placa fijo y VEA lo que su programa está haciendo con los datos usando una combinación de registros/salidas de depuración y algún tipo de sus propias herramientas que muestran información sobre cada paso.

Una vez que encuentre un estado de placa que le dé este problema, intente identificar las funciones donde se inicia y luego podrá corregirlo.