Consigli pratici per il debug della ricorsione profonda?

Question

Sto lavorando ad un algoritmo di gioco da tavolo in cui un grande albero viene attraversato usando la ricorsione, tuttavia, non si comporta come previsto. Come gestisco questo e quali sono le tue esperienze con queste situazioni?

Per peggiorare le cose, utilizza la potatura alfa-beta, il che significa che non vengono mai visitate intere parti dell'albero, e che semplicemente interrompe la ricorsione quando vengono soddisfatte determinate condizioni. Non riesco a modificare la profondità di ricerca in un numero inferiore, perché mentre è deterministico, il risultato varia a seconda della profondità della ricerca e può comportarsi come previsto a una profondità di ricerca inferiore (e lo fa).

Ora, non ti chiederò "dov'è il problema nel mio codice?" ma sto cercando suggerimenti generali, strumenti, visualizzazioni, qualsiasi cosa per il codice di debug come questo. Personalmente, sto sviluppando in C#, ma tutti gli strumenti sono ben accetti. Anche se penso che questo possa essere più applicabile alle lingue imperative.

Answer 1

registrazione . Accedi al tuo codice estensivamente. Nella mia esperienza, la registrazione è la soluzione per questi tipi di problemi. quando è difficile capire che cosa stia facendo il tuo codice, registrarlo estesamente è un'ottima soluzione, in quanto ti consente di stampare dal codice all'interno dello stato interno; non è davvero una soluzione perfetta, ma per quanto ho visto, funziona meglio di qualsiasi altro metodo.

Answer 2

Normalmente testare tali algoritmi con uno o più set di dati predefiniti che hanno risultati ben definiti. In genere eseguivo diversi test di questo tipo in ordine crescente di complessità.

Se ti ostini a debug, a volte è utile al medico il codice con dichiarazioni che controllano per un dato valore, in modo da poter collegare un punto di interruzione in quel momento e luogo nel codice:

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

Answer 3

Una cosa che ho fatto in passato è formattare i registri per riflettere la profondità di ricorsione. Quindi puoi fare una nuova indenzione per ogni recurse, o un altro di qualche altro delimitatore. Quindi creare una DLL di debug che registri tutto ciò che è necessario sapere su ogni iterazione. Tra i due, dovresti essere in grado di leggere il percorso di esecuzione e, auspicabilmente, dire cosa non va.

Answer 4

So che dolore può essere. Al mio lavoro, stiamo attualmente lavorando con un'applicazione di terze parti che si comporta fondamentalmente come una scatola nera, quindi dobbiamo escogitare alcune interessanti tecniche di debug per aiutarci a risolvere i problemi.

Quando stavo frequentando un corso di teoria del compilatore al college, abbiamo utilizzato una libreria software per visualizzare i nostri alberi; questo potrebbe aiutarti anche tu, in quanto potrebbe aiutarti a vedere come appare l'albero. In effetti, potresti creare da te un'applicazione WinForms/WPF per scaricare i contenuti dell'albero in un controllo TreeView: è complicato, ma il lavoro verrà completato.

Si potrebbe anche prendere in considerazione una sorta di output di debug. So che hai detto che il tuo albero è grande, ma forse le dichiarazioni di debug o le interruzioni nel punto chiave durante l'esecuzione che hai problemi a visualizzare ti darebbero una mano.

Tenete a mente, anche, che il debugging intelligente con Visual Studio può fare miracoli. È difficile vedere come sta cambiando lo stato tra più interruzioni, ma Visual Studio 2010 dovrebbe effettivamente aiutare con questo.

Sfortunatamente, non è particolarmente facile eseguire il debug senza ulteriori informazioni. Hai identificato la prima profondità alla quale inizia a rompersi? Continua a rompere con profondità di ricerca più elevate? Potresti voler valutare i tuoi casi lavorativi e cercare di determinare come è diverso.

Answer 5

Dato che l'attraversamento non funziona come previsto, presumo che tu abbia un'idea di dove le cose potrebbero andare storte. Quindi ispezionare il codice per verificare di non aver trascurato qualcosa di base.

Successivamente suggerisco di impostare alcuni semplici test di unità. Se passano, quindi continuare ad aggiungere test fino a quando non riescono. Se falliscono, quindi riduci i test fino a quando non passano o sono semplici come possono essere. Questo dovrebbe aiutarti a individuare i problemi.

Se si desidera eseguire il debug, suggerisco di utilizzare i breakpoint condizionali. Visual Studio consente di modificare i punti di interruzione, in modo da poter impostare le condizioni quando deve essere attivato il punto di interruzione. Ciò può ridurre il numero di iterazioni che è necessario osservare.

Answer 6

Vorrei iniziare strumentando le funzioni. Ad ogni registro delle chiamate ricorsive le strutture dei dati e ogni altra informazione che ti sarà utile per aiutarti a identificare il problema.

Stampa il dump insieme al codice sorgente, quindi allontanati dal computer e fai una bella sessione di debug su carta con una tazza di caffè.

Answer 7

Forse potresti convertire la ricorsione in una iterazione con uno stack esplicito per i parametri. Il test è più semplice in questo modo perché è possibile registrare direttamente i valori, accedere allo stack e non dover passare dati/variabili in ogni autovalutazione o impedire che cadano al di fuori dell'ambito.

Answer 8

Una volta ho avuto un problema simile quando stavo sviluppando un algoritmo di intelligenza artificiale per giocare a un gioco di Tetris. Dopo aver provato molte cose a perdere un sacco di ore nel leggere i miei registri e nel debugging e nell'entrare e uscire dalle funzioni, quello che ha funzionato per me è stato quello di codificare un veloce visualizzatore e testare il mio codice con l'input FIXED.

Quindi, se il tempo non è un problema e si vuole veramente capire cosa sta succedendo, ottenere uno stato di scheda fissa e VEDERE cosa sta facendo il programma con i dati usando un mix di log/output di debug e una sorta di i tuoi strumenti che mostrano le informazioni su ogni passaggio.

Una volta trovato uno stato della scheda che ti dà questo problema, prova a puntare la/e funzione/e in cui inizia e poi sarai in grado di risolverlo.