Basic Search Question

Discussion of anything and everything relating to chess playing software and machines.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Werewolf
Posts: 1314
Joined: Thu Sep 18, 2008 8:24 pm

Basic Search Question

Post by Werewolf » 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?

GregNeto
Posts: 34
Joined: Thu Sep 08, 2016 6:07 am

Re: Basic Search Question

Post by GregNeto » Tue Sep 15, 2020 12:19 pm

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
Posts: 3824
Joined: Tue Apr 03, 2012 2:28 pm

Re: Basic Search Question

Post by chrisw » 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.

Werewolf
Posts: 1314
Joined: Thu Sep 18, 2008 8:24 pm

Re: Basic Search Question

Post by Werewolf » 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?

chrisw
Posts: 3824
Joined: Tue Apr 03, 2012 2:28 pm

Re: Basic Search Question

Post by chrisw » Tue Sep 15, 2020 2:15 pm

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.

Dann Corbit
Posts: 11622
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Basic Search Question

Post by Dann Corbit » Wed Sep 16, 2020 10:33 am

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
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.

tmokonen
Posts: 1144
Joined: Sun Mar 12, 2006 5:46 pm
Location: Kelowna
Full name: Tony Mokonen
Contact:

Re: Basic Search Question

Post by tmokonen » Thu Sep 17, 2020 4:50 am

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

Angrim
Posts: 89
Joined: Mon Jun 25, 2012 8:16 pm
Location: Forks, WA
Full name: Ben Nye

Re: Basic Search Question

Post by Angrim » Fri Sep 18, 2020 4:41 am

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.

Post Reply