The grand design

[SuneF]

My Node object knows internally how to generate a move list, but do not know what to do with it. I store Evaluator object inside Node object. Node evaluates itself using static evaluator or various recursive search evaluators (pv_search, q_search, etc.).

Node can copy own evaluator with different parameters or can create a different evaluator when it needed to evaluate recursively its child nodes.

Code: Select all

class Node {
    //color and tree independent position information
    PieceLayout my; //side to move pieces
    PieceLayout op;

    class Search {
         typedef bool (*Evaluator) (Node&);
         Evaluator evaluator;
         Ply depth;
         Eval alpha, beta;
     } evaluator;
};

Ah sounds like you have merged what I referred to respectively as Node and Board.

May I ask what you have done with the input? How do you stop the search?
For instance how does one poll for input in a node that is not supposed to know anything about I/O?
I can only see 3 possible solutions. Make threaded input and have the thread set a stopflag or give the nodes a reference to some protocol-intelligent instance or finally make a "global" somethingObject.
I don't like any of them, they are all ugly for various reasons. I guess a threaded design is the most clean from a coupling and cohesion perspective, but also by far the most difficult and errorprone I'm sure.

[jhaglund]

I wonder how many have considered the design of their engine from an object orientated perspective.

In particular:
1: What classes do you use and what is their resposibility?
2: How are they coupled?
3: What patterns are you using?
4: When do you trade design for speed?

I'm kinda struggling a bit myself to find the right balance and design.

For me, I like to separate everything, and call as much as I can using globals. This way, for me, seems to be better to manage the code, and definitely easier to add code without having a total re-write.

I do not annotate anything, because I feel if I cannot remember what the code is for or how it works, I shouldn't be writing it.

A GM thinks 4-8 moves per second and does wonders. A trade for design over speed is what I shoot for first.

What's being overlooked is all the conditions your first move should have...

[Gerd Isenberg]

I wonder how many have considered the design of their engine from an object orientated perspective.

In particular:
1: What classes do you use and what is their resposibility?
2: How are they coupled?
3: What patterns are you using?
4: When do you trade design for speed?

I'm kinda struggling a bit myself to find the right balance and design.

I've designed a ChessGame class to encapsulate the state of the game.
There is an abstract Protocol class, which the ChessGame knows about.
The Protocol is specialized into WinboardProtocol and UciProtocol classes - of which the ChessGame doesn't know about.
The idea here is to isolate all protocol stuff from the main system, making it easier to implement new protocols without changing so much as a line in the very messy game/search stuff.

Okay that is basic I guess.
Then I currently have Board, Node and Tree classes.
The board is for holding the current state.
Node is like an extended Board class, it contains Undo information, move lists and so on.
The Tree is a Node container for holding the entire search info.

The main problem here is that these classes get fat, real fat real quick.
Can they be broken up in a natural way?

Hi Sune,

I have a similar design. Since my nodes are somehow distributed, I use embedded node subclasses, that cover incremental updates, stuff on the stack, and data generated from scratch once per node with limited lifetime.

A former mistake of mine seemed to derivate tree from node, to expand it with the node container. In CTree, I often had bugs like (this->)foo versus node.foo issues, the compiler could not catch.

Another design issue, is which class should be resposible for driving the search()?

Clearly, the protocol stuff belongs to seperate classes. Since Xboard and UCI require almost disjoint game state handling, a thin interface between a Game Controller model and the "dumb" tree-searcher(s) would be appropriate.

The search must call the Evaluation(), it must do pruning and extensions, so this would make Board a candidate.
But how can the Board know about "the next ply", the Tree knows about the plies, so this would make Tree a candidate.
Finally, at every node we have lots of parameters, alpha, beta, depth etc.. These are natually stored in a Node or locally declared.
This would make Node a candidate.
My favorite is the Node class, primarily for notation reasons, though the nodes would have to be linked or know about the Tree to go to the next node.

One design decision I've made, is that I accept "global" tables, ie. data floating in a namespace.
My reasoning is, that the notation would get awkward if everything had to get prefixed by some named object or as static members of a class. Not to mention it would probably be slower.

There are many more issues of course, not to mention what is a good parallel design?

Yes, so far I use multiple instances of tree searchers, where a specialized "search" method creates a thread ...

Cheers,
Gerd

[michiguel]

My Node object knows internally how to generate a move list, but do not know what to do with it. I store Evaluator object inside Node object. Node evaluates itself using static evaluator or various recursive search evaluators (pv_search, q_search, etc.).

Node can copy own evaluator with different parameters or can create a different evaluator when it needed to evaluate recursively its child nodes.

Code: Select all

class Node {
    //color and tree independent position information
    PieceLayout my; //side to move pieces
    PieceLayout op;

    class Search {
         typedef bool (*Evaluator) (Node&);
         Evaluator evaluator;
         Ply depth;
         Eval alpha, beta;
     } evaluator;
};

Ah sounds like you have merged what I referred to respectively as Node and Board.

May I ask what you have done with the input? How do you stop the search?
For instance how does one poll for input in a node that is not supposed to know anything about I/O?
I can only see 3 possible solutions. Make threaded input and have the thread set a stopflag or give the nodes a reference to some protocol-intelligent instance or finally make a "global" somethingObject.
I don't like any of them, they are all ugly for various reasons. I guess a threaded design is the most clean from a coupling and cohesion perspective, but also by far the most difficult and errorprone I'm sure.

Why a threaded design is more error prone and difficult? I always had an input thread and a search thread and I was happy with it. I am not saying it never game me problems, but I do not think it gave me more that I would have had with any other approach (I guess....).

Miguel

[SuneF]

I have a similar design. Since my nodes are somehow distributed, I use embedded node subclasses, that cover incremental updates, stuff on the stack, and data generated from scratch once per node with limited lifetime.

A former mistake of mine seemed to derivate tree from node, to expand it with the node container. In CTree, I often had bugs like (this->)foo versus node.foo issues, the compiler could not catch.

It'd be interesting to see some design class diagrams
Here is a simplified version of mine. It's not fully connected yet as there are still things, especially in the threading area, that I have no idea how to connect with.

http://www.computerskak.dk/Design.jpg

I suppose the thread and tree stuff is related in some way.

Also I need to figure out a way to poll for input. It's not obvious how to do that since a Node is not allowed to call back up the hierarchy into Protocol stuff. I don't see any other solution than to go threaded.

[SuneF]

Why a threaded design is more error prone and difficult? I always had an input thread and a search thread and I was happy with it. I am not saying it never game me problems, but I do not think it gave me more that I would have had with any other approach (I guess....).

Miguel

Well I guess there are the usual syncronization issues, what if you receive a new game command in the middle of a search, or a take back? Then you first need to exit the search etc...
Are you using a command queue or how do they syncronize?

What about reading from stdin, that is going to block if there is no input?
Do you then use the main thread for stdout?

[Aleks Peshkov]

Code: Select all

class Uci {
    Root root; //chess position to analyze

    //set when child thinking thread is started
    //reset when search thread returned search result and going to finish
    volatile bool isThinking;

    //search thread is polling this variable
    volatile bool stopSignal;

    thread::Handle thinker;

    //output handling
    std::ostream* out;

    //input handling
    std::istringstream command; //current command line
    std::string token; //current token from the command line

 public:
    Uci () : isThinking(false) {}
   ~Uci () { stop(); }

    void operator() (std::istream& = std::cin, std::ostream& = std::cout);
};

void Uci::wait() {
    if (isThinking) {
        thread::join(thinker);
    }
    assert (!isThinking);
}

void Uci::stop() {
    if (isThinking) {
        stopSignal = true;
        wait();
    }
    assert (!isThinking);
}

void Uci::readyok() {
    *out << "readyok\n" << std&#58;&#58;flush;
&#125;

void Uci&#58;&#58;operator&#40;) &#40;istream& input, ostream& output&#41; &#123;
    out = &output;

    for &#40;std&#58;&#58;string line; std&#58;&#58;getline&#40;input, line&#41;; ) &#123;
        command.clear&#40;); //clear stream status from the previous command
        command.str&#40;line&#41;;

        if &#40;command >> token&#41; &#123;
            if      &#40;token == "position")   &#123; position&#40;); &#125;
            else if &#40;token == "go")         &#123; go&#40;); &#125;
            else if &#40;token == "stop")       &#123; stop&#40;); &#125;
            else if &#40;token == "isready")    &#123; readyok&#40;); &#125;
            else if &#40;token == "quit")       &#123; break; &#125;
            else                            &#123; unknown_command&#40;); &#125;
        &#125;
    &#125;
&#125;

[michiguel]

Why a threaded design is more error prone and difficult? I always had an input thread and a search thread and I was happy with it. I am not saying it never game me problems, but I do not think it gave me more that I would have had with any other approach (I guess....).

Miguel

Well I guess there are the usual syncronization issues, what if you receive a new game command in the middle of a search, or a take back? Then you first need to exit the search etc...
Are you using a command queue or how do they syncronize?

What about reading from stdin, that is going to block if there is no input?
Do you then use the main thread for stdout?

The "search" thread, which is an iterative deepening thread is launched when needed. Every 512 nodes (IIRC) checks if it is out of time, or if a stop_flag is TRUE. If stop_flag == TRUE, it unwinds. The search thread does not check for input at all. It just received global flag "communication signals" from the main thread to know when to stop.

So, the main thread do all the organization work. For instance, it launches a search thread if required and waits for input. The input could be anything and will be processed accordingly (e.g. display a board, help, xboard commands etc.). If it is newgame, it will stop the search thread with stop_flag = TRUE + pthread_join_searchthread() and launches a new search thread.

There are other flags needed and UCI made me have a semaphore at the end of the search thread to work as a gate. I needed to contain the search thread in case it wanted to return earlier (mate found in pondering) that receiving stop.

That is pretty much the whole concept.

Miguel

[Harald]

Interesting questions. I also think a lot about this design.
I have not found a very good solution yet. My work is not very different
from the solutions discussed so far. Here are a few remarks and questions from me.

I have two threads. One only waits for input (winboard style) and the other
does everything else. That is the game, the main loop and the search.
Deep inside the search the global input variables from the other thread
are tested every x nodes. I am not sure whether the search should be a third
thread or the main program and input should be in one thread and the
search in the second one.

Another strange detail of my implementation is the uncommon use of
exceptions. When I test the node count, time condition or input deep in
the search I can handle some requests immediately and continue the search.
Other inputs throw an exception that is captured in the iterative deepening loop
or the main loop of the program or it leads to exit. With this I don't have to write
if ( some_break_condition ) return;
after each call to search() in the search tree. The code looks nice but is it slow?

Harald

[SuneF]

I have two threads. One only waits for input (winboard style) and the other
does everything else. That is the game, the main loop and the search.
Deep inside the search the global input variables from the other thread
are tested every x nodes. I am not sure whether the search should be a third
thread or the main program and input should be in one thread and the
search in the second one.

Another strange detail of my implementation is the uncommon use of
exceptions. When I test the node count, time condition or input deep in
the search I can handle some requests immediately and continue the search.
Other inputs throw an exception that is captured in the iterative deepening loop
or the main loop of the program or it leads to exit. With this I don't have to write
if ( some_break_condition ) return;
after each call to search() in the search tree. The code looks nice but is it slow?

Harald

Seems logical and simpler because you don't have to start and stop threads for every search and there is no syncronizing with the result from a search.
How do you handle if you get a move in the middle of a pondering search?
The stdin thread would get a move, tell the engine to stop searching and then put the move in a command queue, or would the stdin thread wait until the engine has stopped and then make the move, or what? How do you handle this?

I see no need for a third search thread, you'd just be introducing some of the complicated syncronization issues. The fewer the threads the better in general.

I think you should keep exceptions it if it works, it's a cleaner design in many ways (IMHO) but I think there may be a tiny overhead. I think extra stuff is going on when pushing parameters to the stack before a function call. IIRC it was a tad slower when enabling exceptions in my project, maybe 1% but barely measurable. I am not sure if this has changed with newer compilers though.