Page 1 of 1

Basic Search Question

Posted: Tue Sep 15, 2020 12:06 pm
by 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?

Re: Basic Search Question

Posted: Tue Sep 15, 2020 12:19 pm
by 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)

Re: Basic Search Question

Posted: Tue Sep 15, 2020 12:28 pm
by chrisw
Werewolf wrote:
Tue Sep 15, 2020 12: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.

Re: Basic Search Question

Posted: Tue Sep 15, 2020 2:00 pm
by Werewolf
chrisw wrote:
Tue Sep 15, 2020 12:28 pm
Werewolf wrote:
Tue Sep 15, 2020 12: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?

Re: Basic Search Question

Posted: Tue Sep 15, 2020 2:15 pm
by chrisw
Werewolf wrote:
Tue Sep 15, 2020 2:00 pm
chrisw wrote:
Tue Sep 15, 2020 12:28 pm
Werewolf wrote:
Tue Sep 15, 2020 12: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?
Correct. I look back and keep seeing appalling spellings. iPhone spelchek disease.

Re: Basic Search Question

Posted: Wed Sep 16, 2020 10:33 am
by Dann Corbit
Werewolf wrote:
Tue Sep 15, 2020 12: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?
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

Re: Basic Search Question

Posted: Thu Sep 17, 2020 4:50 am
by tmokonen
Dann Corbit wrote:
Wed Sep 16, 2020 10:33 am
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

Re: Basic Search Question

Posted: Fri Sep 18, 2020 4:41 am
by 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.