Unit 1

Meaning and definition of AI:

 Artificial Intelligence (AI) means making computers and machines think and act like humans. It allows
machines to learn, solve problems, and make decisions, just like people do.

 AI is a branch of computer science that enables machines to perform tasks that usually require human
intelligence, such as learning, reasoning, problem-solving, understanding language, and recognizing images

 Artificial Intelligence refers to the simulation of human intelligence in machines that are programmed to
think, reason, and learn like humans. Rather than being explicitly programmed for specific tasks,
AI(Artificial Intelligence) systems use algorithms and vast amounts of data to recognize patterns, make
decisions, and improve their performance over time.

 Artificial Intelligence encompasses a wide range of technologies, including machine learning, natural
language processing, computer vision, and robotics. These technologies enable AI systems to perform
complex tasks, such as speech recognition and face detection, with remarkable accuracy.

For example:

 A voice assistant like Alexa or Siri understands your voice and answers your questions.
 A self-driving car can drive without a human driver.
 A spam filter removes unwanted emails automatically.

study of AI also involves other disciplines including Psychology, Philosophy, Science, etc.

AI works in five steps:

 Input: Data is collected from various sources. This data is then sorted into categories.

 Processing: The AI sorts and deciphers the data using patterns it has been programmed to learn until it
recognizes similar patterns in the data.

 Outcomes: The AI can then use those patterns to predict outcomes.

 Adjustments: If the data sets are considered a “fail,” AI learns from that mistake, and the process is
repeated again under different conditions.

 Assessments: In this way, AI is constantly learning and improving.

Key Aspects of AI:
 Understanding and Communicating (Natural Language Processing - NLP): AI can understand and generate
human language (e.g., chatbots like Siri, Google Assistant).

 Learning and Adapting (Machine Learning - ML):AI can improve its performance over time by learning from
data (e.g., Netflix recommendations, spam filters).

 Reasoning and Problem-Solving (Automated Reasoning):AI can analyze information and make decisions
(e.g., Google Maps finding the best route).

 Recognizing Patterns (Computer Vision):AI can identify images and objects (e.g., face recognition in
phones).

 Physical Interaction (Robotics):AI-powered robots can interact with the physical world (e.g., self-driving
cars, robotic vacuum cleaners).

Different Approaches to AI:

 Acting Humanly (Turing Test Approach):If an AI system can converse so naturally that humans cannot tell it
apart from a real person, it is considered intelligent.

 Thinking Humanly (Cognitive Modeling Approach):AI is designed to think and solve problems like humans,
based on psychology and neuroscience.

 Thinking Rationally (Laws of Thought Approach):AI follows logical rules to always make the best possible
decision.

 Acting Rationally (Rational Agent Approach):AI makes the best possible decision in a given situation, even
under uncertainty (e.g., self-driving cars making real-time decisions).

Intelligent agent and environments:

In artificial intelligence, an agent is a computer program or system that is designed to perceive its environment,
make decisions and take actions to achieve a specific goal or set of goals. The agent operates autonomously,
meaning it is not directly controlled by a human operator.

Agents can be classified into different types based on their characteristics, such as whether they are reactive or
proactive, whether they have a fixed or dynamic environment, and whether they are single or multi-agent
systems.

 Reactive agents are those that respond to immediate stimuli from their environment and take actions
based on those stimuli. Proactive agents, on the other hand, take initiative and plan ahead to achieve their
goals. The environment in which an agent operates can also be fixed or dynamic. Fixed environments have
a static set of rules that do not change, while dynamic environments are constantly changing and require
agents to adapt to new situations.
 Multi-agent systems involve multiple agents working together to achieve a common goal. These agents
may have to coordinate their actions and communicate with each other to achieve their objectives. Agents
are used in a variety of applications, including robotics, gaming, and intelligent systems. They can be
implemented using different programming languages and techniques, including machine learning and
natural language processing.

Artificial intelligence is defined as the study of rational agents. A rational agent could be anything that makes
decisions, such as a person, firm, machine, or software. It carries out an action with the best outcome after
considering past and current percepts(agent’s perceptual inputs at a given instance). An AI system is composed
of an agent and its environment. The agents act in their environment. The environment may contain other
agents.

An agent is anything that can be viewed as:

 Perceiving its environment through sensors and

 Acting upon that environment through actuators

Understanding the Environment

An agent’s environment includes everything it interacts with. However, we only consider the part of the
environment that:

 Affects what the agent perceives.

 Can be influenced by the agent’s actions.

Types of Agents

Simple Reflex Agents: Simple reflex agents make decisions based only on the current situation, ignoring past
experiences. They follow condition-action rules, means perform an action if a certain condition is met. This
works well only in fully observable environments (where all necessary information is available at moment).

Problems with Simple reflex agents are :

 Very limited intelligence.
 No knowledge of non-perceptual parts of the state.
 Usually too big to generate and store.
 If there occurs any change in the environment, then the collection of rules needs to be updated.
Model-Based Reflex Agents:A model-based agent works by using a set of rules that match the current
situation. Unlike simple reflex agents, it can handle partially observable environments by maintaining an
internal state, which helps track unseen parts of the world based on past experiences (percept history).

Updating the Internal State Requires:

 How the world changes on its own – Understanding natural changes in the environment.
 How the agent’s actions impact the world – Knowing the effects of its decisions.

Goal-Based Agents:Goal-based agents make decisions by focusing on their goal (a desired outcome). They
choose actions that bring them closer to the goal, helping them pick the best option among many. Since their
decision-making process is explicit and adjustable, they are more flexible than simple reflex agents. These
agents rely on search and planning, making it easy to change their behavior when needed.

Utility-Based Agents:They are designed to make the best choice when multiple options are available. They
don’t just focus on reaching a goal but consider factors like speed, safety, & cost to make better decisions.They
use a utility function, which measures how "happy" an agent is in a given situation. Since the world is uncertain,
they choose actions that maximize their expected happiness (utility), ensuring the best outcome.
Learning Agent: A learning agent can learn from experience and improve its performance over time. It starts
with basic knowledge and adapts automatically as it learns.

Main Components of a Learning Agent:

1. Learning Element – Improves the agent’s performance by learning from the environment.
2. Critic – Gives feedback on how well the agent is performing based on a fixed standard.
3. Performance Element – Chooses the agent’s actions.
4. Problem Generator – Suggests new actions to help the agent gain useful experiences.

Multi-Agent Systems: Multi-Agent Systems (MAS) consist of multiple agents that work together to achieve a
common goal. These agents can be autonomous or semi-autonomous, meaning they make decisions and take
actions based on their environment.

Types of Multi-Agent Systems:

 Homogeneous MAS – All agents have the same abilities and goals.
 Heterogeneous MAS – Agents have different abilities and goals, making coordination harder but
increasing flexibility.
 Cooperative MAS – Agents work together toward a shared goal.
 Competitive MAS – Agents compete to achieve their own goals.
 Mixed MAS – A mix of cooperation and competition.
Hierarchical Agents:Hierarchical agents are structured in levels, where high-level agents set goals and rules,
and low-level agents perform specific tasks. This setup is useful for managing complex tasks efficiently.

How They Work:

 High-level agents decide goals and constraints based on the system’s overall objective.
 Low-level agents carry out specific tasks to achieve those goals.
 Intermediate-level agents (if present) help coordinate lower-level agents in complex systems.

Nature of environment:
An environment in artificial intelligence is the surrounding of the agent. The agent takes input from the
environment through sensors and delivers the output to the environment through actuators.

When designing an agent, the first step is to clearly define its task environment, which consists of:

 Performance Measure – How we evaluate the agent’s success.

 Environment – The surroundings in which the agent operates.
 Actuators – The parts that allow the agent to take action.
 Sensors – The parts that allow the agent to gather information.

To make it easy to remember, this is called the PEAS (Performance, Environment, Actuators, Sensors)

There are several types of environment:

1. Fully Observable vs Partially Observable

 When an agent sensor is capable to sense or access the complete state of an agent at each point in time,
it is said to be a fully observable environment else it is partially observable.
 Maintaining a fully observable environment is easy as there is no need to keep track of the history of the
surrounding.
 An environment is called unobservable when the agent has no sensors in all environments.
Examples:
Chess – the board is fully observable, and so are the opponent’s moves.
Driving – the environment is partially observable because what’s around the corner is not known.

2. Deterministic vs Stochastic
 When a uniqueness in the agent’s current state completely determines the next state of the agent, the
environment is said to be deterministic.
 The stochastic environment is random in nature which is not unique and cannot be completely
determined by the agent.
Examples:
Chess – there would be only a few possible moves for a chess piece at the current state and these
moves can be determined.
Self-Driving Cars- the actions of a self-driving car are not unique, it varies time to time.

3. Competitive vs Collaborative
 An agent is said to be in a competitive environment when it competes against another agent to optimize
the output.
 The game of chess is competitive as the agents compete with each other to win the game which is the
output.
 An agent is said to be in a collaborative environment when multiple agents cooperate to produce the
desired output.
 When multiple self-driving cars are found on the roads, they cooperate with each other to avoid
collisions and reach their destination which is the output desired.

4. Single-agent vs Multi-agent
 An environment consisting of only one agent is said to be a single-agent environment.
 A person left alone in a maze is an example of the single-agent system.
 An environment involving more than one agent is a multi-agent environment.
 The game of football is multi-agent as it involves 11 players in each team.
5. Dynamic vs Static
 An environment that keeps constantly changing itself when the agent is up with some action is said to be
dynamic.
 A roller coaster ride is dynamic as it is set in motion and the environment keeps changing every instant.
 An idle environment with no change in its state is called a static environment.
 An empty house is static as there’s no change in the surroundings when an agent enters.

6. Discrete vs Continuous
 If an environment consists of a finite number of actions that can be deliberated in the environment to
obtain the output, it is said to be a discrete environment.
 The game of chess is discrete as it has only a finite number of moves. The number of moves might vary
with every game, but still, it’s finite.
 The environment in which the actions are performed cannot be numbered i.e. is not discrete, is said to
be continuous.
 Self-driving cars are an example of continuous environments as their actions are driving, parking, etc.
which cannot be numbered.

7.Episodic vs Sequential
 In an Episodic task environment, each of the agent’s actions is divided into atomic incidents or episodes.
There is no dependency between current and previous incidents. In each incident, an agent receives
input from the environment and then performs the corresponding action.
 Example: Consider an example of Pick and Place robot, which is used to detect defective parts from the
conveyor belts. Here, every time robot(agent) will make the decision on the current part i.e. there is no
dependency between current and previous decisions.

 In a Sequential environment, the previous decisions can affect all future decisions. The next action of the
agent depends on what action he has taken previously and what action he is supposed to take in the
future.
 Example: Checkers- Where the previous move can affect all the following moves.

8. Known vs Unknown
In a known environment, the output for all probable actions is given. Obviously, in case of unknown
environment, for an agent to make a decision, it has to gain knowledge about how the environment works.

Problem solving in AI:

When an agent (a system or program) needs to achieve a goal but doesn't know the correct action immediately,
it must plan ahead. This process of looking for a sequence of actions that lead to a goal is called search. The
agent that performs this process is a problem-solving agent.

Environment Considerations:
This assumes a simple environment with these properties:
✔ Single-agent (only one decision-maker)
✔ Fully observable (agent has complete knowledge of the state)
✔ Deterministic (actions have predictable results)
✔ Static (environment does not change over time)
✔ Discrete (limited number of states and actions)
✔ Known (agent has information about the world)

Types of Problems in AI:

1. Ignorable Problems: These are problems or errors that have minimal or no impact on the overall
performance of the AI system. They are minor and can be safely ignored

2. Recoverable Problems: Those problems where the AI system encounters an issue, but it can recover from
the error, either through manual intervention or built-in mechanisms, such as error-handling functions.

3. Irrecoverable Problems: These are critical problems that lead to permanent failure or incorrect outcomes
in AI systems. Once encountered, the system cannot recover

Steps in Problem Solving in Artificial Intelligence (AI)

 Problem Definition: This initial step involves clearly specifying the inputs and acceptable solutions for the
system. A well-defined problem lays the groundwork for effective analysis and resolution.
 Problem Analysis: In this step, the problem is thoroughly examined to understand its components,
constraints, and implications. This analysis is crucial for identifying viable solutions.
 Knowledge Representation: This involves gathering detailed information about the problem and defining
all potential techniques that can be applied. Knowledge representation is essential for understanding the
problem’s context and available resources.
 Problem Solving: The selection of the best techniques to address the problem is made in this step. It
often involves comparing various algorithms and approaches to determine the most effective method.

Components/terminology of Problem Formulation in AI :

 Problem-solving: Problem-solving is a process that is a solution provided to a complex problem or task.

 State Space - All possible situations the agent can be in. It refers to the area where an agent involved in
problem-solving process can examine all the possible states with the hope of discovering a solution.
 State: An entity represents some unique and specific arrangement of elements in a problem-solving
situation
 Search Algorithm: A search algorithm describes any process or method targeted for examining and
exploring the given problem space to find a solution.
 Heuristic: Heuristic is a thumb rule or guiding principle that is used to make intelligent decisions or solve
the problems that are encountered during the process.
 Initial State - The agent's starting point (e.g., Arad).
 Goal State(s) - The destination(s) (e.g., Bucharest).
 Actions - Possible moves (e.g., travel from Arad to Sibiu).
 Transition Model - The result of an action (e.g., traveling from Arad to Zerind leads to the Zerind state).
 Action Cost Function - The cost of each action (e.g., distance in miles).
 Solution - A sequence of actions leading to a goal (e.g., Arad → Sibiu → Bucharest).
 Optimal Solution - The solution with the lowest cost (shortest distance or least time).

Graph Representation of Search Problems:

 Nodes (Vertices) represent states.

 Edges (Links) represent actions.

Characteristics of AI Problems:

 ·Learning and Adaptation

AI systems should learn from experience or data and improve over time.
Example: A chatbot learns from user conversations and gives better replies next time.
 ·Complexity
AI problems often deal with huge data or complex systems. The system should manage this efficiently.
Example: An AI used in weather prediction handles a lot of data to give accurate results.
 Uncertainty
AI works in situations where full information is not available or results are unpredictable.
Example: A medical diagnosis AI may not have all patient details but still has to give a possible result.
 Dynamism
AI operates in changing environments, so it must keep updating its actions.
Example: A self-driving car changes its driving decisions based on road and traffic conditions.
 Interactivity
AI interacts with humans or other systems and should respond properly.
Example: A voice assistant like Alexa listens and replies to commands.
 Context Dependence
AI performance depends on the situation or environment it's in.
Example: An AI for customer service must behave differently with an angry customer than a happy one.
 Multi-disciplinary
AI uses ideas from many fields like computer science, maths, statistics, and psychology.
Example: Building a robot may need coding (CS), movement logic (physics), and decision-making
(psychology).
 Goal-Oriented Design
AI systems are built to achieve specific goals.
Example: An AI used in chess is designed to win the game.

Challenges of AI:

Technical Challenges in Artificial Intelligence (AI)

 Handling Complex Tasks

AI finds it difficult to deal with real-life situations that need common sense.
Example: A self-driving car might not react properly if a child suddenly runs onto the road, as it may not
fully understand the seriousness of the situation.
 Scalability and Efficiency
Training AI models needs a lot of data and powerful computers. This takes time and is very costly.
Example: Training a big AI model like ChatGPT requires huge computing power, which small companies
can’t always afford.
 Interoperability
Different AI systems use different formats, so they often don’t work well together.
Example: A healthcare AI developed by one company may not work with another company’s system,
making data sharing difficult.

Ethical Challenges in AI

 Bias in AI
If the data used to train AI is biased, the AI will also be biased. This can lead to unfair decisions.
Example: An AI trained mostly on male leaders may prefer men for leadership roles.
 Lack of Transparency and Accountability
Many AI systems are like “black boxes”—it’s hard to know how they make decisions.
 Example: If an AI denies parole to a prisoner, the reason may not be clear, making it hard to challenge the
decision.
 Misuse of AI
AI can be used in harmful ways, like spreading fake videos or hacking.
Example: Deepfakes can be used to spread false information or create fake news videos.

Social and Economic Challenges in AI

 Job Losses
AI can do many tasks automatically, which might replace human workers.
Example: Robots in factories can reduce the need for human workers on assembly lines.
 Increasing Inequality
Only rich companies might be able to afford advanced AI, increasing the gap between rich and poor.
Example: Big companies may use AI to make more money, while small companies can’t keep up.
 Need for Regulations
There should be rules to make sure AI is used safely and fairly.
Example: Laws should control how AI is used in facial recognition to protect people’s privacy

State Space Search:

State Space Search is a method used in AI to find solutions by exploring all possible situations (states) of a
problem step-by-step until the goal is reached.It consider the problem as a series of steps and it moves from
one state to another until goal is reached.

It treats the problem like a graph.

Each node = a state (a situation/configuration of the problem).

Each edge = an action that moves from one state to another.

Used In

 Puzzle solving (like 8-puzzle)

 Pathfinding (like Google Maps)
 Game playing (like chess)
 Decision-making problems
Important Terms:

Term Meaning
State A condition or configuration of the problem
Initial State Starting point
Goal State Desired final result
Transition Action to move from one state to another
Path Sequence of states from start to goal
Search Strategy The method used to search the path

Steps in State Space Search

1. Define the State Space

Identify all possible states and how they connect through actions.
2. Pick a Search Strategy
Choose how the AI will explore the states

Common Search Strategies

Strategy Description
BFS (Breadth-First Search) Explores level by level – guarantees shortest path in unweighted graphs
DFS (Depth-First Search) Goes deep into one path before backtracking – uses less memory
UCS (Uniform Cost Search) Picks the least cost node first – gives cheapest path
Greedy Search Uses a heuristic to pick the node closest to goal
A* Combines cost and heuristic – complete and optimal

3. Start the Search

Begin from the initial state
4. Expand Nodes
Use the strategy to explore next possible states.
5. Avoid Repeated States
Track visited states to avoid loops and unnecessary work.
6. End the Search
Stop when:

 Goal is reached
 All possibilities are checked

Principles & Features of State Space Search

Feature Explanation
Expansiveness How many new states one state can generate
Branching Factor Average number of child nodes per state
Depth Steps needed to reach goal from the start
Completeness Will it always find a solution if one exists?
Optimality Will it find the best (cheapest/shortest) solution?
Time Complexity How much time the search takes
Space Complexity How much memory is needed

Informed vs Uninformed Search:

 Informed Search uninformed search
Known as Heuristic search Blind Search
Definition Uses additional heuristic info Searches blindly without
to find solution faster domain specific knowledge
performance Find solution more quickly Find solution slow
completion May or may not be complete Always complete
Cost factor Cost is low Cost is high
searching Quick searching Slow searching
implement Less lengthy while More lengthy while
implemented implemented
efficiency More efficient as it explores Less efficient as it explores all
only promising path possible paths
optimal Can be optimal if heuristic is Some algo(BFS,UCS)are
consistent optimal, while others are not
memory Require more memory to Requires less memory
store heuristic
complexity Lower time complexity Higher time complexity
dependency Heavily depends on quality of Does not rely on any
heuristic function heauristic information
examples A*,AO*,Best first search DFS,BFS,UCS

Unit 2
Adversarial search:

The Adversarial search is a well-suited approach in a competitive environment, where two or more agents
have conflicting goals. The adversarial search can be employed in two-player zero-sum games which means
what is good for one player will be the misfortune for the other. In such a case, there is no win-win outcome.
In artificial intelligence, adversarial search plays a vital role in decision-making, particularly in competitive
environments associated with games and strategic interactions. By employing adversarial search, AI agents
can make optimal decisions while anticipating the actions of an opponent with their opposing objectives. It
aims to establish an effective decision for a player by considering the possible moves and the counter-moves
of the opponents.
The adversarial search in competitive environments can be utilized in the below scenarios where the AI
system can assist in determining the best course of action by both considering the possible moves and
counter-moves of the opponents.
 Each agent seeks to boost their utility or minimize their loss.
 One agent’s action impacts the outcomes and objectives of the other agents.
 Additionally, strategic uncertainty arises when the agents may lack sufficient information about each
other’s strategies.

Role of Adversarial Search in AI

 Game-playing: The Adversarial search finds a significant application in game-playing scenarios, including
renowned games like chess, Go, and poker. The adversarial search offers the simplified nature of these
games that represents the state of a game in a straightforward approach and the agents are limited to a
small number of actions whose effects are governed by precise rules.
 Decision-making: Decision-making plays a central role in adversarial search algorithms, where the goal is
to find the best possible move or strategy for a player in a competitive environment against one or more
components. This requires strategic thinking, evaluation of potential outcomes, and adaptive decision-
making throughout the game.

Adversarial search algorithms

The search algorithms like DFS, BFS, and A* can be well-suited for single-agent environments where there is
no direct competition or conflict between multiple agents. These algorithms are suitable for finding an
optimal solution in such scenarios. On the other hand, in zero-sum games where two players compete
directly against each other, adversarial search algorithms like Minmax and Alpha-Beta pruning are more
appropriate since these algorithms can determine the best course of action for each player in zero-sum
games.

Applications of adversarial search algorithms

 Board games: Adversarial search is most widely used in various board games like Chess, Checkers, Go and
Connect Four. The above-explained algorithms can help the computers to play against human opponents
or other computer players.
 Game Theory: Adversarial search forms the basis of game theory, which is used in various fields like
economics, political science, and biology to model strategic interactions between rational decision-
makers.
 Puzzle-solving: Adversarial search algorithms can be used to solve puzzles and optimization problems
where the goal is to find the best sequence of moves or actions to achieve a desired outcome.

Adversarial Search is a type of search used in games or problems involving competition between two or more
players, where each player tries to win and the opponent tries to stop them.

 It is called “adversarial” because the players are opponents.

 Example: Chess, Tic-Tac-Toe, Checkers.

Why Normal Search Doesn't Work Here:

In normal search (like path finding), we only try to reach a goal state.
But in games:

 The environment is not under our full control.

 Another player is actively trying to make us lose.

Game as a Search Problem:

A game can be represented as:

 Initial state – starting position.

 Players – usually two: MAX (tries to win) and MIN (tries to block).
 Actions – possible moves.
 Result – new state after an action.
 Terminal state – end of the game (win/loss/draw).
 Utility function – gives the score of a terminal state (like +1 win, -1 lose, 0 draw).

Optimal decision in games:

Let us start with games with two players, whom we'll refer to as MAX and MIN for obvious reasons. MAX is
the first to move, and then they take turns until the game is finished. At the conclusion of the game, the
victorious player receives points, while the loser receives penalties. A game can be formalized as a type of
search problem that has the following elements:
 S0: The initial state of the game, which describes how it is set up at the start.
 Player (s): Defines which player in a state has the move.
 Actions (s): Returns a state's set of legal moves.
 Result (s, a): A transition model that defines a move's outcome.
 Terminal-Test (s): A terminal test that returns true if the game is over but false otherwise. Terminal
states are those in which the game has come to a conclusion.
 Utility (s, p): A utility function (also known as a payout function or objective function ) determines the
final numeric value for a game that concludes in the terminal state s for player p. The result in chess is a
win, a loss, or a draw, with values of +1, 0, or 1/2. Backgammon's payoffs range from 0 to +192, but
certain games have a greater range of possible outcomes. A zero-sum game is defined (confusingly) as
one in which the total reward to all players is the same for each game instance. Chess is a zero-sum game
because each game has a payoff of 0 + 1, 1 + 0, or 1/2 + 1/2. "Constant-sum" would have been a
preferable name, 22 but zero-sum is the usual term and makes sense if each participant is charged 1.

The game tree for the game is defined by the beginning state, ACTIONS function, and RESULT function—a
tree in which the nodes are game states and the edges represent movements. The figure below depicts a
portion of the tic-tac-toe game tree (noughts and crosses). MAX may make nine different maneuvers from his
starting position. The game alternates between MAXs setting an X and MINs placing an O until we reach leaf
nodes corresponding to terminal states, such as one player having three in a row or all of the squares being
filled. The utility value of the terminal state from the perspective of MAX is shown by the number on each
leaf node; high values are thought to be beneficial for MAX and bad for MIN
The game tree for tic-tac-toe is relatively short, with just 9! = 362,880 terminal nodes. However, because
there are over 1040 nodes in chess, the game tree is better viewed as a theoretical construct that cannot be
realized in the actual world. But, no matter how big the game tree is, MAX's goal is to find a solid move. A
tree that is superimposed on the whole game tree and examines enough nodes to allow a player to identify
what move to make is referred to as a search tree.

A sequence of actions leading to a goal state—a terminal state that is a win—would be the best solution in a
typical search problem. MIN has something to say about it in an adversarial search. MAX must therefore
devise a contingent strategy that specifies M A X's initial state move, then MAX's movements in the states
resulting from every conceivable MIN response, then MAX's moves in the states resulting from every possible
MIN reaction to those moves, and so on. This is quite similar to the AND-OR search method, with MAX acting
as OR and MIN acting as AND. When playing an infallible opponent, an optimal strategy produces results that
are as least as excellent as any other plan. We'll start by demonstrating how to find the best plan.
We'll move to the trivial game in the figure below since even a simple game like tic-tac-toe is too complex for
us to draw the full game tree on one page. MAX's root node moves are designated by the letters a1, a2, and
a3. MIN's probable answers to a1 are b1, b2, b3, and so on. This game is over after MAX and MIN each make
one move. (In game terms, this tree consists of two half-moves and is one move deep, each of which is
referred to as a ply.) The terminal states in this game have utility values ranging from 2 to 14.

Game's Utility Function

The optimal strategy can be found from the minimax value of each node, which we express as MINIMAX,
given a game tree (n). Assuming that both players play optimally from there through the finish of the game,
the utility (for MAX) of being in the corresponding state is the node's minimax value. The usefulness of a
terminal state is obviously its minimax value. Furthermore, if given the option, MAX prefers to shift to a
maximum value state, whereas MIN wants to move to a minimum value state. So here's what we've got:

Optimal Decision Making in Multiplayer Games

Let's use these definitions to analyze the game tree shown in the figure above. The game's UTILITY function
provides utility values to the terminal nodes on the bottom level. Because the first MIN node, B, has three
successor states with values of 3, 12, and 8, its minimax value is 3. Minimax value 2 is also used by the other
two MIN nodes. The root node is a MAX node, with minimax values of 3, 2, and 2, resulting in a minimax
value of 3. We can also find the root of the minimax decision: action a1 is the best option for MAX since it
leads to the highest minimax value.
This concept of optimal MAX play requires that MIN plays optimally as well—it maximizes MAX's worst-case
outcome. What happens if MIN isn't performing at its best? Then it's a simple matter of demonstrating that
MAX can perform even better. Other strategies may outperform the minimax method against suboptimal
opponents, but they will always outperform optimal opponents.

Optimal decision making in games means choosing the best possible move at every step, assuming your
opponent also plays perfectly. It aims to maximize your chances of winning or minimize losses.

Where is it used?
It is used in Game Theory and Artificial Intelligence to develop intelligent agents that can play games like chess,
tic-tac-toe, etc.

How do computers make such decisions?

They use algorithms like:

Minimax Algorithm:

Used in two-player games.

Assumes the opponent also plays optimally.

It tries to maximize your gain and minimize the opponent's gain.

Alpha-Beta Pruning:

Improves minimax by cutting off unnecessary branches to save time.

Advantages of Optimal Decision Making:

 Guarantees best possible result if both players play perfectly.

 Helps in building intelligent game bots.
 Works in deterministic games (no luck involved).

Disadvantages:

 Not suitable for complex games like chess without pruning.

 Needs lots of memory and processing.

Stochastic games:
A stochastic game is a type of game where multiple players make decisions over time, and those decisions affect
not only the current situation (called the state) but also what happens next. The word "stochastic" means there’s
some randomness involved—so it's not just skill or logic, but also luck.

Key Elements:

 States (S): These are like different scenes or situations in the game.
 Actions (A): Choices each player can make.
 Transition Probabilities (P): These decide how the game moves from one state to another. It’s not always
certain—random events (like dice rolls) influence it.
 Reward Function (R): Based on the state and action, each player gets a reward (or points).
 Discount Factor (γ): This tells us how much future rewards matter. A low value means “care more about
now,” and a high value means “care more about the future.”
Real-World Example: Think of playing a board game where you roll a dice (randomness), decide how to move
your pieces (decision-making), and earn or lose points depending on your moves and luck.

Role in AI (Artificial Intelligence)

Why do AI researchers care about stochastic games?

 Multi-Agent Systems: AI systems often involve more than one “agent” (like self-driving cars or robots) that
need to cooperate or compete. Stochastic games help model how these agents interact.
 Uncertainty: Real-life isn’t always predictable. These games help AI learn to deal with randomness.
 Sequential Decisions: Many AI tasks require decisions that affect the future. Stochastic games help in
planning ahead.
 Reinforcement Learning (RL): This is a way for AI to learn by trial and error. RL is based on Markov
Decision Processes (a special kind of stochastic game), and multi-agent RL extends it to more than one
player.

Types of Stochastic Games

 Zero-Sum Games: One player's gain is exactly the other’s loss (e.g., chess or a two-player war game).
 General-Sum Games: Players may cooperate or compete, and rewards aren't balanced (used in negotiation or
teamwork AI).
 Markov Games: These follow the “Markov Property,” meaning the next state depends only on the current
state and actions, not on past history.

Solving Stochastic Games

Solving a game means finding the best strategy for each player. This is tough when there are many players or
states.

Some methods include:

 Dynamic Programming (like value iteration, policy iteration)

 Reinforcement Learning (like Q-learning or Deep Q Networks)
 Approximate Methods (like Monte Carlo simulations or heuristics)

Example: Backgammon as a Stochastic Game

Backgammon is a classic board game involving dice rolls. It’s part-skill and part-luck, making it a great example
of a stochastic game.

How it works:

 The dice decide what moves are possible.

 You must choose the best move based on your options.
 But you can’t predict what your opponent will roll next.
 This makes decision-making more about probabilities and expectations.

Game Tree in Backgammon

In chess, a game tree shows all possible moves. In backgammon, we use a stochastic game tree, which includes:

Player decision nodes (squares)

Chance nodes (circles), where dice rolls happen

Each dice roll has a probability:

 36 total combinations of two dice

21 unique rolls (6–5 is the same as 5–6)

Doubles (like 2–2) happen with probability 1/36

Other rolls (like 5–6) happen with probability 1/18

Decision Making: Expected Value

Since outcomes are random, we can’t always know what’s best. Instead, we calculate the expected value for each
option—how good the outcome is on average.

Expectiminimax Algorithm

This is an upgrade of the Minimax algorithm for games that include chance.

How it works:

If it’s your turn (MAX): choose the action that gives the highest expected value.

If it’s the opponent’s turn (MIN): assume they’ll make the move that hurts you the most.

If it’s a chance node (CHANCE): take the weighted average of all outcomes based on their probabilities.

Formula (explained simply):

Expectiminimax(s) =
If it’s the end → Return the final score
If MAX’s turn → Pick the action that gives the max value
If MIN’s turn → Pick the action that gives the min value
If CHANCE’s turn → Calculate expected value = ∑ probability × value of resulting state

Applications of Stochastic Games in AI

 Autonomous Systems (e.g., robots or self-driving cars): They operate in unpredictable environments and
must make smart decisions.
 Financial Markets: Traders and AI bots make decisions under uncertain market conditions.
 Healthcare: Doctors, patients, and insurers are all agents making decisions under uncertainty.
 Cybersecurity: AI models defend against attacks that are unpredictable or random.

Partially observable games: