Capture the Flag II

I've finished the first programming run for "capture the flag." Right now two teams compete eternally and a counter keeps score of who wins more often.

The field itself consists of four regions:
1. The flag zone: The defending team can't go into it's own flag zone, and is a safe haven for an attacking player.
2. The defending zone: The defender and rescuers hang out here. When the enemy attacker is not in this zone, they just track his y-position, when he is, they go after him.
3. The attacking zone: Here, the attacker forms a vector which is the sum of vectors towards the flag, with vectors away from the defender and attacker, with given weights attached to each.
4. The safe zone: In the safe zone, the defender can not capture the attacker, so the attacker no longer tries to avoid anyone and goes straight for the flag. Once he has it, he makes a dash for it to his own zone.

As of now, the rescuer does absolutely nothing - he has the same instructions as the defender, except he isn't allowed to capture. Instead, when an attacker is captured, he has to do a strange sort of dance: first he has to go to the corner of his own zone, then he has to touch his own flag-holder, and then he starts again.

The system often gets into a "deadlock scenario" in which both players eternally get captured, do their dance, and get captured at the exact same place. This problem could be avoided by imposing a time limit on each round and resetting after it expires (the positions of the players are randomized at the start of each round.)

Here's a video of the program in action:



Before doing the really hard part - the genetic algorithm part, one more programming run is needed, to iron out the kinks. This means:

1. Make the program more modular (i.e. variable number of players for each team)
2. Make a jail (to give the rescuers something to do)
3. Clean up the player logic (there's a lot of ad hoc stuff in there right now to make it work)
4. Add timers etc. and pretty it up a little.
   

For now, the C# code and zipped Visual Studio C# project is located here!

Twinkling Streetlights

If you ever look out over a city on a clear night, like on one of those 'make-out points' from cheesy 80's movies, you notice that distant streetlights seem to flicker and dance around a little, whereas closer ones don't. If your not making out with Winnie Cooper at the time, you inevitably start to wonder why that is the case. Notice that the same thing is seen in the sky: stars twinkle, but planets don't (the ones that wee can see, that is.)

The reason for the "twinkling of the stars" is what is called "atmospheric seeing": the atmosphere has layers of turbulent air of varying density and temperature, which leads to a time-varying index of refraction (The speed of light in a vacuum (outer space, say), divided by the speed of light in the material (air here.)) To see why this would make a star twinkle, recall that a lens is just a material of certain index of refraction, shaped in a certain way so as to focus (or diverge) light. The pockets of air blowing around the atmosphere, means that light from a star would rapidly become focused and unfocused as the air above blows around. This is kind of like the pattern you see on the sand, underneath shallow water: the light jumps around like crazy from being randomly bent at the surface. For water the effect is way more pronounced, since the index of refraction of water is about 1.33, whereas for air it's 1.0003 - just barely different than for a vacuum for which, by definition, it's 1. You can check how bad the current "seeing" is here.

So that's why stars twinkle, but then what about planets? The same "seeing effects" would be present for both planets and stars, but we only notice it for planets (actually, if you look through a telescope at Saturn or the Moon, you really start to notice the effects of seeing on a good night vs. a bad night.) The reason is that to us, stars come from a point in the sky - we can't resolve with our eyes what shape they are or what they look like. All our eyes know is that light is coming from one specific direction. When we see an object, say Winnie Cooper, her left ear is focused to one point on our retina, and her right ear is focused to another. That is, we can resolve the shape of the image. For stars, this is not the case: they're so far away that the left part of the star is totally smeared over with the right part of the star. Because light is wave, it can't be focused to an infinitely small point, the focus is limited (by diffraction) to a certain size, and for stars, this size is much bigger, that the size that they would be focused to on our retina. For planets however, we can make out the shape of them and although each point of the planet is experiencing this seeing effect, all of the combined effects average out into a steady (slightly blurred, if you look through a telescope) image. To verify this, we can to a rough calculation.

The minimum resolvable angular distance between two objects which are sent though a lens with diameter D is: sin(θ) = λ/D times some constant which is close to 1 and depends on the type of wave and the exact shape of the lens. For a plane wave through a perfectly circular lens, it is 1.22. For us, D is the diameter of our pupil, say 5 mm, at night. The wavelength of visible light is on the order of 600nm, so λ/D is about 10^(-4) which means that the minimum angle is about θ = 0.0001 (since sin(θ) is pretty much equal to θ when θ is so small.) Now by definition, sin(θ) = Dia/dist, where Dia is the diameter of the object and dist is the distance to it. We now have a test to see if an object is resolvable or not: if Dia/dist is bigger than 0.0001, it should be, if Dia/dist is much less that 0.0001, it's not (keeping in mind the roughness of the calculation.)

Several cases:

Mars: Dia = 6800 km, dist = 55000000 km, Dia/Dist = 0.00012
i.e It should just be resolvable.

Jupiter: Dia = 140000 km, dist = 700000000 km, Dia/Dist = 0.0002
i.e. Again, in the window of resolvability

α-Centauri (nearest star): Dia: 10^6 km, dist = 2*10^13 km, Dia/Dist = .0000005
=> much less that that of the planets.

Now, bringing this back to the original discussion, say that a street lamp has a diameter of about 10 cm. The distance at which it takes up about the same angle as a planet is: dist = Dia/θ = 1 km. Much farther than this, and the lights become point sources, like the stars. From where I live, the lights at the train-station 1 km from my place don't twinkle, but the lights on the ski-hill, 5 km away do. However, the giant billboards by the hill do not - they have a bigger Dia. and therefor are resolvable. These calculations were pretty rough, but they sketch out the main point - that the "twinkling" of stars and distant lights, stems from them being "point-sources" of light to our eyes.

Capture the flag

I'm interested in programming A.I. Not in an academic sense, but just for kicks. The problem is that I'm a pretty mediocre programmer. Still, the best way to learn anything is to just dive in there and sort out all the confusion (while making hundreds of ridiculously stupid mistakes.)

The language I chose to work with is c#. The reason is that I already know Java programming from my undergraduate days, and it seem pretty similar. Also, I'm now using a windows box, so why not use the nice .NET framework - I really just don't want to worry about the details.

My first program will be a game of capture the flag, in which the computer competes against itself. It won't serve much of a purpose, aside from sitting around and playing with itself all day (if this serves as a "purpose" in life, please let me know.)

I'm a "ground-up" kind of guy, so I'll start with a really bare-bones project and then build on it. My dream-goal for the end result is to have a program that makes use of a genetic algorithm and evolves to the ideal player for the job. My idea is that each player will have a geometric profile that determines it's characteristics such as acceleration, drag (air resistance), agility, and stamina. I'd like to see which characteristics emerge given the constraints of their duties.

The first iteration will have two teams, each consisting of a defender, a rescuer, and an attacker. The defender will hang out around the flag, and chase after the enemy attacker, the rescuer will help defend, until the attacker get captured, and the attacker will go for the flag. Each player is represented as a point. At each "tick" of the clock, each player thinks and determines his or her acceleration, and moves. They'll bounce off a wall if they run into it. The behavior will be determined by their "type":
Attacker: acceleration is sum of vectors towards flag and away from defender.
Defender: acceleration is towards where the attacker will be in 'n' steps.
Rescuer: If the attacker is captured, same as attacker but towards attacker instead of flag. Otherwise, same as defender.

I'll try to post the result of each coding session, whenever I have time to work on it.

Source code for version 0 (plus an addition or two), here but not commented and buggy ... more to come.

Version 0 in action: