25,161
edits
Changes
Created page with "'''Home * Search * Score * Centipawns''' FILE:Centipede.jpg|border|right|thumb|Centipede <ref>Centipede in peat [https://en.wikipedia.org/wiki/Wetland..."
'''[[Main Page|Home]] * [[Search]] * [[Score]] * Centipawns'''
[[FILE:Centipede.jpg|border|right|thumb|Centipede <ref>Centipede in peat [https://en.wikipedia.org/wiki/Wetland marshlands] of [https://en.wikipedia.org/wiki/Kawai_Nui_Marsh Kawai Nui], [https://en.wikipedia.org/wiki/Oahu O'ahu], [https://en.wikipedia.org/wiki/Hawaii Hawai'i] photographed by [https://en.wikipedia.org/wiki/User:Marshman Eric Guinther], [https://en.wikipedia.org/wiki/Centipede Centipede from Wikipedia]</ref> ]]
'''Centipawns''', (Centi-pawns)<br/>
a score unit which corresponds approximately to '''one hundredth''' of a [[Pawn Advantage, Win Percentage, and Elo|pawn unit]]. [https://en.wikipedia.org/wiki/Fixed-point_arithmetic Fixed point] representation with centipawn fractions allows a smooth relation of all [[Point Value|piece values]] with a reasonable granularity to distinguish positional scores. 16 or even 15 bits are sufficient to store signed centipawn ranges in [[Hash Table|hash tables]], while sign extension to the common 32-bit integer range is convenient to avoid overflows in scaling terms like in the [[Tapered Eval|tapered eval]], even with an internal finer granularity used inside the evaluation <ref>[http://www.talkchess.com/forum/viewtopic.php?t=29694&start=10 Re: Centipawns and Millipawns] by [[Don Dailey]], [[CCC]], September 08, 2009</ref> .
=Quotes=
==Robert Hyatt==
[[Robert Hyatt]] on score grain in [[Crafty]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=29694&start=14 Re: Centipawns and Millipawns] by [[Robert Hyatt]], [[CCC]], September 09, 2009 </ref>:
Having done all three, my take on the issue is this:
# <code>'''Decipawns''' (0.1) is too coarse. Not every positional consideration is worth 0.1 pawns, so you either have to round the score up to 0.1, or else throw it out since it would be zero.</code>
# <code>'''Millipawns''' (0.001) is too fine. I do not believe that my evaluation has any .001 accuracy ideas in it. As you spread the evaluation scores out, your tree search becomes less efficient (for example, compare a program with no positional scoring to one with, with respect to tree size).</code>
# <code>'''Centipawns''' (0.01) is reasonable. One could make the argument that maybe .05 is better (1/20th of a pawn). Or some other number. But my intuition after trying all three during the development of Crafty is that the right value lies in the interval {0.01, 0.1}. Whether it is on one end or the other, or somewhere in the middle, is a point for conjecture. It is too hard to test the idea, although I suppose I could just do a normal eval and then at the end, reduce it to the accuracy needed. But it is not easy to test for smaller than .01 increments since no increments in crafty would be smaller than .01... </code>
==Aske Plaat==
[[Aske Plaat|Aske Plaat's]] implementation tip on [[MTD(f)]] <ref>[http://people.csail.mit.edu/plaat/mtdf.html MTD(f) - A Minimax Algorithm faster than NegaScout] by [[Aske Plaat]], December 3, 1997</ref>:
The coarser the grain of eval, the less passes [[MTD(f)]] has to make to converge to the minimax value. Some programs have a fine grained evaluation function, where positional knowledge can be worth as little as one hundredth of a pawn. Big score swings can become inefficient for these programs. It may help to dynamically increase the step size: instead of using the previous bound, one can, for example, add an extra few points in the search direction (for failing high, or searching upward, adding the bonus, and for failing low, or searching downward, subtracting the bonus) every two passes or so. ([[Don Dailey]] found that a scheme like this works well in a version of [[Cilkchess]].) At the end, if you overshoot the minimax value, you have to make a small search in the opposite direction, using the previous search bound without an extra bonus, to make the final convergence. Also, it can be quite instructive to experiment with different evaluation function grain sizes. Sometimes coarse grain functions work better than fine grain, both for [[NegaScout]] and MTD(f).
=See also=
* [[Millipawns]]
* [[Pawn Advantage, Win Percentage, and Elo]]
* [[Point Value]]
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=195217 Performance of MTD(f) versus eval granularity?] by Werner Mühlpfordt, [[CCC]], November 01, 2001 » [[MTD(f)]]
* [http://www.talkchess.com/forum/viewtopic.php?t=29694 Centipawns and Millipawns] by Ricardo Gibert, [[CCC]], September 08, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=30695 Winning percentage and centipawns] by [[Luca Hemmerich]], [[CCC]], November 18, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=36389 xboard protocol and centipawn] by [[Joshua Shriver]], [[CCC]], October 17, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=45692 Evaluations in centipawns and symbols] by [[Marek Soszynski]], [[CCC]], October 23, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=61071 Is centipawn the right unit for measuring the score?] by Karol Majewski, [[CCC]], August 09, 2016
=External Links=
* [http://chess.wikia.com/wiki/Centipawn Centipawn - WikiChess]
* [http://en.wiktionary.org/wiki/centi- centi- - Wiktionary]
* [https://en.wikipedia.org/wiki/Centi- Centi- from Wikipedia]
* [https://en.wikipedia.org/wiki/Fixed-point_arithmetic Fixed-point arithmetic from Wikipedia]
* [https://en.wikipedia.org/wiki/Granularity Granularity from Wikipedia]
* [https://en.wikipedia.org/wiki/Resolution Resolution from Wikipedia]
* [https://en.wikipedia.org/wiki/Rounding Rounding from Wikipedia]
* <span id="Centipede"></span>[https://en.wikipedia.org/wiki/Centipede_%28band%29 Centipede] - [https://en.wikipedia.org/wiki/Septober_Energy Septober Energy], 1971 (edited), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: feat. [[Videos#KeithTippett|Keith Tippett]], [[Videos#IanCarr|Ian Carr]], [[Videos#KarlJenkins|Karl Jenkins]], [[Videos#JohnMarshall|John Marshall]], [https://en.wikipedia.org/wiki/Roy_Babbington Roy Babbington], ...
: {{#evu:https://www.youtube.com/watch?v=3wm4Kpb_ygY|alignment=left|valignment=top}}
=References=
<references />
'''[[Score|Up one level]]'''
[[FILE:Centipede.jpg|border|right|thumb|Centipede <ref>Centipede in peat [https://en.wikipedia.org/wiki/Wetland marshlands] of [https://en.wikipedia.org/wiki/Kawai_Nui_Marsh Kawai Nui], [https://en.wikipedia.org/wiki/Oahu O'ahu], [https://en.wikipedia.org/wiki/Hawaii Hawai'i] photographed by [https://en.wikipedia.org/wiki/User:Marshman Eric Guinther], [https://en.wikipedia.org/wiki/Centipede Centipede from Wikipedia]</ref> ]]
'''Centipawns''', (Centi-pawns)<br/>
a score unit which corresponds approximately to '''one hundredth''' of a [[Pawn Advantage, Win Percentage, and Elo|pawn unit]]. [https://en.wikipedia.org/wiki/Fixed-point_arithmetic Fixed point] representation with centipawn fractions allows a smooth relation of all [[Point Value|piece values]] with a reasonable granularity to distinguish positional scores. 16 or even 15 bits are sufficient to store signed centipawn ranges in [[Hash Table|hash tables]], while sign extension to the common 32-bit integer range is convenient to avoid overflows in scaling terms like in the [[Tapered Eval|tapered eval]], even with an internal finer granularity used inside the evaluation <ref>[http://www.talkchess.com/forum/viewtopic.php?t=29694&start=10 Re: Centipawns and Millipawns] by [[Don Dailey]], [[CCC]], September 08, 2009</ref> .
=Quotes=
==Robert Hyatt==
[[Robert Hyatt]] on score grain in [[Crafty]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=29694&start=14 Re: Centipawns and Millipawns] by [[Robert Hyatt]], [[CCC]], September 09, 2009 </ref>:
Having done all three, my take on the issue is this:
# <code>'''Decipawns''' (0.1) is too coarse. Not every positional consideration is worth 0.1 pawns, so you either have to round the score up to 0.1, or else throw it out since it would be zero.</code>
# <code>'''Millipawns''' (0.001) is too fine. I do not believe that my evaluation has any .001 accuracy ideas in it. As you spread the evaluation scores out, your tree search becomes less efficient (for example, compare a program with no positional scoring to one with, with respect to tree size).</code>
# <code>'''Centipawns''' (0.01) is reasonable. One could make the argument that maybe .05 is better (1/20th of a pawn). Or some other number. But my intuition after trying all three during the development of Crafty is that the right value lies in the interval {0.01, 0.1}. Whether it is on one end or the other, or somewhere in the middle, is a point for conjecture. It is too hard to test the idea, although I suppose I could just do a normal eval and then at the end, reduce it to the accuracy needed. But it is not easy to test for smaller than .01 increments since no increments in crafty would be smaller than .01... </code>
==Aske Plaat==
[[Aske Plaat|Aske Plaat's]] implementation tip on [[MTD(f)]] <ref>[http://people.csail.mit.edu/plaat/mtdf.html MTD(f) - A Minimax Algorithm faster than NegaScout] by [[Aske Plaat]], December 3, 1997</ref>:
The coarser the grain of eval, the less passes [[MTD(f)]] has to make to converge to the minimax value. Some programs have a fine grained evaluation function, where positional knowledge can be worth as little as one hundredth of a pawn. Big score swings can become inefficient for these programs. It may help to dynamically increase the step size: instead of using the previous bound, one can, for example, add an extra few points in the search direction (for failing high, or searching upward, adding the bonus, and for failing low, or searching downward, subtracting the bonus) every two passes or so. ([[Don Dailey]] found that a scheme like this works well in a version of [[Cilkchess]].) At the end, if you overshoot the minimax value, you have to make a small search in the opposite direction, using the previous search bound without an extra bonus, to make the final convergence. Also, it can be quite instructive to experiment with different evaluation function grain sizes. Sometimes coarse grain functions work better than fine grain, both for [[NegaScout]] and MTD(f).
=See also=
* [[Millipawns]]
* [[Pawn Advantage, Win Percentage, and Elo]]
* [[Point Value]]
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=195217 Performance of MTD(f) versus eval granularity?] by Werner Mühlpfordt, [[CCC]], November 01, 2001 » [[MTD(f)]]
* [http://www.talkchess.com/forum/viewtopic.php?t=29694 Centipawns and Millipawns] by Ricardo Gibert, [[CCC]], September 08, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=30695 Winning percentage and centipawns] by [[Luca Hemmerich]], [[CCC]], November 18, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=36389 xboard protocol and centipawn] by [[Joshua Shriver]], [[CCC]], October 17, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=45692 Evaluations in centipawns and symbols] by [[Marek Soszynski]], [[CCC]], October 23, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=61071 Is centipawn the right unit for measuring the score?] by Karol Majewski, [[CCC]], August 09, 2016
=External Links=
* [http://chess.wikia.com/wiki/Centipawn Centipawn - WikiChess]
* [http://en.wiktionary.org/wiki/centi- centi- - Wiktionary]
* [https://en.wikipedia.org/wiki/Centi- Centi- from Wikipedia]
* [https://en.wikipedia.org/wiki/Fixed-point_arithmetic Fixed-point arithmetic from Wikipedia]
* [https://en.wikipedia.org/wiki/Granularity Granularity from Wikipedia]
* [https://en.wikipedia.org/wiki/Resolution Resolution from Wikipedia]
* [https://en.wikipedia.org/wiki/Rounding Rounding from Wikipedia]
* <span id="Centipede"></span>[https://en.wikipedia.org/wiki/Centipede_%28band%29 Centipede] - [https://en.wikipedia.org/wiki/Septober_Energy Septober Energy], 1971 (edited), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: feat. [[Videos#KeithTippett|Keith Tippett]], [[Videos#IanCarr|Ian Carr]], [[Videos#KarlJenkins|Karl Jenkins]], [[Videos#JohnMarshall|John Marshall]], [https://en.wikipedia.org/wiki/Roy_Babbington Roy Babbington], ...
: {{#evu:https://www.youtube.com/watch?v=3wm4Kpb_ygY|alignment=left|valignment=top}}
=References=
<references />
'''[[Score|Up one level]]'''
