Jump to content

  • Log In with Google      Sign In   
  • Create Account


Genetic Programming in Games


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
17 replies to this topic

#1 Blessman11   Members   -  Reputation: 110

Like
0Likes
Like

Posted 11 March 2012 - 05:00 AM

How is genetic programming being applied in modern games? I feel its need for bots, because they are just so damn stupid and having being an avid shooter fan, I have now lost faith through being desensitised by the same type of AI carried over from the last generation (the bots don't appear to be smarter). Which games are currently implementing this if anyway? (I feel like this is the graphics craze generation and it hopefully must be the last since it has ruined games for me).

Anyway I'm currently looking into researching genetic algorithms for my final year project at uni, so any general advice in this area?
(This is largely related to cybernetic(systems with react to difference within an environment), which had in another post here)

Sponsor:

#2 Madhed   Crossbones+   -  Reputation: 2012

Like
0Likes
Like

Posted 11 March 2012 - 07:34 AM

I am not sure about the actual implementation of GAs in games but there are quie a few theses about implementing GAs for bots, especially in Quake3 Arena.
Googling "Genetic Algorithm Bots" or "Genetic algorithm Quake 3" will yield some good results. Take this for example:

http://www.ai.rug.nl/~mwiering/thesis_j_g_gerrits.pdf

cheers

#3 Alpha_ProgDes   Crossbones+   -  Reputation: 4505

Like
0Likes
Like

Posted 11 March 2012 - 08:43 AM

I'm not sure if it was in this version of the forums or the old one, but I remember IADaveMark(sp?) having a whole (long) thread about GAs and their use in games.
Beginner in Game Development? Read here.
 
Super Mario Bros clone tutorial written in XNA 4.0 [MonoGame, ANX, and MonoXNA] by Scott Haley
 
If you have found any of the posts helpful, please show your appreciation by clicking the up arrow on those posts Posted Image
 
Spoiler

#4 IADaveMark   Moderators   -  Reputation: 2220

Like
0Likes
Like

Posted 11 March 2012 - 09:08 AM

I'm not sure if it was in this version of the forums or the old one, but I remember IADaveMark(sp?) having a whole (long) thread about GAs and their use in games.

Seriously? It wasn't me. I can't really think of many examples where GAs are used.

Please note there is a difference between "genetic programming" and a "genetic algorithm". The former assembles commands in certain orders over time whereas the later is mostly used for tuning and tweaking values that are used for calculations. The code stays the same, only the variables that it uses change.

That said, if you have complex calculations with "knobs" that can be turned, you can use a GA to optimize them. Theoretically, it saves on the headache of manually tuning them. My contention (and this is what I lecture on quite a bit -- including at the GDC AI Summit last week) is that if your numbers are that obscure that you can't intuitively grok how to tune them, your design might be sub-optimal. Put your numbers together in such a way that you can intuit how their effect cascades through the whole model.
Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

#5 Alpha_ProgDes   Crossbones+   -  Reputation: 4505

Like
0Likes
Like

Posted 11 March 2012 - 01:04 PM


I'm not sure if it was in this version of the forums or the old one, but I remember IADaveMark(sp?) having a whole (long) thread about GAs and their use in games.

Seriously? It wasn't me. I can't really think of many examples where GAs are used.

Well I believe the thread was more along the lines of "DON'T USE (or STOP ASKING ABOUT) GAs IN GAMES". It was a long thread about people misusing them because they are a fad (or something along those lines). If it wasn't you, then my apologies.
Beginner in Game Development? Read here.
 
Super Mario Bros clone tutorial written in XNA 4.0 [MonoGame, ANX, and MonoXNA] by Scott Haley
 
If you have found any of the posts helpful, please show your appreciation by clicking the up arrow on those posts Posted Image
 
Spoiler

#6 kirkd   Members   -  Reputation: 505

Like
1Likes
Like

Posted 12 March 2012 - 09:36 AM

From a research perspective, you should check out NERO by Ken Stanley: http://nerogame.org/ The premise is evolving neural nets to control bots in a FPS type game. He has done a lot of work on evolving neural nets (see http://www.cs.ucf.edu/~kstanley/), and at the risk of being flamed out of existence, I've incorporated a NEAT implementation for evolving a Pac-Man controller: http://sourceforge.net/projects/aipac/?source=directory

Again, all of this is from a research perspective and doesn't necessariliy apply to a commercial game.

-Kirk

#7 IADaveMark   Moderators   -  Reputation: 2220

Like
0Likes
Like

Posted 12 March 2012 - 10:59 AM



I'm not sure if it was in this version of the forums or the old one, but I remember IADaveMark(sp?) having a whole (long) thread about GAs and their use in games.

Seriously? It wasn't me. I can't really think of many examples where GAs are used.

Well I believe the thread was more along the lines of "DON'T USE (or STOP ASKING ABOUT) GAs IN GAMES". It was a long thread about people misusing them because they are a fad (or something along those lines). If it wasn't you, then my apologies.


Oh... that was NNs. Similar, however.
Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

#8 IADaveMark   Moderators   -  Reputation: 2220

Like
0Likes
Like

Posted 12 March 2012 - 11:02 AM

I believe that the premise that FPS AI is stupid-beyond-repair is flawed. There are plenty of good FPS bots out there from companies that decided it was a high priority. Killzone 2's bots, for example, are well-regarded.

The dirty secret is that it is not hard to make a bot that will completely crush people. The hard part is making a bot that feels natural and fun to play against regardless of people's skill levels.
Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

#9 willh   Members   -  Reputation: 160

Like
0Likes
Like

Posted 13 March 2012 - 11:06 AM

I don't know Dave. I play BF3 from time to time, and when a fellow human being and I are able to cooperate to cause carnage without verbally communicating I find the experience very rewarding. None of the bots in the game are smart enough to do that.

The linked paper was attempting to build a cooperative team of bots, not an über bot. It was a good example of using machine learning to explore a problem. Im not sure I would have used a neural network, but the evolutionary strategy was a good one. The resulting bots played better as a team, both with and without a human. Aside from the initial experimental setup, i got the impression that building a new bot took very little time.

It would be a nice thing if there were bots who acted so much like people that you didn't know they were bots. The same thing could apply to MineCraft or a number of other games. NPCs are not a solved problem.

#10 swiftcoder   Senior Moderators   -  Reputation: 8075

Like
1Likes
Like

Posted 13 March 2012 - 12:19 PM

None of the bots in the game are smart enough to do that.

I think you will find that they are intentionally not smart enough to do that.

It takes very little effort to make a bot with perfect aim, perfect reflexes, and the ability to share perfect tactical information with fellow bots. That's probably the easiest type of bot to create.

Designing a bot that misses occasionally, doesn't always notice the player hiding in a corner, and sometimes lets its teammate be killed... That takes considerable thought.

Tristam MacDonald - SDE II @ Amazon - swiftcoding        [Need to sync your files via the cloud? | Need affordable web hosting?]


#11 Net Gnome   Members   -  Reputation: 769

Like
0Likes
Like

Posted 13 March 2012 - 02:12 PM

The dirty secret is that it is not hard to make a bot that will completely crush people.


Damn you Quake ReaperBot! Damn you!

[update] Actually, i think some of the 3rd Gen roguelike AI was actually almost un-killable now that i think about it since it learned player weaknesses and attacks and adjusted its skill choice based on that information. I believe it pre-dated quake.

#12 willh   Members   -  Reputation: 160

Like
0Likes
Like

Posted 13 March 2012 - 03:04 PM


None of the bots in the game are smart enough to do that.

I think you will find that they are intentionally not smart enough to do that.

It takes very little effort to make a bot with perfect aim, perfect reflexes, and the ability to share perfect tactical information with fellow bots. That's probably the easiest type of bot to create.


That's not what I meant. In BF3 there are all kinds of way players can work together with devastating consequences. Take jets; when one player acts as bait, so another can get on the tail of an attacker and gun them down.

These are very complex behaviors with no immediate reward for either player. I haven't seen a bot that is able to spontaneously take part in complex adaptive team work. In the campaign mode of BF3 the enemy NPCs are fun, but not so fun that they would enhance the multiplayer mode.



#13 Franck Dernoncourt   Members   -  Reputation: 142

Like
0Likes
Like

Posted 29 March 2012 - 06:18 PM

This free e-book may interest you: Evolved to Win (2011; 193 pages)

Title: Evolved to Win
Author: Moshe Sipper
Abstract: Recent years have seen a sharp increase in the application of evolutionary computation techniques within the domain of games. Situated at the forefront of this research tidal wave, Moshe Sipper and his group have produced a plethora of award-winning results, in numerous games of diverse natures, evidencing the success and efficiency of evolutionary algorithms in general—and genetic programming in particular—at producing top-notch, human-competitive game strategies. From classic chess and checkers, through simulated car racing and virtual warfare, to mind-bending puzzles, this book serves both as a tour de force of the research landscape and as a guide to the application of evolutionary computation within the domain of games.


But it doesn't directly deal with modern games.

#14 jefferytitan   Members   -  Reputation: 1174

Like
0Likes
Like

Posted 29 March 2012 - 08:32 PM

I would agree that it's not hard to make a bot that crushes people using non-human advantages, e.g. perfect instant aim and perfect knowledge. However I think it would be much harder to make a competitive bot starting from the same assumptions that human have to play under, e.g. 200ms reflex time, need to visually find enemies from pixel data, occasionally faulty input devices (think of general mouse issues and the need to stay on the mousepad etc). Some of the sneaking type games incorporate facets of that. Bring in cheatiness like rocket-jumping type manoeuvres which AIs can't be expected to pick up... the human has an advantage unless they're dumb or don't co-operate. I think limitations can contribute to human likeness as much as specific features.

#15 swiftcoder   Senior Moderators   -  Reputation: 8075

Like
0Likes
Like

Posted 29 March 2012 - 10:19 PM

However I think it would be much harder to make a competitive bot starting from the same assumptions that human have to play under, e.g. 200ms reflex time, need to visually find enemies from pixel data, occasionally faulty input devices (think of general mouse issues and the need to stay on the mousepad etc).

Harder? Ye gads, make that near impossible. You could throw *all* the available processing power at implementing computer vision, and still not reliably "see" opponents.

The point was not that it's too easy to build a decent bot, the point is that it's quite hard to build a bot that plays at a slightly-worse-than-human level. Making it considerably harder to write a human-level bot doesn't help us at all...

Tristam MacDonald - SDE II @ Amazon - swiftcoding        [Need to sync your files via the cloud? | Need affordable web hosting?]


#16 Álvaro   Crossbones+   -  Reputation: 10598

Like
0Likes
Like

Posted 29 March 2012 - 10:25 PM

Having to recognize the scene from pixel data is unfair to the agent. It would be like giving the human an ASCII dump of the current situation every frame. Humans are better at recognizing visual patterns, and that's how the game communicates the information about the current situation to them, but it would be ridiculous to communicate with an AI agent that way.

#17 jefferytitan   Members   -  Reputation: 1174

Like
0Likes
Like

Posted 30 March 2012 - 03:25 AM

I did wonder whether people would focus on that one phrase. ;) What I meant is that an agent which is given an object reference and a position doesn't have to cope with issues such as having difficulty spotting an enemy hiding in the dark, that only has one pixel visible from behind an occluder, that is so far away that they only appear as 1 pixel high, that are wearing an outfit that camoflages well with the background, etc. Most of that can be emulated at much lower cost than burning all your CPU power on true computer vision.

#18 Malabyte   Members   -  Reputation: 583

Like
0Likes
Like

Posted 31 March 2012 - 02:46 PM

I think the AI in many games could've been tons better if the devs just knew wth they were doing. I remember Total Annihilation, a game that had a ton more AI (effectively, not actually) than almost every other RTS to date, because of how the in-game commands were designed and how the AI was scripted with that in mind.

To me, the gaming industry seems to be showing off LESS intelligence nowadays than in certain games before. I guess they're all trying to implement actual AI but at the same time being allergic to illusory AI (an incredibly powerful game feature if implemented correctly, because you can potentially make the AI smarter than the player). Let's call it "reactive AI" instead, as that's more accurate.

I like to think that a good AI is an AI that is hard (if not impossible) to predict. But most games nowadays, maybe with the exception of Starcraft 2 and similar (although that too could've been a lot more unpredictable), are horrendously predictable. I'm thinking that a given mob should be choosing somwhat randomly between more than one AI construct, depending on the information that the mob gets of the player. If the player is passive, the AI should be aggressive and vice versa. But also break it up and then suddenly be behaving differently 30% of the time (not just because something happens that changes its behaviour).

You know, simple Texas Hold'Em psychology. :D

I think one of the biggest mistakes of the gaming industry is to exclusively try to make the cpu as smart as possible. At least that's what it looks like their doing, from a gamer's perspective. The best form of AI, IMO, is one that breaks up smart decisions with a little bit of stupidity here and there, so that it leaves the player wondering "what the heck just happened"? It's kinda embarassing when you see a human NPC having the exact same behaviour as a Wild Boar.

- Awl you're base are belong me! -

- I don't know, I'm just a noob -





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS