Thinker output

[bob]

My only question is this: Why would you not collect the PV on the fly by backing it up along with the score? A PV harvested from the trans/ref table is inaccurate, and (IMHO) makes it harder to debug things. I often look at a PV and score from Crafty, then run down the PV and repeatedly use the score command to tweak things to bring the score closer to what seems reasonable. A hash PV is almost guaranteed to not lead you to the actual position that was scored, which makes debugging much more complicated...

And backing up the PV is not expensive.

It is all about simplicity. It may not be expensive as far as run-time is concerned, but it is still extra ugly code. To me, at least, it looks like that.

Even within Thinker, the implementation of search is hidden from the shell. The tree search is just one form of search. The book search is another. Both have completely different behavior. So, the shell does not care how they find the best move. The shell just knows that they will return one.

To the shell, the book search and the tree search are just "strategies" (in design pattern speak). So, even if I implement a PV collection in the tree search, would I want to expose that? That means the book search would have to return a PV also? That means that any "search strategy" always include a PV. I could design it that way, but that would be a very bad design. That may not be a big deal to others, but it is to me.

Just to give an idea of the simplicity that I am talking about, below is a comparison of the call graphs of Fruit 2.3.1, Crafty 22.9 and Thinker 5.4C.

Cheers...







http://www.winboardengines.de/thinker/C ... -2-3-1.bmp
http://www.winboardengines.de/thinker/C ... y-22-9.bmp
http://www.winboardengines.de/thinker/C ... ker54C.bmp

I can only say that I do not understand what these graphs mean and how you generate them,

When you talk about elegence then I do not understand what is the exact meaning of ut.
I do not know if there is some mathematical way to measure it.

Uri

These are "call graphs". Each node is a function, and each lines (edge) is a function call (from one function to another).

I found this example of a fully labeled one:
http://multimedia.cx/eggs/images/dcng-w ... lgraph.png

I don't think they are an indicator of elegance.

It can however give you an indication of the complexity of the program. The number of functions is a simple indicator, but not very accurate. But if your functions are bunched together and layered, and there are just few lines between those bunched-up (or layered) functions, then it indicates that program is modularized. That is, a group of functions (or a layer) perform a specific task, and there is a well defined small set of interfaces to them.

The Fruit and Crafty code definitely has a lot of functions, and so, you can't see each one of them anymore (they should show-up as rectangles, like in Thinker graph). This explains why the Fruit binary is 10 times the Thinker binary.

Now, I can't accurately comment on modularity of Fruit and Crafty because the individual lines are no longer visible. I just have a feeling that there are a lot of crisscrossing of lines there.

Speaking for myself, I have _lots_ of small functions/procedures. By intent and design, as I subscribe to the "linux approach" of keeping functions as small as possible to make them easier to read and understand...

I don't think a program with one large block of code is more elegant at all, although the call graph would be quite simple...

[Zach Wegner]

I like the approach I use, which is a pv[maxply][maxply]

At any depth, you only store into pv[ply][ply] for a terminal move. As you back up you only back up a part of this array. When you back up from 10 to 9, you copy everything from pv[10][0 to endofpv] and then save the current move in pv[9[[9] to go along with the partial PV being backed up... This is executed _very_ few times and costs nothing as a result.

I never understood this [ply][ply] nonsense. It was in TSCP, which was one of the first programs I ever saw. When I changed from the approach I just described to the two-dimensional array, I use [ply][0]. When you back up a PV, you store the current move in [ply][0] and copy the next ply's starting at [ply][1]. Saves an add.

what add?

You do a 10 ply search and at ply 10, depth=0, you evaluate and start to back up. You have no move here, just a score.

At ply=9, when you complete, you store current move in pv[8][9] and you are done.

At ply=8, you store current move in pv[7][8] aand copy the rest of pv[8][n] where n= 9 only.

At ply=7 you store the current move in pv[6][7], and then copy pv[7][8 & 9] to pv[6]

...

at ply=1 you store current move in pv[0][1] and copy pv[1][2,3,4,5,6,7,8,9] to pv[0].

Very little copying, hardly ever done...

Your method:

Code: Select all

if (value>alpha)
{
  alpha=value;
  pv[ply][ply]=move;
  pv_t=&pv[ply][ply+1];  // here
  pv_f=&pv[ply+1][ply+1];
  while(*pv_f)
    *pv_t++=*pv_f++;
}

Mine:

Code: Select all

if (value>alpha)
{
  alpha=value;
  pv[ply][ply]=move;
  pv_t=&pv[ply][1];  // here
  pv_f=&pv[ply+1][0];
  while(*pv_f)
    *pv_t++=*pv_f++;
}

So mine actually saves two adds in those initial memory accesses. I would guess they might be lea's though, so maybe they would be the same.

[michiguel]

My only question is this: Why would you not collect the PV on the fly by backing it up along with the score? A PV harvested from the trans/ref table is inaccurate, and (IMHO) makes it harder to debug things. I often look at a PV and score from Crafty, then run down the PV and repeatedly use the score command to tweak things to bring the score closer to what seems reasonable. A hash PV is almost guaranteed to not lead you to the actual position that was scored, which makes debugging much more complicated...

And backing up the PV is not expensive.

It is all about simplicity. It may not be expensive as far as run-time is concerned, but it is still extra ugly code. To me, at least, it looks like that.

Even within Thinker, the implementation of search is hidden from the shell. The tree search is just one form of search. The book search is another. Both have completely different behavior. So, the shell does not care how they find the best move. The shell just knows that they will return one.

To the shell, the book search and the tree search are just "strategies" (in design pattern speak). So, even if I implement a PV collection in the tree search, would I want to expose that? That means the book search would have to return a PV also? That means that any "search strategy" always include a PV. I could design it that way, but that would be a very bad design. That may not be a big deal to others, but it is to me.

Just to give an idea of the simplicity that I am talking about, below is a comparison of the call graphs of Fruit 2.3.1, Crafty 22.9 and Thinker 5.4C.

Cheers...







http://www.winboardengines.de/thinker/C ... -2-3-1.bmp
http://www.winboardengines.de/thinker/C ... y-22-9.bmp
http://www.winboardengines.de/thinker/C ... ker54C.bmp

I can only say that I do not understand what these graphs mean and how you generate them,

When you talk about elegence then I do not understand what is the exact meaning of ut.
I do not know if there is some mathematical way to measure it.

Uri

Hi Lance,

What software did you use in creating those graphs? I'm thinking of rewriting my engine using C++ in the near future (I'm currently using C) after I implement SMP and I'm planning to use some Design Patterns to make it more elegant and as simple as it could make it.

Those were generated with IDA.

I think you should be able to achieve in C whatever it is that you want to do in C++, especially in a simple program such as a chess engine. That's just my opinion.

Okay. I will take it as an advice.

By the way, what about your choice of protocol? UCI seems to be more elegant for me compared to Xboard.

Obviously, the beauty is in the eye of the beholder. I do not see the elegance of sending the whole game after each move. I find it awkward. Also, I have seen the people call clean and beautiful when I see the opposite and vice versa. Many people call "elegant" what is a clever trick that saves some code. Well, that code may end up being unreadable and unmaintainable by mortal programmers. Some people see beauty in code that is more resilient to suffer from bugs. Some others see beauty in fewer lines of code. Bubble sort is short and clean? it may be, if you know that you will be sorting no more than a handful of elements, but...

I do not find elegance in trying to fit a model to a different reality. UCI is stateless, but chess is not. Consequently, you end up sending the whole game every move. IMHO, that is a sign that something is flawed.

Miguel

[mhull]

I do not find elegance in trying to fit a model to a different reality. UCI is stateless, but chess is not. Consequently, you end up sending the whole game every move. IMHO, that is a sign that something is flawed.

Or just Wrong.

[CThinker]

The ways that other engines collect PV arrays look very hacky to me. They either allocate a square array, but use only half of it, or, allocates PV arrays on the stack on each call to a search function. Neither is acceptable to me. So, until I device a really clean solution, I am not inclined on polluting the Thinker code.

One idea from Vincent is to make an array pv_stack[MAX_PLY * MAX_PLY / 2]; and then keep a pointer to the first and last entry into it for each ply. Whenever you get a new PV, you save it starting at the first pointer, and then save the last entry. You then pass the entry past the last move (also you need a marker to signify the end of a PV) to the next ply.

ZCT used to do this but I got rid of it because of the copying of PVs in SMP. One CPU could be searching a node with current PV of length 1, then another CPU backs up a PV of length 3. You either have to truncate it or shift the current PV forward in the array to make room for it.

I like the approach I use, which is a pv[maxply][maxply]

At any depth, you only store into pv[ply][ply] for a terminal move. As you back up you only back up a part of this array. When you back up from 10 to 9, you copy everything from pv[10][0 to endofpv] and then save the current move in pv[9[[9] to go along with the partial PV being backed up... This is executed _very_ few times and costs nothing as a result.

Yup, I am aware of this approach, but it does not appeal to me. Half of that array is unused.

And that is a problem because... ???

Well, I guess to you there is no problem then. That's OK.

This is similar to fretting around because you waste up to 63 bytes of memory to force your hash table to sit on a 64-byte memory alignment to improve cache efficiency. Do you worry about that potential loss of 63 bytes of memory? It _is_ wasted...

the 1/2 used array makes the code clean and elegant and fast. All much more important than losing 1/2 of a 64xx64 = 4096 element array. 2048 x 4 = 8K bytes on machines that nowadays have at least 1-2 gigabytes of memory. On that scale, properly aligning the hash table is just as bad... Yet I'd hope everyone does that...

Actually, 63 bytes is a lot in my world. To me, every byte counts, and I mean that literraly. So, if it is at all posible to avoid wasting it, I do take the extra steps, assuming that there is no additional hit on code (binary) size.

Just to illustrate that, I'll use here the constant strings as an example. Most compilers align the strings. And so, you end-up with unused bytes at the end of strings.

If you open the Fruit EXE in a binary editor, you will see unused bytes in between the strings.

Code: Select all

btime   depth   infinite    mate    movestogo   movetime    nodes   ponder  searchmoves winc    wtime   fen     moves   name  

In constrast, if you open any Thinker EXE in a binary editor, you will not see any unused bytes.

Code: Select all

computer easy hard level otim time post nopost st sd xboard go setboard ? force new remove undo quit

Some compilers will take care of this. Some won't, no matter what option you give it.

To make sure that "any compiler" will always not waste any byte, I actually deliberately code for it. Here is a snippet from the Thinker xboard shell:

Code: Select all

    // command strings

    static const char StrCmd[] =

        "computer"      "\0"
        "easy"          "\0"
        "hard"          "\0"
        "level"         "\0"
        "otim"          "\0"
        "time"          "\0"
        "post"          "\0"
        "nopost"        "\0"
        "st"            "\0"
        "sd"            "\0"
        "xboard"        "\0"
        "go"            "\0"
        "setboard"      "\0"
        "?"             "\0"
        "force"         "\0"
        "new"           "\0"
        "remove"        "\0"
        "undo"          "\0"
        "quit"          "\0"
        ;

    #define StrCmd_computer      ( StrCmd )
    #define StrCmd_easy          ( StrCmd_computer      +  8 + 1 )
    #define StrCmd_hard          ( StrCmd_easy          +  4 + 1 )
    #define StrCmd_level         ( StrCmd_hard          +  4 + 1 )
    #define StrCmd_otim          ( StrCmd_level         +  5 + 1 )
    #define StrCmd_time          ( StrCmd_otim          +  4 + 1 )
    #define StrCmd_post          ( StrCmd_time          +  4 + 1 )
    #define StrCmd_nopost        ( StrCmd_post          +  4 + 1 )
    #define StrCmd_st            ( StrCmd_nopost        +  6 + 1 )
    #define StrCmd_sd            ( StrCmd_st            +  2 + 1 )
    #define StrCmd_xboard        ( StrCmd_sd            +  2 + 1 )
    #define StrCmd_go            ( StrCmd_xboard        +  6 + 1 )
    #define StrCmd_setboard      ( StrCmd_go            +  2 + 1 )
    #define StrCmd_movenow       ( StrCmd_setboard      +  8 + 1 )
    #define StrCmd_force         ( StrCmd_movenow       +  1 + 1 )
    #define StrCmd_new           ( StrCmd_force         +  5 + 1 )
    #define StrCmd_remove        ( StrCmd_new           +  3 + 1 )
    #define StrCmd_undo          ( StrCmd_remove        +  6 + 1 )
    #define StrCmd_quit          ( StrCmd_undo          +  4 + 1 )

As you can see, there is extra source code, but that does not affect the actual binary size. These are just pre-processor text substitutions.

This also forces me not to use the strings directly. If the strings need to change (say, I need to Greek version of the xboard commands), then I only need to change in one known place.

Now back to the squre PV array..., in Thinker, the max ply is 128. The square PV array approach would translate to 64K. 32K of that will never be used. For others, its nothing. To me, that's a lot. On a Pocket PC, that may be the difference between running and running out of stack and terminating.

Some developers don't go though this type of detail, but I do. Some don't bother designing (the engine just ends up as one giant chunk of intermingled code), but I do.

But then again, that's just me. To each his own, of course.

[bob]

I don't even think it is that much difference. Because I don't copy the data like that. Look at the bottom of Search() to see the memcpy() approach which is simpler.

[michiguel]

The ways that other engines collect PV arrays look very hacky to me. They either allocate a square array, but use only half of it, or, allocates PV arrays on the stack on each call to a search function. Neither is acceptable to me. So, until I device a really clean solution, I am not inclined on polluting the Thinker code.

One idea from Vincent is to make an array pv_stack[MAX_PLY * MAX_PLY / 2]; and then keep a pointer to the first and last entry into it for each ply. Whenever you get a new PV, you save it starting at the first pointer, and then save the last entry. You then pass the entry past the last move (also you need a marker to signify the end of a PV) to the next ply.

ZCT used to do this but I got rid of it because of the copying of PVs in SMP. One CPU could be searching a node with current PV of length 1, then another CPU backs up a PV of length 3. You either have to truncate it or shift the current PV forward in the array to make room for it.

I like the approach I use, which is a pv[maxply][maxply]

At any depth, you only store into pv[ply][ply] for a terminal move. As you back up you only back up a part of this array. When you back up from 10 to 9, you copy everything from pv[10][0 to endofpv] and then save the current move in pv[9[[9] to go along with the partial PV being backed up... This is executed _very_ few times and costs nothing as a result.

Yup, I am aware of this approach, but it does not appeal to me. Half of that array is unused.

And that is a problem because... ???

Well, I guess to you there is no problem then. That's OK.

This is similar to fretting around because you waste up to 63 bytes of memory to force your hash table to sit on a 64-byte memory alignment to improve cache efficiency. Do you worry about that potential loss of 63 bytes of memory? It _is_ wasted...

the 1/2 used array makes the code clean and elegant and fast. All much more important than losing 1/2 of a 64xx64 = 4096 element array. 2048 x 4 = 8K bytes on machines that nowadays have at least 1-2 gigabytes of memory. On that scale, properly aligning the hash table is just as bad... Yet I'd hope everyone does that...

Actually, 63 bytes is a lot in my world. To me, every byte counts, and I mean that literraly. So, if it is at all posible to avoid wasting it, I do take the extra steps, assuming that there is no additional hit on code (binary) size.

Just to illustrate that, I'll use here the constant strings as an example. Most compilers align the strings. And so, you end-up with unused bytes at the end of strings.

If you open the Fruit EXE in a binary editor, you will see unused bytes in between the strings.

Code: Select all

btime   depth   infinite    mate    movestogo   movetime    nodes   ponder  searchmoves winc    wtime   fen     moves   name  

In constrast, if you open any Thinker EXE in a binary editor, you will not see any unused bytes.

Code: Select all

computer easy hard level otim time post nopost st sd xboard go setboard ? force new remove undo quit

Some compilers will take care of this. Some won't, no matter what option you give it.

To make sure that "any compiler" will always not waste any byte, I actually deliberately code for it. Here is a snippet from the Thinker xboard shell:

Code: Select all

    // command strings

    static const char StrCmd[] =

        "computer"      "\0"
        "easy"          "\0"
        "hard"          "\0"
        "level"         "\0"
        "otim"          "\0"
        "time"          "\0"
        "post"          "\0"
        "nopost"        "\0"
        "st"            "\0"
        "sd"            "\0"
        "xboard"        "\0"
        "go"            "\0"
        "setboard"      "\0"
        "?"             "\0"
        "force"         "\0"
        "new"           "\0"
        "remove"        "\0"
        "undo"          "\0"
        "quit"          "\0"
        ;

    #define StrCmd_computer      ( StrCmd )
    #define StrCmd_easy          ( StrCmd_computer      +  8 + 1 )
    #define StrCmd_hard          ( StrCmd_easy          +  4 + 1 )
    #define StrCmd_level         ( StrCmd_hard          +  4 + 1 )
    #define StrCmd_otim          ( StrCmd_level         +  5 + 1 )
    #define StrCmd_time          ( StrCmd_otim          +  4 + 1 )
    #define StrCmd_post          ( StrCmd_time          +  4 + 1 )
    #define StrCmd_nopost        ( StrCmd_post          +  4 + 1 )
    #define StrCmd_st            ( StrCmd_nopost        +  6 + 1 )
    #define StrCmd_sd            ( StrCmd_st            +  2 + 1 )
    #define StrCmd_xboard        ( StrCmd_sd            +  2 + 1 )
    #define StrCmd_go            ( StrCmd_xboard        +  6 + 1 )
    #define StrCmd_setboard      ( StrCmd_go            +  2 + 1 )
    #define StrCmd_movenow       ( StrCmd_setboard      +  8 + 1 )
    #define StrCmd_force         ( StrCmd_movenow       +  1 + 1 )
    #define StrCmd_new           ( StrCmd_force         +  5 + 1 )
    #define StrCmd_remove        ( StrCmd_new           +  3 + 1 )
    #define StrCmd_undo          ( StrCmd_remove        +  6 + 1 )
    #define StrCmd_quit          ( StrCmd_undo          +  4 + 1 )

As you can see, there is extra source code, but that does not affect the actual binary size. These are just pre-processor text substitutions.

This also forces me not to use the strings directly. If the strings need to change (say, I need to Greek version of the xboard commands), then I only need to change in one known place.

Now back to the squre PV array..., in Thinker, the max ply is 128. The square PV array approach would translate to 64K. 32K of that will never be used. For others, its nothing. To me, that's a lot. On a Pocket PC, that may be the difference between running and running out of stack and terminating.

If you decide to show only the first 8 plies of your PV, it is possible to design everything to squeeze it 128 bytes. 8 plies will mean a world of difference to users. In fact, you can make this adjustable by the user. After all, you are using hashtables, correct? I assume the user can adjust that to the memory they have in the system. There is nothing memory efficient about a hash table!!

As I said, I respect your decision about this, and I certainly admire your talent, a lot. Some people go for the record of smallest code, smallest memory, highest elo etc. etc. I just do not agree when you say that this approach is beautiful, clean, or elegant, somehow implying that approaches to get the PV are ugly or people do not care about elegance anymore. I do not think there is anything beautiful about missing a feature.

Miguel
Edit: You do not need to have the array in the stack.

Some developers don't go though this type of detail, but I do. Some don't bother designing (the engine just ends up as one giant chunk of intermingled code), but I do.

But then again, that's just me. To each his own, of course.

[Dann Corbit]

My only question is this: Why would you not collect the PV on the fly by backing it up along with the score? A PV harvested from the trans/ref table is inaccurate, and (IMHO) makes it harder to debug things. I often look at a PV and score from Crafty, then run down the PV and repeatedly use the score command to tweak things to bring the score closer to what seems reasonable. A hash PV is almost guaranteed to not lead you to the actual position that was scored, which makes debugging much more complicated...

And backing up the PV is not expensive.

It is all about simplicity. It may not be expensive as far as run-time is concerned, but it is still extra ugly code. To me, at least, it looks like that.

Even within Thinker, the implementation of search is hidden from the shell. The tree search is just one form of search. The book search is another. Both have completely different behavior. So, the shell does not care how they find the best move. The shell just knows that they will return one.

To the shell, the book search and the tree search are just "strategies" (in design pattern speak). So, even if I implement a PV collection in the tree search, would I want to expose that? That means the book search would have to return a PV also? That means that any "search strategy" always include a PV. I could design it that way, but that would be a very bad design. That may not be a big deal to others, but it is to me.

Just to give an idea of the simplicity that I am talking about, below is a comparison of the call graphs of Fruit 2.3.1, Crafty 22.9 and Thinker 5.4C.

Cheers...







http://www.winboardengines.de/thinker/C ... -2-3-1.bmp
http://www.winboardengines.de/thinker/C ... y-22-9.bmp
http://www.winboardengines.de/thinker/C ... ker54C.bmp

I can only say that I do not understand what these graphs mean and how you generate them,

When you talk about elegence then I do not understand what is the exact meaning of ut.
I do not know if there is some mathematical way to measure it.

Uri

Hi Lance,

What software did you use in creating those graphs? I'm thinking of rewriting my engine using C++ in the near future (I'm currently using C) after I implement SMP and I'm planning to use some Design Patterns to make it more elegant and as simple as it could make it.

Those were generated with IDA.

I think you should be able to achieve in C whatever it is that you want to do in C++, especially in a simple program such as a chess engine. That's just my opinion.

Okay. I will take it as an advice.

By the way, what about your choice of protocol? UCI seems to be more elegant for me compared to Xboard.

Obviously, the beauty is in the eye of the beholder. I do not see the elegance of sending the whole game after each move. I find it awkward. Also, I have seen the people call clean and beautiful when I see the opposite and vice versa. Many people call "elegant" what is a clever trick that saves some code. Well, that code may end up being unreadable and unmaintainable by mortal programmers. Some people see beauty in code that is more resilient to suffer from bugs. Some others see beauty in fewer lines of code. Bubble sort is short and clean? it may be, if you know that you will be sorting no more than a handful of elements, but...

I do not find elegance in trying to fit a model to a different reality. UCI is stateless, but chess is not. Consequently, you end up sending the whole game every move. IMHO, that is a sign that something is flawed.

Miguel

UCI is clearly better for setup.
Winboard is clearly better for game play and learning.

The best protocol is a simple combination of both of them folded together.

[Zach Wegner]

To make sure that "any compiler" will always not waste any byte, I actually deliberately code for it. Here is a snippet from the Thinker xboard shell:

Code: Select all

    // command strings

    static const char StrCmd[] =

        "computer"      "\0"
        "easy"          "\0"
        "hard"          "\0"
        "level"         "\0"
        "otim"          "\0"
        "time"          "\0"
        "post"          "\0"
        "nopost"        "\0"
        "st"            "\0"
        "sd"            "\0"
        "xboard"        "\0"
        "go"            "\0"
        "setboard"      "\0"
        "?"             "\0"
        "force"         "\0"
        "new"           "\0"
        "remove"        "\0"
        "undo"          "\0"
        "quit"          "\0"
        ;

    #define StrCmd_computer      ( StrCmd )
    #define StrCmd_easy          ( StrCmd_computer      +  8 + 1 )
    #define StrCmd_hard          ( StrCmd_easy          +  4 + 1 )
    #define StrCmd_level         ( StrCmd_hard          +  4 + 1 )
    #define StrCmd_otim          ( StrCmd_level         +  5 + 1 )
    #define StrCmd_time          ( StrCmd_otim          +  4 + 1 )
    #define StrCmd_post          ( StrCmd_time          +  4 + 1 )
    #define StrCmd_nopost        ( StrCmd_post          +  4 + 1 )
    #define StrCmd_st            ( StrCmd_nopost        +  6 + 1 )
    #define StrCmd_sd            ( StrCmd_st            +  2 + 1 )
    #define StrCmd_xboard        ( StrCmd_sd            +  2 + 1 )
    #define StrCmd_go            ( StrCmd_xboard        +  6 + 1 )
    #define StrCmd_setboard      ( StrCmd_go            +  2 + 1 )
    #define StrCmd_movenow       ( StrCmd_setboard      +  8 + 1 )
    #define StrCmd_force         ( StrCmd_movenow       +  1 + 1 )
    #define StrCmd_new           ( StrCmd_force         +  5 + 1 )
    #define StrCmd_remove        ( StrCmd_new           +  3 + 1 )
    #define StrCmd_undo          ( StrCmd_remove        +  6 + 1 )
    #define StrCmd_quit          ( StrCmd_undo          +  4 + 1 )

I thought you said you were concerned about code elegance?!?

[CThinker]

Miguel
Edit: You do not need to have the array in the stack.

Actually, I was not saying that the PV array will go to the stack. Instead, what I was staying is that there is now less memory that can be given to you as stack memory because that memory has been allocated somewhere else. With smaller stack, you run in to the chance of overrunning it. You go a few plies deep, and your program could just crash.

Memory is not free. If you use it in one place, you now have less for others. That 32K could be used for the pawn hash table, for example, which is just about right on a mobile phone.

Cheers...