Thinker output

[CThinker]

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

[CThinker]

And, I don't work on the Thinker code anymore.

Are you working on a new engine?

No, not really. Kerwin does all the Thinker development now. He does a much better, elegant and cleaner job anyway.

I'm "trying" to port the current code to the DS platform. That is progressing slow.

Did that for Crafty. Assuming DS = nintendo DS. Slow processor, odd memory setup, not to mention small memory, etc.

Yup. The Nintendo DS. With all those limitations that you mentioned, I think the Thinker code will feel so at home on it.

[bob]

So how fast does crafty run on a DS? Do you have an estimation of playing strength perhaps?

It's been a while, I believe it was in the 30K nodes per second range. I was asked to do this for a game company a couple of years ago. I had to get rid of rotated bitboards due to space and did a direct calculation to generate moves, which is about 10% slower than rotated/magic. I also had to remove lots of "extras" and use a _really_ small hash table.

I don't remember the specifics however as this was just a quick-and-dirty port...

[bob]

And, I don't work on the Thinker code anymore.

Are you working on a new engine?

No, not really. Kerwin does all the Thinker development now. He does a much better, elegant and cleaner job anyway.

I'm "trying" to port the current code to the DS platform. That is progressing slow.

Did that for Crafty. Assuming DS = nintendo DS. Slow processor, odd memory setup, not to mention small memory, etc.

Yup. The Nintendo DS. With all those limitations that you mentioned, I think the Thinker code will feel so at home on it.

Couple of points, still.

(1) users want a PV, and at present you are providing one so it seems that how you do it is immaterial...

(2) for me, debugging is a significant point, and it is nice to know that here is the PV that led to the best score, and here is the score. I've tried the "gather from hash" and you get some _really_ odd PVs, particularly the last half most likely does not go with the backed up score/position... I find it helps me to see the correct PV and the score when debugging, and I have to hope I don't get those peskey <HT> short PVs...

[glorfindel]

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.

You could try to find a more elegant solution for the problem of showing a PV, if the way you described is not good enough. I don't think the answer can be "there is no elegant solution". How can your design be so good, if it doesn't solve the problem?

Of course, there is also the possibility that you simply don't think it is a problem at all, so you don't try to solve it. That is, in the very first steps of designing Thinker, perhaps in its use case diagram, there is no use case called "analyze", there is only one use case called "play". The result is that Thinker is one of the strongest engines for playing against, but it is of no use when you want to analyze a game, which some people, including myself, need to do.

But if Thinker is really intended to be only an opponent, you should not have made it that strong . I don't completely believe all those people who say they enjoy playing many games against Thinker. I do play games against engines, including yours, but it not very fun when you lose all the time _and_ you don't know what happened in the game, so you have to switch on another engine to analyze the game and show you what Thinker might have been thinking.

[CThinker]

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.

You could try to find a more elegant solution for the problem of showing a PV, if the way you described is not good enough. I don't think the answer can be "there is no elegant solution". How can your design be so good, if it doesn't solve the problem?

Of course, there is also the possibility that you simply don't think it is a problem at all, so you don't try to solve it. That is, in the very first steps of designing Thinker, perhaps in its use case diagram, there is no use case called "analyze", there is only one use case called "play". The result is that Thinker is one of the strongest engines for playing against, but it is of no use when you want to analyze a game, which some people, including myself, need to do.

But if Thinker is really intended to be only an opponent, you should not have made it that strong . I don't completely believe all those people who say they enjoy playing many games against Thinker. I do play games against engines, including yours, but it not very fun when you lose all the time _and_ you don't know what happened in the game, so you have to switch on another engine to analyze the game and show you what Thinker might have been thinking.

Yes Chris, you have put that precisely. The 'analyze' scenario was not a consideration during the design (and redesign). The design goal was the simplest (and cleanest) architecture that would allow for legal chess play.

You can tell from the comparison of the call graphs, that, Thinker has a very simple code set. We can read and understand the code without scrolling through pages. We have been faithful to the design goal, so far.

I understand that users would like to enable a few other scenarios (like, game analysis). We would have to consider that in the next major redesign (whenever that may be). I just want to clarify that we are not talking about trivial bug fixing (hacking) here.

Cheers...

[bob]

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.

You could try to find a more elegant solution for the problem of showing a PV, if the way you described is not good enough. I don't think the answer can be "there is no elegant solution". How can your design be so good, if it doesn't solve the problem?

Of course, there is also the possibility that you simply don't think it is a problem at all, so you don't try to solve it. That is, in the very first steps of designing Thinker, perhaps in its use case diagram, there is no use case called "analyze", there is only one use case called "play". The result is that Thinker is one of the strongest engines for playing against, but it is of no use when you want to analyze a game, which some people, including myself, need to do.

But if Thinker is really intended to be only an opponent, you should not have made it that strong . I don't completely believe all those people who say they enjoy playing many games against Thinker. I do play games against engines, including yours, but it not very fun when you lose all the time _and_ you don't know what happened in the game, so you have to switch on another engine to analyze the game and show you what Thinker might have been thinking.

Yes Chris, you have put that precisely. The 'analyze' scenario was not a consideration during the design (and redesign). The design goal was the simplest (and cleanest) architecture that would allow for legal chess play.

You can tell from the comparison of the call graphs, that, Thinker has a very simple code set. We can read and understand the code without scrolling through pages. We have been faithful to the design goal, so far.

I understand that users would like to enable a few other scenarios (like, game analysis). We would have to consider that in the next major redesign (whenever that may be). I just want to clarify that we are not talking about trivial bug fixing (hacking) here.

Cheers...

If you are using traditional alpha/beta, which it appears you are, backing up the PV is both simple and has almost zero cost...

[sje]

Symbolic uses a simple two-way linked list to store PV move sequences. For sake of efficiency, each worker thread has a designated move node factory instance variable that is used to allocate and recycle both single move nodes and entire lists of move nodes. This is rather faster than calling new/delete (i.e., malloc/free) for each node.

This approach has two advantages over the more common vector/copy method.

1) There is no copying, only a fast re-linking.

2) There is no maximum ply limit or a need for extensible arrays.

In C++, the dirty details are kept out of sight inside accessor functions.

[Zach Wegner]

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.

[bob]

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.