Unit – 2

Adversarial Search

Q1) What is Adversarial search?

A1) Adversarial search

Adversarial search is a type of search in which we look at the issue that develops when we try to plan ahead of the world while other agents plan against us.

●      We've looked at search methods that are solely linked with a single agent that attempts to find a solution, which is commonly stated as a series of actions, in prior subjects.

●      However, there may be times when more than one agent is searching for the same answer in the same search space, which is common in game play.

●      The environment with more than one agent is referred to as a multi-agent environment, in which each agent is an adversary to the other and competes against them. Each agent needs to consider the action of another agent and the effect of that action on their performance.

●      Adversarial searches, often known as Games, are searches in which two or more players with opposing aims try to explore the same search space for a solution.

●      Games are modeled as a Search problem and a heuristic evaluation function, which are the two primary variables that aid in the modeling and solving of games in AI.

Q2) Write the types of games in AI?

A2) Types of games in AI

●      Perfect information: A game with perfect information is one in which agents are able to look at the entire board. Agents have access to all game information and can watch each other's movements. Chess, Checkers, Go, and other games are examples.

●      Imperfect information: Such games as tic-tac-toe, Battleship, blind, Bridge, and others are known as games with incomplete information since the agents do not have all of the knowledge about the game and are unaware of what is going on.

●      Deterministic games: Deterministic games are those that follow a rigid pattern and set of rules, with no element of chance. Chess, Checkers, Go, tic-tac-toe, and other games are examples.

Q3) Explain mini-max algorithm?

A3) Mini -Max Algorithm

●      n decision-making and game theory, the mini-max algorithm is a recursive or backtracking method. It suggests the best move for the player, provided that the opponent is likewise playing well.

●      The Mini-Max algorithm searches the game tree using recursion.

●      In AI, the Min-Max algorithm is mostly employed for game play. Chess, checkers, tic-tac-toe, go, and other two-player games are examples. This Algorithm calculates the current state's minimax choice.

●      The game is played by two players, one named MAX and the other named MIN, in this algorithm.

●      Both players are fighting it, since the opponent player receives the smallest benefit while they receive the greatest profit.

●      Both players in the game are adversaries, with MAX selecting the maximum value and MIN selecting the minimum value.

●      For the investigation of the entire game tree, the minimax method uses a depth-first search technique.

●      The minimax algorithm descends all the way to the tree's terminal node, then recursively backtracks the tree.

Pseudo code for MIN - MAX Algorithm

function minimax(node, depth, maximizingPlayer) is 

if depth ==0 or node is a terminal node then 

return static evaluation of node 

if MaximizingPlayer then      // for Maximizer Player 

maxEva= -infinity           

for each child of node do 

eva= minimax(child, depth-1, false) 

maxEva= max(maxEva,eva)        //gives Maximum of the values 

return maxEva 

else                         // for Minimizer player 

minEva= +infinity  

for each child of node do 

eva= minimax(child, depth-1, true) 

minEva= min(minEva, eva)         //gives minimum of the values 

return minEva 

Q4) Optimal decision in multiplayer games?

A4) Optimal decision in multiplayer games

The best solution in adversarial search is a contingent strategy, which specifies MAX's move in the initial state, then MAX's movements in the states resulting from every potential response by MIN(the opponent), and so on.

One move deep: If a game terminates after one MAX and MIN move each, we say the tree is one move deep, consisting of two half-moves, each of which is termed a ply.

Minimax value: The utility (for MAX) of being in the corresponding state is the node's minimax value, assuming that both players play optimally from there through the finish of the game. The usefulness of a terminal state is its minimax value.

The optimal strategy can be calculated from the minimax value of each node, i.e. MINIMAX, given a game tree (n).

MAX prefers to move to a maximum value state, whereas MIN prefers to move to a minimum value state.

Fig 1: Two ply game tree

Multiplayer games

We need to replace each node's single value with a vector of values. In a three-player game with players A, B, and C, for example, a vector VA, VB, VC> is associated with each node.

This vector represents the utility of a terminal condition from the perspective of each actor.

The utility vector of the successor state with the highest value for the player choosing at n is always the backed-up value of a node n in nonterminal states.

Fig 2: Three piles of a game tree with three players(A,B,C)

Q5) Describe alpha beta pruning?

A5) Alpha beta pruning

●      A modified variant of the minimax method is alpha-beta pruning. It's a way for improving the minimax algorithm.

●      The number of game states that the minimax search algorithm must investigate grows exponentially with the depth of the tree, as we saw with the minimax search method. We can't get rid of the exponent, but we can reduce it by half. As a result, there is a technique known as pruning that allows us to compute the correct minimax choice without having to inspect each node of the game tree. It's named alpha-beta pruning because it involves two threshold parameters, Alpha and beta, for future expansion. Alpha-Beta Algorithm is another name for it.

●      Alpha-beta pruning can be done at any depth in a tree, and it can sometimes prune the entire subtree as well as the tree leaves.

●      Alpha: The best (highest-value) choice we have found so far at any point along the path of Maximizer. The initial value of alpha is -∞.

●      Beta: The best (lowest-value) choice we have found so far at any point along the path of Minimizer. The initial value of beta is +∞.

●      The Alpha-beta pruning to a standard minimax algorithm produces the same result as the regular approach, but it removes those nodes that aren't really affecting the final decision but are slowing down the procedure. Hence by pruning these nodes, it makes the algorithm fast.

Pseudo code for Alpha beta Pruning

function minimax(node, depth, alpha, beta, maximizingPlayer) is 

if depth ==0 or node is a terminal node then 

return static evaluation of node 

if MaximizingPlayer then      // for Maximizer Player 

   maxEva= -infinity           

   for each child of node do 

   eva= minimax(child, depth-1, alpha, beta, False) 

  maxEva= max(maxEva, eva)  

  alpha= max(alpha, maxEva)     

   if beta<=alpha 

 break 

 return maxEva 

else                         // for Minimizer player 

   minEva= +infinity  

   for each child of node do 

   eva= minimax(child, depth-1, alpha, beta, true) 

   minEva= min(minEva, eva)  

   beta= min(beta, eva) 

    if beta<=alpha 

  break         

 return minEva 

Q6) What is a knowledge based agent?

A6) Knowledge based agent

●      For efficient decision-making and reasoning, an intelligent agent needs knowledge about the real world.

●      Knowledge-based agents are capable of maintaining an internal state of knowledge, reasoning over that knowledge, updating their knowledge following observations, and taking actions. These agents can use some type of formal representation to represent the world and act intelligently.

●       Knowledge-based agents are made up of two major components:

A knowledge-based agent must be capable of performing the following tasks:

The Architecture of knowledge based agents

Fig 3: Architecture of knowledge based agents

A generic architecture for a knowledge-based agent is depicted in the diagram above. By observing the environment, the knowledge-based agent (KBA) receives input from it. The input is taken by the agent's inference engine, which also communicates with KB to make decisions based on the knowledge stored in KB. KBA's learning component keeps the KB up to date by learning new information.

Q7) What do you mean by logic?

A7) Logic

A logic is a formal language, with precisely defined syntax and semantics, which supports sound inference. Different logics exist, which allow you to represent different kinds of things, and which allow more or less efficient inference. The logic may be different types like propositional logic, predicate logic, temporal logic, description logic etc. But representing something in logic may not be very natural and inferences may not be efficient.

Example of logic

Language of numerical constraints:

●      A sentence:

x + 3 ≤ z x ,

z - variable symbols (primitives in the language)

●      An interpretation:

I :   x = 5, z = 2

Variables mapped to specific real numbers

●      Valuation (meaning) function V:

V ( x + 3 ≤ z, I) is False for I: x = 5, z = 2

is True for I: x = 5, z = 10

Fig 4: Logic

Types of logic

●      Different types of logics possible

●      Propositional logic

●      First-order logic

●      Temporal logic

●      Numerical constraints logic

●      Map-coloring logic

Q8) Explain propositional logic?

A8) Propositional logic

The simplest kind of logic is propositional logic, in which all statements are made up of propositions. The term "proposition" refers to a declarative statement that can be true or false. It's a method of expressing knowledge in logical and mathematical terms.

Sentences are something of a proposition. Propositional logic employs Boolean reasoning to transform our real-world data into a computer-readable structure. For example, if we say, "Today is hot and humid," the machine will not understand. We can have the machine read and interpret our message if we can construct propositional logic for this statement.

The heart of propositional logic, which is derived from Boolean logic, is the premise that all propositions' final output (meaning) is either true or false. It can't be both at the same time.

The following are some fundamental propositional logic facts.

●      Because it operates with 0 and 1, propositional logic is also known as Boolean logic.

●      In propositional logic, symbolic variables are used to express the logic, and any symbol can be used to represent a proposition, such as A, B, C, P, Q, R, and so on.

●      Propositions can be true or untrue, but not both at the same time.

●      An object, relations or functions, and logical connectives make up propositional logic.

Representation of proposition logic

Propositional logic may represent two sorts of prepositions: atomic and complex prepositions. The term atomic refers to a single preposition such as "the sky is blue," "hot days are humid," "water is liquid," and so on.

Prepositions that have been produced by connecting one, two, or more phrases are known as complex prepositions. There are five symbols in propositional logic that make up the syntax that represents the link of two or more sentences. Syntax refers to the structure used to represent data.

Name	Symbol	Stands for
Conjunction		And
Disjunction		Or
Implication		If-then
Negation		Not
Biconditional		If and only if

Fig 5: Logical connectives

Q9) Write the advantages of propositional logic?

A9) Advantages

Q10) Write short notes on reasoning?

A10) Reasoning

The mental process of deducing logical conclusions and forming predictions from accessible knowledge, facts, and beliefs is known as reasoning. "Reasoning is a way to deduce facts from existing data," we can state. It is a general method of reasoning to arrive at valid conclusions.

In artificial intelligence, reasoning is required so that the machine can think rationally and perform as well as a human brain.

Reasoning is the process of drawing a conclusion from a set of premises using a set of rules.

Thinking, logically arguing, and drawing inferences are all part of the reasoning process.

When a system is expected to do a task for which it has not been expressly instructed, it must reason. It must deduce what it needs to know from the information it already has.

Numerous varieties of reasoning have been found and acknowledged, but there are still many issues about their logical and computational features.

Abduction, induction, model-based reasoning, explanation, and confirmation are all popular strategies of reasoning.

Types of Reasoning

In artificial intelligence, reasoning can be divided into the following categories:

Q11) Define first order logic?

A11) First Order Logic

●      In artificial intelligence, first-order logic is another method of knowledge representation. It's a variant of propositional logic.

●      FOL has enough expressiveness to convey natural language statements succinctly.

●      Predicate logic or First-order predicate logic are other names for first-order logic. First-order logic is a sophisticated language that makes it easier to build information about objects and to articulate relationships between them.

●      First-order logic (like natural language) assumes not just that the world includes facts, as does propositional logic, but also that the world has the following things:

○      Objects: People, numbers, colors, conflicts, theories, squares, pits, wumpus,

○      Relation: It can be a unary relation like red, round, or nearby, or an n-any relation like sister of, brother of, has color, or comes between.

○      Functions: Father of, best friend, third inning of, last inning of......

●      First-order logic contains two basic pieces as a natural language:

○      Syntax

○      Semantics

Q12) Explain Syntax and Semantics of First-Order Logic?

A12) Syntax and Semantics of First-Order Logic

Syntax has to do with what ‘things’ (symbols, notations) one is allowed to use in the language and in what way; there is/are a(n):

●       Alphabet

●       Language constructs

●       Sentences to assert knowledge

Logical connectives (⇒, ∧, ∨, and ⇐⇒ ), negation (¬), and parentheses. These will be used to recursively build complex formulas, just as was done for propositional logic.

Constants symbols are strings that will be interpreted as representing objects, e.g. Bob might be a constant.

Variable symbols will be used as “place holders” for quantifying over objects.

Predicate symbols each have an associated arity (i.e. number of arguments), which might be zero or some other finite value. Predicates will be used to denote properties of objects and relationships among them.

Zero-arity predicate symbols are treated as propositions as in propositional logic, so first-order logic subsumes propositional logic. These propositions can be thought of as properties of the world.

Single argument predicates can be thought of as specifying properties of objects. For example, let Rich be a single arity predicate, then Rich(Bob) would be used to denote that Bob is rich. Multi-arity predicates denote relations among objects. For example, let Owns be a two-arity predicate, then Owns(Bob, Car) indicates that Bob owns Car.

Formula    PrimitiveFormula

   | (Formula Connective Formula)

   |  Sentence

   | Qualifier Variable Formula

PrimitiveFormula  Predicate(Term,…,Term)

Term    Function(Term,…,Term)

   | Constant

   | Variable

Connectifier   

Quantifier  

Constant   any string that is not used as a variable predicate or function

Variable   any string that is not used as a constant predicate or function

Predicate   any string that is not used as a constant variable or function

Function   any string that is not used as a constant predicate or constant

Function symbols each have a specified arity (i.e. number of input arguments) and will be interpreted as functions mapping the specified number of input objects to objects. For example, let FatherOf be a single-arity function symbol, then the natural interpretation of FatherOf(Bob) would be Bob’s father.

Zero-arity function symbols are considered to be constants.

Universal and existential quantifier symbols will be used to quantify over objects. For example, ∀ x Alive(x) ⇒ Breathing(x) is a universally quantified statement that uses the variable x as a placeholder.

Semantics of First-Order Logic

The first stage in establishing the semantics of first-order logic, like with all logics, is to specify the models of first-order logic. Remember that one of the advantages of utilizing first-order logic is that it allows us to talk about things and their relationships openly. As a result, our models will include objects as well as information about their qualities and relationships with other things.

First order model

A first-order model is defined as a tuple hD, Ii, where D is a non-empty object domain and I is an interpretation function. D is just a collection of objects or elements that can be finite, infinite, or even uncountable. The interpretation function I assigns a meaning or interpretation to each of the available constant, function, and predicate symbols as follows:

●      If c is a constant symbol, then I(c) is an object in D. Thus, given a model, a constant can be viewed as naming an object in the domain.

●      If f is a function symbol of arity n, then I(f) is a total function from Dn to D. That is the interpretation of f is a function that maps n domain objects to the domain D.

●      If p is a predicate symbol of arity n > 0, then I(p) is a subset of Dn; that is, a predicate symbol is interpreted as a set of tuples from the domain. If a tuple O = (o1, · · · , on) is in I(p) then we say that p is true for the object tuple O.

●      If p is a predicate symbol of arity 0, i.e. a simple proposition, then I(p) is equal to either true or false.

For example, suppose that we have one predicate TallerThan, one function FatherOf, and one constant Bob. A model M1 for these symbols might be the following:

D = { BOB, JON, NULL }

I(Bob) = BOB

I(TallerThan) = { hBOB, JONi }

Recall that I(FatherOf) is a function, so to give the interpretation of FatherOf we will just show the value for each input

I(FatherOf)(BOB) = JON

I(FatherOf)(JON) = NULL

I(FatherOf)(NULL) = NULL

Another possible interpretation M2 might be,

D = { BOB, JON }

I(Bob) = BOB

I(TallerThan) = { hBOB, JONi,hJON, BOBi }

I(FatherOf)(BOB) = BOB

I(FatherOf)(JON) = JON

In the above, it is important to note the distinction between Bob which is a constant (a syntactic entity) and BOB which is an object in the domain (a semantic entity). The second interpretation is not what we might have in mind (e.g. the objects are fathers of themselves and Taller Than is inconsistent), but it is still a valid model. It is the job of the knowledge base to rule out such unintended models from consideration by placing appropriate constraints on the symbols.

Q13) Explain INFERENCE IN FIRST ORDER LOGIC?

A13) INFERENCE IN FIRST ORDER LOGIC

In First-Order Logic, inference is used to derive new facts or sentences from existing ones. Before we get into the FOL inference rule, it's important to understand some basic FOL terminology.

Substitution:

Substitution is a basic procedure that is applied to terms and formulations. It can be found in all first-order logic inference systems. When there are quantifiers in FOL, the substitution becomes more complicated. When we write F[a/x], we are referring to the substitution of a constant "a" for the variable "x."

Equality:

In First-Order Logic, atomic sentences are formed not only via the use of predicate and words, but also via the application of equality.  For this, we can use equality symbols which specify that the two terms refer to the same object.

FOL inference rules for quantifier:

First-order logic has inference rules similar to propositional logic, therefore here are some basic inference rules in FOL:

Universal Generalization:

●      Universal generalization is a valid inference rule that states that if premise P(c) is true for any arbitrary element c in the universe of discourse, we can arrive at the conclusion x P. (x).

●      If we want to prove that every element has a similar property, we can apply this rule.

●      x must not be used as a free variable in this rule.

Example: Let's represent, P(c): "A byte contains 8 bits", so for ∀ x P(x) "All bytes contain 8 bits.", it will also be true.

Universal Instantiation:

●      According to the UI rule, any phrase P(c) can be inferred by substituting a ground term c (a constant inside domain x) for any object in the universe of discourse in x P(x).

Example: IF "Every person like ice-cream"=> ∀x P(x) so we can infer that

"John likes ice-cream" => P(c)

Existential Instantiation:

●      Existential Elimination, also known as Existential Instantiation, is a valid first-order logic inference rule.

●      It can only be used once to substitute for the existential sentence.

●      Despite the fact that the new KB is not conceptually identical to the previous KB, it will suffice if the old KB was.

●      The only constraint with this rule is that c must be a new word for which P(c) is true.

●      It can be represented as:

Existential introduction

●      An existential generalization is a valid inference rule in first-order logic that is also known as an existential introduction.

●      This rule argues that if some element c in the universe of discourse has the property P, we can infer that something in the universe has the attribute P.

●      It can be represented as:

Example: Let's say that,

"Pritisha got good marks in English."

"Therefore, someone got good marks in English."

Q14) What is forward chaining?

A14) Forward Chaining

When employing an inference engine, forward chaining is also known as forward deduction or forward reasoning. Forward chaining is a type of reasoning that starts with atomic sentences in a knowledge base and uses inference rules to extract more material in the forward direction until a goal is attained.

The Forward-chaining algorithm begins with known facts, then activates all rules with satisfied premises and adds their conclusion to the known facts. This process continues until the issue is resolved.

It's an inference method that starts with sentences in the knowledge base and generates new conclusions, which can then be used to make other inferences. It's a data-driven strategy. To get to the query, we start with known facts and organize or chain them. It employs the ponens modus operandi. It starts with the information that is available and then utilizes inference rules to extract more data until the goal is met.

Example: To determine the color of Fritz, a pet that croaks and eats flies. These rules can be found in the Knowledge Base:

If X croaks and eats flies — → Then X is a frog.

If X sings — → Then X is a bird.

If X is a frog — → Then X is green.

If x is a bird — -> Then X is blue.

Croaks and eats flies are looked up in the KB. As a result, we arrive at rule 1, whose antecedent corresponds to our facts. The KB is updated with the result of rule 1, namely, X is a frog. The KB is now checked again, and rule 3 is picked since its antecedent (X is a frog) matches our recently confirmed data. The new consequence is then added to the knowledge base (i.e. X is green). As a result, we've achieved our goal of determining the color of the pet based on the fact that it croaks and eats flies.

Properties of forward chaining

●      As it moves from bottom to top, it is a down-up method.

●      It is a method of arriving at a conclusion based on known facts or data by starting at the beginning and working one's way to the end.

●      Forward-chaining is also known as data-driven since it allows us to achieve our goal by utilizing existing data.

●      Expert systems, such as CLIPS, business, and production rule systems, frequently employ the forward-chaining methodology.

Q15) Write about backward chaining?

A15) Backward Chaining

When employing an inference engine, backward-chaining is also known as backward deduction or backward reasoning. A backward chaining algorithm is a type of reasoning that begins with the objective and goes backward, chaining via rules to discover known facts that support it.

It is a method of inference that begins with the aim. We locate implication sentences that allow us to come to a conclusion and try to prove its premises. It is a goal-oriented strategy that is used to prove theorems.

Example: To determine the color of Fritz, a pet that croaks and eats flies. The following rules can be found in the Knowledge Base:

If X croaks and eats flies — → Then X is a frog.

If X sings — → Then X is a bird.

If X is a frog — → Then X is green.

If x is a bird — -> Then X is blue.

The third and fourth rules were chosen since they best fit our purpose of selecting the pet's color. X is either green or blue, for example. The rules' antecedents, X is a frog and X is a bird, are both put to the target list. The first two rules are chosen because their consequences correspond to the new goals added to the list, i.e. X is a frog or X is a bird.

We may deduce that Fritz is a frog because the antecedent (If X croaks and eats flies) is true/given. Fritz is green if it's a frog and blue if it's a bird, achieving the purpose of determining the pet's color. It croaks and eats flies, thus it's a frog). As a result, Fritz is a Green.

Properties of backward chaining

●      It is known as a top-down approach.

●      The modus ponens inference rule is used in backward-chaining.

●      The goal is divided down into sub-goals or sub-goals in backward chaining to establish the facts are correct.

●      It's known as a goal-driven strategy because a list of objectives determines which rules are chosen and implemented.

●      In game theory, automated theorem proving tools, inference engines, proof helpers, and other AI applications, the backward-chaining algorithm is used.

●      For proof, the backward-chaining method primarily used a depth-first search strategy.