Game Playing in Artificial Intelligence

GAME PLAYING IN
ARTIFICIAL
INTELLIGENCE
By:
P.MOHIT
16841A0542
CSE-4A
Introduction
• One of the most studied and most interesting areas of Artificial Intelligence is
Game Playing. They are fun, and HARD to create.
• Game playing was one of the first tasks undertaken in Artificial Intelligence.
• Game theory has its history from 1950, almost from the days when computers
became programmable.
• The very first game that is been tackled in AI is chess.
• Initiators in the field of game theory in AI were Konard Zuse, Claude Shannon,
Norbert Wiener and Alan Turing.
Introduction contd...
• Since then, there has been a steady progress in the standard of play, to the
point that machines have been able to beat human champions in chess and
backgammon, and are also competitive in many other games.
• Game Playing in Artificial Intelligence refers to techniques used in computer

and video games to produce the illusion of intelligence in the behaviour of non-
player characters (NPCs).
• The main goal of Game Playing in AI is to develop the rational agents to match
or exceed human performance.
Why are games relevant to AI?
• Games are fun.
• They are limited and have well-defined rules.
• They provide advanced, existing test-beds for developing several ideas and
techniques that are useful elsewhere.
• They are one of the few domains that allow us to build agents.
• Studying games teaches us how to deal with other agents who’re trying to foil
our plans.
• Huge state spaces – Games are highly complex. Usually, there’s not enough
time to work out the perfect move. E.g Go & Chess .
• Nice, clean environment with clear criteria for success.
• Game playing is considered an intelligent human activity.
• AI has always been interested in abstract games.
• Games present an ideal environment where hostile agents may compete.
Types of Games played
• Strategy Games.
• Real-Time Strategy (RTS).
• Turn-Based Strategy (TBS) .
• Helicopter view.
• Role-Playing Games (RPG).
• Single-Player .
• Multi-Player (MMORPG).
• Action Games.
• First-Person Shooters (FPS).
• First-Person Sneakers.
• Sports Games.
• Simulations.
• Adventure Games.
• Puzzle Games.
History and Overview
• Minimax
- Developed by John von Neumann in 1928.
- This algorithm is used extensively in game theory.
• Samuel’s learning program (1959)
- The program learns through the manipulation of the summation of heuristics.
- If the program wins, it raises high heuristic values and lowers low ones. If it loses, it does the opposite.
• 1960s
- Progress and success in Game AI.
- Creating a successful AI meant coming up with the right rules for it to follow.
• 1970s-1980s
- Transition to games as entertainment.
- Using search based AI to emulate entertaining characters would be unnatural.
• Clumsy
- Game play is based more on skill than on rules.
• Early 1990s
- Increased realism becomes the primary focus of the game industry.
- A rift developed between the developers of popular games and AI researchers.
• Late 1990s
- To add intrigue, developers look again to AI.
The Minimax Rule
• MiniMax rule: Decision Making in Multi-agent Systems
• Perfect play for deterministic, perfect-information games.
• Idea: make the move for player MAX which has the most benefit assuming that
MIN makes the best move for MIN in response .
• This is computed by a recursive process
• The backed-up value of each node in the tree is determined by the values of its
children
• For a MAX node, the backed-up value is the maximum of the values of its
children (i.e. the best for MAX)
• For a MIN node, the backed-up value is the minimum of the values of its
children (i.e. the best for MIN)
Minimax Procedure
Consider a 2-ply (two step) game:
Max wants largest outcome --- Min wants smallest.
• Start with the current position as a MAX node.
• Expand the game tree a fixed number of ply (half-moves).
• Apply the evaluation function to the leaf positions.
• Calculate back-up up values bottom-up.
• Pick the move which was chosen to give the MAX value at the root.
Minimax Overview
• MinMax the heart of almost every computer board game
• Applies to games where: -

▫ Players take turns .
▫ Underlying assumption .
 Opponent acts rationally .
▫ Have perfect information .
 Chess, Checkers, Tactics .
• But can work for games without perfect information or chance e.g Poker,
Monopoly.
• Can work in real-time also.

Alpha-Beta Pruning
• Now consider another move of MAX (given fig). That will lead to 3 possible
moves of MIN.
• One of these moves has utility value of 2. Now this becomes beta value of MIN
node.
• Now whatever may be the utility values of other two children, utility value of MIN
node cannot be grater than 2.
• Thus this MIN can propagate upward at the max value of 2. This 2 is less than
current alpha of MAX node i.e. 3. Because MAX is assured with the utility value
of at least 3, it will not consider any MIN node returning utility value less than 3.
• And thus it prunes the search there for this MIN node. Thus without considering
other 2 children of MIN node we can proceed further.
• This is called as alpha pruning i.e. pruning based on alpha value and applied at
the MIN node.
• Beta pruning is same as alpha pruning with the difference that it is applied at
MAX node.
•  -  pruning reduces the search space without affecting final result. Order in
which successors are scanned affects performance.
• With a good ordering we can improve the performance but in the worst case it
may result in no improvement in performance.
• This method of alpha beta pruning can be applied in the games with chance. E.g
chance card game where chance introduced by card shuffling, or games involving
dice rolling.
Examples
• First Person Shooters (Half life, Deus Ex, Unreal

Tournament):
▫ “Suicidal” AI is replaced by more sophisticated AI that
appears to care about its own life.
▫ It coordinates attacks, calls for backup, and retreats when
hurt.
▫ Friendly AI can even be given orders by the player.
• Real Time Strategy:

▫ AI in the broad scheme doesn’t evolve much in RTS games.
▫ Individual unit scripts are added in to some games, but in
the over all picture, the AI still simply pours units at an
enemy until it is defeated. Perhaps this is because of the
foreignness of the RTS paradigm, or maybe it really is the
best strategy.
▫ Most successful human players abide by this “rush”
strategy.
Applications
• Human
-level AI
- Every person is an expert on human-level intelligence
- Testing of AI is easy
• Entertainment
-Game theory is used to define different strategies of different games.
• Economics
-Each factor in the market, such as seasonal preferences, buyer choice, changes in supply and material
costs, and other such market factors can be used to describe strategies to maximize the outcome and thus
the profit.
• Military
▫ -Game theory can be useful in Military also. Military strategists have turned to game theory to play "war
games". Usually, such games are not zero-sum games, for loses to one side are not won by the other.
• Political science
-The properties of n-person non-zero-sum games can be used to study different aspects of political
science and social science. Matters such as distribution of power, interactions between nations, the
distribution of classes and their effects of government, and many other matters can be easily investigated
by breaking the problem down into smaller games, each of whose outcomes affect the final result of a
larger game
• Movies
- Crowd scenes
- Flocking behaviour
- Realistic Movement
Game AI Major Challenges
• Resources
- Realism in computer games focused on graphics.
- Advanced graphics requires many CPU cycles.
- Recent advances in computer hardware have someone alleviated this issue.
• Research and Development
- Lack of cohesion between AI research community and game developers.
- AI in modern computer games seems trivial to AI researchers.
• Human Level Intelligence
- Human level behaviour will require AI.
- We currently have only limited behaviour.
- Human level intelligence is really hard to create and we still do not know how to
achieve it.
• Deadlines
- Game engine must be developed before AI can be tested.
- AI programmers often have to compromise to meet deadlines.
Changes in Gaming
• Games were linear sequences of challenges
▫ Challenge itself as play-value/entertainment.
▫ “World” abstracted and simplified.
• Current trends
▫ High world fidelity, and growing.
▫ Open-ended worlds, player choice/customization .
▫ New aspects of play.
The Future of Game AI
• Intelligent Landscape
- Sims weren’t smart at all
- Instead, surrounding objects contained instructions for use
- AI finds the object that makes them happy and follows instructions
• Fuzzy AI
- Rule based AI is not sufficient to model human intelligence
- Uncertain algorithms such as Genetic Algorithms and Neural Networks are
the future
• Immersive game space

- Instead of creating a reality, the AI borrows from the real world
Summary
Game theory remained the most interesting part of AI from

the birth of AI. Game theory is very vast and interesting topic. Game
theory mainly deals with working in the constrained areas to get the
desired results. They illustrate several important points about
Artificial Intelligence like perfection can not be attained but we can
approximate to it.
THANK YOU!

Game Playing in Artificial Intelligence

Uploaded by

Copyright:

Available Formats

Game Playing in Artificial Intelligence

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Game Playing in Artificial Intelligence

Uploaded by

Copyright:

Available Formats

GAME PLAYING IN

• The very first game that is been tackled in AI is chess.

• Game Playing in Artificial Intelligence refers to techniques used in computer

• Perfect play for deterministic, perfect-information games.

• This is computed by a recursive process

• Applies to games where: -

• Can work in real-time also.

• First Person Shooters (Half life, Deus Ex, Unreal

• Real Time Strategy:

• Immersive game space

Game theory remained the most interesting part of AI from

You might also like