Tim

Here is a little demo of a shadow casting / field of view algorithm I wrote the other day. Enjoy!

Filed under:
Uncategorized by Tim

The telemetry balloon was launch and retrieved successfully, and as all near space launches are, turned out to be quite an adventure. It all started out as a project to find the cheapest / most reliable / easiest to use balloon launch system for high schools to eventually build and build upon. After some searching we came to the conclusion that near space telemetry systems tend to be the greatest investment and should therefore be examined first.

After pouring over the internet and considering various options, the test group was chosen. It consisted of:

1. Byonics MicroTrak AIO: a strong, dependent, long lasting ham radio telemetry system
2. Spot Satellite Messenger: a small, proprietary tracker used commonly by hikers
3. Motorola i290: super small, super lightweight cell phone custom programmed to sample its gps and transmit data to sensor.network

In addition, a Sun SPOT equipped with an SHT15 temp/humidity sensor and a 3-axis magnetometer was sent up.

Launch:

We took off just a bit north of the Mexican border beside a farmer’s field in 95 degree weather.  Things went fairly smoothly, especially considering that we were launching two balloons that day. (We also launched a larger balloon with climate sensors)  The Byonics and SunSPOT were placed together in one styrofoam box, the spot messenger and i290 went into a smaller box equipped with strobe lights beneath that.  All three trackers had emergency lines directly attached to their casing in case their styrofoam boxes broke, and I built a simple harness for each box and attached it to the main line.  A radar reflect, parachute with hoop, and 1000g Kaymont balloon finished it all up.

We let it go at about 9:20, and sought refuge at Best Buy for air conditioning and internet.  We also bought lithium batteries.  According to google aprs, the balloon was actually bending south and headed towards Mexico, all the time keeping a perfectly consistent altitude of 14324 ft.  We were worried, as the Ham beacon was supposed to be more reliable, and the spot messenger didn’t provide much data and the i290 had left cell phone range right after take-off.  However, the gps stream corrected itself and the balloon was actually headed north, and all was well.

After a brief escapade to a farm field to pick up the other balloon we waited for this one to drop below 60,000.  It had traveled considerably farther than the other balloon, and actually ended up landing in the desert in a bombing range.  We got the balloon in the 114 degrees in a 1.5 mile hike and returned, too tired to bother turning everything off right then and there.

End Results:

Byonics:

• Reliable
• Easy to use
• Durable
• Strange initial drift

Spot Messenger:

• Useful for finding the balloon
• lacks altitude
• 10 minute update time

Motorola i290:

• No data from altitude (code may be improvable to fix this)
• Probably works better if it lands somewhere with 3G service (like not in a bombing range)
• Small and cheap

The data we got from the sunspot was somewhat disappointing, since we had turned it on and taped up the boxes, only to take 45 minutes to fill the balloon, wait and fill the second one, discover that we needed more helium and refilled.  Consequentially, the spot ran out of space before it even reached burst altitude.

Overall I felt it was still a good launch, and look forward to more work on the perfect high school balloon launch package.

Filed under:
Uncategorized by Tim

The UCSD balloon team is launching two balloon tomorrow, one of which is flying the Motorola i290, a Byonics MicroTrak AIO, and a GPS Spot Tracker.  Feel free to track our progress here: Visualization powered by sensor.network.com

The goals of the missions are as follows:

Balloon 1:

Send a balloon with various climate change experiments which high school students might want to conduct in the future.  We are flying a ppm sensor, a CO2, O2, a Geiger counter, and a SunSPOT with a 3-axis accelerometer and SHT15 Temp / Humidity sensor.

Balloon 2:

Send a small, cheap balloon with various tracking systems to test for low-cost solutions and their effectiveness.  As noted above, we are using a Byonics MicroTrak, a Motorola i290 programmed to send data to hibal.org and sensor.network, and a SPOT satellite tracker.  Also onboard is a SunSPOT with its 3-axis accelerometer, SHT15, and a 3-axis magnetometer.

We launch tomorrow (7/17) very early.

Filed under:
Uncategorized by Tim

For my final project in Culture, Art, and Technology, I was asked to do something relevant to time, time management, and how we as a race have evolved to view temporality.  Of course I had to find some fun way to mix genetic algorithms into it, and decided that this was my chance to take a stab at what the guy from Evolution is a Blind Watchmaker did (great video, by the way).

Basically, I wrote my own clock genetic algorithm in java, which overnight managed to get to the 1-handed clock stage.  I never bothered to see if it would get farther than that, because my final project deadline was looming.  Instead I wrote a program which only evolved the clock gear ratios, letting gears connect to each other’s rims or shafts.  This was executed in a nice tree structure, each node having a linked list of rim connections and a linked list of shaft connections to gears farther down the line.  It actually works very well, and finds a perfect solution after 15 minutes.

The parameters can be adjusted, such as the number of available gears, teeth, hands, ect.

It is nice to be reminded how amazing these algorithms are.

Here is my project video, enjoy!

Filed under:
Uncategorized by Tim

A fun little program I decided to write up in my free time.  Basically, the idea stems from whether or not gravity travels at the speed of light.  Image that the sun vanished.  Would Earth be flung out into the depth of space instantly, or would it take about 8 and a half minutes? (Time it takes the sun’s light to reach Earth)  I am of the opinion that it takes 8 and a half minutes, because information can’t travel faster than light speed.  Imagine that gravity could be felt instantly.  Then, someone on another planet could swing around a heavy object, and theoretically and very precise gravity measuring device light years away could pick up on it, effectively carrying a message faster than light speed.  Everything else in science goes against this.

Anyway, my program has little asteroids flying around which are attracted to where the other asteroids were rather than where they are.  At every tick, where asteroids are are registered, and it creates a sort of ripple in space-time, propagating outwards.  Any asteroid on the ripple will see the asteroid as being where that ripple was first triggered.  Hence, a time lag.  Adjusting the speed of light adjusts the lag, and accelerating towards an asteroid will decrease the lag, etc.

As always, code is here.

Filed under:
Uncategorized by Tim

I have contemplated designing a serious Java game many times, but never really considered myself up for the challenge. 3D graphics are too much of a challenge, and building some sort of 2D sidescroller proved to be extremely CPU intensive using the java libraries. I came upon a suitable challenge over Spring break, and have since begun working on a turn based model war game.

Warhammer 40k is a tabletop game in which players collect plastic miniatures which are fielded as their army. Lots of six-sided dice are used in firing, dealing damage, etc. The greatest thing about it is that it is turn based, the events of the game split between moving, shooting, and melee combat. This means I don’t need to worry about the real-time graphics problem, resulting in a game which isn’t beyond the scope of my abilities.

Another reason why I chose Warhammer is because I have marveled at the idea of how cool it would be to see this game officially released on the PC. The game’s problem of arguing over rules and the judgement of distance or line of sight would be eliminated, for the computer would calculate all of that for you. Things would move much faster, you wouldn’t have to spend hundreds of dollars (thousands?) on models, and some sort of campaign mode would let you slowly accumulate a dominating force. After seeing Spore, I thought of how cool it would be to customize your own models, purchase armies, and create striking color schemes. Seeing your models come to life in the 3D virtual world of modern day video games would be breathtaking. Basically, it would be awesome, and getting an extremely basic, 2D version of it up and running is a task worth working on.

Seeing as I am not using any third party software to help me out, (no premade GUIs, OpenGL, etc, except whatever NetBeans provides) I figured it was time to learn how to use the JPanel form in NetBeans. The online tutorial on this is pretty good, and covers the basics for writing an extremely simple temperature converter.

For my game, I figured that a larger layout similar to that of Starcraft would be best, with a large panel depicting the battlefield, a small battlefield map in the bottom left, a central area for depicting the stats of selected units, and an area on the right for buttons such. My crude version still in development looks like this:

This was created, as mentioned, but using the NetBeans JPanel form (right click on your project, new → JPanel form). Netbeans will open up a nice graphical user interface which will help you automatically generate your own user interface for your game. You can design the layout in the GUI section, then modify the code by switching tabs. Swing elements such as buttons, JFrames, borders, and labels can be dragged and dropped in, and the code to create it is automatically written to the file.

I simply added four JFrames and a label for my four panel areas, and set the variable values. A first I was stumped on how to write the code for what is displayed in these frames, but found that creating JFrame classes for each and then editing the code in the auto-generated code to implement these classes worked best.

The end result? A simple GUI I can develop into a decent version of Warhammer 40k!

Filed under:
Uncategorized by Tim

I finally finished the grueling task of creating a user interface to checkers, which was both mind-numbingly boring and thoroughly challenging. I am continuously reminded that any visual output in Java is a big hack, as Greg would say, but at least restricting myself to the Java libraries does allow me to experiment with how such things work.

Two weeks ago I wrote about Minimax, a simple algorithm which looks into future possible board positions to pick the move which minimizes an opponent’s good moves, and maximizes one’s own. I claimed that my algorithm had produced a proficient checkers player, but I was unable to really test it until I had completed the user interface. Now I have, and you can check it out here.

Unfortunately, I found that the minimax, as I have created it, performs rather poorly, most likely due to the simplistic nature of the board evaluation function (It judges how good a position is), and how my implementation leads to the same evaluation for many different board states.

Consider the following two board positions. I admit that I am not a great checkers player, but in my opinion the one on the left is fairly equal, whereas the one on the right has black within an inch of getting a King with several of white’s pieces about to be destroyed. However, in my current approach the two board positions are evaluated as equal, since the pieces are all that count.

Chinook, the famous checkers program which cannot lose, uses several factors to evaluate board position. Among them are, according to Computational Intelligence in Games, an interesting book I recently checked out, “(1) piece count, (2) kings count, (3) trapped kings, (4) turn, (5) runaway checkers (unimpeded path to king); and other minor factors.” Multiple other approaches might work, such as assigning pieces at the board’s edges a higher value than those in the center, or looking to reduce the number of possible moves for the opponent.

I tried the following, (based off this article), weighing a piece’s position using the grid:

This improved my checkers AI, but there is still a lot of improvement to be had. For some reason, once the AI gets a king it likes to jump it back and forth infinitely, getting nothing done when it could be advancing another piece. I have no idea why it does this, and am trying to figure it out. If anyone has any observations, feel free to post them.

However, my next undertaking will not be to follow the shoes of Chinook, with its human-crafted board evaluation function. Instead I will take the path of Anaconda, the program described in Computational Intelligence in Games, which uses a genetic algorithm and neural nets to evolve an expert level checkers ai out of essentially nothing.

Filed under:
Uncategorized by Tim

One of the grand applications of computers is as adversaries in board games. Deep Blue, the legendary chess computer, beat Garry Kasparov in 1997. Chinook, a computer from the University of Alberta, plays checkers so well that it cannot lose. WOPR, the AI from War Games, is trained on all manner of board games before set to analyze nuclear war scenarios.

I was struck by the idea of a computer “knowing” how to win a game, and set to write my own checkers AI. “Knowing” of course is a bad use of the word. A computer does not know things. Instead, it creates a logical formula, and sets about crunching out its solution.

Before we begin looking at the algorithm itself, consider a game of checkers as an abstract collection of board positions, each board position representing a score. In positions where black has the advantage, the score is high for black and low for red, when red has the advantage, the opposite. How are these scores determined? In a perfect world, every possible board position could be analyzed and placed into a giant tree and connected together, each possible move acting as a string to another board position. Those positions leading to a win for black, without a chance for red winning, are good for black. The opposite is true for red.

However, in real life we can’t do this, due to a limitation on processing power and space. According to wikipedia, American Checkers has 10^20 positions, far too many for my computer to store or analyze. Instead, programmers use some formula to determine a board’s value. This is called a heuristic. In my algorithm I chose to find the difference in number of pieces, Kings counting as two. If black has more pieces, I assume black is winning. At least that is the idea. More complicated heuristics consider the position of pieces on the board, pieces in corners or on the sides (invulnerable positions) contributing more to a board’s score, or do any other complicated analyses. I stuck to something short and simple.

So now, given any board position, we can come up with a value.

The minimax algorithm lets us use these values to come up with the best move given a certain number of possible moves, by looking into the future.

Consider this: At the start of the game, the first player has 7 possible moves (each involving shifting a piece in their first row up by one.) We can look at the value of each of the resulting board positions and pick the best one.

This, however, is pretty lame, since each move has the same board value (at least in my setup), and doesn’t get you very far. Instead, we continue on into the future of possible moves and find that for each move, player 2 has 7 possible responses. That makes 49 possible board configurations 2 moves into the future. Now, since player 2 is responding, we will assume that they are intelligent and pick the response that is best for them. Therefore, if we were stopping here, instead of picking the board position that maximizes the score, we pick the board position which minimizes the score (hence the mini-max name).

Now that we know what they are going to do, we can pick the move that leaves them with the worst set of moves for them.

What the minimax algorithm does is look a certain number of turns (aka, depth) into the future, and using successive minimizing and maximizing, find the one move that screws the other player over the most, and simultaneously helps themselves the most.

While this approach is simple, it has its setbacks. First, any human can tell you that most of the analyzed moves are wasted cpu time, because the majority of those configurations are dumb board positions that no one would ever play through. Additionally, if for every move the other player has about 7 responses, that means the number of possible ending positions is 7^d, where d is the depth of the search. Looking only, say, 6 moves into the future results in 117,609 board positions! (My computer runs out of Java heap space if I check more than 8 moves in the future, about 5,750,000 board positions.) A human can get rid of all but the most likely ones in seconds, whereas a computer blindly checks them all.

It is important to remember that computers are simply mathematical constructs, but if you steer one in the right direction, they manage to cast a glimmer of brilliance.

This document is the output for a game with each side looking 8 moves into the future.  It ends in a draw, where each side would oscillate forever with its kings.  r = player1, b = player2, capital letters signify kings. Eventually I will get around to making a nice graphical interface where you can play against it.  As always, the code is online.  You can find it here.

Filed under:
Uncategorized by Tim

Last week I gave a brief introduction to neural networks, but left out most of the math. It turns out that, like genetic algorithms, neural nets have extremely awesome mathematical properties which allow computer programmers to create efficient and effective neural programs.

Remember how each neural takes in charge, figures out if it is higher than a certain threshold, and then sends out charge to other neurons? Well, it turns out that this can be easily represented as an equation.

In the simplest case you have one neuron with a singe neuron before it, and a single neuron after it. The neuron has a singe value, say T, which represents its threshold. If the charge coming into the neuron, say C, is larger than T, {if(C > Y)}, then it will fire. C, in this case, is simply the charge from the one neuron before this one.

Okay, so we have the math logic, {if(C > Y) fire!}. This neuron now gives off charge to the next one down the line. We call this amount of charge the weight of the connection, W. A higher weight is how much of the neuron’s charge goes to the next neuron. If a pulse has 1 charge, then the next neuron gets W * 1 = W charge.

The great thing about this simple mathematical model is that it is easy to expand. Consider the following setup, 2 neurons → 1 neuron → 2 neurons.

Here, C for the middle neuron is {C = Winput1 + Winput2}, and if C is > Y, it will fire an amount Woutput1 and Woutput2. Simple. Easy. Efficient.

Now consider 2 → 3 → 2. The middle layer (the 3 neurons) C values can be set up as follows:

F1*W1,1 + F2*W2,1 = C1

F1*W1,2 + F2*W2,2 = C2

F1*W1,3 + F2*W2,3 = C3

F is 0 or 1, depending on whether the previous neuron fired or not. W n,m is the weight of the previous neuron n to the next neuron m.

For those sharper mathematical fellows, this is a very simple set of linear equations. This simply means the equation forms a straight line, and because of its straightforward linear properties, can be easily converted into a set of matrix equations. The previous example reduces to the following matrix equation:

[W11    W21]    [F1]    [C1]

[W12    W22] * [F2] = [C2]

[W13    W23]    [F3]    [C3]

The first matrix is called the Weight Matrix, the second I call the Pulse Matrix, and the last is the Charge Matrix. The Weight Matrix contains the information of how strong the charge connections between neuron layers are, the Pulse Matrix is whether or not the neurons in that layer are firing, and the Charge Matrix is the sum of the charges on the next layer. All you need to do with the Charge Matrix is see if it is bigger than the threshold for the neurons it represents to get the next Fire Matrix.

Using this math you can reduce a very complicated neural network into a streamlined set of matrix equations. Instead of evolving a set of neuron objects, you can adjust the contents of each layer’s weight matrix and threshold matrix, and presto, you get an evolved creation. The following is a demonstration video for a juiced up version of my last program, now using matrix math.  (Note: the creatures now are more like tanks, with a left tread and a right tread.  They adjust their motion by adjusting the speed of each tread.  Hence the tight turns.)

The code for my upgraded matrix math neural net can be found here.

Filed under:
Uncategorized by Tim

While genetic algorithms are immeasurably interesting, there exist far more captivating concepts in computer programming. One such concept is the idea of neural networks.

I became intrigued by neural networks when I started thinking about artificial intelligence and how a computer programmer might get a computer to “think,” “learn,” and all these other things such as “have a consciousness” which we humans often claim as uniquely ours.

Just as Leonardo Da Vinci and many other enlightenment thinkers looked to birds to create their designs for flying ornithopters, the concepts for a neural net also comes from a look at nature. Brain cells, also known as neurons, are the fundamental building block of the brain, and therefore are considered a good place to start for building a virtual mind inside a computer.

Any neuron, whether inside your head or from the lowest of life forms supporting such cells, works fairly similarly. Scientists are still working out all of the details, but a neurons basically acts as an all-or-nothing electric pulse. It collects charge from the incoming connections, and if it is sufficient to cause it to blow, it will release a certain amount of charge over its outgoing connections, possibly stimulating cells further down the line.

The typical neuron contains a list of weights which magnify or reduce the charge sent through them from the parent neuron, and a threshold value which determines whether or not that neuron will fire. If a neuron’s accumulated charge is above the threshold value, it fires, and an amount of virtual charge is sent into the neurons it is connected to according to the weight attributed to each connection.

A simple representation of a neuron

According to Wikipedia, the human brain consists of roughly 100 billion neurons, and about 100 trillion neural connections. While the interplay at the neuron level seems quite mathematical and artificial, the combined performance of neurons on such a scale can, and does, produce a thinking, conscious being. (Where this line is, of course, is under extreme debate, and is simply a problem of definition. The answer is: there is no line, we simply designate where it is.)

What a computer programmer can do is set a computer up with hundreds of virtual neurons, with thousands of virtual connections, and then let it run its electric pulses and watch what it does. Just as in the human body, neurons in a computer can trigger certain actions. In a human, certain neurons control certain movements, whereas in a program certain neurons might trigger the AI you are fighting against to fire, to run and hide, or to strafe left.

I decided to play it simple with my first neural network, writing code which simulated creatures (red dots) fighting for food (blue dots) in a two dimensional, bounded, habitat. Each creature has a little brain inside, a neural network which receives stimulus from its environment. In this case, they are all fed the vector towards the nearest food source, whether it is to its left or right, above or below, and the same information towards the nearest other creature. These charges work their way through the network, and then the pulses on the output layer determines how it accelerates on the x and y axis. The code can be found here.

Each creature’s “mind” is set in stone. They do not learn as we do, which is something I plan on adding in the future. Instead, they act more as filters, turning one set of pulses into another set of pulses, which cause (or don’t cause) movement.

Here is the same program, after it had evolved.

Better minds were evolved by allowing a creature which found food to give birth to a mutated offspring. Creatures which did not find food slowly died of starvation. If the population level goes below a certain level, random individuals are added to keep things moving. Creatures which collide take big chunks out of each other.

Initially, the creatures do nothing, but a small percentage spin in circles, or travel in a straight line across the screen. These have a higher chance of hitting food, which gives rise to more creatures which can move. Eventually, the entire population consists of gliders, creatures which by default follow a straight path. After a while, they eventually evolve to change their movement based on their inputs, and actually swerve towards the nearest piece of food.

This is done with about 30 neurons, far less than the 100 billion, give or take, between your ears! But if 30 neurons can give red dots a means of getting food, who says that 100 thousand can’t get a computer to walk around, or 500 million to recognise faces, 100 billion to hold a real conversation with you, and 100 trillion to propel the human and machine races into the next technological epoch?

Still, for now they are dots on a screen. We’ll have to liven it up a bit next time.

Filed under:
Uncategorized by Tim