25,161
edits
Changes
Created page with "'''Home * Search * Alpha-Beta * Odd-Even Effect''' FILE:Odd even.png|border|right|thumb||Odd Numbers and Even Numbers <ref>Image by TNSENesamaniTpr, J..."
'''[[Main Page|Home]] * [[Search]] * [[Alpha-Beta]] * Odd-Even Effect'''
[[FILE:Odd even.png|border|right|thumb||Odd Numbers and Even Numbers <ref>Image by TNSENesamaniTpr, July 06, 2017, [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
The '''Odd-Even Effect''' of [[Alpha-Beta]] is caused by the topology of the [[Search Tree#MinimalGameTree|minimal game tree]] of uniform [[Depth|depth]] '''n''' and [[Branching Factor|branching factor]] '''b'''. [[Michael Levin]] found the formula of the number of [[Leaf Node|leaf nodes]], which was published in [[Daniel Edwards|Edwards']] and [[Timothy Hart|Hart's]] 1961 Alpha-Beta paper <ref>[[Daniel Edwards]], [[Timothy Hart]], ('''1961'''). ''The Alpha-Beta Heuristic''. AIM-030, available from [http://dspace.mit.edu/handle/1721.1/6098 DSpace] at [[Massachusetts Institute of Technology|MIT]]</ref> .
=Even Leaves=
2b<span style="vertical-align: super;">n/2</span> - 1
=Odd Leaves=
b<span style="vertical-align: super;">(n+1)/2</span> + b<span style="vertical-align: super;">(n-1)/2</span> - 1
=Node Types=
Number of Leaf nodes of a certain [[Node Types|Node type]] at depth n <ref>[http://www.talkchess.com/forum/viewtopic.php?t=48205 CUT/ALL nodes ratio] by [[Daniel Shawul]], [[CCC]], June 06, 2013</ref>:
'''n = even:'''
PV<span style="vertical-align: sub;">n</span> = 1
CUT<span style="vertical-align: sub;">n</span> = b<span style="vertical-align: super;">n/2</span> - 1 = CUT<span style="vertical-align: sub;">n-1</span>
ALL<span style="vertical-align: sub;">n</span> = b<span style="vertical-align: super;">n/2</span> - 1 = ALL<span style="vertical-align: sub;">n-1</span> + b<span style="vertical-align: super;">n/2</span> - b<span style="vertical-align: super;">(n-2)/2</span>
'''n = odd:'''
PV<span style="vertical-align: sub;">n</span> = 1
CUT<span style="vertical-align: sub;">n</span> = b<span style="vertical-align: super;">(n+1)/2</span> - 1 = CUT<span style="vertical-align: sub;">n-1</span> + b<span style="vertical-align: super;">(n+1)/2</span> + b<span style="vertical-align: super;">(n-1)/2</span>
ALL<span style="vertical-align: sub;">n</span> = b<span style="vertical-align: super;">(n-1)/2</span> - 1 = ALL<span style="vertical-align: sub;">n-1</span>
So for the sum of the Leaf-nodes at depth n as well as the total sum of nodes (including [[Interior Node|interior nodes]]) up to depth n holds
ALL<span style="vertical-align: sub;">n</span> = CUT<span style="vertical-align: sub;">n-1</span>
<span id="Leaves"></span>
=Leaves by Depth=
Assuming a constant [[Branching Factor|branching factor]] of 40, this results in following number of leaves, using the [https://en.wikipedia.org/wiki/Floor_and_ceiling_functions floor and ceiling] formulas :
CUT<span style="vertical-align: sub;">n</span> = b<span style="vertical-align: super;">⌈n/2⌉</span> - 1
ALL<span style="vertical-align: sub;">n</span> = b<span style="vertical-align: super;">⌊n/2⌋</span> - 1
{{Number of Leaves}}
resulting in following
=Leaf Ratios=
'''n = even:'''
[[File:OddEven_EvenFormula.jpg|none|text-bottom]]
'''n = odd:'''
[[File:OddEven_OddFormula.jpg|none|text-bottom]]
=Iterative Deepening=
Inside an [[Iterative Deepening|iterative deepening]] framework, the odd-even effect causes an asymmetry in time usage. Even-odd transitions grow (much) more than odd-even. The effect diminishes due to [[Quiescence Search|quiescence search]] and [[Selectivity|selectivity]] in the upper part of the tree. However, past and recent programs addressed that issue. For instance [[L'Excentrique]] used two [[Ply|ply]] increments <ref>[[Eric Thé]] ('''1992'''). ''[http://digitool.library.mcgill.ca/R/?func=dbin-jump-full&object_id=56753&local_base=GEN01-MCG02 An analysis of move ordering on the efficiency of alpha-beta search]''. Master's thesis, [[McGill University]], advisor [[Monroe Newborn]]</ref>, and [[Bebe]] had no quiescence at all, and searched in two ply increments as well <ref>[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/fb40c7c141dc062a Odd ply versus even ply searches] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], February 28, 1996</ref>. Other programs used fractional plies for [[Extensions#FractionalExtensions|extensions]] <ref>[[David Levy]], [[David Broughton]], and [[Mark Taylor]] ('''1989'''). ''The SEX Algorithm in Computer Chess''. [[ICGA Journal#12_1|ICCA Journal, Vol. 12, No. 1]]</ref> and [[Iterative Deepening|ID]] increments.
<span id="ScoreOscillation"></span>
=Score Oscillation=
Additionally, many programs exhibit an effect on the [[Score|score]] based on the [https://en.wikipedia.org/wiki/Parity_%28mathematics%29 parity] of the search depth due to the extra tempo of odd ply searches. Scores are stable when one looks at results from the odd plies only, or even plies only, but are sometimes unstable when they are mixed. One remedial on this odd-even effect is to apply a [[Tempo|tempo bonus]] in [[Evaluation|leaf evaluation]] for the [[Side to move|side to move]].
=See also=
* [[Asymmetric Evaluation]]
* [[Window#MinimaxWall|Minimax Wall]]
* [[Parity Pruning]]
=Forum Posts=
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/fb40c7c141dc062a Odd ply versus even ply searches] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], February 28, 1996 » [[BeBe]]
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/d3e7bdb00afc9dc4 PROG: odd/even score alternance] by [[Rémi Coulom]], [[Computer Chess Forums|rgcc]], June 5, 1997 » [[Tempo]]
* [https://www.stmintz.com/ccc/index.php?id=10903 pv score oscillation] by [[Will Singleton|Willie Wood]], [[CCC]], October 18, 1997
* [http://www.open-chess.org/viewtopic.php?f=5&t=1403 Node counts at a given depth/iteration in search] by [[Mark Watkins|BB+]], [[Computer Chess Forums|OpenChess Forum]], May 23, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=48205 CUT/ALL nodes ratio] by [[Daniel Shawul]], [[CCC]], June 06, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=60262 Asymmetrical evaluation] by [[Laurie Tunnicliffe]], [[CCC]], May 24, 2016 » [[Asymmetric Evaluation]]
=External Links=
* [https://en.wikipedia.org/wiki/Parity_(mathematics) Parity (mathematics) from Wikipedia]
=References=
<references />
'''[[Alpha-Beta|Up one level]]'''
[[FILE:Odd even.png|border|right|thumb||Odd Numbers and Even Numbers <ref>Image by TNSENesamaniTpr, July 06, 2017, [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
The '''Odd-Even Effect''' of [[Alpha-Beta]] is caused by the topology of the [[Search Tree#MinimalGameTree|minimal game tree]] of uniform [[Depth|depth]] '''n''' and [[Branching Factor|branching factor]] '''b'''. [[Michael Levin]] found the formula of the number of [[Leaf Node|leaf nodes]], which was published in [[Daniel Edwards|Edwards']] and [[Timothy Hart|Hart's]] 1961 Alpha-Beta paper <ref>[[Daniel Edwards]], [[Timothy Hart]], ('''1961'''). ''The Alpha-Beta Heuristic''. AIM-030, available from [http://dspace.mit.edu/handle/1721.1/6098 DSpace] at [[Massachusetts Institute of Technology|MIT]]</ref> .
=Even Leaves=
2b<span style="vertical-align: super;">n/2</span> - 1
=Odd Leaves=
b<span style="vertical-align: super;">(n+1)/2</span> + b<span style="vertical-align: super;">(n-1)/2</span> - 1
=Node Types=
Number of Leaf nodes of a certain [[Node Types|Node type]] at depth n <ref>[http://www.talkchess.com/forum/viewtopic.php?t=48205 CUT/ALL nodes ratio] by [[Daniel Shawul]], [[CCC]], June 06, 2013</ref>:
'''n = even:'''
PV<span style="vertical-align: sub;">n</span> = 1
CUT<span style="vertical-align: sub;">n</span> = b<span style="vertical-align: super;">n/2</span> - 1 = CUT<span style="vertical-align: sub;">n-1</span>
ALL<span style="vertical-align: sub;">n</span> = b<span style="vertical-align: super;">n/2</span> - 1 = ALL<span style="vertical-align: sub;">n-1</span> + b<span style="vertical-align: super;">n/2</span> - b<span style="vertical-align: super;">(n-2)/2</span>
'''n = odd:'''
PV<span style="vertical-align: sub;">n</span> = 1
CUT<span style="vertical-align: sub;">n</span> = b<span style="vertical-align: super;">(n+1)/2</span> - 1 = CUT<span style="vertical-align: sub;">n-1</span> + b<span style="vertical-align: super;">(n+1)/2</span> + b<span style="vertical-align: super;">(n-1)/2</span>
ALL<span style="vertical-align: sub;">n</span> = b<span style="vertical-align: super;">(n-1)/2</span> - 1 = ALL<span style="vertical-align: sub;">n-1</span>
So for the sum of the Leaf-nodes at depth n as well as the total sum of nodes (including [[Interior Node|interior nodes]]) up to depth n holds
ALL<span style="vertical-align: sub;">n</span> = CUT<span style="vertical-align: sub;">n-1</span>
<span id="Leaves"></span>
=Leaves by Depth=
Assuming a constant [[Branching Factor|branching factor]] of 40, this results in following number of leaves, using the [https://en.wikipedia.org/wiki/Floor_and_ceiling_functions floor and ceiling] formulas :
CUT<span style="vertical-align: sub;">n</span> = b<span style="vertical-align: super;">⌈n/2⌉</span> - 1
ALL<span style="vertical-align: sub;">n</span> = b<span style="vertical-align: super;">⌊n/2⌋</span> - 1
{{Number of Leaves}}
resulting in following
=Leaf Ratios=
'''n = even:'''
[[File:OddEven_EvenFormula.jpg|none|text-bottom]]
'''n = odd:'''
[[File:OddEven_OddFormula.jpg|none|text-bottom]]
=Iterative Deepening=
Inside an [[Iterative Deepening|iterative deepening]] framework, the odd-even effect causes an asymmetry in time usage. Even-odd transitions grow (much) more than odd-even. The effect diminishes due to [[Quiescence Search|quiescence search]] and [[Selectivity|selectivity]] in the upper part of the tree. However, past and recent programs addressed that issue. For instance [[L'Excentrique]] used two [[Ply|ply]] increments <ref>[[Eric Thé]] ('''1992'''). ''[http://digitool.library.mcgill.ca/R/?func=dbin-jump-full&object_id=56753&local_base=GEN01-MCG02 An analysis of move ordering on the efficiency of alpha-beta search]''. Master's thesis, [[McGill University]], advisor [[Monroe Newborn]]</ref>, and [[Bebe]] had no quiescence at all, and searched in two ply increments as well <ref>[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/fb40c7c141dc062a Odd ply versus even ply searches] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], February 28, 1996</ref>. Other programs used fractional plies for [[Extensions#FractionalExtensions|extensions]] <ref>[[David Levy]], [[David Broughton]], and [[Mark Taylor]] ('''1989'''). ''The SEX Algorithm in Computer Chess''. [[ICGA Journal#12_1|ICCA Journal, Vol. 12, No. 1]]</ref> and [[Iterative Deepening|ID]] increments.
<span id="ScoreOscillation"></span>
=Score Oscillation=
Additionally, many programs exhibit an effect on the [[Score|score]] based on the [https://en.wikipedia.org/wiki/Parity_%28mathematics%29 parity] of the search depth due to the extra tempo of odd ply searches. Scores are stable when one looks at results from the odd plies only, or even plies only, but are sometimes unstable when they are mixed. One remedial on this odd-even effect is to apply a [[Tempo|tempo bonus]] in [[Evaluation|leaf evaluation]] for the [[Side to move|side to move]].
=See also=
* [[Asymmetric Evaluation]]
* [[Window#MinimaxWall|Minimax Wall]]
* [[Parity Pruning]]
=Forum Posts=
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/fb40c7c141dc062a Odd ply versus even ply searches] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], February 28, 1996 » [[BeBe]]
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/d3e7bdb00afc9dc4 PROG: odd/even score alternance] by [[Rémi Coulom]], [[Computer Chess Forums|rgcc]], June 5, 1997 » [[Tempo]]
* [https://www.stmintz.com/ccc/index.php?id=10903 pv score oscillation] by [[Will Singleton|Willie Wood]], [[CCC]], October 18, 1997
* [http://www.open-chess.org/viewtopic.php?f=5&t=1403 Node counts at a given depth/iteration in search] by [[Mark Watkins|BB+]], [[Computer Chess Forums|OpenChess Forum]], May 23, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=48205 CUT/ALL nodes ratio] by [[Daniel Shawul]], [[CCC]], June 06, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=60262 Asymmetrical evaluation] by [[Laurie Tunnicliffe]], [[CCC]], May 24, 2016 » [[Asymmetric Evaluation]]
=External Links=
* [https://en.wikipedia.org/wiki/Parity_(mathematics) Parity (mathematics) from Wikipedia]
=References=
<references />
'''[[Alpha-Beta|Up one level]]'''
