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.

CREATED BY :

·         MUHAMMAD IMAM ZULKARNAEN    (54415652)

·         LESKA NATURALISA                   (53415812)

·         RATNA UTAMI HANDINI              (57415565)

·         TIKA PURNAMA PUTRI                (56425899)

·         SAMUEL ADRIAN NIVEN              (56415357)

Source :
https://www.techopedia.com/definition/190/artificial-intelligence-ai
https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=26&cad=rja&uact=8&ved=0ahUKEwjq256tiaPaAhXClZQKHYv5DdwQFgjXATAZ&url=https%3A%2F%2Fwww.inc.com%2Farticles%2F2003%2F04%2F25423.html&usg=AOvVaw1XdbyI0JSSlS_ZPYnV3H_O
https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=6&cad=rja&uact=8&ved=0ahUKEwjg653EiaPaAhVLo5QKHZhfCvQQFghbMAU&url=https%3A%2F%2Fmedium.com%2Fomarelgabrys-blog%2Fpath-finding-algorithms-f65a8902eb40&usg=AOvVaw1CXTegazaEh37VrmKjdyRh