Game Engines 2021W Lecture 12

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.