TalkChess.com

Werewolf wrote: ↑Tue Sep 15, 2020 2:06 pm If a standard alpha-beta engine has a branching factor of 3, what does that mean to searching all possible moves at the root position?

For example, suppose a position has 35 legal moves, 10 are interesting and worthy of some analysis. Does it literally mean only 3 possibilities are considered and each possibility gives rise to 3 new possibilities?

I doubt this is the case as it would mean many moves are missed.

Can someone clarify how it works? Is it that it does a wide search near the root and then transforms into something more selective with a BF=3 at a deeper ply level?

chrisw wrote: ↑Tue Sep 15, 2020 2:28 pm

Werewolf wrote: ↑Tue Sep 15, 2020 2:06 pm If a standard alpha-beta engine has a branching factor of 3, what does that mean to searching all possible moves at the root position?

they all get searched

For example, suppose a position has 35 legal moves, 10 are interesting and worthy of some analysis. Does it literally mean only 3 possibilities are considered and each possibility gives rise to 3 new possibilities?

no, all will get searched.

I doubt this is the case as it would mean many moves are missed.

Can someone clarify how it works? Is it that it does a wide search near the root and then transforms into something more selective with a BF=3 at a deeper ply level?

BF = average branching factor, the emphasis on average.

AB works on the principal that at any node in the tree, if a move is searched that “refutes“ the move it replies to, then no more moves from that node need be considered for the simple reason that there’s no point in looking for a “better” refutation, when the one you just found is “good enough”. That’s the B algorithm in AB.
If you omit the B algorithm, you are left with A. Aka minimax search.
AB results in much smaller tree but still returns the same move and score as A. Therefore we use it in preference.

Werewolf wrote: ↑Tue Sep 15, 2020 4:00 pm

chrisw wrote: ↑Tue Sep 15, 2020 2:28 pm

Werewolf wrote: ↑Tue Sep 15, 2020 2:06 pm If a standard alpha-beta engine has a branching factor of 3, what does that mean to searching all possible moves at the root position?

they all get searched

For example, suppose a position has 35 legal moves, 10 are interesting and worthy of some analysis. Does it literally mean only 3 possibilities are considered and each possibility gives rise to 3 new possibilities?

no, all will get searched.

I doubt this is the case as it would mean many moves are missed.

Can someone clarify how it works? Is it that it does a wide search near the root and then transforms into something more selective with a BF=3 at a deeper ply level?

BF = average branching factor, the emphasis on average.

AB works on the principal that at any node in the tree, if a move is searched that “refutes“ the move it replies to, then no more moves from that node need be considered for the simple reason that there’s no point in looking for a “better” refutation, when the one you just found is “good enough”. That’s the B algorithm in AB.
If you omit the B algorithm, you are left with A. Aka minimax search.
AB results in much smaller tree but still returns the same move and score as A. Therefore we use it in preference.

Thanks, super clear.

Presumably the process above keeps repeating per search iteration? So everything is checked a little deeper per iteration and a refutation at ply 3 (say) doesn't permanently discard a move?

Werewolf wrote: ↑Tue Sep 15, 2020 2:06 pm If a standard alpha-beta engine has a branching factor of 3, what does that mean to searching all possible moves at the root position?

For example, suppose a position has 35 legal moves, 10 are interesting and worthy of some analysis. Does it literally mean only 3 possibilities are considered and each possibility gives rise to 3 new possibilities? I doubt this is the case as it would mean many moves are missed.

Can someone clarify how it works? Is it that it does a wide search near the root and then transforms into something more selective with a BF=3 at a deeper ply level?

Dann Corbit wrote: ↑Wed Sep 16, 2020 12:33 pm If you want to understand Alpha-Beta, read this:
http://www.seanet.com/~brucemo/topics/alphabeta.htm