Hopscotch Theory: Enemy AI with Evolution!

hopscotch
problems

#1

NOTE: None of the following is actually tested, this is all just a theory.

Recently there has been a lot of talk on the forums about game AI. So far, all of it has been rule based AI, meaning "When player does x, do y"

Which works well for most games, but what if you can't account for all those rules? What if you don't know where your player is going to go or do at what time? This happens to me in many games whenever there are multiple things the computer has to account for in making a decision on what to do. In that case, you can't just use rule based AI. You need to computer to adapt to it's situation. But how could you possibly do that? You can't make a fully functioning brain in Hopscotch! And that is true, making a human scale intelligence is pretty much impossible. But, I introduce to you a new way to make enemy AI where the enemies learn and adapt from past experiences.

Genetic Algorithms

But, what is a genetic algorithm?

Well, to answer this question I will quote a passage from Dawkin's book The Blind Watchmaker which does a great job of describing Evolutionary/Genetic Algorithms.

"I don't know who it was first pointed out that, given enough time, a monkey bashing away at random on a typewriter could produce all the works of Shakespeare. The operative phrase is, of course, given enough time. Let us limit the task facing our monkey somewhat. Suppose that he has to produce, not the complete works of Shakespeare but just the short sentence 'Methinks it is like a weasel', and we shall make it relatively easy by giving him a typewriter with a restricted keyboard, one with just the 26 (capital) letters, and a space bar. How long will he take to write this one little sentence?"

Well, it turns out that a computer program made to do this task would not produce this phrase, even given the lifetime of the universe to run. So Dawkins describes another way to produce this phrase

We again use our computer monkey, but with a crucial difference in its program. It again begins by choosing a random sequence of 28 letters, just as before ... it duplicates it repeatedly, but with a certain chance of random error – 'mutation' – in the copying. The computer examines the mutant nonsense phrases, the 'progeny' of the original phrase, and chooses the one which, however slightly, most resembles the target phrase, METHINKS IT IS LIKE A WEASEL.

By continuously repeating this process, a 28 character string of gibberish will soon turn into the target phrase.

This is what a genetic algorithm is. Taking an original parent, creating copies of it that are slightly different, taking the best one out of those, and creating mutations off of that, etc.

But we want enemy AI, not to produce phrases!

Well, we can apply genetic algorithms to enemy AI. We first start out with the "skeleton" of the AI. For my example I will use a rock paper scissors AI. We need 3 variables in this case, one for the probability of rock, one for the probability of scissors, and one for the probability of paper.

Paper=33%
Rock=33%
Scissors=33%

This is our "seed"

Then, we play 16 games against the player. Each 4 times we use a slightly different probability.

Game 4:

Paper=35%
Rock=30%
Scissors=35%

Game 8:

Paper=29%
Rock=38%
Scissors=33%

Etc.

How much the probabilities are changed is up to you.

Then we take each of the probabilities and how many games they won, and compare them. Lets say that with this probability:

Paper=29%
Rock=38%
Scissors=33%

We won 3/4 games, our best score out of all the others. We then take that probability and go back to step one, except instead of all 33%, we use our new best.

And there you have it! Rock paper scissors AI! You can then apply this to any game with some tweaking of the variables!

That's great! But what are the downsides?

Here is where it gets tricky. There are two main downsides to genetic algorithms, which I will explain here.

They are slow

If you have a complicated game, your AI is not going to adapt very fast. With rock paper scissors it is ok because a totally random algorithm will work, but in a defense game or rpg type thing, your enemies are going to act very weirdly at first while they try to learn what is happening and what they are supposed to do. It won't be until you fight them enough for them to learn how to fight you back.

Implementation is hard

Your main problem when coding it will be comparing all the wins and finding which set of variables did the best. This is because Hopscotch does not have support for lists/arrays, so you can either:

  1. Make a bunch of variables to manually store each one, which will slow down your code and make it considerably larger

  2. Find a way to compare as you go using some sort of temporary variable wizardry

In conclusion
Hopscotch being a turing complete language, we know it is possible to implement a genetic algorithm for enemy AI. And in some cases, it works great! But, when you have a complex game and your enemy has to immediately know what to do, I would say to use a rule based AI or a mix of genetic and rule based.
So the moral of the story is:

Hopscotch, please add lists!


Some ideas on Artificial Intelligence
Advanced Collab
#2

Cool! Seems complicated though


#3

Is it a bit complicated, and it doesn't help that I'm not particularly good at describing it, but I would suggest googling "Genetic algorithm" there are plently of really good explanations.


#4

This is enjoyable to read. I appreciate the time you've taken to express it.

I think you want matrices and case structures as well.

I hesitate to bring up a topic like this, because I fear that it is outside of the mission for Hopscotch, which is a mission for which I have sentimental respect. That would not prevent me from coding ideas like these, "publishing" them without much ado and leaving them to be discovered by those who are ready for it and to be ignored by the rest.

Here is my question to you, @BuildASnowman: can you say something about what motivates this topic for you? I know you have already spoken to its potential use in a game. But what I would like to know is what really drives so much interest that you would post this and and why you would even consider "going there" in Hopscotch, given the avilability of other means. That is not to push against the motive but to understand it and to pull it a little closer, if i can. It is also to test a hunch concerning you. And I don't mind saying that part of that hunch is that you enjoy a challenge for the sake of a challenge and that you are interested in other advanced and creative topics. Right or wrong, i would enjoy reading your answer. :sunglasses:


#5

I guess I will never have the gamemode of a game when you fight against a robot. This is because I'm very bad at understanding things.


#6

@Hoppertoscotch No! That's completely wrong! You can design a robot and an AI if you try, I know you can. This method may be complex, but this is just one way of doing it! There are plenty of hopscotch games out there with AI, and I bet none of them use this method. Look at their code and see if you can understand how they do it. This method is over-complex and should only be used when there really is no other way.

Just because you can't understand this post doesn't mean enemy AI isn't for you. This is just a more complex way of doing it.


#7

@oio I wasn't even aware of case structures before this (Quite new to evolutionary computing) and I tried to learn about matrices (Mostly because I liked the word matrix :stuck_out_tongue: ) but I went down the "math rabbit hole" in that, while trying to find out what they are, I encountered some other terms which I didn't know what they meant, and in trying to find out what those terms meant I met more terms I didn't know, etc. I think that is one benefit school has over the internet - structure. But in school, we are quite far away from learning about matrices (I believe they are precalc, I'm currently in pre-algebra) so, I'm not sure what I can do.

As to your other question... I'm still thinking about it. I don't really know what drives me to try to understand this stuff, it's just... fun! I know that isn't a complete answer at all, and I'll try to come up with something better.


#8

Well, I need help with it!! And I need so many different AI codes for what I'm doing, there is a difficulty Easy, Normal, Hard, and a gamemode I don't have a name for yet, which is the AI you gave the description about. It's a big project. Not only that, there will also be a 2 player gamemode. I'm actually thinking of putting them in different projects. But, that isn't how a real game is. I just, just, am BAD at coding just plain BAD! B.A.D.


#9

Hey @Hoppertoscotch, you could never say you are bad at coding, I used to be a novice in coding back in March or February or something, and I never gave up. When I have mistakes, I can get really mad at my self, but........ I always somehow got help or I fixed my own mistakes.


#10

I'm literally stuck right now. I'm doing such a big project, it probably has the most coding I've ever done. I also am in collab with someone and I need to make a big choose your path game, AND I' making a game when you take care of a Dino and there is a minicams INSIDE that game! So, I'm in a complicated state right now, @AHappyCoder, I'm not trying to complain about collaborating with you, or anything, just don't be surprised if I don't get that done in a while.


Advanced Collab
#11

I understand what you mean. If a player jumps in a fighting game,each time they jump a jump value can go up by 10 and decrease by 1 per second until it reaches 0. If the jump value reaches around 150-200, this shows the players habit is to jump allot as the jump value has gone up 10 each time they jump. A strategy to code could be the CPU AI runs along the ground to the opposite side of the player more to avoid the players jumping and attack when the jump value is over 150. Also if the player doesn't move much a still value can go up and only decrease when a player moves. A high still value would encourage more ranged attacks by the CPU AI as the still value reaches 150.


#12

`Awesome tutorial! I know I'm bumping an old post, but this is amazing @BuildASnowman! #lounge


#13

@BuildASnowman, I'm in the middle of a huge project, and I've found that even with this, as you pointed out, it is definitely challenging for the computer to learn as you go, or "adapt". I have made a simple tutorial to go through that might compensate for this, however. The limits of this aren't foreseeable, but I imagine that if you were to repeat the same pattern over and over, then switch unpredictably, then it could get glitchy. I'm still looking into this, but this is great!