[computer-go] Remarks on the Indigo-Paper

[Don Dailey]

Chrilly,

I use very much the same testing techniques.  When I'm experimenting it
is very natural to write the "easy" version of some routine - a version
that is not efficient but is easy to write without bugs.   Then I check
it out - see if it is interesting or good.  If I like it, then it get's
re-written with much more efficient code.   In this case it's not a
different programming language, but at least the routine is
significantly different and one version is more likely to be correct.

In chess I always did the symmetrical testing too.   That catches lot's
of problems.

Sometimes in alpha/beta searching you can compare search results.  This
was a real help when I did computer chess.   I always made sure I had a
deterministic mode in my programs - a mode where you could count on a
certain exact result (node count, score, move)  This was useful when you
were optimizing the program and not changing the evaluation for
instance.   I had switches where I could turn off those things that
could change this.    If you are working on move ordering then you must
turn off hash tables for initial debugging for instance.

It was very common for us, when I was working with Larry Kaufman, to
find a bug in the program and then go through the standard sequence of
turning one thing off after another until the bug went away - and we
usually had our culprit.  

Of course every programmer knows it's usually one of the last things you
worked on that is causing the problem - even if it doesn't seem likely.

As I have gotten older I code more defensively.   I tend to have fewer
bugs and when I discover one I usually know right away where it is.  So
it has made me a little lazier about testing.   I almost never spend
more than a few minutes finding a problem.

One example of defensive coding is to avoid malloc when writing c code.
I used to use it a lot - but it almost always can be avoided and it's a
performance drag.   When I do use it, I am very careful and paranoid.  I
isolate it to very simple high level things - like setting initial hash
table size, etc.

- Don

On Mon, 2006-06-19 at 07:26 +0200, Chrilly wrote:
> >
> > However I do have two problems with classical unit testing applied to go:
> >
> > 1. Getting the unit tests to pass is sometimes too hard. E.g. fixing an
> > algorithm to help it solve one life and death problem sometimes breaks
> > another. Is this a regression that should be reverted, or is it an
> > improvement. So it turns into measuring pass/fail rate across a large
> > test suite, but then it is harder to see genuine regressions due to
> > introducing a bug; it is also slower (see problem 2)
> >
> > 2. Unit tests are supposed to run in seconds; some of mine take minutes,
> > and I usually disable those that take even longer, defeating the purpose
> > of having them.
> >
> I think this is a very difficult problem, because one needs for many tests 
> the whole system. One possibility of testing is to implement the same 
> functionality twice. In different programming languages and/ or with quite 
> different implemention methods. E.g. I have in Hydra a C-simulator for the 
> FPGA-engine. The simulator and the hardware must aggree. If not, something 
> is wrong. To my surprise its often the simulator. I have implemented now a 
> general pattern-matcher along the ideas of Mark Boon. But after some 
> comments of David I decided to implement move-generation matching as 
> hard-coded switch-statements. I think this is a good way to test both pieces 
> of software. For the ladder routine I have also a fast and a slow version.
> In case of the Hydra-Hardware writing a simulator is general practice. In 
> software one has. the problem that C++ and Java are too close. One would 
> automatically write both programms in a very similar way and would make in 
> both versions the same errors.
> This does not help to prevent algorithmic/design errors. But it catches a 
> lot of  simple coding bugs.
> 
> In the general matcher I had an interesting bug: The board structure was 
> defined as:
> typedef struct {
>     Uint8 wAdjacent;
>     Uint8 bAdjacent;
> } Adjacent_t;
> 
> typedef union {
>     Uint32 Board32;
>     struct {
>         Uint8 Stone;
>         Adjacent_t Adjacent;
>         Uint8         LibsAdjacent;
>     };
> };
> 
> To speed things up the matcher compared only the Board32 variable and not 
> the individual fields. But this failed, because the compiler put the 16-Bit 
> Adjacent_t structure on an even address. And increased then the whole 
> structure to 8 Bytes. So Board32 was not "covering" all fields. Rearranging 
> the elements and putting Adjacent_t on the first place solve the problem.
> Generally this union{} technique is a bad programming habit if mine. Its 
> Assembler programming in C and I have already introduced a lot of errors 
> with these tricks.  Besides this the code is not portable, because it uses 
> the Microsoft language extension of unnamed-structs. But it saves typing.
> 
> 
> Another way of testing is to select bug statistics. E.g. the bug-hotspot in 
> chess is enpassant. An enpassant bug has even become an industry-standard in 
> the old ChessBase database format. To save space the moves were stored as 
> the move-numbers of a simple move-generator. This generator could make an 
> enpassant move from the a to the h-line. Every version of the Deep Blue 
> hardware chip had an enpassant error. Interestingly this knowledge does not 
> reduce the bugs in new programms. But it helps to concentrate the testing 
> process on these hot areas. I know that the union-techniques above is error 
> prone and put test-statements about the assumption in the code. In this case 
> an "ASSERT()" does not help, because the Debug and the fully-optimized code 
> can have different padding-rules.
> Another frequent bug is the "white-black-bug". One writes first some logic 
> for white and then the same for black. This is done by "copy and paste" and 
> then some replacement statements. Its common to overlook some changes and to 
> ask also for black the white fact. One way to test this is to setup mirror 
> positions and to look, if the result is the same.
> 
> Chrilly
> 
> 
> 
> 
> 
> > Darren
> > _______________________________________________
> > computer-go mailing list
> > computer-go at computer-go.org
> > http://www.computer-go.org/mailman/listinfo/computer-go/
> > 
> 
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/