Artificial Intelligence Fundamentals: Key Concepts

Posted on Aug 15, 2025 in Business Administration and Innovation Management

Minimax Search Algorithm for Two-Player Games

The Minimax algorithm is used in two-player zero-sum games (like chess or tic-tac-toe) to determine the optimal move for a player, assuming the opponent also plays optimally.

Minimax Algorithm Steps

1. Input: Current game state (node), depth (how many moves ahead to consider), and whether it’s the maximizing or minimizing player’s turn.
2. Check for Terminal State or Depth = 0: If the current state is a terminal state (game over) or the maximum search depth is reached, return the utility value of the current state.
3. If Maximizing Player’s Turn:
   • Initialize the best value to -∞.
   • For each possible move (child of the current state):
     • Recursively call Minimax for the minimizing player.
     • Update the best value if the returned value is higher.
   • Return the best value.
4. If Minimizing Player’s Turn:
   • Initialize the best value to +∞.
   • For each possible move (child of the current state):
     • Recursively call Minimax for the maximizing player.
     • Update the best value if the returned value is lower.
   • Return the best value.

Alpha-Beta Pruning: Performance Optimization

Alpha-Beta Pruning is an optimization technique for Minimax that eliminates branches that cannot possibly affect the final decision, significantly reducing the number of nodes explored.

• Alpha (α): The best value that the maximizing player can guarantee so far.
• Beta (β): The best value that the minimizing player can guarantee so far.

If at any point β ≤ α, the rest of the subtree is pruned (i.e., not explored), as it will not lead to a better outcome for the current player.

Game Theory Defined

Game Theory is a branch of mathematics and economics that studies strategic interactions among rational decision-makers. It provides models and tools to analyze situations where the outcome for each participant (or “player”) depends not only on their own actions but also on the actions of others.

Monte Carlo Tree Search (MCTS)

Monte Carlo Tree Search (MCTS) is a heuristic search algorithm used for decision-making in large and complex search spaces, especially in game-playing AI (like Go, Chess, and other board games). MCTS builds a search tree incrementally and uses random simulations (called playouts) to evaluate the potential of moves. It balances exploration of new moves and exploitation of known good moves using the Upper Confidence Bound for Trees (UCT) formula.

Four Main Steps of MCTS

1. Selection: Starting from the root, select child nodes according to a policy (e.g., UCT) until a leaf node is reached.
2. Expansion: Expand the leaf node by adding one or more child nodes.
3. Simulation (Rollout): Perform a random playout from the new node to a terminal state.
4. Backpropagation: Update the values of nodes on the path back to the root based on the simulation result.

Limitations of MCTS

1. Computationally Expensive: Requires many simulations to provide reliable estimates, which can be slow in real-time or resource-constrained environments.
2. Poor Performance in Deterministic or Simple Domains: Random simulations may be ineffective in some deterministic or simple games where strategic depth is more important.
3. Bias in Rollouts: The quality of random simulations affects performance; naive rollouts may produce misleading results.
4. Large Branching Factor Issues: In games or problems with extremely large branching factors, the tree can grow too large for practical exploration.
5. Difficulty Handling Hidden Information: MCTS struggles with games involving imperfect or hidden information without modifications.
6. No Guaranteed Optimality: MCTS is heuristic-based and may not always find the optimal move, especially with limited computation time.

Cutoff Procedure in Search Algorithms

The cutoff procedure is a technique used in search algorithms, especially in game tree search like Minimax, to limit the depth of the search to reduce computation time and resource usage.

Cutoff means stopping the expansion of nodes beyond a certain depth limit or other conditions instead of searching until terminal states. When the cutoff condition is met, the algorithm does not continue expanding the tree. Instead, it evaluates the current node using a heuristic evaluation function to estimate its value.

Cutoff Procedure Example: Tic-Tac-Toe

1. Normally, Minimax would explore all moves until the end of the game.
2. Suppose we set a cutoff depth of 2 plies (half-moves).
3. When Minimax reaches depth 2, it will stop expanding further and use an evaluation function to score the board (e.g., number of possible winning lines).
4. Based on these heuristic scores, Minimax will choose the best move without looking further.

Key Problem-Solving Strategies

Backtracking Algorithm

Backtracking is a general algorithmic technique for solving problems incrementally, by trying partial solutions and then abandoning them (“backtracking”) if they do not lead to a valid complete solution.

Features of Backtracking

• Recursive approach.
• Explores all possible configurations.
• Includes an “undo” step when a dead end is reached.
• Efficient for combinatorial problems, such as puzzles or constraint satisfaction.

Backtracking with the N-Queens Problem

The N-Queens problem involves placing N queens on an N × N chessboard so that no two queens attack each other (i.e., no two queens are in the same row, column, or diagonal).

Backtracking Approach for N-Queens

1. Start in the first row.
2. Try placing a queen in each column of the current row.
3. After placing a queen, move to the next row and repeat.
4. If a conflict is found (same column or diagonal), backtrack to the previous row and try the next column.
5. Continue this until all queens are placed or no solution is possible in the current configuration.

Constraint Satisfaction Problem (CSP)

A Constraint Satisfaction Problem (CSP) is a type of problem in Artificial Intelligence (AI) and computer science where the goal is to find values for variables that satisfy a set of constraints.

CSP Definition Components

1. Variables (X): A set of variables X = {X₁, X₂, …, X_n}.
2. Domains (D): Each variable X_i has a domain D_i, which is the set of possible values it can take. Example: D_i = {1, 2, 3}.
3. Constraints (C): A set of constraints C = {C₁, C₂, …, C_m} that restrict the values the variables can take. Each constraint involves one or more variables and specifies allowable combinations of values.

Example: Map Coloring Problem

1. Variables: WA, NT, SA, Q, NSW, V, T (Australian states/territories).
2. Domain: Each variable can take values {Red, Green, Blue}.
3. Constraints: No two adjacent regions can have the same color. E.g., WA ≠ NT, SA ≠ WA, NT ≠ SA.

What is an AI Agent?

An agent is an entity that perceives its environment through sensors and acts upon that environment through actuators to achieve specific goals. It can be a software program, robot, or human being that performs actions based on observations.

Examples of AI Agents Around Us

1. Autonomous Vacuum Cleaner (e.g., Roomba): Perceives room layout and cleans.
2. Google Maps: Senses traffic data and suggests optimal routes.
3. Thermostat: Senses temperature and adjusts heating or cooling.
4. Chatbot: Understands queries and responds appropriately.
5. Self-Driving Car: Perceives surroundings and drives accordingly.

Knowledge-Based Agents & Wumpus World

A Knowledge-Based Agent (KBA) uses logical reasoning and a knowledge base (KB) to make decisions.

Wumpus World Example

The Wumpus World is a grid-based environment used to demonstrate KBAs. Hazards include:

• Wumpus (monster)
• Pits
• Gold

The agent must use limited percepts (like breeze or stench) to infer safe paths.

How a KBA Works in Wumpus World

• The agent starts with some initial knowledge (e.g., breeze indicates a pit nearby).
• It adds new percepts as it explores.
• Uses inference rules to deduce which cells are safe.
• Chooses actions based on logical reasoning.

Example Rule: If there is a breeze in (1,1), then at least one adjacent cell has a pit: Breeze(1,1) → Pit(1,2) ∨ Pit(2,1)

Steps of the Knowledge Engineering Process

Knowledge Engineering is the process of building knowledge-based systems.

1. Identify the Task: Define the problem the system will solve.
2. Acquire Knowledge: Gather information from experts, documents, or databases.
3. Represent Knowledge: Use formal languages (like predicate logic) to encode facts and rules.
4. Implement Reasoning: Develop inference mechanisms to draw conclusions.
5. Test and Refine: Evaluate the system’s performance and adjust knowledge and rules.

Propositional vs. First-Order Logic

Wumpus World Environment with PEAS Description

The Wumpus World is a simple grid-based world (typically 4×4) used in AI to demonstrate knowledge-based agents. The agent must navigate safely, find gold, and avoid dangers like the Wumpus (a monster) and pits.

Agent Percepts in Wumpus World

1. Stench: Indicates a Wumpus is nearby.
2. Breeze: Indicates a pit is nearby.
3. Glitter: Gold is in the current cell.
4. Bump: The agent ran into a wall.
5. Scream: The Wumpus has been killed.

PEAS Description of Wumpus World Agent

• P (Performance Measure): Grab the gold, exit safely, minimize steps and risk.
• E (Environment): 4×4 grid with Wumpus, pits, walls, and gold.
• A (Actuators): Move forward, turn left/right, grab, shoot, climb.
• S (Sensors): Stench, Breeze, Glitter, Bump, Scream.

Inference Rules in First-Order Logic (FOL)

Types of Planning in Artificial Intelligence

Planning is a fundamental aspect of AI where an agent decides what actions to take and in what order to achieve specific goals. Planning systems use models of the world, actions, and goals to generate sequences of actions.

1. Classical Planning

   Works in static environments. Example: STRIPS (Stanford Research Institute Problem Solver). Application: Puzzle solving, game logic.

2. Conditional Planning

   Plans include conditions and branches, containing “if-then” rules to handle different outcomes. Example: If door is locked, try key A; else, try key B. Application: Robotics, adaptive systems.

3. Contingency Planning

   Prepares for unexpected situations by including alternatives. Handles incomplete knowledge or uncertainty. Application: Space missions, disaster management.

4. Hierarchical Planning (HTN – Hierarchical Task Network)

   Breaks goals into sub-goals or tasks using a top-down approach. Example: “Plan a wedding” → book venue, invite guests, arrange catering. Application: Project planning, complex systems.

5. Probabilistic Planning

   Deals with uncertain outcomes using probabilities. Actions have multiple possible results, each with a probability. Application: Autonomous vehicles, financial decision-making.

6. Strategic vs. Tactical Planning

   • Strategic Planning: Long-term, high-level goals (e.g., explore Mars).
   • Tactical Planning: Short-term, specific steps (e.g., charge battery, move rover 2 meters).

Core Components of Artificial Intelligence

AI systems are built from various components that allow them to perceive, reason, act, and learn. Here’s a breakdown of the core components:

1. Learning

   Definition: The ability of an AI system to learn from data and improve performance over time.

   Types:

   • Supervised Learning: Learns from labeled data.
   • Unsupervised Learning: Learns patterns from unlabeled data.

2. Reasoning

   Definition: Drawing logical conclusions based on available knowledge.

   Types:

   • Deductive Reasoning: From general rules to specific cases.
   • Inductive Reasoning: From specific cases to general rules.

3. Problem Solving

   Definition: Finding a sequence of actions that leads from a start state to a goal state.

   Includes: Search algorithms, planning techniques, and heuristics. Example: Solving a maze, pathfinding in games.

4. Perception

   Definition: Gathering data from the environment using sensors. Example: Vision (image recognition), speech recognition, sensor data.

5. Language Understanding (NLP)

   Definition: The ability to understand, interpret, and generate human language.

   Subfields:

   • Syntax analysis
   • Semantic analysis
   • Machine translation

   Applications: Chatbots, voice assistants, translation systems.

6. Action (Actuation)

   Definition: Acting upon the environment using effectors. Example: A robot moving its arm, a car turning left. Tools: Motors, actuators, display systems.

AI System Architecture

AI architecture defines the framework or structure that integrates the above components to create an intelligent system.

1. Perception Layer

   Gathers input from the environment. Devices: Cameras, microphones, sensors. Converts raw data to structured data.

2. Knowledge Base

   Stores facts, rules, and world models. Used by the reasoning engine to make decisions.

3. Inference Engine / Reasoning Layer

   Applies logic and inference rules to derive conclusions. Example: Rule-based systems, expert systems.

4. Learning Component

   Updates the knowledge base based on new data. Machine learning algorithms are used here.

5. Planning and Decision-Making Layer

   Selects actions based on goals, constraints, and environment. Includes: Planning algorithms, search strategies.

6. Action/Execution Layer

   Converts decisions into real-world actions. Uses effectors like motors, displays, speakers.

7. User Interface

   Communicates with the user via GUI, voice, or text.

Problem Solving vs. Planning in AI

AI Reasoning Methods: Chaining

Forward Chaining

Forward Chaining is a data-driven reasoning method. It starts from known facts and applies rules to infer new facts until the goal is reached.

How Forward Chaining Works

1. Begin with the initial facts.
2. Apply rules whose conditions match the current facts.
3. Add new facts to the knowledge base.
4. Repeat until the goal is derived or no new facts can be added.

Example:

Rules: IF A THEN B. IF B AND C THEN D.
Facts: A, C.
Inference: A → B → (B and C) → D

Advantages of Forward Chaining

• Good for exploration and discovering all consequences.
• Useful when all data is known at the start.
• Helpful in real-time systems (e.g., monitoring).

Disadvantages of Forward Chaining

• Can produce irrelevant conclusions.
• May explore many unnecessary paths.
• Less efficient when the goal is specific.

Backward Chaining

Backward Chaining is a goal-driven reasoning method. It starts with the goal and works backward to see if known facts support it.

How Backward Chaining Works

1. Begin with a goal to prove.
2. Look for rules where the conclusion matches the goal.
3. Recursively try to prove the antecedents (conditions).
4. If all sub-goals are true, the main goal is proven.

Example:

Goal: Prove D
Rules: IF B AND C THEN D. IF A THEN B
Facts: A, C.
Reasoning: Need B and C → A gives B → C is known → D is proven

Advantages of Backward Chaining

• Efficient when the goal is known.
• Avoids irrelevant rules and paths.
• Ideal for decision-making systems (e.g., diagnosis).

Disadvantages of Backward Chaining

• Can be inefficient if many sub-goals or deep chains exist.
• May get stuck if not all facts are known.

Ontological Engineering

Ontological Engineering is the study and development of ontologies, which are formal representations of knowledge within a particular domain. It provides a structured framework for defining the concepts, relationships, and rules that exist in that domain.

In AI, ontologies help machines to:

• Understand domain knowledge.
• Enable semantic reasoning.
• Facilitate data sharing and reuse.

What is an Ontology?

An ontology is a specification of:

• Concepts (e.g., Person, Car, Disease)
• Relationships (e.g., hasPart, isA)
• Properties/Attributes (e.g., name, color)
• Rules/Constraints (e.g., “Every car must have wheels”)

Example: In a medical ontology:

• Concept: “Disease”
• Property: “hasSymptom”
• Relationship: “isTreatedBy”

Planning in Non-Deterministic Domains

In non-deterministic domains, actions may have multiple possible outcomes, and the environment may change unpredictably. Planning must account for uncertainty and partial observability. Plans include contingencies: different branches based on possible outcomes. This often uses conditional or contingency planning, which plans for various eventualities. Example: A robot navigating a slippery floor where movement can fail; it must have backup plans.

Importance of Planning in AI

• Enables autonomous decision-making.
• Helps in efficient resource management.
• Supports complex tasks by breaking them into manageable steps.
• Facilitates anticipation of future events and handling uncertainties.
• Essential for goal-directed behavior in robots, software agents, and logistics.

Algorithm for Classical Planning (STRIPS-like)

1. Initialize: Set initial state S0.
2. Goal Test: Check if the current state satisfies the goal; if yes, stop.
3. Select Actions: Choose actions whose preconditions are met in the current state.
4. Apply Actions: Generate new states by applying chosen actions.
5. Search: Use search (e.g., forward search, backward search) through states to find a sequence of actions leading to the goal.
6. Return Plan: The sequence of actions from the initial to the goal state.

Limits and Future Opportunities of AI

Limits of AI

• Lack of Common Sense: AI struggles with understanding context like humans.
• Uncertainty and Ambiguity: Difficulty in dealing with incomplete or noisy data.
• Ethical Issues: Bias, privacy concerns, decision accountability.
• Computation Limits: Some problems are too complex (NP-hard).
• Dependency on Data: AI quality depends on the quantity and quality of data.

Future Opportunities with AI

• Explainable AI (XAI): Improving transparency and trust in AI decisions.
• General AI (AGI): Developing AI that can learn across diverse domains.
• Healthcare: Personalized medicine and diagnostics.
• Autonomous Vehicles: Safer and more efficient transport.
• Smart Environments: Integration with IoT and smart cities.
• Collaboration: AI-human teaming to augment human abilities.

Knowledge Representation Structures

Knowledge Representation (KR) is how an AI system organizes and stores knowledge about the world so that it can be used for reasoning, learning, and decision-making.

Unification in AI

Unification is a fundamental process in AI, especially in logic programming and automated reasoning. It is the process of finding a substitution that makes two logical expressions identical. The goal is to find a most general unifier (MGU) — the simplest substitution that makes the expressions equal. Unification is used in predicate logic inference, Prolog programming, and theorem proving.

Steps of the Unification Algorithm

1. Initialize the set of substitutions θ to empty.
2. Compare the two expressions:
   • If they are identical constants or variables, no substitution is needed.
   • If one is a variable and the other is a term, substitute the variable.
   • If both are compound terms (functions), recursively unify their arguments.
3. Check for Conflicts: A variable cannot be substituted with a term containing that same variable (occurs check). If a conflict occurs, unification fails.
4. Return the set of substitutions (MGU) if successful.

First-Order Logic (FOL)

First-Order Logic (FOL) is a powerful formal language used to represent knowledge with objects, relations, functions, and quantification. It extends propositional logic by adding quantifiers and predicates.