Mobility

From Chessprogramming wiki
Jump to: navigation, search

Home * Evaluation * Mobility

Samuel Bak, Quite Clear [1] [2]

Mobility,
a measure of the number of choices (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 [3] .

Calculating Mobility

In computer programs, mobility is sometimes calculated differently than simply by summing up the number of legal or 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 bishops and knights is more important than that of the 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 incrementally updated attack tables. In some cases, most notably in case of a knight, a middle-of-the-ground approach, not counting squares controlled by enemy pawns, seems best.

Papa's Entropy

Notes by Tony Marsland on The World Computer-Chess Championship by Hayes and Levy [4] [5] [6] :

Freedom and Papa both use mobility as their primary term in their evaluation functions. As with Wita, both use the ratio of computer's moves / opponent moves. Papa and Wita also multiply by the ratio of the squares controlled and Papa goes one step further and takes the logarithm of this product to form the "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. 

The Value of Reaching a Square

Dan Heisman [7] represents an attempt at mathematical abstraction applied to chess, introducing seven concepts as fundamental in analyzing a chess position: mobility, flexibility, vulnerability, center control, piece coordination, time and speed. Heisman applies two dichotomies: actual versus potential and local versus global:

local global
actual Single moves
from this position
All reachable squares
from this position
potential Single moves
on an empty board
All reachable squares
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 ICCA Journal, Vol. 16, No. 3 [8] . 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 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 piece's mobility graph to determine what is close to and what is close to it. From a DISTANCE standpoint, moves on the 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. 

Mobility with Bitboards

For programs using Bitboards, piece mobility can be calculated very quickly either by Population Count or a SIMD-wise kind of weighted population count. Similar to 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 balance and mobility.

Progressive Mobility

Fill approaches, like Dumb7Fill or 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 [9] . Another application in late endings is to determine whether a piece may control a decisive stop or telestop of a passed pawn in time. Path finding algorithms for various pieces may be applied to find so called Trajectories [10] [11] .

Quotes

Alan Turing

Quote by Alan Turing on Slater's 1950 paper Statistics for the Chess Computer and the Factor of Mobility [12] [13]:

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 [14] :

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

Mobility in Chess 4.6

Publications

1949 ...

1980 ...

1990 ...

2000 ...

Forum Posts

1993 ...

1995 ...

Re: Playing for position (mobility) by Peter Mysliwietz, rgcc, October 02, 1995 » Mobility in Zugzwang

2000 ...

2005 ...

2010 ...

2015 ...

2020 ...

External Links

References

  1. Chess in the Art of Samuel Bak, Center for Holocaust & Genocide Studies, University of Minnesota
  2. The mountain in the background looks like Torghatten near Brønnøysund
  3. Eliot Slater (1950). 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 transcript of a discussion with Alan Turing and Jack Good
  4. Jean E. Hayes, David Levy (1976). The world computer chess championship, Stockholm 1974. University Press (Edinburgh) ISBN 0852242859
  5. wita-awit#19-box2.pdf from Wita Notes by Tony Marsland
  6. Entropy in thermodynamics and information theory from Wikipedia
  7. Dan Heisman (1990, 1999, 2010). Elements of Positional Evaluation. Russell Enterprises
  8. Robert Levinson, Richard Snyder (1993). DISTANCE: Toward the Unification of Chess Knowledge. ICCA Journal, Vol. 16, No. 3
  9. John L. Jerz (2008, 2013). A Proposed Heuristic for a Computer Chess Program.
  10. Boris Stilman (1994). A Linguistic Geometry of the Chess Model. Advances in Computer Chess 7, pdf draft
  11. Boris Stilman (2000). Linguistic Geometry - From Search to Construction (Operations Research/Computer Science Interfaces Series). amazon.com
  12. Eliot Slater (1950). 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 transcript of a discussion with Alan Turing and Jack Good
  13. Conference on Information theory, 26-29 September 1950
  14. Computer Chess Compendium, pp. 115-117. Discussion on Dr. E. Slater's paper
  15. 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. ICCA Journal, Vol. 10, No. 2: "De Groot did not consider in-check positions, so imposing De Groot Mobility as a distinct norm"

Up one level