Lecture 12
----------
Game AI
first, should discuss AI and Alife
Artificial Intelligence
- algorithms that immitate "intelligent activity"
Agents are addressed in AI but AI is broader
- an agent is just something that acts "independently",
generally in some sort of environment
problems addressed by AI
- pattern recognition
- planning (path, other)
- search <- the big one
Search is key because most of AI involves formulating other problems
as search problems
- e.g., planning is search over possible ordering of tasks
Big contribution of AI: learning is search
Why is AI hard
- how to define the right search space?
- how to search it effectively (when it is way, way to big to search
exhaustively)?
A good search space
- allows for expression of possible solutions
- can be effectively searched, i.e., it is possible to make "progress"
Think of search spaces as landscapes
- in 2D, planes, mountains, valleys, etc
- but generalizes to higher dimensions (in sometimes surprising ways)
- how do you find the highest peak?
- without a global view?
- if the landscape is easily searchable, local gradients are helpful
- but in general, local gradients only get you so far
- because of local maxima (the local hill, not the distant mountains)
- once you get to a top of a hill, nowhere to go that isn't "worse"
- good search algorithms have strategies to avoid local maxima
- note peak = optimal solution, so this is also talking about optimization
Artificial Life
- how do we simulate "lifelike" behavior?
- ant foraging rather than playing chess
- chess is an artificial problem that is hard for humans
- looking in an environment for food is easy for most living things
- alife is much more interested in "good enough" rather than "optimal" approaches
- alife cares about dynamic environments with active, adaptive adversaries
- why optimization generally isn't feasible, the game keeps changing
- most AI formulations assume a static task
- one formulation: evolutionary stable strategies
How does Alife and AI connect to Game AI?
- game AI can make use of AI and alife techniques
- but game AI has fundamentally different goals
First, consider symmetric games
- computer "player" follows same rules as human player
- e.g., Chess, board games
- do you want the best computer player you can make?
- generally no, as it will often be too good
- need ways to make it worse than optimal
- traditionally AI players were much worse than good human players
- but even there, you need to scale skills
- today, AI players can be very good indeed
When can a game AI do really well?
- when the search space of possibilities can be effectively searched
- modern hardware means we can do a lot more searching!
- also, many algorithmic improvements
How do you scale a symmetric game AI
- limit search
- add randomness, deliberate mistakes
- simulate "styles"
- start getting into alife
With asymmetric games, gets more complicated
- in general, computer has much more knowledge than the player
- controls many agents & the world
- thus, it is always possible for the game AI to "win" by cheating
- think strategy games where it knows all the rules & secrets
- so, to make it fun, the game AI must play "fair"
- act as if it doesn't know more than the player
- but, to make the behavior work, you still may need to make use
of info the player doesn't have
most game AI's cheat in some way
- make use of info the player doesn't have
for situations where the AI task is complex, this may be essential
- without cheating, the AI would be too dumb or too slow
Game AI's need lots of tuning because it is hard to formally define
what is "fun"
This is also why online gaming has become so popular
- more fun to play against people rather than bots,
because people play in more "interesting" ways
Think about Among Us
- basic mechanics are *so* simple
- sophistication comes from interactions with other players
- text chat with them!
- who is the murderer?
If you allow players to act in completely flexible ways, you get a
world where bots have to pass the Turing test in order to be fun
- if you go there, you really just bring in other humans
In single player games, we have to limit player actions so game AIs
have a chance to behave in interesting ways
- limit branching of stories
- limited conversations with NPCs
Compare computer RPGs with playing tabletop RPGs
Text adventures tried to get some of the open-ended feel
- but you quickly run into limitations of the parser and world
automated turing test competitons
- chatbots that try to pretend they are humans
- can be pretty convincing, but mainly by being absurd
- you're not going to have a "real conversation"
Traditionally game AI and real AI are very different
- but there's lots of opportunity for them to become closer in interesting
ways
While game engines today have very limited support for game AI, I
think a future direction for game engines will be adding rich support
for AI that would enable non-player characters that you could interact
with in much more flexible ways. Things like AI Dungeon I think are
on the forefront of this, so it is worth keeping an eye on them. The
trouble is that current mainstream approaches to AI aren't likely to
produce really flexible chatbots - I think that would require a more
alife approach.