Tree Search Debugging / Diagnose

[rfadden]

I am looking for ideas on the following subject:

Diagnosing subtle problems in Tree Search.

I'm looking at search statistics and I believe I have a problem in my program but I have not yet developed tools for monitoring what is going on during search and looking for problems.

I dread the thought of stepping through tree search in the debugger and I am wondering if other developers have come up with ideas or tools that they use in the case where they suspect the may have a bug in search logic.

My program is not playing Chess, it is a system for playing Chaxx, which is a game very close to Camelot. If you are curious, here is a link to information on the board game of Camelot.

http://en.wikipedia.org/wiki/Camelot_(board_game)


What is the best way to walk through search and find problems? What do you use for technique? Can you tell me of your own experiences, perhaps even mentioning "the hard way" and "the easy way."

Are there any related thoughts that you would like to add?

[Guetti]

My favorite technique is printf().

[Gerd Isenberg]

Introduce all kind of counters as an "inner eye" of the search, as already mentioned:
http://64.68.157.89/forum/viewtopic.php ... 58&t=20562

Implement some trigger by position aka zobrist key. If you enter a node with a position of interest, that is zobristkey == debugzobrist, enable logging all kind of usefull stuff for that node (and probably with an similar trigger all nodes below), for instance alpha, beta, all moves tried with score, bestmove, bestscore etc.. Don't forget to reset the log-trigger if you leave that node.

Also in a debug-version match your incremental update against on the fly computation of a position. Use asserts to check preconditions.

Gerd

[Onno Garms]

Keep the move stack in a (global) variable. At every node, dump the parameters of the search function and the move stack to an XML file. Also dump the reason for stopping the search of a node and the result that is returned.

In XML viewer you can browse the search tree like the directory tree in the Windows Explorer. As the XML dumps can be very large (hundreds of MB) you will need an xml viewer that does not load the whole file into memory but only the parts that are displayed.

[michiguel]

My favorite technique is printf().

I am more sophisticated.

Mine is fprintf(stdlog, ...);

Miguel

[hgm]

I include code in the Search() routine to print alpha, beta, requested depth. And then a list of moves that are searched, with the score that they got, and the best score so far.

All these print statements are conditional, and trigger only in one node of the tree. To select that node, I test for the level in the tree, and the path leading to it from the root.

When I suspect a search problem, I first print that info in the root. From the list of scores I can see which move was scored wrong (i.e. the move actually chosen was too high, or the node I think should have been chosenn in stead too low). Then I rerun the search, now giving output in the node after that move.

By repeating this, I follow the offending branch, to see how it got its score. If I end in a node that was satisfied by a hash hit, I print the hash index and key.

I then rerun the search, activating a conditional print in the hash-store code, that prints the move path from the root if the selected entry is written with the sgiven key. That way I can pick up the tree across hash hits, and continue climbing deeper into the tree from the search that filled that entry, by now putting the path to that node in my condition.

[AndrewShort]

in debug mode I have calls all over search to log certain events to a log file (a text file), where each row of the log is an event with certain parameters I've logged.

Then, I load the huge log file into Excel 2007, which can handle the first 1 million rows of your log file. Then I use Excel to analyze the data, using AutoFilter and other tools in Excel.

I also have Debug.Assert all over the place, which frankly has been more useful to me than the log file...

[Allard Siemelink]

My search has a trace option that dumps the whole search tree into a file.
Each entry contains depth, tt-value, alpha, beta, move and some flags.
I use a separate (Java) utility to view and analyze the tree.

[rfadden]

Keep the move stack in a (global) variable. At every node, dump the parameters of the search function and the move stack to an XML file. Also dump the reason for stopping the search of a node and the result that is returned.

In XML viewer you can browse the search tree like the directory tree in the Windows Explorer. As the XML dumps can be very large (hundreds of MB) you will need an xml viewer that does not load the whole file into memory but only the parts that are displayed.

Amazing! That's excellent.

What is a good way to get started with this use of XML? Also what do you recommend for an XML viewer?

Thanks!

[rfadden]

I include code in the Search() routine to print alpha, beta, requested depth. And then a list of moves that are searched, with the score that they got, and the best score so far.

All these print statements are conditional, and trigger only in one node of the tree. To select that node, I test for the level in the tree, and the path leading to it from the root.

When I suspect a search problem, I first print that info in the root. From the list of scores I can see which move was scored wrong (i.e. the move actually chosen was too high, or the node I think should have been chosenn in stead too low). Then I rerun the search, now giving output in the node after that move.

By repeating this, I follow the offending branch, to see how it got its score. If I end in a node that was satisfied by a hash hit, I print the hash index and key.

I then rerun the search, activating a conditional print in the hash-store code, that prints the move path from the root if the selected entry is written with the sgiven key. That way I can pick up the tree across hash hits, and continue climbing deeper into the tree from the search that filled that entry, by now putting the path to that node in my condition.

This is a great idea! This is far better than anything that I have been contemplating.