Basic Search Question

[Werewolf]

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?

[GregNeto]

no, it does not work this way:

best explanations:

https://www.chessprogramming.org/Alpha-Beta

https://en.wikipedia.org/wiki/Alpha-beta_pruning (with animated examples)

[chrisw]

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]

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?

[chrisw]

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?

Correct. I look back and keep seeing appalling spellings. iPhone spelchek disease.

[Dann Corbit]

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?

The average branch factor using alpha-beta is c*SQRT(mobility) where C is a constant, and a large one if your move ordering is not perfect.

If you want to understand Alpha-Beta, read this:
http://www.seanet.com/~brucemo/topics/alphabeta.htm

[tmokonen]

If you want to understand Alpha-Beta, read this:
http://www.seanet.com/~brucemo/topics/alphabeta.htm

The link doesn't work any more, but it is archived:

http://web.archive.org/web/200802160306 ... habeta.htm

[Angrim]

alpha-beta can get your average branching factor down to around 6-8 with great move ordering, since it alternates trying all moves at one depth with trying just the one move needed to refute that move at the next depth. And since it only discards moves that are proven to not affect the final score it never causes a mistake. To get branching factor down to 3 you are having to discard a lot of moves that are "probably" not going to change the score, but not proven, so sometimes it causes a mistake but on average the higher depth makes up for the occasional oversight.