Supporting game design with evolutionary algorithms(gamedeveloper.com)
gamedeveloper.com
Supporting game design with evolutionary algorithms
https://www.gamedeveloper.com/design/supporting-game-design-with-evolutionary-algorithms
62 comments
The dichotomy of interest isn't really NNs vs GAs but about stochasticity vs determinism. The user/player doesn't care which it is until they learn to see the patterns and to reliably exploit the rules. Once you notice these patterns, the spell is partially broken and immersion is compromised. That's part of the reason stochastic methods have been such a hit throughout the history of game development for NPC behavior.
I think things get really interesting when you combine small, efficient ANNs with evolutionary/genetic algorithms.
The biggest challenge with these is coming up with a function that clearly represents the fitness of a candidate. EAs are worthless if you can't provide good selection pressure over time. There are always multiple conflicting objectives in the most practical cases. I've recently discovered that you can skip all the nasty objective weighting business if you just select the Pareto front every generation. You never know when a trip down a less important path might result in the most optimal global solution.
The biggest challenge with these is coming up with a function that clearly represents the fitness of a candidate. EAs are worthless if you can't provide good selection pressure over time. There are always multiple conflicting objectives in the most practical cases. I've recently discovered that you can skip all the nasty objective weighting business if you just select the Pareto front every generation. You never know when a trip down a less important path might result in the most optimal global solution.
Oh wow, this kind of idea goes way back, to Doug Lenat's Eurisko. Good old fashioned AI. He famously used that to craft winning strategies for Traveller Trillion Credit Squadron, a non-computer game.
Today's game designers might use this sort of thing to find game-breaking exploits before those damned players do.
Today's game designers might use this sort of thing to find game-breaking exploits before those damned players do.
Optimal gameplay balance != fun gameplay.
Many games were ruined post-release because developers tried to make the gameplay "more balanced". This usually leads to everything feeling the same.
Helldivers 2 was a good recent example, which is suprising since it's not a PvP game at all but a co-op PvE only.
Many games were ruined post-release because developers tried to make the gameplay "more balanced". This usually leads to everything feeling the same.
Helldivers 2 was a good recent example, which is suprising since it's not a PvP game at all but a co-op PvE only.
well, extract a good metric for "fun" (like engagement) and make that the optimization criteria. It would be equally as easy.
There is no good metric for fun.
Call of duty occacionally asks you after a match if you had fun (5 options from "boring" to extremely fun), I bet thats a good metric for fun.
Heart rate, pupil dilation, breathing rate…
Missing the OG: NERO https://nn.cs.utexas.edu/nero/about.php
NEAT is really well suited to modeling behaviors in a less structured way and gets used to play videogames.
NEAT is really well suited to modeling behaviors in a less structured way and gets used to play videogames.
Seems unlikely to work imo. Games need to account for the fact that 90% of the player base will be deeply unskilled and the remaining 10% will be tightly invested in a meta of dominant strategies. You’d need the bots to be able to consider this and also not just equalize every character.
[deleted]
Yeah. A truly balanced game is boring. There’s no drama or tension.
You need the power fantasy of being strongest characters and the underdog tale of winning against the strongest characters as a less meta one.
You need the power fantasy of being strongest characters and the underdog tale of winning against the strongest characters as a less meta one.
Why not abandon the idea of balance entirely and tailor balance situational for maximum drama.make the meta shakespearean..
Valve memorably did just this over a decade ago with the Director system in Left4Dead.
See also the storytellers in Rimworld. Randy in particular is a master of the dramatic turn.
That’s exactly what “balancing” a game means.
This can be accounted for by training bots using player inputs from historical games, no? If you then partition the training set by player ranking, you'd presumably get a set of bots that approximate a player from each ranking. With that, you could simulate the effect of a balance change on players of various skill levels.
Suppose you wanted to rebalance the rules of chess so that the black pieces had equal odds. You really only need to achieve this at the superhuman skill level, and then you could let the matchmaking algorithm could do the rest of the work.
Not a great example. Chess is a 1v1 symmetric game and is pretty well balanced.
white moves first, in any perfect game black can only play to a draw
[deleted]
> in any perfect game black can only play to a draw
You’re making this up. Chess is not solved.
It’s also largely irrelevant to my point.
You’re making this up. Chess is not solved.
It’s also largely irrelevant to my point.
Nope, all the research with Stockfish et al is pointing to chess being a draw with perfect play.
That’s not what “prove” means and notably is not specific to black which was the more significant claim.
I think it is highly likely that perfect play results in a tie for both sides.
I think it is highly likely that perfect play results in a tie for both sides.
That's what a draw is my guy.
Yes I’m agreeing with you. But I’m saying it’s not proven and it’s not expected to be favoring either side as claimed.
Saying black can at best tie against perfect play is not the same thing as saying both players can at best tie when facing perfect play.
Saying black can at best tie against perfect play is not the same thing as saying both players can at best tie when facing perfect play.
Not really. It would take immense effort to train bots to play “like humans” and not “as performantly” as humans which is very different. And if you’re going to be optimizing game parameters that means you’re assuming that either the AI doesn’t change its behaviors even though the game is different or you’re assuming that humans will adapts in the same way the bots do.
Like if all the humans use the AK because it’s super over powered, and your optimization algorithm sets the AK damage to 0; what are your “human” bots going to do? Because all the training data says to use the AK.
This approach only makes sense if you’re evaluating bot-optimal play outcomes.
It also takes away a lot of the design thinking behind balance. You probably don’t want to nerf the AK. You probably want to buff counterplay options (guns are not a great example but still)
Like if all the humans use the AK because it’s super over powered, and your optimization algorithm sets the AK damage to 0; what are your “human” bots going to do? Because all the training data says to use the AK.
This approach only makes sense if you’re evaluating bot-optimal play outcomes.
It also takes away a lot of the design thinking behind balance. You probably don’t want to nerf the AK. You probably want to buff counterplay options (guns are not a great example but still)
> Not really. It would take immense effort to train bots to play “like humans” and not “as performantly” as humans which is very different.
There is precedent in Maia Chess, which does a good job of mimicking human chess players at various ELO ratings. Of course, it's a lot more difficult to extrapolate to games with significantly more state/movesets, but I imagine that this space will be further explored in the near future.
> And if you’re going to be optimizing game parameters that means you’re assuming that either the AI doesn’t change its behaviors even though the game is different or you’re assuming that humans will adapts in the same way the bots do.
This could be addressed by including the game parameters of interest (what map, what character, the weapon stats at time of gameplay, etc.) in the input to the training data.
> It also takes away a lot of the design thinking behind balance. You probably don’t want to nerf the AK. You probably want to buff counterplay options (guns are not a great example but still)
Tool-assisted QA is nothing new. Using AI is a newer iteration of the concept. You still have to interpret the results it gives and make decisions based on that. The design thinking isn't replaced, it's augmented with additional insights. Are those insights potentially inaccurate? Sure, but you can account for that with sanity checks/manual intervention/play testing.
There is precedent in Maia Chess, which does a good job of mimicking human chess players at various ELO ratings. Of course, it's a lot more difficult to extrapolate to games with significantly more state/movesets, but I imagine that this space will be further explored in the near future.
> And if you’re going to be optimizing game parameters that means you’re assuming that either the AI doesn’t change its behaviors even though the game is different or you’re assuming that humans will adapts in the same way the bots do.
This could be addressed by including the game parameters of interest (what map, what character, the weapon stats at time of gameplay, etc.) in the input to the training data.
> It also takes away a lot of the design thinking behind balance. You probably don’t want to nerf the AK. You probably want to buff counterplay options (guns are not a great example but still)
Tool-assisted QA is nothing new. Using AI is a newer iteration of the concept. You still have to interpret the results it gives and make decisions based on that. The design thinking isn't replaced, it's augmented with additional insights. Are those insights potentially inaccurate? Sure, but you can account for that with sanity checks/manual intervention/play testing.
You’ve largely missed or ignored my point. If you change the game your AI either fails to adapt or adapts in an AI way. But it can’t reliably adapt in a human way without data on how humans adapt to the change. That’s just not how it works. Maia won’t mimic humans hypothetical behavior if you make it so that bishops can also move like knights.
There’s nothing wrong with using bots in play test data but you shouldn’t ever expect an optimization algorithm to generate fun balanced game mechanic stats based on their behaviors by tweaking things until the bots are evenly matched.
There’s nothing wrong with using bots in play test data but you shouldn’t ever expect an optimization algorithm to generate fun balanced game mechanic stats based on their behaviors by tweaking things until the bots are evenly matched.
I found that to design games for the crowd seperatly and merge them, works wonders. One crowd gets a hyper-challenging rts, the others get to play heroe units making all the difference in a small dota game, playing off the the hyper-rts. The OPs can take over and micro, but they wont never micro as well as a human, for whom it is the whole game.
One example.. of course, you goto keep it civil. No pro players dunking on the mom&pop gamers who just want to have 5mins of fun on a tablet.
One example.. of course, you goto keep it civil. No pro players dunking on the mom&pop gamers who just want to have 5mins of fun on a tablet.
I agree that a rudimentary evolutionary algorithm probably wouldn't work since they often don't take into account multimodality. There are global stochastic algorithms that take into account this sort of multi modality. Most particle swarm framworks could handle this sort of bipartite nature with a more complicated fitness function. Differential Evolution frameworks in R also allow you to do a post operation on each candidate, which include something like rejecting it because it does not seem to lie in one of the two modes.
You can get around that by telling those 10% to f- off and play something else.
The ones who are most interested in your game to actually learn it? That’s a strat but it’s certainly not the game dev meta
Amazingly, "better player" doesn't imply "better customer". That is, unless it's a P2W game, where better = willing to spend more money.
But so very often it implies "Loudest customer" -- that is, they are the most likely to loudly and publicly complain. Games live and die on the whims of their audiences; It's generally a very bad idea to piss off the most dedicated 10% of your playerbase.
Unless that dedication is highly remunerative, pissing them off can be the smart thing to do, if that means pleasing the other 90%. The problem comes when the developers are having their egos stroked by this dedication. Imagining that those players are somehow valuable for PR is part of the rationalization for serving them, but experienced lesser players will learn that a game that caters to that elite won't be fun for them, and will treat that catering as the negative sign it is.
You're not wrong, but the other end of the spectrum is that you don't have any players because the only ones talking about it are unhappy.
I used to work on F2P games, and you have to balance things. As nice as it would be to ignore the loudmouths, unless you can guarantee that no one else is listening to them either, which you can't, you'll have to cater to them somewhat to pacify them.
I used to work on F2P games, and you have to balance things. As nice as it would be to ignore the loudmouths, unless you can guarantee that no one else is listening to them either, which you can't, you'll have to cater to them somewhat to pacify them.
I think Quake 3 used a bit of genetic algorithms to optimize some of the variables of the bots
Programmers always want to automate content creation. I get it as I’m a coder and it’s a fun problem space. Plus creating content is super time and skill intensive. It’s really hard to get right in my experience. Kind of like trying to automate writing a novel…
OK I read the article. I'm very skeptical of this approach. I doubt we can actually uncover fitness functions that reliably maps to "fun", and I believe it would require huge engineering effort to keep the game "simulable." Their examples aren't convincing. What would be convincing is a full, complex, and _fun_ game using these techniques.
Also the article seems like an ad for their AI solution.
OK I read the article. I'm very skeptical of this approach. I doubt we can actually uncover fitness functions that reliably maps to "fun", and I believe it would require huge engineering effort to keep the game "simulable." Their examples aren't convincing. What would be convincing is a full, complex, and _fun_ game using these techniques.
Also the article seems like an ad for their AI solution.
> Programmers always want to automate content creation
We have a god complex that brain surgeons can only envy. How many universes have they built?
We have a god complex that brain surgeons can only envy. How many universes have they built?
I suspect everyone on HN started out wanting to build COOL WORLDS as a kid!
I wouldn’t say it was an inspiration, no
https://en.wikipedia.org/wiki/Cool_World_(SNES_video_game)
https://en.wikipedia.org/wiki/Cool_World_(SNES_video_game)
I still do :)
> I doubt we can actually uncover fitness functions that reliably maps to "fun"
You don't have to. Get empirical data and form a proxy evaluator. Usable enough for most evolutionary algorithms. I've done this sort of stuff for very subjective metrics and actually sold something with it.
You don't have to. Get empirical data and form a proxy evaluator. Usable enough for most evolutionary algorithms. I've done this sort of stuff for very subjective metrics and actually sold something with it.
> Kind of like trying to automate writing a novel…
So you are saying procedural level design could be solved with generative AI?
So you are saying procedural level design could be solved with generative AI?
In theory. It'll be more convincing once generative AI proves itself useful for writing novels.
AI can already write short stories, just not very good ones. It'll be doing novels once the context windows are big enough.
Note also that base models (foundation models) are much better at writing fiction than models tuned for chat. See https://nostalgebraist.tumblr.com/post/706441900479152128/no...
Agreed, the technology looks promising but isn't ready yet.
It's orders of magnitude better than procedural methods written by humans.
At writing novels or creating games? I'm open to evidence of either...
At writing novels. So potentially also at procedural level design.
I'm admittedly skeptical. The AI generated novels I've seen have been bad. Really really bad. It's been a few months, however, so maybe the landscape has evolved faster than I expected.
Is there a source you can recommend for further reading?
Is there a source you can recommend for further reading?
Which novels? Did you compare them to novels created by handcrafted algorithms? I guarantee you, what you have read wasn't bad, it was fantastically good, compared to anything a software could have come up with without machine learning. So it seems likely that traditional procedural level generation could also be far outperformed by AI systems.
> procedural methods written by humans
I did not understand what you intended here, but I see what you mean. I totally agree that these are the algorithms to beat.
I'd argue that procedural methods should also include human writing processes, which to date have produced the best output.
I assume the technology will get there eventually.
I did not understand what you intended here, but I see what you mean. I totally agree that these are the algorithms to beat.
I'd argue that procedural methods should also include human writing processes, which to date have produced the best output.
I assume the technology will get there eventually.
I've been able to write coherent stories a dozen pages long. You need to have it generate plot points and other auxiliary information about characters and whatnot and it does a pretty good job. Obviously it's not going to one shot all that yet.
[deleted]
I would call it a very good implementation of "old school" AI, where the behavior of your actors is all about utility curves, Monte Carlo search, and genetic algorithms. Basically all math/algorithm based stuff, kind of like old expert system AI implementations.
Of course "new school" AI is all about neural networks that can automatically learn those complex actor behaviors without the developer explicitly specifying all those mathematical algorithms.
Like many people here I'm very interested in working on hooking up modern "new school" AIs to virtual worlds, so it's very interesting to see Grail as a good concrete example of the algorithmic approach to game AI. I suspect some hybrid fusion of both approaches may give us some interesting and fun AI behavior.
[1] https://grail.com.pl/media/Grail_Whitepaper_June_2021.pdf