Alphabeta on top of Engine cluster

[dangi12012]

How would a Pseudocode alphabeta search work if evaluation is only done by child processes. In other words if eval() is a call to a running engine with setpos fen - go depth xy.

Could this be parallelized?
In other words i am looking for a search algo thats so generic that the movegen is done by the server - and the eval is done by a cluster of isready uci waiting engines.

This would make clustering much easier since piping stdio over a network literally has no effort to implement.

Lets not discuss problems like latency - but how would the Pseudocode look like?

[Sopel]

AB won't work like that because it's sequential. This needs either some form of MCTS like PUCT where you can form batches, or lazy SMP with exchanging TT entries between nodes, like stockfish cluster version does for example.

[dangi12012]

AB won't work like that because it's sequential. This needs either some form of MCTS like PUCT where you can form batches, or lazy SMP with exchanging TT entries between nodes, like stockfish cluster version does for example.

Ah another one of your troll attemps. There is a whole 10000 view thread about how to parallelize AB. It works but not too well.

As I said im not interested in discussing problems but only Pseudocode. How would AB look like in its simplest form?

[AndrewGrant]

AB won't work like that because it's sequential. This needs either some form of MCTS like PUCT where you can form batches, or lazy SMP with exchanging TT entries between nodes, like stockfish cluster version does for example.

Ah another one of your troll attemps. There is a whole 10000 view thread about how to parallelize AB. It works but not too well.

As I said im not interested in discussing problems but only Pseudocode. How would AB look like in its simplest form?

So you don't know how AB looks in its simpliest form (wikipedia), yet you feel confident in flaming someone?

[jtwright]

The advantage of alpha-beta over vanilla minimax is the ability to communicate information about your analysis of, say, move 1 to make your analysis of move 2 more efficient. And like minimax, it's depth-first by nature. You can't assign a score to a node until you've visited all of its (relevant) children/descendants.

You could forgo this at the top level if you wanted and, say, divide up the root movelist and hand them to a set of worker threads (effectively doing multiple alpha-beta searches, rather than one unifed one), but I'm skeptical you could extend this concept down arbitrarily while still doing alpha-beta.

[amanjpro]

AB won't work like that because it's sequential. This needs either some form of MCTS like PUCT where you can form batches, or lazy SMP with exchanging TT entries between nodes, like stockfish cluster version does for example.

Ah another one of your troll attemps. There is a whole 10000 view thread about how to parallelize AB. It works but not too well.

As I said im not interested in discussing problems but only Pseudocode. How would AB look like in its simplest form?

Baseless accusation? Where is the trolling in his reply? If you keep posting your baseless reply, best not to reply at all

[R. Tomasi]

The advantage of alpha-beta over vanilla minimax is the ability to communicate information about your analysis of, say, move 1 to make your analysis of move 2 more efficient. And like minimax, it's depth-first by nature. You can't assign a score to a node until you've visited all of its (relevant) children/descendants.

You could forgo this at the top level if you wanted and, say, divide up the root movelist and hand them to a set of worker threads (effectively doing multiple alpha-beta searches, rather than one unifed one), but I'm skeptical you could extend this concept down arbitrarily while still doing alpha-beta.

You could try to do it for all-nodes only. But I really doubt you will get big improvements... as you (and others) already pointed out to Daniel, in AB nodes are sequentially dependent. Not only does a node require information from nodes that have been inspected earlier, but also the choice of these nodes matters - that's why we sort them. By just searching them all in parallel you might (in some pathological cases) even end up taking a longer time, because you search more nodes in each thread than you do in total with a vanilla ab-search.

[brianr]

How would a Pseudocode alphabeta search work if evaluation is only done by child processes. In other words if eval() is a call to a running engine with setpos fen - go depth xy.

Could this be parallelized?
In other words i am looking for a search algo thats so generic that the movegen is done by the server - and the eval is done by a cluster of isready uci waiting engines.

This would make clustering much easier since piping stdio over a network literally has no effort to implement.

Lets not discuss problems like latency - but how would the Pseudocode look like?

It works, but not very well.
See: https://www.chessprogramming.org/ChessBrain

[dangi12012]

So to keep the discussion going: If not AB on top of engines. (like I understand that this is alogrithmically serial because it depends on sorting and expanding only the best node at any given time).

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

No one posted simple pseudocode yet. What search algorithm lends itself to parallelism and converges towards the perfect outcome?

Its really just about replacing EVAL() with a call to waiting engines. This is 100% game agnostic because movegen and eval are handled by external software. You could have a program with a TT and other goodies inside that works for ANY type of nonrandom branching game. Eval and Movegen is outsourced.

That software could be improved independent of engines.
My question is. If not AB what search algo fits best for a "Many cores architecture?"

Also I dont get it since Stockfish also performs better with 256 Threads than with 128 than with 1. So what is going on?

[dangi12012]

How is SF Multithreaded then?
Maybe it was wrong to ask about AB to begin with.

What algorithm is best for multithreaded scenarios?
https://www.chessprogramming.org/Parallel_Search

I need the expert knowledge in this forum because the wiki mentions 20 algos or so.