Artificial Intelligent for Computer Games
What is Artificial
Intellegence?
Artificial
intelligence or intelligence added to a system that can be used in a scientific
or Artificial Intelligence context is defined as the intelligence of a
scientific entity. Such systems are generally computers. Printing and inserting
into the machine (computer) in order to do the work as humans can. Some areas
use artificial intelligence, computer games (games), fuzzy logic, artificial
neural networks and robotics.
It
may be that AI will grow to the point where AI has reached True Sentience. When
it happens the AI is no longer a machine but a creature that can think and when
it happens also we can not control them anymore so the decisions they make will
be beyond human estimates.
Decision
Making: Decision Tree, State Machine and Rule System
Decision
Making
is a series of algorithms designed to include some possibility steps that an
application can do. In the game, decision making gives ability of a character
to decide what to do.
Decision Tree
Decision trees are
powerful and popular tools for classification and prediction. The decision tree
method was a method that transformed a very large fact into a decision tree
which was presenting the rules so it is easy to understand with natural
language. A Decision Tree is made up of connected decision points.
1.
Tree
has starting decision (root)
2.
For
each decision (starting from root), one of a set of ongoing options is chosen
3.
Choice
is made based on conditions derived from the character’s knowledge/values
4.
Continue
along the tree until the decision process has no more decisions to make
5.
Each
leaf is an action, to be executed
A
sample decision tree of a soldier character
The
action for the character is determined by going through a series of decision
points
State Machine
Finite State Machine
(FSM) is a control system methodology that describes system’s behavior using
three things, State, Event, and Action. On a program, the system would be in
one active state. The system can switch or move to another state if it gets a
certain input or event from external or components in the system itself (eg
timer interruptions). Transitions of this state are also followed with actions
by the system in response to inputs.
In procedural programming
languages such as C, FSM is usually applied by using switch case control
statements or/and if..then to be easily tracked in case of logic errors.
Rule
System
Rule
Based System is a method of decision-making based on certain rules that have
been set. A RBS is built on two main components, a set of facts and a set of
rules.
· A
set of facts or knowledge base are combination of data, such as income and a
condition such as ‘is zero’, or ‘is greater than 10’.
·
A
set of rules (the rules engine) describe
the relationship between the IF and the THEN statements. For example a rule
might be “IF a loan applicant has an income of zero THEN refuse the loan”.
Rule Based System can
be applied to virtual agents in the form of artificial intelligence that can
perform certain actions. The action is represented by a set of rules that is
the cause the action occurs, process and the result of the action.
You can have many more
rules. The main scheme is to write this set of rules and execute them
continuously during the game (at each iteration of the game loop or in fixed
intervals).
Path
Finding
The pathfinding method is easiest to meet in the type
of strategy game in which we designate one numbers
to move to a specific location by clicking on the location they want to go to.
The character will immediately move in
the direction specified, and "smart" can find the shortest path or avoid obstacles that exist. One pathfindin algorithm
is quite common and the most widely
used to find the shortest distance efficiently is the A * algorithm (read: A star). In general, the A * algorithm defines the
search area into the node set (tile). The
starting and ending points are determined first to begin the search on each nodes that make it possible to search. From here, a
score will be obtained that shows the magnitude the
cost of taking the found path, plus the heuristic value that is the value cost estimates from the existing node towards the
final destination. Iteration will be done until finally
achieved target.
Neural
network (neural network)
Neural networks are quite good when applied to
non-linear or take cases decisions that can
not be made with traditional methods. Its application is often on gamegame which requires adaptive ability or
learning from experience. For example, if suatau when
there is a battle between the player with the computer unit, and the
computer unit is defeated, then on another
similar occasion, the computer will choose not to fight. More many experiences experienced computer, then the
computer becomes smarter. The basic principle of this
artificial neural network is a continuous increase in weight for the resulting
output become more accurate (getting smarter).
The
path search or cool term is pathfinding in my description is the search process
route / route (usually the closest route) of an arena that generally has
barriers from the arena. The barrier can be a wall, a river, etc. Goal from
this pathfinding on generally is to find the most efficient path by avoiding
obstacles as much as possible which exists.
Pathfinding
can be applied for example in making AI of a game, for example in order for the
AI can pursue enemies efficiently and without crashing against walls or
avoiding other obstacles.
There
are several methods that can be applied in this pathfinding, one of the most
frequent methods used is A *. Ok, without a convoluted we just get acquainted
with this one method.
Waypoint
Waypoint
is the reference point / set of coordinates used for navigational purposes for
identify a point on the map. Coordinates that usually include longitude,
latitude, and sometimes altitude for air navigation purposes. Waypoints are
used in various navigation has no tracks that look like navigation in the air
and navigation at sea, as well as on land navigation which has no clear path.
Special navigation on land that does not use man as determining the direction
but the robot, waypoint is used although there is a clear path. This is
important in order robots still have a route.
Waypoint
is divided into two types, namely waypoint fly by and waypoint fly over.
Waypoint fly by does not pass the location over the way point but keeps toward
the destination, while the waypoint fly over passes the location above the way
point. After one waypoint is passed, the pilot must assign the next waypoint
called the active waypoint.
A* Search
The basic informed search strategies
are:
1. Greedy search (best first search)
2. A* search
What is A* Search Algorithm?
A* Search algorithm is one of the best and popular
technique used in path-finding and graph traversals. What makes A* different
and better for many searches is that for each node, A* uses a function that gives an estimate of the total cost of a
path using that node. Therefore, A* is a heuristic function, which differs from
an algorithm in that a heuristic is more of an estimate and is not necessarily
probably correct. A* expands paths that are already less
expensive by using this function:
where
f (n) = total estimated cost of path
through node
g (n) = cost so far to reach node
h (n) = estimated cost from to goal. This is the heuristic part of the
cost function, so it is like a guess.
Djikstra Algorithm
Dijkstra's algorithm is an algorithm for
finding the shortest paths between nodes in a graph, which may represent, for
example, road networks. It was conceived by computer scientist Edsger W.
Dijkstra in 1956 and published three years later.
Dijkstra Algorithms is a subsets from
Greedy Algorithms. Dijkstra Algorithms and Greedy is a algorithm which every
step of the process takes a edge or arc that has the minimum value weight that
connects a vertex which has been chosen with another vertex that has not been
chosen.
Example for Djikstra Algorithm :
Tactical
and Strategic AI
Certainly when we’re
thinking about AI at this particular level, it is at the upper level, it is
about making a reasonably long term plans or trying to ponder and take into
what you can make to characterizes the
big picture and then to make some decisions on this. Tactical and strategic AI
encompasses a wide range of algorithms that try to :
·
Derive a tactical assessment of some situation,
possibly using incomplete or probabilistic information.
·
Use tactical assessments to make decisions and
coordinate the behavior of multiple characters.
Waypoint
tactics
A waypoint is simply a position in the
game world. A waypoint can be
represented as a single position in the game level (“nodes”, “representative points” used for
pathfinding). To use waypoints tactically,
you need to add more data to the nodes (not just location info).
Some examples of use of waypoints to represent position in the level with
unusual tactical features or information. This features is called tactical
points. Tactical points can be either set by the designer or derived from game
data or analytical algorithms.
Tactical nodes can be combined with
pathfinding nodes to provide tactically aware path finding. Although common to
combine two sets of waypoints (one for tactical, one for pathfinding), it is
not efficient nor flexible, e.g. Cover and sniping waypoint nodes are not
useful for pathfinding which result in
unrealistic movements within level.
Using
Tactical Locations
How do we build a tactical mechanism
within the character AI? There are three approaches:
1.
Controlling
tactical movement (simple method)
2.
Incorporate
tactical information into decision-
making
3.
Use
tactical information during pathfinding
All three of them can produce character
motion that is always tactically aware.
1. Tactical Movement
Tactical waypoints are queried during
game when the character AI needs to make a tactical move. E.g. Character needs
to reload bullets, it queries the tactical waypoints in the immediate area to
look for “nearest suitable location” to stop and reload, before continuing.
Action decision is carried out first, then apply tactical information to
achieve its decision. There are some limitation in realism, and not able to use
tactical information to influence decision-making due to limited use.
2. Tactical Information
in Decision-Making
Decision Tree is mainly build to create
a conclusion of various data and/or information. Give the “decision-maker”
access to tactical information, just like any other game world information. DT
example:
3. Tactical Information during Pathfinding
Relatively simple extension of basic
pathfinding. Rather than finding shortest/quickest path, it takes into consideration tactical situation of game.
Simplest way is to manipulate graph connection costs (by adding “tactical cost” to locations that are
dangerous or reducing “tactical cost” at
locations that are easy)
Tactical
Analyses
Sometimes known as influence maps – a
technique pioneered and widely used in
RTS games where the AI keeps track of
areas of military influence in game. Can also be used in simulation/evolution
games, FPSs or MMOs. Overwhelming majority
of current implementations are based on
tile-based grid worlds. Even for non-tile-based
worlds, a grid can be imposed over the geometry for tactical analyses. The influence map can be used to
identify points of weakness and strength and, from this, drive strategic goal
solution.
Influence maps allows AI to see which areas of the game are safe, which areas to avoid, where the border between teams are weakest.
This is a link to our youtube video for this article :
https://www.youtube.com/watch?v=yOPh5Hxa2Yw
CREATED BY :
·
MUHAMMAD
IMAM ZULKARNAEN (54415652)
·
LESKA
NATURALISA (53415812)
·
RATNA
UTAMI HANDINI (57415565)
·
TIKA
PURNAMA PUTRI (56425899)
·
SAMUEL
ADRIAN NIVEN (56415357)
Sources :
