Alphabeta on top of Engine cluster

[Desperado]

...

Then I was suggested this: https://www.chessprogramming.org/APHID

...

Some time ago ...

forum3/viewtopic.php?f=7&t=78598&p=9112 ... id#p911205

[dangi12012]

...

Then I was suggested this: https://www.chessprogramming.org/APHID

...

Some time ago ...

forum3/viewtopic.php?f=7&t=78598&p=9112 ... id#p911205

So APHID is the best parallel algo?
I dont understand how SF is multithreaded if everyone here says its so impossible except APHID (which SF doesnt use?).

[JohnWoe]

AB is hopelessly serial. It's made parallel by launching threads populating hash table in different depths. So it's parallelized by hash table. Without hash table no parallel. AB sucks. Some monte carlo - algo is the way to go.

[dangi12012]

AB is hopelessly serial. It's made parallel by launching threads populating hash table in different depths. So it's parallelized by hash table. Without hash table no parallel. AB sucks. Some monte carlo - algo is the way to go.

I like montecarlo. It has the nice side effect of being game agnostic as well..

But given 512 waiting engines. What algo is the best for that? Seems to mee that the same parallelisation by different depths works there too?
hashtable and movegen would be maintained by a server. And all the eval would be handled by a cluster.

Advantage: No additional programming required. Also game agnostic since you seperate AB+TT from the acutal engines.

[R. Tomasi]

How is SF Multithreaded then?

Afaik (my information may be out-dated) stockfish uses lazy SMP, which basically means starting all threads on the same node, and since there will be timing differences between them they help each other in populating the transposition table. That really has nothing to do with what you suggest.

There are other algorithms, too, but they all stuggle because AB is intrinsically serial.

[R. Tomasi]

No one posted simple pseudocode yet.

Indeed. Go figure why... (hint: you are asking for something that is impossible).

[Desperado]

...

Then I was suggested this: https://www.chessprogramming.org/APHID

...

Some time ago ...

forum3/viewtopic.php?f=7&t=78598&p=9112 ... id#p911205

So APHID is the best parallel algo?
I dont understand how SF is multithreaded if everyone here says its so impossible except APHID (which SF doesnt use?).

Well, not only SF is multithreaded. Most (advanced) engines today are multithreaded of course.

The fact that AB is basically a serial algorithm does not mean paralism is not possible.
The nature of AB is not optimal for parallel search, that is the point. (This is a completely different conclusion)

If you understand the reason, you will create own ideas and solutions others already had 5,10,20 and 40 years ago.
APHID addresses the synchronization problem that is caused by a serial algorithm. (at least now you should begin to understand).

There are many ways to parallelize AB, all with strong and weak points. Many of them try to speedup AB, but others like Lazy SMP
do not intend to be faster but provide qualitiy gain in the search without explizit sychronization or give more freedom with effect and code complexity.

So, APHID is not the best in any way. But i doubt there is a best in general without a concrete context or existing frame for implementation.

[dangi12012]

How is SF Multithreaded then?

Afaik (my information may be out-dated) stockfish uses lazy SMP, which basically means starting all threads on the same node, and since there will be timing differences between them they help each other in populating the transposition table. That really has nothing to do with what you suggest.

There are other algorithms, too, but they all stuggle because AB is intrinsically serial.

Your information is outdated regarding smp. Why comment that something is impossible. Its like on stackoverflow where 9 people say its impossible and 1 person provides the perfect answer.

[dangi12012]

...

Then I was suggested this: https://www.chessprogramming.org/APHID

...

Some time ago ...

forum3/viewtopic.php?f=7&t=78598&p=9112 ... id#p911205

So APHID is the best parallel algo?
I dont understand how SF is multithreaded if everyone here says its so impossible except APHID (which SF doesnt use?).

Well, not only SF is multithreaded. Most (advanced) engines today are multithreaded of course.

The fact that AB is basically a serial algorithm does not mean paralism is not possible.
The nature of AB is not optimal for parallel search, that is the point. (This is a completely different conclusion)

If you understand the reason, you will create own ideas and solutions others already had 5,10,20 and 40 years ago.
APHID addresses the synchronization problem that is caused by a serial algorithm. (at least now you should begin to understand).

There are many ways to parallelize AB, all with strong and weak points. Many of them try to speedup AB, but others like Lazy SMP
do not intend to be faster but provide qualitiy gain in the search without explizit sychronization or give more freedom with effect and code complexity.

So, APHID is not the best in any way. But i doubt there is a best in general without a concrete context or existing frame for implementation.

Thank you! That was i was looking for.
It seems that for this problem the way to go would be:
- Monte Carlo
- APHID
- The same implementation SF uses for its multithreading approach. (Some people here said its impossible but stockfish uses MT already so....)

Does anyone here know what SF uses internally for its MT magic or is it best to just read the sourcecode?

[Desperado]

...

Then I was suggested this: https://www.chessprogramming.org/APHID

...

Some time ago ...

forum3/viewtopic.php?f=7&t=78598&p=9112 ... id#p911205

So APHID is the best parallel algo?
I dont understand how SF is multithreaded if everyone here says its so impossible except APHID (which SF doesnt use?).

Well, not only SF is multithreaded. Most (advanced) engines today are multithreaded of course.

The fact that AB is basically a serial algorithm does not mean paralism is not possible.
The nature of AB is not optimal for parallel search, that is the point. (This is a completely different conclusion)

If you understand the reason, you will create own ideas and solutions others already had 5,10,20 and 40 years ago.
APHID addresses the synchronization problem that is caused by a serial algorithm. (at least now you should begin to understand).

There are many ways to parallelize AB, all with strong and weak points. Many of them try to speedup AB, but others like Lazy SMP
do not intend to be faster but provide qualitiy gain in the search without explizit sychronization or give more freedom with effect and code complexity.

So, APHID is not the best in any way. But i doubt there is a best in general without a concrete context or existing frame for implementation.

Thank you! That was i was looking for.
It seems that for this problem the way to go would be:
- Monte Carlo
- APHID
- The same implementation SF uses for its multithreading approach. (Some people here said its impossible but stockfish uses MT already so....)

Does anyone here know what SF uses internally for its MT magic or is it best to just read the sourcecode?

Well, you did not listen carefully.

Nobody said that MT is not possible with AB. People told you that AB is a serial algorithm.
They tried to tell you that no algorithm or other magic will change that fact.

Various SMP solutions handle this fact differently.

Finaly i do not know what SF is exactly doing, but it took me two minutes to check the source.
MainThread::search() starts all threads at the same time when the go command is received. My impression at this point is, that it is still using Lazy SMP.