“If the search algorithm is really 20 lines of code, then why is my search routine over 20 pages of code?”
M. Newborn, 1985
Introduction
The above statement (which I found in Jonathan Schaeffer's Heuristic Search lecture notes) is equally true today as it was 28 years ago. E.g the Stockfish recursive search() function is almost 600 lines of code. Of course, computer screens also have greatly expanded beyond the 24 lines per page of the 1980s, but 600 lines is still a very long function to keep inside a human's working memory. The answer to this engineering paradox can also be found in the lecture notes mentioned above: efficient search is all about the search enhancements. E.g. the Stockfish code contains no less than 20 documented search enhancements. On this forum, Bert Tuyt is keeping us all informed on the subtle interactions between the various enhancements, and of the increase in playing strength each of these enhancements can imply.
The Idea
With my Draughts and Checkers Template Library, I strive to keep functions ultra-short in order to adhere to the Single Responsibility Principle: a function should do only one thing, and do it well. With the rules and board dependent position and a move generator, the goal of short and efficient functions has been more or less met (or so I hope!). But how can a state-of-the-art but very long search function (such as the one in Stockfish) be refactored to be only 20 lines at the top level? I don't claim I have found a magic bullet, but below I want to explore a direction that was inspired by the Boost.Graph library (BGL). The BGL defines several skeletons for recursive search algorithms that take a so-called Visitor class as a parameter. Depending on the recursive algorithm, the Visitor class defines so-called "hook" functions that allow for user-defined code to be executed on specific customization points inside the recursive skeleton.
Prototype
Since a state-of-the-art negamax search is complicated beast, I prototyped the idea on the familiar perft() function, see the code below:
template<typename Position, typename Enhancements>
NodeCount perft(Position const& p, int depth, int ply, Enhancements e)
{
e.update_statistics(ply); // (0)
auto const find = e.find(p, depth); // (1)
if (find.first) return find.second;
NodeCount nodes = 0;
auto const terminal = e.terminal(p, depth); // (2)
if (terminal.first) { nodes = terminal.second; } else {
Arena<Move> a;
auto const moves = successor::generate(p, a);
for (auto const& m: moves)
nodes += perft(successor::make_copy(p, m), depth - 1, ply + 1, e);
}
e.insert(p, nodes, depth); // (3)
return nodes;
}
Even for those not familiar with C++ template syntax, this code should look familiar as the perft skeleton. Apart from taking a Position, depth and ply level, it is also parameterized on an Enhancements class (which plays the part of Visitor of the BGL). Inside the perft() function, there are 4 points of customization. At each point, the creator of an Enhancements class can define what code should be executed. The only convention is that each but the last "hook" function returns a struct containing a bool (member "first") and a node count (member "second"). This allows the perft() skeleton to implement flow control conditional on each of the customization points.
The default perft() implementation does not use any data structure except for some statistics logging, and an implementation looks like follows
The essential code here is the `terminal()` function which returns 1 if the depth==0 condition has been met. The hash table code has been disabled for the regular perft() algorithm. The BGL documentation states: "since the visitor parameter is passed by value, if your visitor contains state then any changes to the state during the algorithm will be made to a copy of the visitor object, not the visitor object passed in. Therefore you may want the visitor to hold this state by pointer or reference." I have implemented this suggestion by letting the Enhancements class take a handle to the data structure. Of course, this is only a prototype and in real code I would strive for better encapsulation and define forwarding wrapper functions.
An enhanced algorithm such as the one used by Aart Bik in his perft(28) project would do hashing and bulk counting. This can be realized through the following code:
This code stops at depth==1 and returns the number of moves. It also looks up the position in a hash table and returns the number of stored nodes if and only if the stored depth matches the current depth.
Results
I have tested this code with my DCTL library. There is 0% runtime overhead compared to my old perft() implementations: all the passing around of enhancement objects with pointers to their data and the flow control by structs of booleans and node counts is completey optimized away by the compiler (gcc 4.7.2).
Discussion.
This reformulation of perft() is only an exercise. The skeleton is exactly 20 lines of code (OK, I reformatted it a little...). Changing the perft() implementation only requires that the calling code uses " hash_tag" instead of "default_tag". Of course, this is only a prototype and no real gain is obtained, apart from the fun of playing with new abstractions.
Outlook
I am currently experimenting with reformulating the negamax search() as a skeleton with around 7 different customization points. At each point, a hook function is called that calls 2-5 different search enhancements. E.g. after the find() hook (that not only does TT lookup but also can handle opening book, endgame databases or repetitions) and before move generation, Stockfish has 4 enhancements (razoring, static null move pruning, dynamic null move pruning, probcut). Just after move generation, another family of 3 search enhancements can be called (ETC, singular extensions, multi-cut). Grouping these related functions together and parameterizing the search on a single Enhancement class, allows for easy parameterized testing. Each engine version takes its own Enhancements class. I hope this will allow me to better manage the complexity of creating a state-of-the-art search algorithm for draughts engines.
Last edited by Rein Halbersma on Wed Jan 23, 2013 10:49, edited 1 time in total.
Although I also program in c++, I guess i partly still live in the Fortran world.....
Is there a good book you could recommend with all these principles (templates , ... ) ?
BertTuyt wrote:Rein, I envy your c++ craftsmanship !
Although I also program in c++, I guess i partly still live in the Fortran world.....
Is there a good book you could recommend with all these principles (templates , ... ) ?
Bert
Hi Bert,
There are several good books about templates, but the subject is very large and technical, so I made some selection and reading order to get the smoothest possible learning experience.
Chapter 13 (27 pages) of Stroustrup's book The C++ Programming Language. This summarizes what class and function templates can do, how the syntax works, and how you can customize your code using templates. Note that a 4th edition is scheduled to come out in Q2 of 2013, with all the new features of the C++11 Standard, so you might get a cheap copy of the 3rd edition somewhere and buy the new one later this year.
Part I (Chapters 2-7, 97 pages) of Vandevoorde's & Josuttis's book C++ Templates The Complete Guide. This is explains the basics of how to specialize class templates, how to overload function templates and how to organize your source code. It should cover everything you are likely to encounter with basic usage of templates. This is a really pedagogical book with very clear examples.
Chapters 1-2 (39 pages) of Alexandrescu's book Modern C++ Design. Chapter 1 is about template design strategies and how to mix traditional inheritance based polymorphism with templates. C++ templates are not just a convenient tool for writing generic code, but also provide a compile-time mini-language of their own. Chapter 2 introduces some basic template techniques for such compile-time computations (aka template meta-programming) that were completely new in 2001, but have now been (almost) completely absorbed in the new C++ Standard.
