Search speed

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Krzysztof Grzelak
Posts: 816
Joined: Tue Jul 15, 2014 10:47 am

Search speed

Post by Krzysztof Grzelak » Fri Oct 04, 2019 9:10 am

I have such a request and a question for the developers of this forum. I have a processor Ryzen Threadripper 1950X. I am not a programmer but I would like to help another person who knows programming. I will only add that it concerns programming in C++. Can anyone write the code that would use to search in the processor AMD - L1 cache size and L2 cache size. I mean it would be the best and greatest search in kN/s. For all information - thank you in advance.

Krzysztof

Dann Corbit
Posts: 10205
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Search speed

Post by Dann Corbit » Fri Oct 04, 2019 4:36 pm

Use of the CPU cache is automatic. The hardware itself handles that. It would be a mistake, though, to limit hash size to the hardware cache.

The most important thing for search speed is not nps but branching factor. If you want the fastest search, the best place to spend effort is branching factor. If you run Stockfish against a pure alpha beta searcher with no other pruning and give the pure alpha beta searcher a machine 100 times faster, at tournament time control, Stockfish would destroy the alpha beta searcher due to better branching factor.
A pure alpha beta searcher has a branching factor of 6 and Stockfish is about 1.5.
Compare the function pow(6,x) with pow(1.5,x) and you will see it is no contest.
Now, a huge, fast cache is nice. But is not the big deal you imagine, at least for chess.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

Joost Buijs
Posts: 990
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: Search speed

Post by Joost Buijs » Fri Oct 04, 2019 6:18 pm

Krzyzstof probably means n/s speed, lowering the branching factor increases search depth but not search speed. Lowering the branching factor helps to make the engine tactically stronger, engines with a very low branching factor play a silly kind of chess, they don't give much (if anything) away, they are just waiting for the opponent to make a tactical error. Positionally they are not very clever, maybe time to spend more effort in the evaluation function instead of the branching factor.

Dann Corbit
Posts: 10205
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Search speed

Post by Dann Corbit » Fri Oct 04, 2019 7:07 pm

I guess it was Kenny Rogers who said it best, "... knowing what to throw away and knowing what to keep ..."
That is the gist of search, as I see it.

If you want to find the vein of gold in the mountain, you follow the flakes in the stream.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

dragontamer5788
Posts: 172
Joined: Thu Jun 06, 2019 6:05 pm
Full name: Percival Tiglao

Re: Search speed

Post by dragontamer5788 » Mon Oct 07, 2019 8:17 pm

Can anyone write the code that would use to search in the processor AMD - L1 cache size and L2 cache size. I mean it would be the best and greatest search in kN/s
Fundamentally, I think that kN/s is the wrong metric. "Practical" is about "Time to Depth" (searching ply 10 faster). Even then, maybe time-to-depth is bad (since all different search algorithms throw away different parts of the tree). Stockfish will reach ply 30 at times, but it isn't an exhaustive search... while an exhaustive search to ply 10 would be way harder than what Stockfish does.

Ultimately, people care about one thing: playing strength. That is "Elo", or the probability of winning (or losing) matches.

Dann Corbit
Posts: 10205
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Search speed

Post by Dann Corbit » Tue Oct 08, 2019 2:11 am

dragontamer5788 wrote:
Mon Oct 07, 2019 8:17 pm
Can anyone write the code that would use to search in the processor AMD - L1 cache size and L2 cache size. I mean it would be the best and greatest search in kN/s
Fundamentally, I think that kN/s is the wrong metric. "Practical" is about "Time to Depth" (searching ply 10 faster). Even then, maybe time-to-depth is bad (since all different search algorithms throw away different parts of the tree). Stockfish will reach ply 30 at times, but it isn't an exhaustive search... while an exhaustive search to ply 10 would be way harder than what Stockfish does.

Ultimately, people care about one thing: playing strength. That is "Elo", or the probability of winning (or losing) matches.
I think that ultimately, search speed is very hard to measure.
The Elo notion can partly capture it, but consider NN engines. They have very low NPS and very high Elo.
The problem with a simple time to depth measurement is that you can make an engine prune too much and get very good TTD.
An example are some of the ExChess versions, which had the fastest TTD of any engines, but were not as strong as others which achieved the same depth in more time.

I guess that in reality the main thing we want to measure is Elo.

But search is incredibly important in this regard. Improvements to things like eval only give linear increase. All the incredible leaps and bounds are from search innovations.

If we can lower the branching factor without significantly hurting the accuracy, then that is a major win.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

Krzysztof Grzelak
Posts: 816
Joined: Tue Jul 15, 2014 10:47 am

Re: Search speed

Post by Krzysztof Grzelak » Sat Oct 12, 2019 6:48 am

We didn't understand each other a bit. Still, thank you for the answers.

Dann Corbit
Posts: 10205
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Search speed

Post by Dann Corbit » Sat Oct 12, 2019 6:53 am

Well, DDR5 memory is out now. It not be a big deal
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

Krzysztof Grzelak
Posts: 816
Joined: Tue Jul 15, 2014 10:47 am

Re: Search speed

Post by Krzysztof Grzelak » Sat Oct 12, 2019 6:59 am

Dann Corbit wrote:
Sat Oct 12, 2019 6:53 am
Well, DDR5 memory is out now. It not be a big deal
I didn't write about DDR5.

Dann Corbit
Posts: 10205
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Search speed

Post by Dann Corbit » Sat Oct 12, 2019 7:26 am

Cache, ddr5, none of it matters.
Linear speedup is um... Linear
Your focus is on the pretty body and not the incredible mind
Imo, ymmv
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

Post Reply