Artificial Intelligence - Midterm

Searching

defined as a sequence of steps that creates a path between the initial state and the goal state. Different algorithms may be utilized in order to perform this.

search algorithms

In an environment, _____ _________ generally treat states and actions as atomic - without any internal structure.

This also takes a problem as an input and returns a solution or an indication of failure.

Search tree

This is commonly used to illustrate paths between states, towards a particular goal. It may contain multiple paths to any given state, but each node in the tree has a unique path back to the root.

Root

In a search tree, this corresponds to the initial state of the problem.

Nodes

In a search tree, these correspond to the states within the state space of the problem.

Edges

In a search tree, these correspond to the available actions relative to the problem.

Search data structure

This is required to keep track of the search tree. Each node in the tree may be represented by a data structure with four (4) usual components: node.STATE, node.PARENT, node.ACTION, and node.PATH-COST.

Uninformed search

involves algorithms that do not have any domain-specific knowledge. This search proceeds in a systematic way of exploring nodes in a predetermined order.

Breadth-first Search

- This search process checks all the nodes per level, starting at the left working towards the right side of the tree, before searching the tree one level deeper. This search algorithm can provide a solution with the minimum number of steps from the initial state. It is also a simple search that can be applied to any search problem.

However, its complexity still depends on the number of nodes.

Depth-first Search

- It is one of the main search processes used in AI. The process starts at the root of the tree and down to the left branch until it gets to the bottom node. If the goal state is not reached, the process goes back up and tries the next branch. The process continues until the goal state is reached. This search algorithm goes deep into the tree as fast as possible, but does not guarantee an optimal path.

Time complexity and space complexity are the most important factors to consider in dealing with this specific algorithm.

Iterative Deepening Search

- This search process combines many advantages of the depth-first and breadth-first search. The memory required in this search is relatively moderate. It is optimal for problems where all actions have the same cost. Each iteration generates a new level or performs search per level, in the same way that breadth-first search is performed, but without storing all nodes in memory.

Bidirectional Search

- It encompasses a distinctive process that simultaneously searches forward from the initial state and backwards from the goal state(s), with the anticipation that the two (2) searches will meet. It technically replaces a single search tree with two smaller sub-trees and terminates when the two graphs meet. In most cases, this search algorithm can reduce the cost of exploration.

Uniform-cost Search

- This search process can be considered as a variant of the Dijkstra's algorithm. The complexity of this search can be characterized through the cost of the optimal solution. The search process spreads out in waves of uniform path-cost. It considers all paths systematically in terms of increasing cost, making it a comprehensive and cost-optimal search. On the other hand, this particular algorithm can also be implemented as a best-first search with a path-cost as an evaluation function.

Breadth-first search, Depth-first search, Iterative Deepening Search, Bidirectional search, Uniform-cost search

Uninformed search algorithms

Informed search

also known as heuristic search, involves domain-specific knowledge and allows access to additional information, such as pattern databases with solution costs, that improves the search process. This search encompasses the exploration of nodes that are most likely to be nearest to the goal state. This search utilizes heuristics as an evaluation function.

Best-first Search

It is a general strategy used in searching. On each iteration of this search algorithm, the node with the minimum evaluation function value is selected. If the search has not yet reached a goal state, the process expands and child nodes are generated. Each child node is added at the priority queue if it has not been reached before or is re-added if it is currently being reached through a path that has a lower cost than any of the previous paths.

Hill Climbing Search

- It is a search technique for finding the maximum or the minimum of an evaluation function. This is considered an irrevocable scheme since it does not allow shifting back to previously suspended alternatives, even if it may have offered a better alternative than the one at hand. This search only requires little memory, since alternatives are not stored for future consideration.

A* Search

- This is the most common informed search technique that uses the evaluation function: f(n) = g(n) + h(n), where g(n) is the path- cost from the initial state to a specific node n, h(n) is the estimated cost of the shortest path from node n to the goal state, and f(n) is the estimated cost of the best path that continues from node n to the goal (Russell & Norvig, 2022). The algorithm used in this search combines the features of a uniform-cost search and a pure heuristic search to efficiently compute for the optimal solution.

Beam Search

- This is a search technique that utilizes heuristics to trim the state space and turn it into a small number of nearly optimal alternatives. This implements the breadth-first search in building the search tree. Successors are generated for each state at the current level, sorting those states in an increasing order based on their heuristic cost. However, it only stores a predetermined number of best states at each level, called the beam width, and only those states are expanded.

Constraint Satisfaction

- It is a search strategy that deals with constraints that are the same as the ones that can be encountered in the real world. Constraints can either be temporal or tangible. Either way, dealing with constraints poses a varying degree of success. Extensive domain-specific and heuristic knowledge are needed in dealing with this kind of search strategy.

Game playing

exhibits different aspects of intelligence, particularly the ability to plan at an immediate tactical level and/or for long-term strategic level and the ability to learn.

i. Problems for which no exact algorithms are known, but approximation can be applied.

ii. Problems for which exact solutions are known, but the computations cannot be practically produced.

According to Gupta & Mangla (2020), the following types of problems that utilize heuristic searches are:

i. Games visualize and manifest real-life situations in a constricted manner and permits simulations.

ii. Games provide a well-structured task where success and failure can be measured with the least amount of effort.

iii. Extensive amount of domain-specific knowledge is infrequently needed because of the limited rules of games.

Below are the reasons why game playing serves an important role in AI development (Gupta & Mangla, 2020).

Game theory

is a branch of applied mathematics that encompasses a theoretical framework that abstracts social situations of multiple agents (competing players) in a well-defined environment. This can also be considered as the science of strategy or the optimal decision-making of independent and competing agents in a strategic environment.

· Game

- An environment that involves a set of circumstances that can produce a particular result dependent on the actions of two (2) or more players.

· Players

- These are the strategic decision-makers within the game.

· Strategy

- It is a complete plan of action of a player that considers the set of circumstances that may occur within the game.

· Payoff

- It is something quantifiable that a player can receive in arriving at a particular outcome.

· Information Set

- This encompasses the available information at a particular point in a game, which is commonly utilized in games that has sequential components.

· Notion of Equilibrium

- It is a point in a game where both players have made their decisions or moves and a particular outcome is reached.

1. If the total number of agents is very large, then it is possible to consider the agents as an aggregate - an economy.

2. Considering the argumentative - adversarial agents as part of the environment, even if it makes the environment nondeterministic.

3. Explicitly model adversarial agents with a specific search strategy or technique.

There are at least three (3) viewpoints that can be derived in an environment with multiple agents, such as games. What are the viewpoints? (Russell & Norvig, 2022).

A plausible move generator, a static evaluation function generator

Two (2) major components of a game playing program

· A plausible move generator:

If the number of permissible moves is too high, then it is impossible to perform a full-width search to a depth adequate enough to have a good game. This is considered an important search alternative in such domains. The process expands only the selected moves. It is not possible for all moves to be examined, since the given amount of time for a specific move is limited and the available computational power is also limited. However, further researches are being conducted aiming to enhance computational power using parallel processing architectures.

· A static evaluation function generator:

This is the most important component of a game playing program. It is used to evaluate every move that is being made. This holds a crucial role since it utilizes heuristic knowledge for evaluating and it acts like a pointer towards a plausible move generator that will generate the future paths. This can also be considered as a limiting factor in a search algorithm. Thus, when this is good, this should be very fast.

game tree

Possible game states/conditions can be represented using a directed graph, commonly called a ____ ____.

nodes, arcs

The _____ of a game tree represent the states of the game and the ____ represent the possible moves by the players

Minimax Strategy, Alpha-Beta Pruning

The basic strategies for game playing are as follows:

· Minimax strategy

- This is a well-known strategy for two (2) player games, where one player is identified as a maximizer (MAX) and the other as a minimizer (MIN). The main objective of this strategy is for a player to minimize loss and maximize benefit. Therefore, the move that leads to a terminal state with maximum payoff, under the assumption that the opponent plays to minimize payoff, can be considered optimal.

A static evaluation function

The algorithm for the minimax strategy begins at the current position and implements the plausible move generator to generate a set of possible successor positions. _______________ is then applied to those positions. Then, the best successor will be chosen and its value will be placed back up to the starting position to represent the evaluation.

Alpha-beta pruning

This is a minimax strategy with alpha-beta cut-offs. A slight modification in the search procedure is necessary in order to handle both maximizer and minimizer. This strategy requires the maintenance of two (2) threshold values, which are Alpha and Beta.

This strategy is strongly affected by the order in which game tree branches are explored.

Alpha

- It represents the lower bound value that a maximizing node may be assigned. Thus, representing the minimum score that the maximizer is assured of.

Beta

- It represents the upper bound value that a minimizing node may be assigned. Thus, representing the maximum score that the minimizer is assured of.

positive ( + ) infinity

For the minimizing nodes, the score computed starts with _______________________ and decreases with time.

negative ( - ) infinity

For maximizing nodes, the score computed starts with ______________________ and increases with time.

Knowledge

is defined as the body of facts, information, and skills acquired through experience or education. This is closely related to intelligence.

Intelligence

is the ability to acquire and apply knowledge and skills. A characteristic of intelligent people is that they possess a large amount of knowledge.

Knowledge representation

refers to the concept of identifying ways to provide machines with the knowledge that humans possess so that AI systems can become better (Bansal, 2021). The task of AI developers is to represent the knowledge of the human world in a way that machines can understand.

Domain-Specific Knowledge, Common-Sense Knowledge

2 main types of knowledge

· Domain-specific knowledge

- specialized knowledge required to perform a particular task. To acquire this knowledge, you have to train or study it.

· Common sense knowledge

- all other pieces of knowledge that help in reasoning other than domain-specific knowledge.

Procedural knowledge

- the compiled or processed form of information. It is related to the performance of some tasks. It provides information about how to achieve something.

· It is knowledge about knowledge (meta knowledge) and how to gain and use pieces of information.

· It involves more senses, such as hands-on experience, practice in solving problems, and understanding the limitations of a specific solution.

· Statements can be written without regard for the use that will be made of them later in the program, but in practice, the programmer will always have this in mind.

The following are advantages: of Procedural Knowledge.

Declarative knowledge

- knowledge about facts and things. These schemes include logic-based and relational approaches. This declares every piece of knowledge and permits the reasoning system to use the rules of inference to come out with new pieces of information.

· It is the ability to use knowledge in ways that the system designer did not foresee.

· A statement involving several variables needs only be written once in declarative form and can be used in different ways on different occasions according to the results sought.

· A declarative structure is easy to modify, and new statements can be added easily.

The following are advantages of Declarative Knowledge:

A knowledge-based system (KBS)

captures knowledge to solve problems in specific domains. This system has two (2) sub-systems, Knowledge Base and Inference Engine

Database

- A collection of data organized in some form

- Structured according to specific requirements and enables users to

access the desired information quickly and efficiently

- Updated by systems personnel

Knowledge Base

- Any collection of information, used very broadly

- More complex and requires greater computing capabilities

- Updated by domain experts

A knowledge representation scheme

is a set of syntactic and semantic conventions used in describing various objects. Some widely known representation schemes are logical representation, semantic network, frame representation, and production rules.

Logical representation

- the most basic form of representing knowledge that uses a well-defined syntax with concrete rules. This syntax has no ambiguity in its meaning and deal with propositions. It can be of two (2) types: Propositional Logic and Predicate Logic.

· Propositional logic

- the study of propositions, where a proposition is a statement that can be either true or false. This may be used to encode simple arguments expressed in natural language and determine their validity. An example of a proposition is "5 is a prime number."

· Predicate logic

- allows complex facts about the world to be represented, and new facts may be determined via deductive reasoning. A predicate is a proposition that depends on the value of some variables. For example, the statement "x is prime" will either be true or false depending on the value of x.

Semantic or associative network

- a structure that represents knowledge as a pattern of interconnected nodes and arcs. It is also defined as a graphical representation of knowledge. The objects under consideration serve as nodes, while the relationships with other nodes give the arcs.

Frame

- a collection of attributes and associated values which describes an entity in the real world. It is a record-like structure consisting of slots and their values. Slots vary in size and type and have names and values.

Production rules

- consist of condition-action pairs or if-then statements. All rules whose conditions are satisfied are found (rule matching), one of them is selected (conflict resolution), and its action is called (rule firing). This complete process is called the recognize-act cycle.