Monday, July 24, 2006

The Game of Nim and a Winning Strategy

Let me introduce the game of Nim. It is a two-person game where there initially are a number of piles with a number of sticks in each pile. A typical initial configuration is 3 piles with 3, 4 and 5 sticks. The players alternately pick a pile from which he or she removes one or more sticks. The player who first removes all the sticks is the winner.

This is all well and simple, but how should you play this game? I remember some years ago when a friend of mine introduced me to this game. He beat me every time. Every single time. I couldn't figure out what the "trick" was. Thinking about it I don't think he actually knew the complete solution to this problem, but his "heuristic" method was apparently good enough to beat me over and over again.

Before continuing, let ⊕ represent the bitwise operator exclusive-or. The result of ab is essentially a normal addition of the binary digits of a and b, but ignoring all carries.

The winning strategy can now be formulated. Let there be n piles with ak sticks in pile k. If a player now, every time it is his/her turn, removes a number of sticks such that a1a2 ⊕ ... ⊕ an = 0, he/she will win.

I think this is quite fascinating. Why is a bitwise operator an essential part of this game? As far as I can tell, there is nothing binary about this game at all. What seems to matter is the fact that ⊕ over the non-negative integers form an Abelian group with 0 as the neutral element and where each element is its own inverse:
  • a ⊕ b = b ⊕ a
  • a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c
  • a ⊕ 0 = 0 ⊕ a = a
  • a ⊕ a = 0
Are these properties what makes ⊕ an essential part of this game? Is ⊕ the only operator that has these properties? I am no expert on Abelian groups, but I doubt it. So what is it? I probably need to study the proofs for this winning strategy more closely. Hmm...

Link: Nim on Wikipedia
(Rumour has it that the Nim game and its winning strategy is also treated in the exercises for Section 7.1.3, Bitwise Tricks and Techniques, of The Art of Computer Programming, Volume 4...)

NASA Apollo Chronicles

I just stumbled across the following cool stories. Included are also a number of nice images.

Episode 1: Dark Shadows.

Episode 2: Jack Skis the Moon.

Episode 3: The Mysterious Smell of Moondust.

Episode 4: Wide Awake on the Sea of Tranquillity.

Sunday, July 16, 2006

What is Latitude, Really?

Having worked some time with GPS-coordinates, I started thinking "what do longitude and latitude really represent?". I mean, some kind of idealized model of the earth must obviously be used, and I was pretty sure it wasn't simply a sphere. Using a sphere would make the concept of longitude and latitude fairly trivial, but it's not a sphere, it's an ellipsoid. And in that case, at least for me, there are several possible answers, at least in the case of latitude. I ended up doing some research and this is what I found out.

Let us start with longitude, since this is the easiest to define. Consider first the plane on which the equator lies. Denote the center of the earth point C (which also lies on this plane). Project now the position of the Royal Greenwich Observatory, Greenwich, England, perpendicularly onto this plane and denote it point G. Finally we take the position, not necessarily at sea level, for which we wish to find the longitude and also project it perpendicularly onto the plane. We denote it P. The angle ρ between the line segments CG and CP is now the longitude.Some details should be noted. First of all, the positive direction of the angle is anti-clockwise when considering the equatorial plane from the north pole. Secondly, we require -π ≤ ρ ≤ π. Of course, degrees are normally used and a 'W' or 'E' is used instead of negative and positive numbers.

What makes longitudes easy to handle is due to the fact that every that every plane cut through the earth, which is parallel to the equatorial plane, makes a cut through the earth's surface which is a perfect circle. This is of course not the case in the "real world", but it is the case for the reference model that is used for modelling the sea level of the earth.

Let us now turn to the real subject, namely latitude. For that we need to take a closer look at the reference model mentioned above. If we make a plane cut through the earth with both the north and south pole lying on this plane, we get an ellipse.
We will denote the semi-major axis (half the largest "diameter") a and the semi-minor axis (half the smallest "diameter") b. According to the WGS 84 standard (the reference model currently used for GPS devices) we have
a = 6378137 m
f = 1 - a/b = 1/298.257223563
where f is the so-called flattening, leading to b ≈ 6356752.3 m.

Let us now consider the following Cartesian coordinate system. The origo is at the center of the earth, the first axis, the r-axis, lies in the equatorial plane and the second axis, the Z-axis, goes in the direction of the north pole. We ignore longitude for the moment, since this is simple rotation about the south-north pole axis, which we can apply afterwards.

The reference ellipse above is easily represented by
r = a cos θ
Z = b sin θ
So is θ simply latitude? No, although it is sometimes called reduced or parametric latitude.

Let us denote the actual angle between the equatorial plane and the line from the center of the earth to the point in question by σ. The relation between σ and θ is easily seen to be
tan σ = (1-f) tan θ
So is σ latitude? No, but it is sometimes called geocentric latitude.

Let us turn to "real" latitude, then. It is commonly called geodetic or atronomical latitude. Imagine standing on the earth's surface, looking in the direction of north. Image furthermore that you can see a star located directly on the line of the poles (Polaris is a good choice). The angle between the direction of the horizon and the direction of the north star is latitude.

In the reference model we do the following. We imagine making a plane cut through the reference ellipsoid containing the position in question and both the north and south pole. In this plane we have our (r,Z)-coordinate system. Let the position be at the earth's surface (or rather, on the surface of the reference ellipsoid) and call it P. If the parametric latitude is θ we see that the direction of the tangent at P is (-a sin θ, b cos θ), so the relation between the geodesic latitude λ and θ is
tan λ = tan θ / (1-f)

Now given geodesic latitude λ we have the position at the earth's surface (in our longitude-plane) as
r = a cos θ
Z = b sin θ
where θ = arctan((1-f) tan λ).
We can rewrite this so we get rid of θ using
cos(arctan(v)) = 1/sqrt(v2 + 1)
sin(arctan(v)) = v/sqrt(v2 + 1)
leading to
r = a K cos λ
Z = b (1-f) K sin λ = a (1-f)2 K sin λ
where K = 1/sqrt((1-f)2 sin2 λ + cos2 λ).

But apart from longitude and latitude there is also height h. Height is to be measured perpendicularly to the tangent plane so our actual position P has the coordinates
r = r + h cos(λ) = (a K + h) cos(λ)
Z = Z + h sin(λ) = (a (1-f)2 K + h) sin(λ)
where K = 1/sqrt((1-f)2 sin2 λ + cos2 λ).

Let us finally collect all the threads. Consider the 3-dimensinal Cartesian coordinate system with origo at the center of the earth, the X-axis lying in the equatorial plane and pointing in the direction of the Greenwich observatory, the Z-axis pointing towards the north pole and the Y-axis completing the coordinate system such that a right-handed orthogonal coordinate system is created. Given longitude ρ, (geodesic) latitude λ and height h, we get
X = r cos(ρ) = (a K + h) cos(λ) cos(ρ)
Y = r sin(ρ) = (a K + h) cos(λ) sin(ρ)
Z = (a (1-f)2 K + h) sin(λ)
where K = 1/sqrt((1-f)2 sin2 λ + cos2 λ).

Left are some interesting questions. Given X, Y and Z, how do we find longitude, latitude and height? This is actually not a simple problem (see this drawing). Another question is how do we calculate the distance between two positions, following the curvature of the earth (and not the Euclidian distance)? Maybe I will get back to these questions in later posts.

Some links:
The Global Positioning System
Spheroid Geometry

Sunday, May 07, 2006

Neural Networks - Let's Not Get Carried Away

Let me start off by saying that, yes, I know that neural networks have been known, and used, for a long time. In fact, neural networks are at least as old as computers.

Their creation was motivated by the way the brain seemed to work with receptors, synapses and what have you. And this is where the problem arises: Since the brain is considered intelligent, neural networks are automatically considered intelligent. I often hear statements such as "using neural networks, we have incorporated artificial intelligence into our software". Neural networks may be the core ingredient of human intelligence, but this does not mean that a software module built around a neural network implies (artificial) intelligent behaviour.

A typical neural network consists of a number of source neurons/nodes (colored green in the example figure), a number of hidden neurons (colored blue) and a number of output neurons/nodes. Given some input values for each of the source nodes, these input signals flow through the network and produce some output values for each of the output nodes. The output is deterministic, mind you, in that the same input values produce the exact same output values.

One of the strengths of neural networks is that they are able to "learn" (here, again, a neural network is given human characteristics although the network may be the smallest and stupidest ever seen). Given some network structure, the parameters of the network (synaptic weights, among other things) can be adjusted in such a way that some known input sets produce output values equal to, or close to, some corresponding output sets.

So we have a structure that, given some input, produces some output, and the parameters of the system can be adjusted such that certain input values correspond to certain output values. The first of these characteristics is simply that of a mathematical function. The second concerns that of curve fitting. And this is my point: A neural network is nothing more than a (complex) mathematical function, for which you, given some data sets, carry out curve fitting/optimization.

Some simple neural network with two input values x and y and an output value z may correpond to the function z(x,y) = a x2 + b y, and exercising supervised learning could simply be question of adjusting a and b such that z1 = z(x1, y1) and z2 = z(x2, y2).

This is of course a somewhat simplistic view. First of all, it will typically be close to impossible to explicitly write up a closed form that represents some given neural network. And even if you could, the process of adjusting the parameters of the system/function so that some wellness of fit function was optimized, given some data sets, would most likely be very difficult. And this is what makes neural networks superior in some situations. Their ability to learn, or adjust its parameters, in a fairly simple way during some learning process.

So neural networks can no doubt be used with great success in a lot of applications. My point is simply that they represent nothing more than a (complex) mathematical function, that can be fitted to some input/output sets. Whether people will call this (artificial) intelligent behaviour is clearly another discussion, but in most cases I will claim that there is nothing intelligent about it...