25,161
edits
Changes
Created page with "'''Home * Evaluation * Mobility''' FILE:SamuelBakQuiteClear.jpg|border|right|thumb|link=http://chgs.elevator.umn.edu/asset/viewAsset/57f3b6787d58ae5f74bf8..."
'''[[Main Page|Home]] * [[Evaluation]] * Mobility'''
[[FILE:SamuelBakQuiteClear.jpg|border|right|thumb|link=http://chgs.elevator.umn.edu/asset/viewAsset/57f3b6787d58ae5f74bf8ba9#57f3b6d77d58ae5574bf8bcb| [[Arts#Bak|Samual Bak]], Quite Clear <ref>[http://chgs.elevator.umn.edu/asset/viewAsset/57f3b6787d58ae5f74bf8ba9#57f3b6d77d58ae5574bf8bcb Chess in the Art of Samuel Bak], [http://chgs.elevator.umn.edu/ Center for Holocaust & Genocide Studies], [https://en.wikipedia.org/wiki/University_of_Minnesota University of Minnesota]</ref> <ref>The mountain in the background looks like [https://en.wikipedia.org/wiki/Torghatten Torghatten] near [https://en.wikipedia.org/wiki/Br%C3%B8nn%C3%B8ysund Brønnøysund]</ref> ]]
'''Mobility''',<br/>
a measure of the number of choices ([[Legal Move|legal moves]]) a player has in a given position. It is often used as a term in the evaluation function of chess programs. It is based on the idea that the more choices you have at your disposal, the stronger your position. A study by [[Eliot Slater]] of 350 tournament games in which the material balance was still even after the 20th move showed a definite correlation between a player's mobility and the number of games won <ref>[[Eliot Slater]] ('''1950'''). ''[http://www.eliotslater.org/index.php/chess/147-statistics-for-the-chess-computer-and-the-factor-of-mobility Statistics for the Chess Computer and the Factor of Mobility]''. Proceedings of the Symposium on Information Theory, London. Reprinted ('''1988''') in [[Computer Chess Compendium]], pp. 113-117. Including the [http://www.eliotslater.org/index.php/chess/159-discussion-on-the-above-paper-alan-turing-et-al-1950 transcript of a discussion] with [[Alan Turing]] and [[Jack Good]]</ref> .
=Calculating Mobility=
In computer programs, mobility is sometimes calculated differently than simply by summing up the number of [[Legal Move|legal]] or [[Pseudo-Legal Move|pseudo-legal moves]]. Often, it is done piece-by-piece, and the mobility bonus per possible move is not always the same for each type of piece (e.g., in the opening, the mobility of the [[Bishop|bishops]] and [[Knight|knights]] is more important than that of the [[Rook|rooks]]). Sometimes forward mobility is scored higher than backward mobility, sometimes (in case of rooks) vertical mobility gets priority over horizontal mobility. Also, if a piece can move to the square of another friendly piece, sometimes that move is also counted - although it would not be a legal move, it is protecting the friendly piece, and therefore still serves a useful role.
==Safe Mobility==
A couple of programs evaluates so-called '''safe mobility''' - counting only squares where a piece can move without being [[En prise]]. This might be quite expensive, unless a program already keeps [[Incremental Updates|incrementally updated]] [[Attack and Defend Maps|attack tables]]. In some cases, most notably in case of a knight, a middle-of-the-ground approach, not counting [[Square Control|squares controlled]] by enemy pawns, seems best.
<span id="Papa"></span>
==Papa's Entropy==
Notes by [[Tony Marsland]] on ''[[WCCC 1974|The World Computer-Chess Championship]]'' by [[Jean Hayes Michie|Hayes]] and [[David Levy|Levy]] <ref>[[Jean Hayes Michie|Jean E. Hayes]], [[David Levy]] ('''1976'''). ''[http://www.getcited.org/pub/101724802 The world computer chess championship, Stockholm 1974]''. University Press (Edinburgh) ISBN 0852242859</ref> <ref>[http://webdocs.cs.ualberta.ca/~tony/Public/Awit-Wita-ComputerChess/Wita-base/WitaNotes/wita-awit%2319-box2.pdf wita-awit#19-box2.pdf] from [http://webdocs.cs.ualberta.ca/~tony/Public/Awit-Wita-ComputerChess/Wita-base/WitaNotes/ Wita Notes] by [[Tony Marsland]]</ref> <ref>[https://en.wikipedia.org/wiki/Entropy_in_thermodynamics_and_information_theory Entropy in thermodynamics and information theory from Wikipedia]</ref> :
[[Freedom]] and [[Papa]] both use [[Mobility|mobility]] as their primary term in their [[Evaluation function|evaluation functions]]. As with [[Awit|Wita]], both use the ratio of computer's moves / opponent moves. Papa and Wita also multiply by the ratio of the [[Square Control|squares controlled]] and Papa goes one step further and takes the [https://en.wikipedia.org/wiki/Logarithm logarithm] of this product to form the "[[Papa#Entropy|entropy]]" of the position. The true merit of this entropy over the product ratio was not made clear, but it does ensure that in extreme situations the evaluation remains more closely bounded.
<span id="TheValueofReachingaSquare"></span>
=The Value of Reaching a Square=
[[Dan Heisman]] <ref>[[Dan Heisman]] ('''1990, 1999, 2010, 2015''').''[http://www.danheisman.com/elements-of-positional-evaluation.html The Positional Elements of Chess]''. Russell Enterprises</ref> represents an attempt at mathematical abstraction applied to chess, introducing seven concepts as fundamental in analyzing a chess position: mobility, flexibility, vulnerability, [[Center Control|center control]], piece coordination, time and speed. Heisman applies two [https://en.wikipedia.org/wiki/Dichotomy dichotomies]: ''actual'' versus ''potential'' and ''local'' versus ''global'':
{| class="wikitable"
|-
!
! local
! global
|-
! actual
| style="text-align:center;" | Single moves<br/>from this position
| style="text-align:center;" | All reachable squares</br/>from this position
|-
! potential
| style="text-align:center;" | Single moves<br/>on an empty board
| style="text-align:center;" | All reachable squares<br/>on an empty board
|}
[[Distance]] as generalization of mobility and unification of Heisman's notions was introduced by [[Robert Levinson]] and [[Richard Snyder]] in the famous 1993 [[ICGA Journal#16_3|ICCA Journal, Vol. 16, No. 3]] <ref>[[Robert Levinson]], [[Richard Snyder]] ('''1993'''). ''DISTANCE: Toward the Unification of Chess Knowledge''. [[ICGA Journal#16_3|ICCA Journal, Vol. 16, No. 3]]</ref> . Abstract and excerpt:
This article suggests a new approach to computer chess. A graph-theoretic representation of chess knowledge, uniformly based on a single mathematical abstraction, DISTANCE, is described. Most of the traditional forms of [[Knowledge|chess knowledge]], it is shown, can be formalized in this new representation. In addition to comparing this approach to others, the article gives some experimental results and suggests how the new representation may be unified with existing approaches.
The DISTANCE idea is based on exploring a [[Pieces|piece's]] mobility graph to determine what is close to and what is close to it. From a DISTANCE standpoint, [[Moves|moves]] on the [[Chessboard|chess-board]] are only considered good if they result in improved movement graphs for the mover's pieces and/or inferior ones for the opponent's pieces. Often, a good chess-player will move a piece, not to improve the attacking chances of that piece but rather the attacking chances of the piece behind it.
<span id="MobilityWithBitboards"></span>
=Mobility with Bitboards=
For programs using [[Bitboards]], piece mobility can be calculated very quickly either by [[Population Count]] or a [[SIMD and SWAR Techniques|SIMD-wise]] kind of [[SSE2#SSE2dotproduct|weighted population count]]. Similar to [[Sliding Piece Attacks#AttacksbyOccupancyLookup|Attacks by Occupancy Lookup]] to determine attack sets of sliding pieces, one may use pre-calculated population count or even center-weighted population count as a rough estimate on piece mobility. However it does not consider subsets of let say safe target squares. Most strong chess programs use a mobility calculation as part of the positional evaluation in some way. This approach is taken to the extremes in case of [[OliThink]] - a chess engine whose evaluation consists entirely of [[Material|material]] balance and mobility.
<span id="ProgressiveMobility"></span>
=Progressive Mobility=
[[Fill Algorithms|Fill approaches]], like [[Dumb7Fill]] or [[Kogge-Stone Algorithm|Kogge-Stone algorithm]] are great to determine target sets one may reach in two or more moves, which population or weighted population might be considered as progressive mobility in some kind of positions <ref>[[John L. Jerz]] ('''2008, 2013'''). ''[http://www.johnljerz.com/superduper/tlxdownloadsiteMAIN/id80.html A Proposed Heuristic for a Computer Chess Program]''.</ref> . Another application in late [[Endgame|endings]] is to determine whether a piece may [[Control of Stop and Telestop|control a decisive stop or telestop]] of a [[Passed Pawn|passed pawn]] in time. [[All Shortest Paths|Path finding]] algorithms for various pieces may be applied to find so called [[Trajectory|Trajectories]] <ref>[[Boris Stilman]] ('''1994'''). ''A Linguistic Geometry of the Chess Model''. [[Advances in Computer Chess 7]], [http://www.stilman-strategies.com/bstilman/boris_papers/Jour94_CHESS7.pdf pdf draft]</ref> <ref>[[Boris Stilman]] ('''2000'''). ''Linguistic Geometry - From Search to Construction (Operations Research/Computer Science Interfaces Series)''. [http://www.amazon.com/Linguistic-Geometry-Construction-Operations-Interfaces/dp/0792377389/ref=sr_1_1?ie=UTF8&s=books&qid=1257674191&sr=1-1 amazon.com]</ref> .
=Quotes=
==Alan Turing==
Quote by [[Alan Turing]] on [[Eliot Slater|Slater's]] 1950 paper ''Statistics for the Chess Computer and the Factor of Mobility''. <ref>[[Eliot Slater]] ('''1950'''). ''[http://www.eliotslater.org/index.php/chess/147-statistics-for-the-chess-computer-and-the-factor-of-mobility Statistics for the Chess Computer and the Factor of Mobility]''. Proceedings of the Symposium on Information Theory, London. Reprinted ('''1988''') in [[Computer Chess Compendium]], pp. 113-117. Including the [http://www.eliotslater.org/index.php/chess/159-discussion-on-the-above-paper-alan-turing-et-al-1950 transcript of a discussion] with [[Alan Turing]] and [[Jack Good]]</ref>:
I wish to make two points concerning Dr. Slater's paper. I was greatly interested by the statistics provided, but fear that some people might draw invalid conclusions from them. It might for instance be thought that a good way of playing is to maximize one's mobility at one's next move, or perhaps to minimize that of one's opponent at his next move but one. It is evidently not feasible to foresee mobilities many moves ahead. Although the immediate mobility is a useful measure of the relative advantage of the players in normal play it by no means follows that it is wise to direct one's play to maximizing such a measure. To do so would be like taking a statistical analysis of the laundry of men in various positions and deciding, from the data collected, that an infallible method of getting ahead in life was to send a large number of shirts to the wash each week.
==Eliot Slater==
[[Eliot Slater]] in reply <ref>[[Computer Chess Compendium]], pp. 115-117. Discussion on Dr. E. Slater's paper</ref> :
Dr. Turing's argument by analogy what a naive laundry worker might conclude about ways of becoming rich really amounts to the suggestion that strategic advantage is the cause rather than the product of an advantage in mobility. I do not think that this can be accepted. An advantage in mobility usually appears in a game a number of moves before strategic advantage is detectable in other ways; it seems to be an essential aspect of what chess-players understand by "development"; and it supplies the decisive criterion of winning or losing.
=See also=
* [[Blockade]]
* [[Center Control]]
* [[Connectivity]]
* [[CPW-Engine_eval]]
* [[Influence Quantity of Pieces]]
* [[Pin]]
* [[Population Count]] of [[Bitboards]]
: [[CDC Cyber#Mobility|Mobility in Chess 4.6]]
* [[Search with Random Leaf Values]]
* [[Space]]
* [[Square Control]]
* [[Strategy]]
* [[Trapped Pieces]]
=Publications=
==1949 ...==
* [[Claude Shannon]] ('''1949'''). ''[http://www.pi.infn.it/%7Ecarosi/chess/shannon.txt Programming a Computer for Playing Chess]''. [http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf pdf] from [[The Computer History Museum]]
* [[Eliot Slater]] ('''1950'''). ''[http://www.eliotslater.org/index.php/chess/147-statistics-for-the-chess-computer-and-the-factor-of-mobility Statistics for the Chess Computer and the Factor of Mobility]''. Proceedings of the Symposium on Information Theory, London. Reprinted ('''1988''') in [[Computer Chess Compendium]], pp. 113-117. Including the [http://www.eliotslater.org/index.php/chess/159-discussion-on-the-above-paper-alan-turing-et-al-1950 transcript of a discussion] with [[Alan Turing]] and [[Jack Good]]
* [[Adriaan de Groot]] ('''1965, 1978'''). ''Thought and Choice in Chess''. Mouton & Co Publishers, The Hague, The Netherlands. [http://www.amazon.com/gp/reader/9027979146/ref=sib_dp_pt#reader-link amazon], [http://books.google.com/books?vid=ISBN9789053569986 google] <ref>Quotes by [[Adriaan de Groot]]: "... one of the important characteristics of a chess position is the number of possibilities available, i.e., the player's freedom of choice", as mentioned in [[Dap Hartmann]] ('''1987'''). ''How to Extract Relevant Knowledge from Grandmaster Games. Part 2: the Notion of Mobility, and the Work of De Groot and Slater''. [[ICGA Journal#10_2|ICCA Journal, Vol. 10, No. 2]]: "De Groot did not consider in-check positions, so imposing ''De Groot Mobility'' as a distinct norm" </ref>
==1980 ...==
* [[Dap Hartmann]] ('''1987'''). ''How to Extract Relevant Knowledge from Grandmaster Games. Part 2: the Notion of Mobility, and the Work of De Groot and Slater''. [[ICGA Journal#10_2|ICCA Journal, Vol. 10, No. 2]]
* [[Jan Eric Larsson]] ('''1987'''). ''Challenging that Mobility is Fundamental''. [[ICGA Journal#10_3|ICCA Journal, Vol. 10, No. 3]]
==1990 ...==
* [[Dan Heisman]] ('''1990, 1999, 2010, 2015''').''[http://www.danheisman.com/elements-of-positional-evaluation.html The Positional Elements of Chess]''. Russell Enterprises
* [[Chrilly Donninger]] ('''1992'''). ''The Relation of Mobility, Strategy and the Mean Dead Rabbit in Chess''. [[3rd Computer Olympiad#Workshop|Heuristic Programming in AI 3]]
* [[Robert Levinson]], [[Richard Snyder]] ('''1993'''). ''Distance: Toward the Unification of Chess Knowledge''. [[ICGA Journal#16_3|ICCA Journal, Vol. 16, No. 3]]
* [[Jonathan Allen]], [[Edward Hamilton]], [[Robert Levinson]] ('''1997'''). ''New Advances in Adaptive Pattern-Oriented Chess''. [[Advances in Computer Chess 8]]
==2000 ...==
* [[Mark Levene]], [[Trevor Fenner]] ('''2001'''). ''The Effect of Mobility on Minimaxing of Game Trees with Random Leaf Values''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 130, No. 1, Review in [[ICGA Journal#24_4|ICGA Journal, Vol. 24, No. 4]], [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.21.6342&rep=rep1&type=pdf pdf]
* [[John L. Jerz]] ('''2008, 2013'''). ''[http://www.johnljerz.com/superduper/tlxdownloadsiteMAIN/id80.html A Proposed Heuristic for a Computer Chess Program]''.
=Forum Posts=
==1993 ...==
* [https://groups.google.com/d/msg/rec.games.chess/au2AlGf7T30/jgAq306Bix4J deriving piece values from mobility] by [[Barney Pell]], [[Computer Chess Forums|rgc]], August 09, 1993
* [https://groups.google.com/d/msg/rec.games.chess/6vwtkcF6sRU/4M3oOiDNYwgJ Mobility Measure: Proposed Algorithm] by Dietrich Kappe, [[Computer Chess Forums|rgc]], September 23, 1993
==1995 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/aeb03d37e406bf27 Playing for position (mobility)] by S.Read, [[Computer Chess Forums|rgcc]], September 29, 1995
: [http://groups.google.com/group/rec.games.chess.computer/msg/6d07c745072dc611 Re: Playing for position (mobility)] by [[Peter Mysliwietz]], [[Computer Chess Forums|rgcc]], October 02, 1995 » [[Mobility]] in [[Zugzwang (Program)|Zugzwang]]
* [https://groups.google.com/d/msg/rec.games.chess.computer/47bgYzU2kyQ/-dkD4FhigHYJ Re: Incoporating chess knowledge in chess programs] by [[Bruce Moreland]], [[Computer Chess Forums|rgcc]], June 28, 1996 » [[Search with Random Leaf Values]]
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/a589e61aa33f271 Mobility in evaluation functions- how much is it worth?] by [[Tom King]], [[Computer Chess Forums|rgcc]], June 07, 1997
* [https://www.stmintz.com/ccc/index.php?id=12388 Mobility in eval] by [[Will Singleton|Willie Wood]], [[CCC]], November 24, 1997
==2000 ...==
* [https://groups.google.com/d/msg/rec.games.chess.computer/yZP38jTDewQ/WTcajkky4kgJ Mobility in chess engines] by [[Jean-François Gazet]], [[Computer Chess Forums|rgcc]], May 11, 2003
* [https://www.stmintz.com/ccc/index.php?id=340896 piece mobility?] by [[Daniel Shawul]], [[CCC]], January 08, 2004
* [https://www.stmintz.com/ccc/index.php?id=347567 An idea: Offensive and defensive mobility] by [[Tord Romstad]], [[CCC]], February 06, 2004
==2005 ...==
* [https://www.stmintz.com/ccc/index.php?id=404397 Mobility] by [[David B. Weller]], [[CCC]], January 06, 2005
* [https://www.stmintz.com/ccc/index.php?id=474550 Mobility in Chess Evaluation Function at terminal-nodes] by [[Stuart Cracraft]], [[CCC]], December 28, 2005
* [https://www.stmintz.com/ccc/index.php?id=480043 Re: CCC Retirement], [[Robert Hyatt]] on Mobility, [[CCC]], January 16, 2006
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6823 Magic and precomputation] by [[Onno Garms]], [[Computer Chess Forums|Winboard Programming Forum]], September 23, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=19273 The limits of "Just-mobility-evaluation"] by [[Oliver Brausch]], [[CCC]], January 29, 2008
* [https://groups.google.com/d/msg/rec.games.chess.computer/Ab9uA1-8Hlw/UjT_JXTiHuIJ Random number mobility scores] by Guest, [[Computer Chess Forums|rgcc]], September 20, 2008 » [[Search with Random Leaf Values]]
* [http://www.talkchess.com/forum/viewtopic.php?p=234786 future mobility evaluation term] by [[Stuart Cracraft]], [[CCC]], December 01, 2008
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=36307 mobility evaluation of stockfish] by [[Uri Blass]], [[CCC]], October 09, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=38084 Attack and mobility evaluation in chess variants] by [[Evert Glebbeek]], [[CCC]], February 15, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=43527 Mobility eval] by [[Harm Geert Muller]], [[CCC]], May 01, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=47497 static mobility(Q&D)] by [[Harm Geert Muller]], [[CCC]], March 13, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48841 Safe spatial mobility] by [[Lyudmil Tsvetkov]], [[CCC]], August 04, 2013
* [http://talkchess.com/forum/viewtopic.php?start=20&t=49687&topic_view=threads Re: Engine results: a surprise!] by [[Harm Geert Muller]], [[CCC]], October 18, 2013
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=56360 mobility score] by [[Colin Jenkins]], [[CCC]], May 15, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=61284 Bishop Mobility ?] by [[Henk van den Belt]], [[CCC]], August 31, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61693 Mobility Evaluation ?] by [[Mahmoud Uthman]], [[CCC]], October 12, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=64645 Safe mobility?] by [[J. Wesley Cleveland]], [[CCC]], July, 18, 2017
=External Links=
* [https://en.wikipedia.org/wiki/Mobility Mobility from Wikipedia]
* [https://en.wikibooks.org/wiki/Chess_Strategy/Mobility Chess Strategy/Mobility - Wikibooks]
* [http://radagast.se/othello/bitmob.c bitboard mobility] Copyright (c) 2003, [[Gunnar Andersson]] » [[Othello]]
=References=
<references />
'''[[Evaluation|Up one level]]'''
[[FILE:SamuelBakQuiteClear.jpg|border|right|thumb|link=http://chgs.elevator.umn.edu/asset/viewAsset/57f3b6787d58ae5f74bf8ba9#57f3b6d77d58ae5574bf8bcb| [[Arts#Bak|Samual Bak]], Quite Clear <ref>[http://chgs.elevator.umn.edu/asset/viewAsset/57f3b6787d58ae5f74bf8ba9#57f3b6d77d58ae5574bf8bcb Chess in the Art of Samuel Bak], [http://chgs.elevator.umn.edu/ Center for Holocaust & Genocide Studies], [https://en.wikipedia.org/wiki/University_of_Minnesota University of Minnesota]</ref> <ref>The mountain in the background looks like [https://en.wikipedia.org/wiki/Torghatten Torghatten] near [https://en.wikipedia.org/wiki/Br%C3%B8nn%C3%B8ysund Brønnøysund]</ref> ]]
'''Mobility''',<br/>
a measure of the number of choices ([[Legal Move|legal moves]]) a player has in a given position. It is often used as a term in the evaluation function of chess programs. It is based on the idea that the more choices you have at your disposal, the stronger your position. A study by [[Eliot Slater]] of 350 tournament games in which the material balance was still even after the 20th move showed a definite correlation between a player's mobility and the number of games won <ref>[[Eliot Slater]] ('''1950'''). ''[http://www.eliotslater.org/index.php/chess/147-statistics-for-the-chess-computer-and-the-factor-of-mobility Statistics for the Chess Computer and the Factor of Mobility]''. Proceedings of the Symposium on Information Theory, London. Reprinted ('''1988''') in [[Computer Chess Compendium]], pp. 113-117. Including the [http://www.eliotslater.org/index.php/chess/159-discussion-on-the-above-paper-alan-turing-et-al-1950 transcript of a discussion] with [[Alan Turing]] and [[Jack Good]]</ref> .
=Calculating Mobility=
In computer programs, mobility is sometimes calculated differently than simply by summing up the number of [[Legal Move|legal]] or [[Pseudo-Legal Move|pseudo-legal moves]]. Often, it is done piece-by-piece, and the mobility bonus per possible move is not always the same for each type of piece (e.g., in the opening, the mobility of the [[Bishop|bishops]] and [[Knight|knights]] is more important than that of the [[Rook|rooks]]). Sometimes forward mobility is scored higher than backward mobility, sometimes (in case of rooks) vertical mobility gets priority over horizontal mobility. Also, if a piece can move to the square of another friendly piece, sometimes that move is also counted - although it would not be a legal move, it is protecting the friendly piece, and therefore still serves a useful role.
==Safe Mobility==
A couple of programs evaluates so-called '''safe mobility''' - counting only squares where a piece can move without being [[En prise]]. This might be quite expensive, unless a program already keeps [[Incremental Updates|incrementally updated]] [[Attack and Defend Maps|attack tables]]. In some cases, most notably in case of a knight, a middle-of-the-ground approach, not counting [[Square Control|squares controlled]] by enemy pawns, seems best.
<span id="Papa"></span>
==Papa's Entropy==
Notes by [[Tony Marsland]] on ''[[WCCC 1974|The World Computer-Chess Championship]]'' by [[Jean Hayes Michie|Hayes]] and [[David Levy|Levy]] <ref>[[Jean Hayes Michie|Jean E. Hayes]], [[David Levy]] ('''1976'''). ''[http://www.getcited.org/pub/101724802 The world computer chess championship, Stockholm 1974]''. University Press (Edinburgh) ISBN 0852242859</ref> <ref>[http://webdocs.cs.ualberta.ca/~tony/Public/Awit-Wita-ComputerChess/Wita-base/WitaNotes/wita-awit%2319-box2.pdf wita-awit#19-box2.pdf] from [http://webdocs.cs.ualberta.ca/~tony/Public/Awit-Wita-ComputerChess/Wita-base/WitaNotes/ Wita Notes] by [[Tony Marsland]]</ref> <ref>[https://en.wikipedia.org/wiki/Entropy_in_thermodynamics_and_information_theory Entropy in thermodynamics and information theory from Wikipedia]</ref> :
[[Freedom]] and [[Papa]] both use [[Mobility|mobility]] as their primary term in their [[Evaluation function|evaluation functions]]. As with [[Awit|Wita]], both use the ratio of computer's moves / opponent moves. Papa and Wita also multiply by the ratio of the [[Square Control|squares controlled]] and Papa goes one step further and takes the [https://en.wikipedia.org/wiki/Logarithm logarithm] of this product to form the "[[Papa#Entropy|entropy]]" of the position. The true merit of this entropy over the product ratio was not made clear, but it does ensure that in extreme situations the evaluation remains more closely bounded.
<span id="TheValueofReachingaSquare"></span>
=The Value of Reaching a Square=
[[Dan Heisman]] <ref>[[Dan Heisman]] ('''1990, 1999, 2010, 2015''').''[http://www.danheisman.com/elements-of-positional-evaluation.html The Positional Elements of Chess]''. Russell Enterprises</ref> represents an attempt at mathematical abstraction applied to chess, introducing seven concepts as fundamental in analyzing a chess position: mobility, flexibility, vulnerability, [[Center Control|center control]], piece coordination, time and speed. Heisman applies two [https://en.wikipedia.org/wiki/Dichotomy dichotomies]: ''actual'' versus ''potential'' and ''local'' versus ''global'':
{| class="wikitable"
|-
!
! local
! global
|-
! actual
| style="text-align:center;" | Single moves<br/>from this position
| style="text-align:center;" | All reachable squares</br/>from this position
|-
! potential
| style="text-align:center;" | Single moves<br/>on an empty board
| style="text-align:center;" | All reachable squares<br/>on an empty board
|}
[[Distance]] as generalization of mobility and unification of Heisman's notions was introduced by [[Robert Levinson]] and [[Richard Snyder]] in the famous 1993 [[ICGA Journal#16_3|ICCA Journal, Vol. 16, No. 3]] <ref>[[Robert Levinson]], [[Richard Snyder]] ('''1993'''). ''DISTANCE: Toward the Unification of Chess Knowledge''. [[ICGA Journal#16_3|ICCA Journal, Vol. 16, No. 3]]</ref> . Abstract and excerpt:
This article suggests a new approach to computer chess. A graph-theoretic representation of chess knowledge, uniformly based on a single mathematical abstraction, DISTANCE, is described. Most of the traditional forms of [[Knowledge|chess knowledge]], it is shown, can be formalized in this new representation. In addition to comparing this approach to others, the article gives some experimental results and suggests how the new representation may be unified with existing approaches.
The DISTANCE idea is based on exploring a [[Pieces|piece's]] mobility graph to determine what is close to and what is close to it. From a DISTANCE standpoint, [[Moves|moves]] on the [[Chessboard|chess-board]] are only considered good if they result in improved movement graphs for the mover's pieces and/or inferior ones for the opponent's pieces. Often, a good chess-player will move a piece, not to improve the attacking chances of that piece but rather the attacking chances of the piece behind it.
<span id="MobilityWithBitboards"></span>
=Mobility with Bitboards=
For programs using [[Bitboards]], piece mobility can be calculated very quickly either by [[Population Count]] or a [[SIMD and SWAR Techniques|SIMD-wise]] kind of [[SSE2#SSE2dotproduct|weighted population count]]. Similar to [[Sliding Piece Attacks#AttacksbyOccupancyLookup|Attacks by Occupancy Lookup]] to determine attack sets of sliding pieces, one may use pre-calculated population count or even center-weighted population count as a rough estimate on piece mobility. However it does not consider subsets of let say safe target squares. Most strong chess programs use a mobility calculation as part of the positional evaluation in some way. This approach is taken to the extremes in case of [[OliThink]] - a chess engine whose evaluation consists entirely of [[Material|material]] balance and mobility.
<span id="ProgressiveMobility"></span>
=Progressive Mobility=
[[Fill Algorithms|Fill approaches]], like [[Dumb7Fill]] or [[Kogge-Stone Algorithm|Kogge-Stone algorithm]] are great to determine target sets one may reach in two or more moves, which population or weighted population might be considered as progressive mobility in some kind of positions <ref>[[John L. Jerz]] ('''2008, 2013'''). ''[http://www.johnljerz.com/superduper/tlxdownloadsiteMAIN/id80.html A Proposed Heuristic for a Computer Chess Program]''.</ref> . Another application in late [[Endgame|endings]] is to determine whether a piece may [[Control of Stop and Telestop|control a decisive stop or telestop]] of a [[Passed Pawn|passed pawn]] in time. [[All Shortest Paths|Path finding]] algorithms for various pieces may be applied to find so called [[Trajectory|Trajectories]] <ref>[[Boris Stilman]] ('''1994'''). ''A Linguistic Geometry of the Chess Model''. [[Advances in Computer Chess 7]], [http://www.stilman-strategies.com/bstilman/boris_papers/Jour94_CHESS7.pdf pdf draft]</ref> <ref>[[Boris Stilman]] ('''2000'''). ''Linguistic Geometry - From Search to Construction (Operations Research/Computer Science Interfaces Series)''. [http://www.amazon.com/Linguistic-Geometry-Construction-Operations-Interfaces/dp/0792377389/ref=sr_1_1?ie=UTF8&s=books&qid=1257674191&sr=1-1 amazon.com]</ref> .
=Quotes=
==Alan Turing==
Quote by [[Alan Turing]] on [[Eliot Slater|Slater's]] 1950 paper ''Statistics for the Chess Computer and the Factor of Mobility''. <ref>[[Eliot Slater]] ('''1950'''). ''[http://www.eliotslater.org/index.php/chess/147-statistics-for-the-chess-computer-and-the-factor-of-mobility Statistics for the Chess Computer and the Factor of Mobility]''. Proceedings of the Symposium on Information Theory, London. Reprinted ('''1988''') in [[Computer Chess Compendium]], pp. 113-117. Including the [http://www.eliotslater.org/index.php/chess/159-discussion-on-the-above-paper-alan-turing-et-al-1950 transcript of a discussion] with [[Alan Turing]] and [[Jack Good]]</ref>:
I wish to make two points concerning Dr. Slater's paper. I was greatly interested by the statistics provided, but fear that some people might draw invalid conclusions from them. It might for instance be thought that a good way of playing is to maximize one's mobility at one's next move, or perhaps to minimize that of one's opponent at his next move but one. It is evidently not feasible to foresee mobilities many moves ahead. Although the immediate mobility is a useful measure of the relative advantage of the players in normal play it by no means follows that it is wise to direct one's play to maximizing such a measure. To do so would be like taking a statistical analysis of the laundry of men in various positions and deciding, from the data collected, that an infallible method of getting ahead in life was to send a large number of shirts to the wash each week.
==Eliot Slater==
[[Eliot Slater]] in reply <ref>[[Computer Chess Compendium]], pp. 115-117. Discussion on Dr. E. Slater's paper</ref> :
Dr. Turing's argument by analogy what a naive laundry worker might conclude about ways of becoming rich really amounts to the suggestion that strategic advantage is the cause rather than the product of an advantage in mobility. I do not think that this can be accepted. An advantage in mobility usually appears in a game a number of moves before strategic advantage is detectable in other ways; it seems to be an essential aspect of what chess-players understand by "development"; and it supplies the decisive criterion of winning or losing.
=See also=
* [[Blockade]]
* [[Center Control]]
* [[Connectivity]]
* [[CPW-Engine_eval]]
* [[Influence Quantity of Pieces]]
* [[Pin]]
* [[Population Count]] of [[Bitboards]]
: [[CDC Cyber#Mobility|Mobility in Chess 4.6]]
* [[Search with Random Leaf Values]]
* [[Space]]
* [[Square Control]]
* [[Strategy]]
* [[Trapped Pieces]]
=Publications=
==1949 ...==
* [[Claude Shannon]] ('''1949'''). ''[http://www.pi.infn.it/%7Ecarosi/chess/shannon.txt Programming a Computer for Playing Chess]''. [http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf pdf] from [[The Computer History Museum]]
* [[Eliot Slater]] ('''1950'''). ''[http://www.eliotslater.org/index.php/chess/147-statistics-for-the-chess-computer-and-the-factor-of-mobility Statistics for the Chess Computer and the Factor of Mobility]''. Proceedings of the Symposium on Information Theory, London. Reprinted ('''1988''') in [[Computer Chess Compendium]], pp. 113-117. Including the [http://www.eliotslater.org/index.php/chess/159-discussion-on-the-above-paper-alan-turing-et-al-1950 transcript of a discussion] with [[Alan Turing]] and [[Jack Good]]
* [[Adriaan de Groot]] ('''1965, 1978'''). ''Thought and Choice in Chess''. Mouton & Co Publishers, The Hague, The Netherlands. [http://www.amazon.com/gp/reader/9027979146/ref=sib_dp_pt#reader-link amazon], [http://books.google.com/books?vid=ISBN9789053569986 google] <ref>Quotes by [[Adriaan de Groot]]: "... one of the important characteristics of a chess position is the number of possibilities available, i.e., the player's freedom of choice", as mentioned in [[Dap Hartmann]] ('''1987'''). ''How to Extract Relevant Knowledge from Grandmaster Games. Part 2: the Notion of Mobility, and the Work of De Groot and Slater''. [[ICGA Journal#10_2|ICCA Journal, Vol. 10, No. 2]]: "De Groot did not consider in-check positions, so imposing ''De Groot Mobility'' as a distinct norm" </ref>
==1980 ...==
* [[Dap Hartmann]] ('''1987'''). ''How to Extract Relevant Knowledge from Grandmaster Games. Part 2: the Notion of Mobility, and the Work of De Groot and Slater''. [[ICGA Journal#10_2|ICCA Journal, Vol. 10, No. 2]]
* [[Jan Eric Larsson]] ('''1987'''). ''Challenging that Mobility is Fundamental''. [[ICGA Journal#10_3|ICCA Journal, Vol. 10, No. 3]]
==1990 ...==
* [[Dan Heisman]] ('''1990, 1999, 2010, 2015''').''[http://www.danheisman.com/elements-of-positional-evaluation.html The Positional Elements of Chess]''. Russell Enterprises
* [[Chrilly Donninger]] ('''1992'''). ''The Relation of Mobility, Strategy and the Mean Dead Rabbit in Chess''. [[3rd Computer Olympiad#Workshop|Heuristic Programming in AI 3]]
* [[Robert Levinson]], [[Richard Snyder]] ('''1993'''). ''Distance: Toward the Unification of Chess Knowledge''. [[ICGA Journal#16_3|ICCA Journal, Vol. 16, No. 3]]
* [[Jonathan Allen]], [[Edward Hamilton]], [[Robert Levinson]] ('''1997'''). ''New Advances in Adaptive Pattern-Oriented Chess''. [[Advances in Computer Chess 8]]
==2000 ...==
* [[Mark Levene]], [[Trevor Fenner]] ('''2001'''). ''The Effect of Mobility on Minimaxing of Game Trees with Random Leaf Values''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 130, No. 1, Review in [[ICGA Journal#24_4|ICGA Journal, Vol. 24, No. 4]], [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.21.6342&rep=rep1&type=pdf pdf]
* [[John L. Jerz]] ('''2008, 2013'''). ''[http://www.johnljerz.com/superduper/tlxdownloadsiteMAIN/id80.html A Proposed Heuristic for a Computer Chess Program]''.
=Forum Posts=
==1993 ...==
* [https://groups.google.com/d/msg/rec.games.chess/au2AlGf7T30/jgAq306Bix4J deriving piece values from mobility] by [[Barney Pell]], [[Computer Chess Forums|rgc]], August 09, 1993
* [https://groups.google.com/d/msg/rec.games.chess/6vwtkcF6sRU/4M3oOiDNYwgJ Mobility Measure: Proposed Algorithm] by Dietrich Kappe, [[Computer Chess Forums|rgc]], September 23, 1993
==1995 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/aeb03d37e406bf27 Playing for position (mobility)] by S.Read, [[Computer Chess Forums|rgcc]], September 29, 1995
: [http://groups.google.com/group/rec.games.chess.computer/msg/6d07c745072dc611 Re: Playing for position (mobility)] by [[Peter Mysliwietz]], [[Computer Chess Forums|rgcc]], October 02, 1995 » [[Mobility]] in [[Zugzwang (Program)|Zugzwang]]
* [https://groups.google.com/d/msg/rec.games.chess.computer/47bgYzU2kyQ/-dkD4FhigHYJ Re: Incoporating chess knowledge in chess programs] by [[Bruce Moreland]], [[Computer Chess Forums|rgcc]], June 28, 1996 » [[Search with Random Leaf Values]]
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/a589e61aa33f271 Mobility in evaluation functions- how much is it worth?] by [[Tom King]], [[Computer Chess Forums|rgcc]], June 07, 1997
* [https://www.stmintz.com/ccc/index.php?id=12388 Mobility in eval] by [[Will Singleton|Willie Wood]], [[CCC]], November 24, 1997
==2000 ...==
* [https://groups.google.com/d/msg/rec.games.chess.computer/yZP38jTDewQ/WTcajkky4kgJ Mobility in chess engines] by [[Jean-François Gazet]], [[Computer Chess Forums|rgcc]], May 11, 2003
* [https://www.stmintz.com/ccc/index.php?id=340896 piece mobility?] by [[Daniel Shawul]], [[CCC]], January 08, 2004
* [https://www.stmintz.com/ccc/index.php?id=347567 An idea: Offensive and defensive mobility] by [[Tord Romstad]], [[CCC]], February 06, 2004
==2005 ...==
* [https://www.stmintz.com/ccc/index.php?id=404397 Mobility] by [[David B. Weller]], [[CCC]], January 06, 2005
* [https://www.stmintz.com/ccc/index.php?id=474550 Mobility in Chess Evaluation Function at terminal-nodes] by [[Stuart Cracraft]], [[CCC]], December 28, 2005
* [https://www.stmintz.com/ccc/index.php?id=480043 Re: CCC Retirement], [[Robert Hyatt]] on Mobility, [[CCC]], January 16, 2006
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6823 Magic and precomputation] by [[Onno Garms]], [[Computer Chess Forums|Winboard Programming Forum]], September 23, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=19273 The limits of "Just-mobility-evaluation"] by [[Oliver Brausch]], [[CCC]], January 29, 2008
* [https://groups.google.com/d/msg/rec.games.chess.computer/Ab9uA1-8Hlw/UjT_JXTiHuIJ Random number mobility scores] by Guest, [[Computer Chess Forums|rgcc]], September 20, 2008 » [[Search with Random Leaf Values]]
* [http://www.talkchess.com/forum/viewtopic.php?p=234786 future mobility evaluation term] by [[Stuart Cracraft]], [[CCC]], December 01, 2008
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=36307 mobility evaluation of stockfish] by [[Uri Blass]], [[CCC]], October 09, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=38084 Attack and mobility evaluation in chess variants] by [[Evert Glebbeek]], [[CCC]], February 15, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=43527 Mobility eval] by [[Harm Geert Muller]], [[CCC]], May 01, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=47497 static mobility(Q&D)] by [[Harm Geert Muller]], [[CCC]], March 13, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48841 Safe spatial mobility] by [[Lyudmil Tsvetkov]], [[CCC]], August 04, 2013
* [http://talkchess.com/forum/viewtopic.php?start=20&t=49687&topic_view=threads Re: Engine results: a surprise!] by [[Harm Geert Muller]], [[CCC]], October 18, 2013
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=56360 mobility score] by [[Colin Jenkins]], [[CCC]], May 15, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=61284 Bishop Mobility ?] by [[Henk van den Belt]], [[CCC]], August 31, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61693 Mobility Evaluation ?] by [[Mahmoud Uthman]], [[CCC]], October 12, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=64645 Safe mobility?] by [[J. Wesley Cleveland]], [[CCC]], July, 18, 2017
=External Links=
* [https://en.wikipedia.org/wiki/Mobility Mobility from Wikipedia]
* [https://en.wikibooks.org/wiki/Chess_Strategy/Mobility Chess Strategy/Mobility - Wikibooks]
* [http://radagast.se/othello/bitmob.c bitboard mobility] Copyright (c) 2003, [[Gunnar Andersson]] » [[Othello]]
=References=
<references />
'''[[Evaluation|Up one level]]'''
