Topic 9

Notes
Prolog
It is a declarative language where programs are expressed in terms of relations, and execution occurs
by running queries over these relations. Prolog is particularly useful for symbolic reasoning, database
and language parsing applications. Prolog is widely used in AI today.

Lisp
It is a practical mathematical notation for computer programs based on lambda calculus. Linked
lists are one of the Lisp language's major data structures, and Lisp source code is itself made up of
lists. As a result, Lisp programs can manipulate source code as a data structure, giving rise to
the macro systems that allow programmers to create new syntax or even new domain-specific
programming languages embedded in Lisp. There are many dialects of Lisp in use today, among
which are Common Lisp, Scheme, and Clojure.

Techniques and practices of game AI

There exist many techniques to cover different aspects in game AI, from fundamental movement to
advanced environment sensing and decision making. Let's look at them one by one.

Navigation
Navigation for AI is usually built up of the following tools:

Navigation Mesh: Using tools such as Navigation Mesh, also known as NavMesh, you can
designate areas in which AI can traverse. NavMesh is a simplified polygonal representation of a level
(the green region in the following screenshot), where each polygon acts as a single node connected
to its nearby ones. Usually, this process is automated and doesn't require designers to place nodes
manually. Using special tools in Unreal, they analyze the geometry of the level and generate the most
optimized Navigation Mesh accordingly. The purpose, of course, is to determine the playable areas
in the level by the game agents. Note that this is the only path-finding technique available; we will
use NavMesh in the examples provided in this book because it works well in this demonstration.

Path Following (Path nodes): A similar solution to NavMesh, Path nodes can designate the space
in which the AI traverses:
• Behavior Tree: Using Behavior Tree to influence your AI's next destination can create a more
varied player experience. It not only calculates its requested destination, but also decides whether it
should enter the screen with a cart wheeling double-back flip, no hands, or the triple somersault and
jazz hands
• Steering behaviors: Steering behaviors affect the way AI moves while navigating to avoid
obstacles. This also means using Steering to create formations with your fleets that you have set to
attack the king's wall. Steering can be used in many ways to influence the movement of the character.
• Sensory systems: Sensory systems can provide critical details, such as the nearby players, sound
levels, nearby cover, and many other variables of the environment that can alter movement. It's
critical that your AI understands the changing environment so that it doesn't break the illusion of
being a real opponent.
While all these components aren't necessary to achieve AI navigation, they all provide critical
feedback, which can affect the navigation. Navigating within a world is limited only by pathways
within the game.
Root
This node is the beginning node that sends the signal to the next node in the tree. This connects to a
composite, which begins your first tree. What you may notice is that you are required to use a
composite first to define a tree and then to create a task for this tree. This is because hierarchical FSM
creates branches of states. These states will be populated with other states or tasks. This allows an
easy transition among multiple states.
Decorators
Decorators are conditional statements (the blue part on top of a node) that control whether or not a
branch in the tree or even a single node can be executed. I used a decorator in the AI we will make
to tell it to update to the next available route. In the following image, you can note the Attack &
Destroy decorator that defines the state on top of the composite. This state includes two tasks, Attack
Enemy and Move To Enemy, which also has a decorator telling it to execute only when the both
state is Search:
This state includes two tasks, Attack Enemy and Move To Enemy, which also has a decorator
telling it to execute only when the both state is Search
Composites
These are the beginning points of the states. They define how the state will behave with returns and
execution flow. They have three main types: Selector, Sequence, and Simple Parallel. This beginning
branch has a conditional statement, if the state is equal or greater than Search state Selector executes
each of its children from left to right and doesn't fail; however, it returns success when one of its
children returns success. So, this is good for a state that doesn't check for successfully executed nodes.
Natural Language Processing
Natural Language Processing (NLP) refers to AI method of communicating with an intelligent
systems using a natural language such as English. Processing of Natural Language is required when
you want an intelligent system like robot to perform as per your instructions, when you want to hear
decision from a dialogue based clinical expert system, etc.

The field of NLP involves making computers to perform useful tasks with the natural languages
humans use. The input and output of an NLP system can be:
i. Speech
ii. Written Text

Components of NLP
There are two components of NLP as given:

Natural Language Understanding (NLU)

Understanding involves the following tasks:
i. Mapping the given input in natural language into useful representations.
ii. Analyzing different aspects of the language.

Natural Language Generation (NLG)

It is the process of producing meaningful phrases and sentences in the form of natural language
from some internal representation. It involves:
i. Text planning: It includes retrieving the relevant content from knowledge base.
 ii. Sentence planning: It includes choosing required words, forming meaningful phrases,
setting tone of the sentence.
iii. Text Realization: It is mapping sentence plan into sentence structure. The NLU is harder
than NLG.

Difficulties in NLU
i. NL has an extremely rich form and structure.
ii. It is very ambiguous.

There can be different levels of ambiguity:

i. Lexical ambiguity: It is at very primitive level such as word-level. For example, treating the
word “board” as noun or verb?
ii. Syntax Level ambiguity: A sentence can be parsed in different ways. For example, “He lifted
the beetle with red cap.” – Did he use cap to lift the beetle or he lifted a beetle that had red
cap?
iii. Referential ambiguity: Referring to something using pronouns. For example, Rima went to
Gauri. She said, “I am tired.” - Exactly who is tired?
o One input can mean different meanings.
o Many inputs can mean the same thing.

NLP Terminology

i. Phonology: It is study of organizing sound systematically.

ii. Morphology: It is a study of construction of words from primitive meaningful units.
iii. Morpheme: It is primitive unit of meaning in a language.
iv. Syntax: It refers to arranging words to make a sentence. It also involves determining the
structural role of words in the sentence and in phrases.
v. Semantics: It is concerned with the meaning of words and how to combine words into
meaningful phrases and sentences.
vi. Pragmatics: It deals with using and understanding sentences in different situations and how
the interpretation of the sentence is affected.
vii. Discourse: It deals with how the immediately preceding sentence can affect the interpretation
of the next sentence.
viii. World Knowledge: It includes the general knowledge about the world.

Steps in NLP
There are general five steps:
1. Lexical Analysis
It involves identifying and analyzing the structure of words. Lexicon of a language means the
collection of words and phrases in a language. Lexical analysis is dividing the whole chunk of txt
into paragraphs, sentences, and words.
2. Syntactic Analysis (Parsing)
It involves analysis of words in the sentence for grammar and arranging words in a manner that shows
the relationship among the words. The sentence such as “The school goes to boy” is rejected by
English syntactic analyzer.
3. Semantic Analysis
It draws the exact meaning or the dictionary meaning from the text. The text is checked for
meaningfulness. It is done by mapping syntactic structures and objects in the task domain. The
semantic analyzer disregards sentence such as “hot ice-cream”.
4. Discourse Integration
The meaning of any sentence depends upon the meaning of the sentence just before it. In addition, it
also brings about the meaning of immediately succeeding sentence.
5. Pragmatic Analysis
During this, what was said is re-interpreted on what it actually meant. It involves deriving those
aspects of language which require real world knowledge.

Implementation Aspects of Syntactic Analysis

There are a number of algorithms researchers have developed for syntactic analysis, but we consider
only the following simple methods:
i. Context-Free Grammar
ii. Top-Down Parser

Let us see them in detail:

Context-Free Grammar
It is the grammar that consists rules with a single symbol on the left-hand side of the rewrite rules.
Let us create grammar to parse a sentence –“The bird pecks the grains”

Articles (DET): a | an | the.

Nouns: bird | birds | grain | grains
Noun Phrase (NP): Article + Noun | Article + Adjective + Noun

= DET N | DET ADJ N

Verbs: pecks | pecking | pecked

Verb Phrase (VP): NP V | V NP
Adjectives (ADJ): beautiful | small | chirping

The parse tree breaks down the sentence into structured parts so that the computer can easily
understand and process it. In order for the parsing algorithm to construct this parse tree, a set of
rewrite rules, which describe what tree structures are legal, need to be constructed.

These rules say that a certain symbol may be expanded in the tree by a sequence of other symbols.
According to first order logic rule, ff there are two strings Noun Phrase (NP) and Verb Phrase (VP),
then the string combined by NP followed by VP is a sentence. The rewrite rules for the sentence are
as follows:

S -> NP VP
NP -> DET N | DET ADJ N VP -> V NP

Lexocon:
DET -> a | the
ADJ -> beautiful | perching
N -> bird | birds | grain | grains
V -> peck | pecks | pecking

The parse tree can be created as shown:

Now consider the above rewrite rules. Since V can be replaced by both, "peck" or "pecks", sentences
such as "The bird peck the grains" can be wrongly permitted. i. e. the subject-verb agreement error
is approved as correct.

Merit: The simplest style of grammar, therefore widely used one.

Demerits:
i. They are not highly precise. For example, “The grains peck the bird”, is a syntactically correct
according to parser, but even if it makes no sense, parser takes it as a correct sentence.
ii. To bring out high precision, multiple sets of grammar need to be prepared. It may require a
completely different sets of rules for parsing singular and plural variations, passive sentences,
etc., which can lead to creation of huge set of rules that are unmanageable.

Top-Down Parser

Here, the parser starts with the S symbol and attempts to rewrite it into a sequence of terminal
symbols that matches the classes of the words in the input sentence until it
consists entirely of terminal symbols.

These are then checked with the input sentence to see if it matched. If not, the process is started
over again with a different set of rules. This is repeated until a specific rule is found which
describes the structure of the sentence.
Merit: It is simple to implement.

Demerits:
i. It is inefficient, as the search process has to be repeated if an error occurs.
ii. Slow speed of working.