Hacker News new | past | comments | ask | show | jobs | submit login
Show HN: Space Invaders but the invaders evolve with genetic algorithm (github.com/victorqribeiro)
155 points by atum47 on Nov 19, 2019 | hide | past | favorite | 36 comments

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.

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

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.

Very cool! Good luck!

You may want to look at Spore, if you haven't already.

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

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. :)

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.

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.

You've hit upon the fundamental difficulty in game ai design. It's trivial to make an AI execute strategies perfectly (in most games). The trick (and the significant difficulty) lies in making it not perfect, but in a way that is humanlike, or at least makes sense.

If a solution to make AIs function at human levels, for example a built-in delay between seeing a player and say, shooting at them, becomes noticable, it cheapens the experience for the player significantly.

An old quote sums it up perfectly for me: “The job of game AI is not to win, but to lose in an entertaining manner.”

yes, this. I love this.

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.

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

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

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.

nah, it's on line 33 of player.js

     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.

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.

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.

I would like to step it up to 3 and 5 bullets in action, maybe with powerup

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.

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?


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

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?

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

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.

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).

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.

> 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.

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.

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.

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

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

Can wait for Ender's Game level ai.

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

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.

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.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact