Software Engineering

[Onno Garms]

One of the main ingredients of Onno is software engineering. As this
means to design a hole engine, this "idea" cannot easily be
transplanted to other engines.

Look at Fruit. Fruit has fairly clean code. There are functions,
comments, and assertions. This is much better than in most other
source codes. I think that the relative absence of bugs is what made
Fruit strong. Therefore, Fabien has proven that the software
engineering approach works.

However, for me there was still not enough of software engineering in
Fruit. There are no unit tests. There are macros rather then enums,
classes, or inline functions. There are global variables. There is a
longjump. I didn't want to work that way.

My approach included:

• - C++ rather than Fruit's C+
  - abstract interfaces
  - assertions
  - unit tests
  - various log files, namely
  • - an EventLogger for differential tests (dump actions to determine
    exactly where search goes differently from the previous version)
    - an XML dump of the search tree (usable for small trees only,
    viewable in an XML viewer similar to the directory tree in a file
    browser)
    - statistics on node types and children

I love structuring and ordering, I love software design. So I enjoyed
my approach.

My approach has proven to work but I cannot calculate how much of
Onno's strength comes from it. However my approach has also proven to
be too slow to keep pace with the rapid improvement of engines. At
least for a single part time programmer.

To emphasize the importance of software engineering, let us have a
look at Toga. Fabian gave a fairly well structured code as a starting
base (Fruit). Thomas made it stronger, but he also introduced several
bugs. With proper software engineering these bugs would have been
detected and Toga would have been stronger.


Bug 1 (in Toga 1.2.1a):

sort.cpp, line 951 computes the index in a wrong way.

Code: Select all

index = PIECE_TO_12(board->square[MOVE_FROM(move)]) * 64
      + SQUARE_TO_64(MOVE_FROM(move)) * 64
      + SQUARE_TO_64(MOVE_TO(move));

The first summand should be multiplied by 4096 rather then 64.

This kind of bug would never have passed unit testing.

Impact on playing strength: None at all! I tried fixing the bug, but
the strength is unchanged. This might indicate that the whole
heuristic is not worth much.


Bug 2:

search_full.cpp, line 796

Code: Select all

if (best_value == ValueNone) { // no legal move
      if (in_check) {
         ASSERT(board_is_mate(board));
         return VALUE_MATE(height);
      } else {
         ASSERT(board_is_stalemate(board));
         return ValueDraw;
      }
   }

With the introduction of windowing, the comment "no legal move" is no
longer true. It might be possible that all moves have been pruned. In
this case, it is a very bad idea to return VALUE_MATE or ValueDraw.

If Toga had been run with assertions enabled, this bug would easily
have been uncovered. It seems nobody in the open source community ever
did this! Here you can learn from commercial software developers.

Impact on playing strength: Considerable.

Bugfix: insert

Code: Select all

      if (move_found) { // all moves pruned
         return full_quiescence(board,old_alpha,beta,0,height,pv);
      }

Over the years, things got worse. Too many cooks have spoilt the
broth. Toga is almost not maintainable now.

[bhlangonijr]

My approach included:

• - C++ rather than Fruit's C+
  - abstract interfaces
  - assertions
  - unit tests
  - various log files, namely
  • - an EventLogger for differential tests (dump actions to determine
    exactly where search goes differently from the previous version)
    - an XML dump of the search tree (usable for small trees only,
    viewable in an XML viewer similar to the directory tree in a file
    browser)
    - statistics on node types and children

Can you elaborate more on why you think the use of abstract interfaces are so important for a chess program? A chess engine specifically.
In earlier versions of my program I had an abstract interface for the search class. I was thinking about the possibility of including in the future many concrete classes using different approaches, such MTD(f), PVS, Monte Carlo, etc. The hash table class and the evaluator class were also eligible for applying such patterns.
As the time has passed I came to conclusion that a very sophisticate software engineering applied for a chess engine is an over-refinement that is not worth the time you spend with it. IMO the chess engine is a very simple program with a lot of rules. It doesn't require a very fancy software design.
Also, I personally think that assertions will be gradually replaced by clever unit testing frameworks in modern software engineering. And I'd include in your nice list of good practices:

- Don't use Goto;

It is sad when a original chess author gives up of his program.

Regards and thanks for sharing your very nice ideas.

[Onno Garms]

Can you elaborate more on why you think the use of abstract interfaces are so important for a chess program? A chess engine specifically.
In earlier versions of my program I had an abstract interface for the search class. I was thinking about the possibility of including in the future many concrete classes using different approaches, such MTD(f), PVS, Monte Carlo, etc. The hash table class and the evaluator class were also eligible for applying such patterns.

You should not use abstract interfaces for everything. When I started, I came with an abstract interface of Search, having one implementation AlphaBeta for real use and another implementation Minmax for testing. That was not a good idea, Minmax is fairly useless. You need just one implementation and there is no reason to separate the interface from the implementation. Now I have search classes (one for root node and one for other nodes) without abstract interfaces.

An example of a useful abstract interface is the class Callback. The search just gets the interface Callback. In production, an object of the implementation UciCallback is passed and will print search information in UCI syntax. In another situation I just want to dump statistics on the time to reach a fixed depth. There I have another implementation of Callback that dumps this statistics. In the search there is absolutely no change required. Without the abstract interface of Callback, I would either have to hack the statistics dump into the search or to parse the UCI output. Both are not desirable.

Another example is the UCI parser. I have one class Uci that just parses the strings and calls pure virtual member functions such as Uci::go(). The class Uci can be tested independent of the rest of the engine. My main implementation, UciWaiting only has to care about calling Onno's search functions.

As the time has passed I came to conclusion that a very sophisticate software engineering applied for a chess engine is an over-refinement that is not worth the time you spend with it.

Maybe you are right. In deed this approach is too slow for today's rapid development, so I gave up Onno now.

IMO the chess engine is a very simple program with a lot of rules. It doesn't require a very fancy software design.

Sometimes a testable design helps. Suppose you have changed something and think it will not change the search except for a slight speedup. You run differential tests and see it did change the search. Dump some log and see where it changed the search. Analyze this to find your mistake.

Also, I personally think that assertions will be gradually replaced by clever unit testing frameworks in modern software engineering.

I prefer using both assertions and unit testing.

And I'd include in your nice list of good practices:
- Don't use Goto;

In principle I agree with you and I rarely use gotos.

However it is useful to have the search stack accessible which is not possible with a pure recursive search. One option is recursive search without function parameters, but I decided to use a fully iterative search. It is not so easy to write readable code for iterative search. Several people have posted macro based solutions. Compared to those I find my goto based solution very readable.

I just think of the gotos this way:

The block

Code: Select all

  child->alpha = ...
  child->beta = ...
  child->ret_addr = Label::my_label;
  ...
  goto recurse;
my_label:

can be replaced in my mind by a recursive call. I know that eventually the program will jump back to my_label and have the result in child->pv.

Once used to this notation, using gotos this way is as easy as using recursive calls.