Stockfish and optimizing options for SMP search

[bob]

And, as I said, that idea is flawed. And anyone that has studied parallel search issues would see why. In fact, it is the inverse of best practice. Which would you rather split at, a node where only 1 move has been searched previously, or one where 10 have been searched? Simple answer. The latter. because there is a much higher probability that all of the remaining moves have to be searched. And that avoids search overhead.

You are hopeless, this is really childish. I say "the sky is blue", then you come and claim "you are completely wrong, you have no clue, the sky is not yellow, it is blue." You don't even try to understand what ppl claim, or you just pretend that you don't understand. In the end it doesn't matter, the effect is the same.

You have no clue. Additionally, just to try to help stamp out ignorance, the idea behind "minimum split depth" (which came _directly_ from Crafty, btw) is to try to balance work to be done in parallel against the cost of doing the split operation. If you split too near the tips, the work is small, the overhead is high, performance suffers. This is no longer the way I make this decision in Crafty. I have been using something different for a couple of years. And I will likely be using something different again in the next version. There are well-known issues.

Again patronizing about trivial stuff. Minimum split depth is so obvious concept that any average Joe you pick up on the street could figure it out. Bragging about how you "invented" that in Crafty just demonstrates boundless narcissism.

Your "master's thesis" comment shows just exactly how deep your lack of knowledge really is... No surprise there.

Sorry Bob, but your "authority" attitude might only work with laymen and your students. Others (many on this forum) however understand the true nature behind. However, most ppl chose not to confront. I'm not one of them. If the emperor is naked I will always say it.
You do have an iconic status in chess programming community, but in the sense of pioneering and education, not in the sense of scientific contribution and bringing new (groundbreaking) ideas. I know this hurts your ego a lot, but that's the fact...

Actually, in any post you write here, "fact" is one thing nobody will find...

I did _not_ say your idea was good. I said it was flawed, and explained why. If you don't get that...

[bob]

I have a problem with the assumption that people can't come up with the same idea independently.

It has happened. Donskoy, et al (Kaissa) apparently developed the bitboard approach to represent a chess board independently and at the same time as Slate/Atkin were doing it for chess 4.0.

But in this case, Crafty was parallel before anyone could spell it on a PC. And there were _numerous_ discussions about this concept. Even in Cray Blitz.

I agree with Milos that the "minimum split depth" idea seems quite obvious to anyone who is used to make parallel algorithms. One of the basic goals in any parallel algorithm is to only split work between threads when that doesn't cause too much overhead, and "minimum split depth" follows directly from that.

[Sven]

that the "minimum split depth" idea seems quite obvious to anyone who is used to make parallel algorithms

It's easy to be wise after the event

It's even easier to be an apple-polisher .

Your inappropriate language does not get more value by using a smiley.

People following various discussions between Bob and myself (and possibly others) know my general attitude towards Bob and his unique style of discussion. That includes to know that I sometimes have an opinion which differs a lot from Bob's. And that includes to know that I always try to keep as factual, objective and on topic as possible.

Which is not the case for everyone in this thread, as you might know very well ...

But even huge differences in opinion between someone and myself do not make me believe that everything the other one says is "nonsense" or "childish". Just tell him your opinion and your reasons, and respect his view, and very soon the communication will work much better. You may be right in a few points, regarding "authority" and so on. But that does not grant attacking and offending.

Maybe even you can learn that, although P<0.01 ...

Also, please refrain from further replies here since this is already OT by far (note we are in Programming subforum ...).

Sven

[sje]

I have a problem with the assumption that people can't come up with the same idea independently.

It has happened. Donskoy, et al (Kaissa) apparently developed the bitboard approach to represent a chess board independently and at the same time as Slate/Atkin were doing it for chess 4.0.

And long before Kaissa and the Northwestern Chess 4.x, there were bitboards in the Samuel Checker Player by Arthur Samuel. Samuel mapped the 32 playing squares of a checkerboard into a 36 bit word and used the extra four bits to enable some clever shift and mask trickery.

Were some chess program authors influenced by Samuel's papers, but did not acknowledge them as sources? At one time at least, reading these reports (or at least a reference) was a standard practice in university AI classes.

There were a lot of ideas that I thought were original from me. Then around 1987 or so I joined the ICCA (now known as the ICGA), got all the back issues of the ICCA Journal, and saw how much I had done had already been done by others.

[Sven]

Did Bob claim people can't come up with the same idea independently?

He certainly implied it when he said this:

This was a Crafty idea, from the beginning, and everyone seems to have copied the idea without giving any more thought to the problem.

Not only does it seem everyone copied it, but they were even incapable of improving on it, poor bastards.

I don't see how this quoted sentence implies the statement I asked about, nor do I see any reason to believe that these were his thoughts. "Without giving any more thought to the problem" I would understand as a general criticism towards copying of ideas without knowing exactly how their implementation works. With my question I intended to say that Bob did not state it were impossible in general to come up with the same idea independently. Read also Bob's parallel post in this thread.

Do you claim that this idea was brought up independently by several people?

I don't know either way, but I do claim it is obvious enough that it probably did. Again, it follows directly the basic principles of parallel programming - only parallelize work when that speeds up the algorithm, in other cases do it serially.

I propose not to throw in such assumptions if you do not know exactly when A) this idea was developped by Bob, when B) the first Crafty version implementing it was published (open source!), and whether there was really someone else having the same idea roughly in the interval between A and B (or even prior to A). "Obvious enough" is not enough for me here.

It's easy to be wise after the event

It's easy to come up with clichés like that instead of critically evaluating the specific case we're discussing.

My contribution is to try to get more objectivity into the discussion.

As Bob stated early in this thread, the "Minimum Split Depth" idea was already removed from Crafty years ago. Neither Milos nor you gave the impression to have noticed that, though, please correct me if I am wrong. It is also possible that you actually mixed two different ideas. Bob was writing about an idea related to the "threads per split" number when he stated that this idea was copied by other engines. It seems this was slightly misquoted here.

Also, what I wrote is not a cliché. I wanted to say that today we know most of those ideas very well, so what permits us now to say things like "that is obvious"? You can say that immediately when it comes up. Not years later.

I would certainly agree if you'd say that "Minimum Split Depth", or "variable no. of threads per split", or whatever you choose, was not the biggest fundamental epoch-making idea that gave a tremendous boost to chess programming. Bob did not claim so. But he says Crafty was the first engine to implement these ideas, and in certain cases they appeared in other engines, too, later on. Let him say so, if it is true. And try to get the message behind it.

Sven

[Sven]

I have a problem with the assumption that people can't come up with the same idea independently.

It has happened. Donskoy, et al (Kaissa) apparently developed the bitboard approach to represent a chess board independently and at the same time as Slate/Atkin were doing it for chess 4.0.

And long before Kaissa and the Northwestern Chess 4.x, there were bitboards in the Samuel Checker Player by Arthur Samuel. Samuel mapped the 32 playing squares of a checkerboard into a 36 bit word and used the extra four bits to enable some clever shift and mask trickery.

Were some chess program authors influenced by Samuel's papers, but did not acknowledge them as sources? At one time at least, reading these reports (or at least a reference) was a standard practice in university AI classes.

There were a lot of ideas that I thought were original from me. Then around 1987 or so I joined the ICCA (now known as the ICGA), got all the back issues of the ICCA Journal, and saw how much I had done had already been done by others.

Although I am certainly not in the position to disagree completely, I'd like to point out that back in the 70s/80s there was no internet and no "open source" like today. That makes it much more likely than today to develop ideas independently from each other, at least. Again, I cannot claim so. But could it be possible that your findings were simply not known to those other people?

The same question would apply to the bitboards/Checkers topic you mentioned. Today we find virtually all information we need within seconds. Back then, do you think all chess programmers did actually read, or even have access to, all papers about checkers programs? O.k., both belonged to "AI" somehow, but I am not sure about the spreading of such papers at that time. Also, using 36 bits for a checker board might still be somewhat different from bitboards for chess, although the basic idea may be similar.

Sven

[sje]

I have a problem with the assumption that people can't come up with the same idea independently.

It has happened. Donskoy, et al (Kaissa) apparently developed the bitboard approach to represent a chess board independently and at the same time as Slate/Atkin were doing it for chess 4.0.

And long before Kaissa and the Northwestern Chess 4.x, there were bitboards in the Samuel Checker Player by Arthur Samuel. Samuel mapped the 32 playing squares of a checkerboard into a 36 bit word and used the extra four bits to enable some clever shift and mask trickery.

Were some chess program authors influenced by Samuel's papers, but did not acknowledge them as sources? At one time at least, reading these reports (or at least a reference) was a standard practice in university AI classes.

There were a lot of ideas that I thought were original from me. Then around 1987 or so I joined the ICCA (now known as the ICGA), got all the back issues of the ICCA Journal, and saw how much I had done had already been done by others.

Although I am certainly not in the position to disagree completely, I'd like to point out that back in the 70s/80s there was no internet and no "open source" like today. That makes it much more likely than today to develop ideas independently from each other, at least. Again, I cannot claim so. But could it be possible that your findings were simply not known to those other people?

The same question would apply to the bitboards/Checkers topic you mentioned. Today we find virtually all information we need within seconds. Back then, do you think all chess programmers did actually read, or even have access to, all papers about checkers programs? O.k., both belonged to "AI" somehow, but I am not sure about the spreading of such papers at that time. Also, using 36 bits for a checker board might still be somewhat different from bitboards for chess, although the basic idea may be similar.

Remember than Samuel did his work in the 1950s and early 1960s, was supported by IBM, and saw several papers published. These found their way into every AI book that touched on the topic of computer game playing. And other than changing the bit count from 32 to 64, the bitboard concepts are identical: piece location, attack maps, move generation, etc. Oh, and hashing, too if I recall correctly. Plus an opening book, signature tables, and even some primitive machine learning.

Unless a chess program author took no AI courses and never bothered to research the topic in a library, it is hard to believe that said author did not see a write-up of Samuel's Checker Player. Remember that this was a program that achieved near master level performance in the checker domain two decades before near master level chess programs appeared.

So claims made by some that the authors of Karissa and the Northwestern Chess 4.x somehow invented bitboards without being influenced by Samuel are just not credible.

[bob]

Did Bob claim people can't come up with the same idea independently?

He certainly implied it when he said this:

This was a Crafty idea, from the beginning, and everyone seems to have copied the idea without giving any more thought to the problem.

Not only does it seem everyone copied it, but they were even incapable of improving on it, poor bastards.

I don't see how this quoted sentence implies the statement I asked about, nor do I see any reason to believe that these were his thoughts. "Without giving any more thought to the problem" I would understand as a general criticism towards copying of ideas without knowing exactly how their implementation works. With my question I intended to say that Bob did not state it were impossible in general to come up with the same idea independently. Read also Bob's parallel post in this thread.

Do you claim that this idea was brought up independently by several people?

I don't know either way, but I do claim it is obvious enough that it probably did. Again, it follows directly the basic principles of parallel programming - only parallelize work when that speeds up the algorithm, in other cases do it serially.

I propose not to throw in such assumptions if you do not know exactly when A) this idea was developped by Bob, when B) the first Crafty version implementing it was published (open source!), and whether there was really someone else having the same idea roughly in the interval between A and B (or even prior to A). "Obvious enough" is not enough for me here.

I thought I might try to answer that question. The oldest version of Crafty I have that supported SMP was 15.17, and "min_thread_depth" was in that version. 15.0 was the first SMP version, which was around 1996, although I am not sure exactly when. 15.17 has some 1997 modification dates, so it could have been then. The "thread group" concept (max threads at any single split point) was added in the 16.x versions, I don't have them all on my laptop, but it was in 16.9 at least.

I doubt two different people would come up with similar names for similar concepts, if they didn't come from a common idea. And note that there is nothing wrong with using that idea. But for reference, the same idea as LMR was called "history pruning" in fruit, for example. Same names are unusual, for unusual ideas.

It's easy to be wise after the event

It's easy to come up with clichés like that instead of critically evaluating the specific case we're discussing.

My contribution is to try to get more objectivity into the discussion.

As Bob stated early in this thread, the "Minimum Split Depth" idea was already removed from Crafty years ago. Neither Milos nor you gave the impression to have noticed that, though, please correct me if I am wrong. It is also possible that you actually mixed two different ideas. Bob was writing about an idea related to the "threads per split" number when he stated that this idea was copied by other engines. It seems this was slightly misquoted here.

Also, what I wrote is not a cliché. I wanted to say that today we know most of those ideas very well, so what permits us now to say things like "that is obvious"? You can say that immediately when it comes up. Not years later.

I would certainly agree if you'd say that "Minimum Split Depth", or "variable no. of threads per split", or whatever you choose, was not the biggest fundamental epoch-making idea that gave a tremendous boost to chess programming. Bob did not claim so. But he says Crafty was the first engine to implement these ideas, and in certain cases they appeared in other engines, too, later on. Let him say so, if it is true. And try to get the message behind it.

Sven

[bob]

I have a problem with the assumption that people can't come up with the same idea independently.

It has happened. Donskoy, et al (Kaissa) apparently developed the bitboard approach to represent a chess board independently and at the same time as Slate/Atkin were doing it for chess 4.0.

And long before Kaissa and the Northwestern Chess 4.x, there were bitboards in the Samuel Checker Player by Arthur Samuel. Samuel mapped the 32 playing squares of a checkerboard into a 36 bit word and used the extra four bits to enable some clever shift and mask trickery.

Were some chess program authors influenced by Samuel's papers, but did not acknowledge them as sources? At one time at least, reading these reports (or at least a reference) was a standard practice in university AI classes.

There were a lot of ideas that I thought were original from me. Then around 1987 or so I joined the ICCA (now known as the ICGA), got all the back issues of the ICCA Journal, and saw how much I had done had already been done by others.

Although I am certainly not in the position to disagree completely, I'd like to point out that back in the 70s/80s there was no internet and no "open source" like today. That makes it much more likely than today to develop ideas independently from each other, at least. Again, I cannot claim so. But could it be possible that your findings were simply not known to those other people?

Impossible to say. I've started several threads on parallel search issues over the years, here on CCC, and on r.g.c.c prior to that. My comment was based on a couple of things.

(1) same terminology. "thread group" (max number of threads at any single split point) and "thread depth" (minimum remaining depth otherwise a split won't be done as it is too close to the tips.) Same terminology, same idea, most likely came from Crafty. Which was the intended consequence of releasing the source. They are not "great" ideas. They are just ideas. The original PVS search (where we split only down the left-hand side of the tree was a great idea. Incremental ideas (from me) included EPVS, that eliminated much wait time where all processors but one were sitting at a node with nothing more to do. DTS was a great idea. Everybody doesn't work together. Splits can be done anywhere. Processors help each other as they become available. Complicated, and efficient. My current code is a bit worse then DTS because I elected to keep the recursive search for cleanliness.

The same question would apply to the bitboards/Checkers topic you mentioned. Today we find virtually all information we need within seconds. Back then, do you think all chess programmers did actually read, or even have access to, all papers about checkers programs? O.k., both belonged to "AI" somehow, but I am not sure about the spreading of such papers at that time. Also, using 36 bits for a checker board might still be somewhat different from bitboards for chess, although the basic idea may be similar.

I learned about bitboards from two sources. (1) direct communication with Dave Slate and (b) Frey's 1976 "Chess Skill in Man and Machine" book. Slate's idea caught my attention because they used a 60 bit word CDC Cyber 176, which was 4 bits short. Got me to thinking about using 2x32 bits in 1994 when I started developing Crafty, as that was no less efficient than Slate having to use 2x60 to get 64 bits...

Sven

All I can say is "you weren't there." We had a "mail internet" where we exchanged mag tapes (I had a copy of COKO IV from Cooper/Kozdrowicki around 1972 or so). And we had computer-to-computer connections, starting in the early 70's, using modems (not always acoustic either).

There's always been a lot of sharing...

[bob]

I have a problem with the assumption that people can't come up with the same idea independently.

It has happened. Donskoy, et al (Kaissa) apparently developed the bitboard approach to represent a chess board independently and at the same time as Slate/Atkin were doing it for chess 4.0.

And long before Kaissa and the Northwestern Chess 4.x, there were bitboards in the Samuel Checker Player by Arthur Samuel. Samuel mapped the 32 playing squares of a checkerboard into a 36 bit word and used the extra four bits to enable some clever shift and mask trickery.

Were some chess program authors influenced by Samuel's papers, but did not acknowledge them as sources? At one time at least, reading these reports (or at least a reference) was a standard practice in university AI classes.

There were a lot of ideas that I thought were original from me. Then around 1987 or so I joined the ICCA (now known as the ICGA), got all the back issues of the ICCA Journal, and saw how much I had done had already been done by others.

Although I am certainly not in the position to disagree completely, I'd like to point out that back in the 70s/80s there was no internet and no "open source" like today. That makes it much more likely than today to develop ideas independently from each other, at least. Again, I cannot claim so. But could it be possible that your findings were simply not known to those other people?

The same question would apply to the bitboards/Checkers topic you mentioned. Today we find virtually all information we need within seconds. Back then, do you think all chess programmers did actually read, or even have access to, all papers about checkers programs? O.k., both belonged to "AI" somehow, but I am not sure about the spreading of such papers at that time. Also, using 36 bits for a checker board might still be somewhat different from bitboards for chess, although the basic idea may be similar.

Remember than Samuel did his work in the 1950s and early 1960s, was supported by IBM, and saw several papers published. These found their way into every AI book that touched on the topic of computer game playing. And other than changing the bit count from 32 to 64, the bitboard concepts are identical: piece location, attack maps, move generation, etc. Oh, and hashing, too if I recall correctly. Plus an opening book, signature tables, and even some primitive machine learning.

Unless a chess program author took no AI courses and never bothered to research the topic in a library, it is hard to believe that said author did not see a write-up of Samuel's Checker Player. Remember that this was a program that achieved near master level performance in the checker domain two decades before near master level chess programs appeared.

So claims made by some that the authors of Karissa and the Northwestern Chess 4.x somehow invented bitboards without being influenced by Samuel are just not credible.

My claim was they were the first I was aware of that used them. I graduated in 1970 (BS computer science) and my AI class did _not_ look at samuel's checker program or his papers. For board games, the only ones mentioned were the early chess projects at places like the USSR and Los Alamos. Some not even playing real chess but using a 6x6 board instead...

If Samuels created the idea, that's fine by me.