Project Sarica

So I've finally gotten around to making the artificial intelligence programs I've been talking about for however long it's been. I spent about a good two hours last night working on a simple neural network setup, and evolution algorithm to allow it to learn. I was able to finish them both in only 2 classes, each with less then 100 lines. Knowing that a lot of the processes here are going to be quite taxing, I challenged myself to make them run as memory friendly, and CPU friendly as possible. To achieve this, I make the entire network run solely in arrays. Using only 4 (really long) arrays, more specifically.

Wanting to stress test it, I make a 100 x 100 neuron brain, (plus 99 bias neurons), and ran it 1000 times to find the average time for a single step. I was quite surprised that the entire network, consisting off 10,099 neurons, and 999,900 connections, completed a single step in only a mere 2.7 ms. That's insane. I'm quite happy.

In addition to only using arrays to store all of the neutral network data, I didn't use and taxing functions such as Sigmoid. I used a base 4 polynomial, which was set by the evolutionary algorithm to whatever function is wanted. This means that all of the math used in the network was simply adding and multiplication. Because of the MAD rule in computing, (MAD basically means that multiplying then adding can be preformed in a single CPU cycle.) this was almost no problem at all for the computer. This is well more then enough neurons to complete most tasks that a neural network would need.

In fact, the network could be expanded on even more, if needed. The largest I was able to do before running into memory issues was 300 x 300. At this point, I was already using all of the virtual memory Java had given to me by default. I could've easily allocated more memory, but it was unnecessary. At 300 x 300 neurons, the network completed a single step in about 195\ms.

If you want to see the code for this class, see this link. (Note: By the time you read this, the code may have been expanded on, so it may have a lot more features, be faster, or whatever else I do to it.)

---

Now, to start out with this project, I need to think of an environment. I was originally going to make a hunt and gather type world, but that wouldn't really put must focus on the types of learning I've really been wanting to dive into. As of now, I'm stumped as for which type of world to make for it.

Sub Conscious Learning System

I had a thought, today. It was for a type of learning which seemed quite natural, but I had not even imagined being able to implement, previously. It is a system for self-scoring. As you might know, in general evolutionary algorithms, a computer program is given a score based on how well it functions, and it's children carry on that score, and build onto it. Eventually, after many generations, it gets smarter and smarter. However, with this system, if forces the entire species to lean as a whole, rather then individually. This works perfectly fine if the algorithm is designed to only master a single task, even if it's complex. But what about more complex tasks?

How could an artificial intelligence agent be designed, so that it can make it's own choices. Score it's own actions and abilities. This is an important trait for agents who want to have any hope in thriving in a complex environment, where more then a single action must be scored. This is a critical base for higher level thinking machines. Machines that learn strategy, and can plan out actions ahead of time. Taking into consideration events which only they specifically have encountered, not their previous generations.

Here is my proposal. For this system, the original generation based learning algorithm is still in place. This judges actions solely around things such as survival of the individual, and expanding the population. But there is also another learning system in play, here. The second learning system is per agent, and effects only their brain. This is constantly updating, as well.

In this system, imagine we have an entire AI brain network. Neurons and all. Now, take a chunk of it. Say, 25% or so, and mark this as the subconscious. This part is unable to be edited by the agent. In addition, this chunk is close to the end or the network, and all linked together closely. Yes, there are many connections going in, and also several going out. Though, in the middle of these, there are "emotion" neurons. These release emotional responses based on their input. Positive input, results in a positive output. Negative input, results in a negative output. Highly positive input, results in a highly positive output. And so on. Now, these emotional responses are the "score" values for the agent. It wants these to be as high as possible. So it is constantly weighing in different neuron values for the rest of the brain to try to influence the emotions. Now, the main evolutionary algorithm still wants the brain to function a certain way, to accomplish it's overall tasks. Survive, and thrive.

When a new agent is born, it's default brain state is given to it by the evolutionary algorithm. It also decides which parts of the brain are editable, or not. (This network is also assuming the same setup as the one I described in my article "Smoother Node Map Learning".)

By doing it this way, the agent is allowed to learn and adapt to it's environment at it's own pace, while the main algorithm gives a general path for everyone to follow. Both algorithms fight each other, and also work together to achieve a goal.

As each agent is it's own brain, and learning path, each one will have it's own personality, goals, and so on. Each will behave in their own way, but still follow the same overall instincts given to them when they are born.

I am quite excited to see how this plays out, so I will be playing with the code for it. (Though most likely I'll just get lazy and never finish it, as is the case for most of these ideas.)

Pathfinding as Better AI

When most people think of pathfinding algorithms, such as A Star, they think of simply finding the shortest distance between two locations on a map. Although this was it's original purpose, it can be so much more then that. A lot of implementations of pathfinding take advantage of the movement cost to make the paths more realistic. Such as avoiding wall-crawling, or preferring to walk on the sidewalk instead of grass unless necessary. These are very simple operations, but yet have already rocketed the simple find-the-shortest-path to a more natural, actual walking pattern.

But why do we have to stop there?

Let's build onto this a little bit. Instead of messing with solely the cost to move to a specific node, let's add more nodes. In addition to nodes like "move north," "move south," etc. Let's add "sprint forward," and "jump forward." Then adjust the cost to include time taken, and energy consumed, and demand to get to the end as quickly as possible. By doing this, more complex paths are available. Enemies will walk around normally, but when a player starts to walk by, they will rush towards you. Possibility breaking into full sprint to get to the player if they need. Adding a maximum energy could even persuade the enemy to give up, if it becomes too difficult to reach the player. Imagine how realistic monster movement would be now!

We can go even deeper.

What if we add even more complex functions. Such as "wait," "swing sword, " "shoot bow, " "drink healing potion." At this point, imagine how much more complex the creature's intelligence will become. It could actually hide behind a pillar out of the player's sight, and shoot a bow when they're not looking. Or charge up and hit you with a sword, then run. The possibilities quickly become immense. Simple enemies are become something to fear, and computer controlled pets become the most important companions.

Pros and Cons?

Well, there are a few of each. For pros, it adds a very high intelligence simulations. And it's highly flexible.

Cons, wells, balancing the point values can be a little tricky. I'll explain how to work with scoring, below. But the biggest issues are calculating heuristics, if applicable, and performance.

Performance is something that becomes a huge resource on this. As so many more dimensions are being explored. Working even on a simple grid instantly becomes a massive chore for the CPU. In addition, if heuristics, which are already very difficult to calculate, are done incorrectly, the computer could be wondering around for quite a while before finding an acceptable path. As for heuristics, it's much harder to calculate, as now multiple paths are being explored, such as "should I sprint or not?" This effect can hugely break the outcome for algorithms that depend on it. A star can get away with it, by always setting the value to 0. Though it will take longer to find a path. (Though it will always be the most accurate path to meet your needs.

Scoring is a little weird, but easy if you use square mean. Basically, make sure all values you're scoring, raise about the same way. (Such as the all have roughly the same starting and ending values. And none level up faster then the others.) Now, for each node, get all scores for it. Raise all of them to the power of 2. And find the average. That is the cost for this cell. :)

Now, much sure for make each cell store as little memory as possible. In really difficult situations, it may take many, many nodes to find a result.

In summary, this is my proposal. It sounds great in theory, but I'll have to test it some to see how practical it would actually be in real AI. Thanks for reading, and I hope this gives you some ideas for your game/program/whatever. xD

Learning to Learn

One really interesting thing about node map learning, it it's flexibility. Given the right functions, and enough time, the node map can be theoretically capable of learning to preform any task. Though this can be very slow, and very daunting process. So why not teach itself?

A quick Google search will show how powerful learning algorithms are. Amazing tasks can be taught to the AI. Some preforming calculations far more powerful then previously thought possible. Other things can be taught to. Such as creating the fastest car, or the best fighting stick figure. Well, that's awesome. But I'm sure it took a while to get to that state using only self learning methods. And it does. And when thrown into a new environment, it can take a very, very long time to make the correct adaptations. Our algorithms are good, but not that good.

So let's let the AI figure it out. AI algorithms are already able to define the perfect algorithms for specific tasks, to a point that far surpases that of any human. Why not let the AI find a perfect learning algorithm?

The concept behind this is to have a "master" node map which is constantly learning and expanding it's knowledge of the functions it has, and how to use them. And use that to generate possible learning algorithm maps. Then send these maps out into a large series of varying tests. (There must be a large number of them, and they must be very diverse in order to minimize pattern finding and exploiting.) It wouldn't do every test, but a random selection of them. This helps to prevent the node map from excelling in a specific test to boost it's score. Then return the results over time for each test. Take all of the results from each test, and find the average learning curve. The idea for the master node map is find and create an algorithm that generates the highest learning curve. This process is very time consuming, and takes many, many, many more tests and passes then usual. That's because all of the learning is done ahead of time. More tests will have to constantly be added, and do to randomness, and test weaknesses, learning should not cease. This new learning algorithm would be constantly getting better over time, until it can finally surpases all of our current learning algorithms by far.

Cleaning Up The Map

With the node map, running a function may or may not be very taxing. But even if it's not, excessive use of these small functions do build up. The node map has no actual idea how the functions operate. It only know that the functions do operate, somehow, and some return data, while others don't. Certain ones will actually help the node map achieve it's goal, while others will just process data. It is important to try and reduce the size of the map by removing unnecessary uses of functions. (Such as having 13 functions processing a line of data that goes no where, is completely useless. To remedy this, the node map is designed with a "cost". The idea is to find the shortest path, sort of speak. When giving a function to the node map, a cost would also be supplied. This cost would explain to the node map how extensive it is against CPU. A function which just adds two numbers is very simple, and can be called many more times then say, a distance formula. So the add function would have a much lower cost then the distance formula. Here's how these costs are counted:

The sum of each cost of all functions on the map is collected. Next, the "fitness" of each trial is collected. The sum is taken away from this number, and the fitness continues down it's path. By doing it this way, the node map will take function cost into account, and only use functions which help it reach it's goal better then the amount of power it would require at it's current state. If a function is just sitting there taking up space, it is just draining the fitness. The node map will catch on to this, and remove the useless function instance.

Node Map Reading

The first step to creating this Node Map Learning algorithm, is to design a node map object which can be read, and executed correctly. This doesn't include any learning functions, yet. Or even any of the functions which would be placed inside of it. Creating this type of node map has it's difficulties because it does not flow completely straight forward. It branches inward, outward, and skips layers. There are even multiple inputs, if desired. (Using many sources of input can be good because the AI can choose which ones it wants to use, and which ones are useless and just take up space. Some input functions may be something like random number generators which also help the AI in some way or another.) Though I use the term "Input" a lot, there are technically no inputs. Just parent-less functions. To make this node map function correctly, all that's really needed is to store a list of function instances. Then each step, run through each function on the list. If that function has already been ran, skip it and move on to the next one. If it hasn't, check to see if all of it's parents have been ran. If they have, then run the function with the data that was returned by it's parent functions. For "input" functions, it has no parents, so this will always return true. If only a single function step is wanted, then return after running a single function. If the iterator passes over the last element on the last, then every function has been ran. If all functions can be ran gap-less, then simply continue to run down the list, calling functions when they can be. When the end of the list is reached, jump back to the beginning of the list, and start over. Do this until a full pass has been made over the list, beginning to end, without calling a single function. When this is the case, all functions have been ran, thus ending the node map step.

After this algorithm is complete, then we can move onto the next step, node map generation. I'll explain this step in more detail as I complete more and more sections of working code bits.

Node Map Learning

Artificial Intelligence is an amazing topic. The whole concept of a computer program learning about it's environment and adapting to it is amazing. I've always loved AI, and have made many attempts to reproduce it. Though I have run into numerous problems along the way. Mostly due towards my lack of knowledge on the subject, and because of the ridiculous amount of work involved to make such a program. Though this is to be expected. AI is not a simple subject. There's so much involved in it, that it's almost necessary to use large teams to design anything of a decent scale. Though it can be done. So why don't we have AI around us commonly if it possible? Well, in a small sense we do. Neural Networks for example, are used at banks to help read off hand writing into computer text, and can do so with over 99% accuracy. But this isn't the type of machine learning I am referring to. What about emotions? Self set goals? These things are possible, and have been created in several instances. But the design behind them almost seem primitive compared to even small animals. This is because even though we have many different algorithms to aid in machine learning, they all have one thing in common. They are slow. It will often take many, many, many passes before the computer finally gets anywhere logical. Yes, in a sense the human mind is the same way, taking the first several years of our lives to learn about how to interact with the world around us. But we can't wait that long. For a computer, an environment on a scale such as ours would take almost centuries to understand, and lots of storage space. Not to mention a ridiculous CPU to calculate decisions in real time. Resources we don't have to spare. That's why AI is such a largely studied field. It's constantly coming up with new ways to speed things up, and make it more efficient. That's why I'm here. I proposing a new type of learning method which I hope will make learning on a mass scale much easier. Though I do not fully understand every part of the algorithm yet, I hope to keep fleshing it out more and more over time. This information right here is a basic summary of the algorithm, rather then any detailed math behind it.


The Node Map Learning method is machine learning concept which is hopefully better at understanding much larger and more complex environments then regular algorithms such as Neural Networks and Genetic Algorithms. It works by basically creating it's very own node map, (which functions similar to a program's code, shown right) then filling this node map with many, many functions. Anything that can be given to it. This includes stuff like distance between two points, sorting a list, adding numbers, and of course, actual functions for interacting with the environments. The AI takes all this data, and tries to organize it into a complex tree of data processing to work with such. The tree is constantly changing and evolving. Some of the functions given to the AI might be things such as Neural Networks or Genetic Algorithms, in which case it would also use these functions, and as the AI operated, would also learn to make better use of these functions. One last thing to note, is that each limb of the tree, (the data that comes out of functions, and gets thrown into other ones) must have a "type" assigned to it. Such as "number". This means that a function which accepts 1 input in the form of a number can only accept data that is assigned as a type of number. Data types can extend other data types. Such as "integer" would extend "number". Thus, all integers can be used as numbers, but not all numbers can be used as integers. The tree grows constantly as well, becoming more and more complex as needed. This process occurs in a similar method to genetic algorithms. The AI will semi-randomly (see paragraph below) start testing out different tree designs by adding, removing, or replacing branches on the tree. If the new design functions better, use that tree instead. If not, revert to previous tree. This process continues infinity, until there is absolutely no better way of designing the tree, without completely remaking it.

It chooses a base design by randomly creating X number of completely random tree designs initially. (X is determined by the complexity of the environment, though is usually around 100 or so. Though can be much higher for intricate environments.) Then it tests all X concepts, and looks for patterns in each one, and compares these patterns to how well it did. For example, the AI may test 250 designs, and looking at the designs, trees the used the pattern "Function 1 > Function 2 > Function 3 and 4" tended to have better results, while trees that use the pattern "Function 1 > Function 4" seemed to function very poorly. Taking all the patterns into account, it designs a new tree a sees how it functions. Constantly testing it, changing it, and making it better. Each and every new tree that is tested is broken down into a list of patterns and given a numerical value based on how well it functioned. This builds up after a while, and eventually will give the AI a very clear idea of what kind of designs work better then others.

This is my concept. I hope to have a working proof of concept out later. Thanks for taking the time to read this, and follow to keep updated. I will be posting more on the subject soon.