Manhattan distance

    Keywords: Theory, Go term

Manhattan distance is a measure of the distance between two vertices used in computer go. It is determined as the number of horizontal and vertical steps one has to take to go from one stone to another.

Manhattan path  

For example, the diagram shows the path from B1 to B3. A Manhattan resident has to make 4 steps to get from one stone to another. The underlying geometry is called [ext] taxicab geometry. (For more information read the book Taxicab Geometry by Eugene F. Krause, published by Dover in 1987. ISBN 0-486-25202-7. [ext] Amazon)

An additional requirement can be set, demanding that the opponent's stones are never touched along the path.

(Sebastian:) But this would not be Manhattan distance anymore. Maybe Bronx distance?

Tas: Manhattan distance with traffic jams...

A Circle with Radius 9 in Taxicab Geometry  

A "circle" is defined as the set of all points that have the same distance from a given point.

Fhayashi: Presumably, the name reflects the fact that in modern urban cities with orthogonal streets, regardless of the straight-line distance between two points, the practical distance is the number of block-sides you must transit to get to your destination...

Velobici: The concept is discussed on detail in the book [ext] Taxicab Geometry by Eugene Krause.

The Manhattan distance is between 2 stone on an empty board, but what is when the board is filled with enemy stones ?

Distance 9 with a White wall  

Manhattan distance could be argued to be a natural measure of distance between stones the following way (solid connections all the way isn't very natural in Go): Let's say that stones connected solidly, diagonally, or by one point jump are all practically uncuttably connected to each other. Keima is not, because it is far more commonly cut than one point jumps. The distance between two points would be the minimum number of these moves required to connect one to the other. This results in "circles" like this:

You can connect any of the marked points to the center stone with 3 solid, diagonal or one point jump moves, and no less.  

If dx is the horizontal distance, dy the vertical distance, M(dx, dy) the Manhattan distance and C(dx, dy) the "natural connection distance" described above, then C(dx, dy) = ceil(M(dx, dy)/2). Since C(dx, dy) can be obtained from Manhattan distance by halving it and rounding up, the Manhattan distance contains strictly more information than it does. As seen on the board, the C(dx, dy) = 3 circle is the combination of the M(dx, dy) = 5 and M(dx, dy) = 6 circles; one does not lose anything by distinguishing distance twice as finely.

The relation between M and C is easily proved: M(dx, dy) = dx+dy by definition, and C(dx, dy) = min(dx, dy)+ceil(|dx-dy|/2) because it's optimal to use diagonal moves as long as possible, then one-point jumps and finally an extension if needed. Basic arithmetic leads to M(dx, dy) = 2min(dx, dy)+|dx-dy| and ceil(M(dx, dy)/2) = min(dx, dy)+ceil(|dx-dy|/2) = C(dx, dy).

Manhattan distance last edited by on October 31, 2015 - 13:52
RecentChanges · StartingPoints · About
Edit page ·Search · Related · Page info · Latest diff
[Welcome to Sensei's Library!]
Search position
Page history
Latest page diff
Partner sites:
Go Teaching Ladder
Login / Prefs
Sensei's Library