6 ms·

Show HN: Space Invaders but the invaders evolve with genetic algorithm

155 points by atum47 7y ago

atum47 7y ago
My final thesis, that I'll defend next week, is about genetic algorithm and digital games. This is the project that motivated me to think: "how can we use genetic algorithm as a game mechanic?"; I end up implementing another experiment (I'll share the project here as soon as I have something more consistent to show) but this is the one that started the whole thing. Well, good luck to me.
- Jemaclus 7y ago
  Very cool! Good luck!
- markandrewj 7y ago
  You may want to look at Spore, if you haven't already.
  - deleted 7y ago
    [deleted]
- millette 7y ago
  I remember playing Tron (light-cycles!) against GA bots. There was thesis on it in 2001: http://www.demo.cs.brandeis.edu/papers/funes_phd.pdf http://www.demo.cs.brandeis.edu/papers/funes_phd.pdf I felt there was one large flaw (which I explained at the time) since the experiment ran for a few years, computers kept improving. Problem was, the speed at which the game played accelerated along with cpu speeds. You needed quicker reflexes if your computer was faster. If there's anything to retain from this is, make sure the gameplay speed remains the same, whatever the hardware.
jcims 7y ago
Could be fun but the firing rate just makes it too frustrating to play for long.
- godelski 7y ago
  Alternatively the creator could just reduce the screen height. Because I felt the same way. Difficulty also doesn't increase fast enough. I'm not sure why invaders cluster from the top center, but it makes it easy to pick off a few.
- pbhjpbhj 7y ago
  I'm kinda surprised that they didn't start with an open source space invader game and just modify the aliens? For me it doesn't work at all, bullets go through, the fire rate is far too low for the speed of the aliens, movement is slow to respond and moves way too far per keypress (about 20% of the horizontal screen distance).
vlod 7y ago
>To keep things interesting, after 7 generations, a new wave >is created from scratch and only the best of the 7 past >generations is keep. What could possibly go wrong with this? .. .. .. SKYNET! ;)
a-priori 7y ago
Next step: apply an adversarial learning algorithm to the shooter, so the two can co-evolve automatically.
ravitation 7y ago
I'd like to see a version where the "player" evolves with a genetic algorithm as well (maybe through a set of parallel "games" for each "player" generation) and then look at the results over the course of thousands of generations.
- reaperducer 7y ago
  Let them play each other until they give up ("The only winning move is not to play"), or realize that they live in a simulation and try to break out of the computer.
deleted 7y ago
[deleted]
holoduke 7y ago
Would be fun to create a central hosted but distributed ai. So generations are shared amongst sessions between multiple players simultaneously. That way you can really see envolvement. Also add more parameters. Like shooting rate. Shooting speed etc
- Razengan 7y ago
  I often think about the applications of distributed generational AI in realistic multiplayer FPS games. You could then take the evolved AI and shove it into real world Terminators. :)
  - rapind 7y ago
    Depending on the game I could imagine that strategies to beat noobs wouldn't work well against pros, and strategies to beat pros would unnecessarily lengthen games against noobs. I suppose the AI could pretty quickly determine the skill level of the opponent though and adapt.
  - anon777778 7y ago
    I think that this would be not enjoyable. In multiplayer FPS, it would be enough to reach high hitrate. For example, players' hitrates are rarely higher than 10% (only in special cases). And it is hard for human to do better, because all players are constantly moving and players do not have such level of agility. However, I believe that AI could do much better. And AI reaching something like 80% hitrate would cause players to think that they are facing a cheater. In single player environment things are even more complicated. Usually AI has massive advantage there (multiple controlled entities) and to be fun it has to be a bit dumb. Of course it cannot just stand in the middle but rather try to trick player into thinking that it is aware of an enemy nearby. Looking clever but stupid inside.
    - unkulunkulu 7y ago
      Yes, the trick could be choosing the target to optimize. I once had an online chess adversary that seemed strong but who appeared to be losing to me in complications, I even briefly considered an idea he was doing it on purpose to gift some entertainment and fun to his opponents. An AI targeted to do something creative and challenging and at the same time not trying to abuse its obvious advantages could be fun to play against.
Jimpulse 7y ago
Can wait for Ender's Game level ai.
dang 7y ago
This was discussed at https://news.ycombinator.com/item?id=18339551 https://news.ycombinator.com/item?id=18339551, but since it's been about a year (https://news.ycombinator.com/newsfaq.html https://news.ycombinator.com/newsfaq.html), a repost is ok.
- phonebucket 7y ago
  While this post strictly adheres to the rules, more stringent rules on self-promotion compared to other posts would make sense to me. However, this is likely not the best place to discuss these meta-issues. Not wanting to detract from the OP, who executed a creative and fun idea.
  - dang 7y ago
    HN's problems with promoters aren't coming from users who post their stuff once a year. If that changes, we can change the rule.
mc3 7y ago
I played for a bit, and I noticed as the game progresses the invaders seem to cluster together - making it easier to win (less movements between shots). Maybe the algorithm makes them all play the same eventually? As a team of invaders they should want to sacrifice more so they get at least some through the barrier.
jsf01 7y ago
Fun and creative idea. A couple of things I think would make this more enjoyable... 1. Prevent double tapping buttons from zooming in on mobile 2. Increase the firing rate
- snazz 7y ago
  I’m not at my computer, but I think .the-name-of-the-button-class { touch-action: manipulation; } would fix both issues on mobile and make it a lot more fun.
- noobermin 7y ago
  2. might just be the lay of the land. Tbh if you never played old space shooters they weren't easy; you had to learn to cope with the firing rate, it more or less became part of the game. Modern shooters tend to make it more easier and thus hit gratification buttons quicker.
  - chimi 7y ago
    nah, it's on line 33 of player.js if(this.isShooting){ this.bullet.y -= 0.1 * dt; Changing that 0.1 to 1 would make the bullet move 10x faster. It'd be neat if you could have multiple bullets on the screen at the same time, but then the developer would need to maintain an array of bullets and update all of their .y values. In this case, a new bullet is created when the .y value gets to zero, so there isn't an easy way to increase the firing rate except to increase the speed of the bullet. By "easy" I mean, can be done in under 5 keystrokes to the code and without introducing potential bugs. Adding an array of bullets moving at the same rate, but able to be fired with less time delay between each bullet, would require at least an order of magnitude or two more than that amount of effort and also a not insignificant amount of testing.
- jacobwilliamroy 7y ago
  There is no fire rate. The bullet has to hit an enemy or reach the end of the screen before the player can fire again. I think it's kinda neat.
jacobwilliamroy 7y ago
I got to 70 generations before I ran out of time and had to go to work. Around 50 it finally tried spreading all the enemies out across the screen. This is cool, OP, and it's really got my mind racing. I'd write more if it wouldn't make me late for work.
- pc86 7y ago
  > Around 50 it finally tried spreading all the enemies out across the screen. Based on my understanding of this line from the description that's just by chance, right? > The way they move are directly related to their body shape.
zurtri 7y ago
Now we need to evolve the spaceship and then the war of the genetic algorithms will begin!
blueboo 7y ago
How has no one mentioned rRootage, Kenta Cho's classic shooter where you fight giant bosses who evolve to respond to how you fight them? http://www.asahi-net.or.jp/~cs8k-cyu/windows/rr_e.html http://www.asahi-net.or.jp/~cs8k-cyu/windows/rr_e.html
- mikekchar 7y ago
  Wow! I love rRootage, but I never realised that the bosses evolve. Now I need to play some more :-)
ouid 7y ago
Command is happy to report that they have finally domesticated the invaders by killing them from left to right.
notelonmusk 7y ago
There was a game that got progressively harder like this. But it didn't use AI, or space invaders. Your ship was a blue triangle and the enemy was the green triangles. Every new turn, the enemy would be a set of copies of all your movements in the previous rounds, with an extra ship. Does anyone know the name of what I'm talking about or has a link?

155 points by atum47 7y ago

My final thesis, that I'll defend next week, is about genetic algorithm and digital games. This is the project that motivated me to think: "how can we use genetic algorithm as a game mechanic?"; I end up implementing another experiment (I'll share the project here as soon as I have something more consistent to show) but this is the one that started the whole thing. Well, good luck to me.

Jemaclus 7y ago
Very cool! Good luck!
markandrewj 7y ago
You may want to look at Spore, if you haven't already.
- deleted 7y ago
  [deleted]
millette 7y ago
I remember playing Tron (light-cycles!) against GA bots. There was thesis on it in 2001: http://www.demo.cs.brandeis.edu/papers/funes_phd.pdf http://www.demo.cs.brandeis.edu/papers/funes_phd.pdf I felt there was one large flaw (which I explained at the time) since the experiment ran for a few years, computers kept improving. Problem was, the speed at which the game played accelerated along with cpu speeds. You needed quicker reflexes if your computer was faster. If there's anything to retain from this is, make sure the gameplay speed remains the same, whatever the hardware.

jcims 7y ago

Could be fun but the firing rate just makes it too frustrating to play for long.

godelski 7y ago
Alternatively the creator could just reduce the screen height. Because I felt the same way. Difficulty also doesn't increase fast enough. I'm not sure why invaders cluster from the top center, but it makes it easy to pick off a few.
pbhjpbhj 7y ago
I'm kinda surprised that they didn't start with an open source space invader game and just modify the aliens? For me it doesn't work at all, bullets go through, the fire rate is far too low for the speed of the aliens, movement is slow to respond and moves way too far per keypress (about 20% of the horizontal screen distance).

vlod 7y ago

>To keep things interesting, after 7 generations, a new wave >is created from scratch and only the best of the 7 past >generations is keep. What could possibly go wrong with this? .. .. .. SKYNET! ;)

a-priori 7y ago

Next step: apply an adversarial learning algorithm to the shooter, so the two can co-evolve automatically.

ravitation 7y ago

I'd like to see a version where the "player" evolves with a genetic algorithm as well (maybe through a set of parallel "games" for each "player" generation) and then look at the results over the course of thousands of generations.

reaperducer 7y ago
Let them play each other until they give up ("The only winning move is not to play"), or realize that they live in a simulation and try to break out of the computer.

deleted 7y ago

[deleted]

holoduke 7y ago

Would be fun to create a central hosted but distributed ai. So generations are shared amongst sessions between multiple players simultaneously. That way you can really see envolvement. Also add more parameters. Like shooting rate. Shooting speed etc

Razengan 7y ago
I often think about the applications of distributed generational AI in realistic multiplayer FPS games. You could then take the evolved AI and shove it into real world Terminators. :)
- rapind 7y ago
  Depending on the game I could imagine that strategies to beat noobs wouldn't work well against pros, and strategies to beat pros would unnecessarily lengthen games against noobs. I suppose the AI could pretty quickly determine the skill level of the opponent though and adapt.
- anon777778 7y ago
  I think that this would be not enjoyable. In multiplayer FPS, it would be enough to reach high hitrate. For example, players' hitrates are rarely higher than 10% (only in special cases). And it is hard for human to do better, because all players are constantly moving and players do not have such level of agility. However, I believe that AI could do much better. And AI reaching something like 80% hitrate would cause players to think that they are facing a cheater. In single player environment things are even more complicated. Usually AI has massive advantage there (multiple controlled entities) and to be fun it has to be a bit dumb. Of course it cannot just stand in the middle but rather try to trick player into thinking that it is aware of an enemy nearby. Looking clever but stupid inside.
  - unkulunkulu 7y ago
    Yes, the trick could be choosing the target to optimize. I once had an online chess adversary that seemed strong but who appeared to be losing to me in complications, I even briefly considered an idea he was doing it on purpose to gift some entertainment and fun to his opponents. An AI targeted to do something creative and challenging and at the same time not trying to abuse its obvious advantages could be fun to play against.

Jimpulse 7y ago

Can wait for Ender's Game level ai.

dang 7y ago

This was discussed at https://news.ycombinator.com/item?id=18339551 https://news.ycombinator.com/item?id=18339551, but since it's been about a year (https://news.ycombinator.com/newsfaq.html https://news.ycombinator.com/newsfaq.html), a repost is ok.

phonebucket 7y ago
While this post strictly adheres to the rules, more stringent rules on self-promotion compared to other posts would make sense to me. However, this is likely not the best place to discuss these meta-issues. Not wanting to detract from the OP, who executed a creative and fun idea.
- dang 7y ago
  HN's problems with promoters aren't coming from users who post their stuff once a year. If that changes, we can change the rule.

mc3 7y ago

I played for a bit, and I noticed as the game progresses the invaders seem to cluster together - making it easier to win (less movements between shots). Maybe the algorithm makes them all play the same eventually? As a team of invaders they should want to sacrifice more so they get at least some through the barrier.

jsf01 7y ago

Fun and creative idea. A couple of things I think would make this more enjoyable... 1. Prevent double tapping buttons from zooming in on mobile 2. Increase the firing rate

snazz 7y ago
I’m not at my computer, but I think .the-name-of-the-button-class { touch-action: manipulation; } would fix both issues on mobile and make it a lot more fun.
noobermin 7y ago
2. might just be the lay of the land. Tbh if you never played old space shooters they weren't easy; you had to learn to cope with the firing rate, it more or less became part of the game. Modern shooters tend to make it more easier and thus hit gratification buttons quicker.
- chimi 7y ago
  nah, it's on line 33 of player.js if(this.isShooting){ this.bullet.y -= 0.1 * dt; Changing that 0.1 to 1 would make the bullet move 10x faster. It'd be neat if you could have multiple bullets on the screen at the same time, but then the developer would need to maintain an array of bullets and update all of their .y values. In this case, a new bullet is created when the .y value gets to zero, so there isn't an easy way to increase the firing rate except to increase the speed of the bullet. By "easy" I mean, can be done in under 5 keystrokes to the code and without introducing potential bugs. Adding an array of bullets moving at the same rate, but able to be fired with less time delay between each bullet, would require at least an order of magnitude or two more than that amount of effort and also a not insignificant amount of testing.
jacobwilliamroy 7y ago
There is no fire rate. The bullet has to hit an enemy or reach the end of the screen before the player can fire again. I think it's kinda neat.

jacobwilliamroy 7y ago

I got to 70 generations before I ran out of time and had to go to work. Around 50 it finally tried spreading all the enemies out across the screen. This is cool, OP, and it's really got my mind racing. I'd write more if it wouldn't make me late for work.

pc86 7y ago
> Around 50 it finally tried spreading all the enemies out across the screen. Based on my understanding of this line from the description that's just by chance, right? > The way they move are directly related to their body shape.

zurtri 7y ago

Now we need to evolve the spaceship and then the war of the genetic algorithms will begin!

blueboo 7y ago

How has no one mentioned rRootage, Kenta Cho's classic shooter where you fight giant bosses who evolve to respond to how you fight them? http://www.asahi-net.or.jp/~cs8k-cyu/windows/rr_e.html http://www.asahi-net.or.jp/~cs8k-cyu/windows/rr_e.html

mikekchar 7y ago
Wow! I love rRootage, but I never realised that the bosses evolve. Now I need to play some more :-)

ouid 7y ago

Command is happy to report that they have finally domesticated the invaders by killing them from left to right.

notelonmusk 7y ago

There was a game that got progressively harder like this. But it didn't use AI, or space invaders. Your ship was a blue triangle and the enemy was the green triangles. Every new turn, the enemy would be a set of copies of all your movements in the previous rounds, with an extra ship. Does anyone know the name of what I'm talking about or has a link?