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?
Basic Search Question
Moderators: hgm, Rebel, chrisw
-
- Posts: 35
- Joined: Thu Sep 08, 2016 8:07 am
Re: Basic Search Question
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)
best explanations:
https://www.chessprogramming.org/Alpha-Beta
https://en.wikipedia.org/wiki/Alpha-beta_pruning (with animated examples)
-
- Posts: 4346
- Joined: Tue Apr 03, 2012 4:28 pm
Re: Basic Search Question
they all get searched
no, all will 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?
BF = average branching factor, the emphasis on average.
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?
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.
-
- Posts: 1814
- Joined: Thu Sep 18, 2008 10:24 pm
Re: Basic Search Question
chrisw wrote: ↑Tue Sep 15, 2020 2:28 pmthey all get searchedno, all will 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?
BF = average branching factor, the emphasis on average.
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?
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?
-
- Posts: 4346
- Joined: Tue Apr 03, 2012 4:28 pm
Re: Basic Search Question
Correct. I look back and keep seeing appalling spellings. iPhone spelchek disease.Werewolf wrote: ↑Tue Sep 15, 2020 4:00 pmchrisw wrote: ↑Tue Sep 15, 2020 2:28 pmthey all get searchedno, all will 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?
BF = average branching factor, the emphasis on average.
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?
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?
-
- Posts: 12568
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Basic Search Question
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.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?
If you want to understand Alpha-Beta, read this:
http://www.seanet.com/~brucemo/topics/alphabeta.htm
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
-
- Posts: 1301
- Joined: Sun Mar 12, 2006 6:46 pm
- Location: Kelowna
- Full name: Tony Mokonen
Re: Basic Search Question
The link doesn't work any more, but it is archived: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
http://web.archive.org/web/200802160306 ... habeta.htm
-
- Posts: 97
- Joined: Mon Jun 25, 2012 10:16 pm
- Location: Forks, WA
- Full name: Ben Nye
Re: Basic Search Question
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.