Artificial Intelligence and Machine Learning in Game

Types of AI used in games:

  • Deterministic — Deterministic performance or behaviour is predetermined and predictable. There isn’t any ambiguity. A basic chasing algorithm is an example of deterministic behaviour. By progressing along the x and y coordinate axes until the character’s x and y coordinates correspond with the target location, you can specify code a nonplayer character to advance toward a target point.

The bread and butter of game AI are deterministic AI approaches. These techniques are straightforward to build, comprehend, test, and debug since they are predictable, quick, and simple. Despite their benefits, deterministic approaches lay the task of anticipating all circumstances and explicitly writing all behaviour on the developers’ shoulders.
Furthermore, deterministic techniques obstruct learning and evolution. Deterministic activities tend to become predictable after a little practice. This, in a sense, shortens a game’s lifespan.

  • Nondeterministic — The counterpart of deterministic behaviour is nondeterministic behaviour. There is a degree of uncertainty in behaviour, and it is somewhat unpredictable (the degree of uncertainty depends on the AI method employed and how well that method is understood). A nonplayer character learning to adapt to a player’s battle techniques is an example of nondeterministic behaviour. A neural network, a Bayesian approach, or a genetic algorithm could be used in this type of learning.

Learning and unexpected games are made easier with nondeterministic approaches. Furthermore, developers are not required to code all behaviours explicitly in front of all possible instances. Nondeterministic approaches can also learn and extrapolate on their own, as well as foster emergent behaviour, which occurs without explicit instructions. Non-deterministic AI encompasses approaches for learning and reacting to character behaviour. Non-deterministic AI was employed in a number of popular games, including Creatures, Black & White, Battlecruiser 3000AD, Dirt Track Racing, Fields of Battle, and Heavy Gear. Their success rekindled interest in AI techniques like decision trees, neural networks, genetic algorithms, and probabilistic methodologies.

Establishing the AI in Game

Gaming — Computer at an advantage — Just think and pause here for a while about any war game and then read further.

Photo by Sigmund on Unsplash
  • Cheating — Cheating has been the most broadly utilized AI method in games. In a war simulation game, for example, the computer team can have access to all information about its human opponents’ base location; the types, number, and placement of units, and so on, without having to send out scouts as a human player would. This type of cheating is frequent, and it helps the machine gain an advantage against intelligent human gamers.

Unbalanced cheating can also offer computer opponents an unfair advantage, making it impossible for the player to defeat them. If the player sees his efforts are in vain, he is likely to lose interest. Cheating must be balanced in order to provide the player with just enough of a challenge to make the game engaging and enjoyable.

  • Fine State machine — A finite state machine (FSM) is a type of abstract machine that can exist in one of the multiple specified states. A finite state machine can additionally specify a set of criteria for when the state should change. The state machine’s behaviour is determined by its current state.
    Finite state machines have been used in computer games since the beginning. The ghosts in Pac Man, for example, are finite state machines. They have complete freedom to explore, chase, or dodge the player. They act differently in each state, and their transitions are dictated by the player’s activities. If the player takes a power pill, for example, the ghosts’ state may change from chasing to dodging. It could be clearly explained through Markov Model.

A Markov Reward Process (MRP) is a Markov model where transitions may have an associated reward or cost. Specifically, an MRP is a tuple (S, P, R, γ) where S is the set of states, P: S × S → [0, 1] is the transition function, R: S × S → R is a reward function associated with every transition and γ ∈ [0, 1] is a discount factor.

A cricket batsmen example about what will be the next state out of three state Miss, Out and Run.

import numpy as np
class Cricket:# A function that implements the Markov model to forecast the state/mood.
    def batting_forecast(bowl):
    
            # The statespace
        states = ["Miss","Out","Run"]# Possible sequences of events
        transitionName = [["MM","MO","MR"],["OM","OR","OO"],["RM","RO","RR"]]# Probabilities matrix (transition matrix)
        transitionMatrix = [[0.2,0.6,0.2],[0.1,0.6,0.3],[0.2,0.7,0.1]]# Choose the starting state
        nextbowl = "Miss"
        print("Start state: " + nextbowl)
        # Shall store the sequence of states taken. So, this only has the starting state for now.
        activityList = [nextbowl]
        i = 0
        # To calculate the probability of the next bowl
        prob = 1
        while i != bowl:
            if nextbowl == "Miss":
                change = np.random.choice(transitionName[0],replace=True,p=transitionMatrix[0])
                if change == "MM":
                    prob = prob * 0.2
                    activityList.append("Miss")
                    pass
                elif change == "MO":
                    prob = prob * 0.6
                    nextbowl = "Out"
                    activityList.append("Out")
                else:
                    prob = prob * 0.2
                    nextbowl = "Run"
                    activityList.append("Run")
            elif nextbowl == "Out":
                change = np.random.choice(transitionName[1],replace=True,p=transitionMatrix[1])
                if change == "OM":
                    prob = prob * 0.5
                    activityList.append("Miss")
                    pass
                elif change == "OR":
                    prob = prob * 0.2
                    nextbowl = "Run"
                    activityList.append("Run")
                else:
                    prob = prob * 0.3
                    nextbowl = "Out"
                    activityList.append("Out")
            elif nextbowl == "Run":
                change = np.random.choice(transitionName[2],replace=True,p=transitionMatrix[2])
                if change == "RM":
                    prob = prob * 0.1
                    activityList.append("Miss")
                    pass
                elif change == "RO":
                    prob = prob * 0.2
                    nextbowl = "Out"
                    activityList.append("Out")
                else:
                    prob = prob * 0.7
                    nextbowl = "Run"
                    activityList.append("Run")
            i += 1  
        a = str(activityList)
        b = str(bowl) 
        c= nextbowl
        d =  str(prob)
        
        forecast = {"Possible states": a, "End state after": b, " activity": c,
                    "Probability of the possible sequence of states":d }
         
        return forecast
  • Chasing and Evading — There are two elements to the chasing/evading problem. The first stage involves deciding whether to pursue or flee. The second step is to carry out the chase or evasion, which entails either getting your predator to the prey or having the prey get as far away from the predator as possible without being captured. In certain ways, the chasing/evading dilemma could be said to have a third component: barrier avoidance. Avoiding obstacles while chasing or escaping adds to the complexity of the algorithms, making them more difficult to develop.
  • Pattern Movement — Simple pattern movement can be used to create the illusion of intelligent behaviour. Essentially, the computer-controlled figures move in a predetermined way that gives the impression that they are conducting complicated, well-planned actions.

Pattern movement is often implemented by taking the required pattern and encoding the control data into an array or series of arrays. The control data is made up of particular movement instructions like advance forward and turn that force the computer-controlled object or character to move in the appropriate manner. You can use these algorithms to make a circle, square, zigzag, curve, or any other design that can be encoded into a short set of movement instructions.

  • Pathfinding — Pathfinding is simply the process of moving the position of a game character from its initial location to the desired destination.

Breadcrumb pathfinding — Because the player is unintentionally building the path for the computer-controlled character, breadcrumb pathfinding can make computer-controlled characters appear incredibly sophisticated. Every time the player makes a step, an invisible marking, or breadcrumb, is left on the game world. When a gaming character interacts with a breadcrumb, the breadcrumb just follows the trail. Until the player is reached, the game character will follow in the footsteps of the player. The path’s complexity and the number of barriers in the route are unimportant. Because the player has already created the path, no complex computations are required.

Pathfinding is a CPU-intensive and time-consuming procedure. Precalculating pathways whenever possible is one approach to mitigate this issue. Waypoint navigation solves this challenge by carefully establishing nodes in the game environment and then moving between them using pre-calculated pathways or low-cost pathfinding methods.

One of the most fundamental difficulties in-game AI is pathfinding. Poor pathfinding can make game characters appear robotic and brainless. Nothing ruins a game’s immersion faster than a gaming character being unable to overcome a simple set of barriers. Pathfinding is a difficult topic to solve, yet it may make a game more fun and immersive for the user.

A* Algorithm

Fortunately, the A* algorithm is a viable solution to the pathfinding problem. The A* algorithm is undoubtedly one of, if not the most widely utilised pathfinding method in today’s games. The A* method is intriguing because it guarantees to identify the optimum path between any starting point and any ending point, providing that such a path exists. It’s also a fairly efficient algorithm, which contributes to its appeal. In fact, you should use it whenever possible unless you’re dealing with a unique situation.

Steps:

  1. Defining the Search Area
  2. Starting the Search
  3. Scoring
  4. Finding a Dead End
  5. Terrain Cost

In its most basic version, the typical A* algorithm simply calculates path cost based on the distance travelled. A longer path is thought to be more expensive and so less desirable. A good pathfinding algorithm is frequently thought of as one that discovers the shortest path possible.

  • Fuzzy logic — Fuzzy logic is a manner of presenting problems to computers in a way that is similar to how people solve them. The core idea of fuzzy logic is that everything is a question of degree. What exactly does it imply when “problems are given to computers in a manner comparable to how humans solve them”? The premise is that humans frequently assess situations or solve problems in a sloppy manner. We may not have all of the information, or the facts may be ambiguous, or we may only be able to generalise the facts without precise data or measurements. Fuzzy logic allows you to pose and answer problems using linguistic words that are comparable to what you may use.

In fact, everything can be thought of in terms of fuzzy logic and be true to vary degrees. In fuzzy logic, anything is completely true if we state it is true to degree 1. An absolute false is truth to degree 0. We can have something that is either absolutely true or completely untrue in fuzzy logic, or anything in between with a degree between 0 and 1.

Fuzzy logic can be used in a variety of ways in games. Fuzzy logic can be used to control bots or other nonplayer character units. You can also use it to assess the hazards that players pose. Furthermore, both player and non-player characters can be classified using fuzzy logic.

  • Rule-Based AI — For both real-world and game AI applications, rule-based AI systems are perhaps the most extensively utilised AI systems. Rule-based systems are made up of a series of if-then style rules that are used to draw inferences or action decisions in their most basic form.

Working memory and rules memory are the two major components of rule-based systems. The rules’ assertions and known facts are stored in the working memory. The rules memory, or rules for short, is a collection of if-then-style rules that operate on the facts in working memory. When rules are triggered, or fired in rule-based system jargon, they can perform an action or change the state of the system, such as in a finite state machine, or they can modify the contents of the working memory by adding new assertions.

Forward chaining is the most frequent inference algorithm for rule-based systems. There are three basic phases to this method. Matching rules to facts stored in working memory is the initial phase. This is accomplished by comparing the if-parts of each rule to the set of facts or assertions stored in working memory. When a rule is fired, the next part of the rule is executed. More than one rule could potentially match a given set of facts in working memory. In this instance, we must determine which rule to revoke. The so-called conflict resolution phase follows. We must analyse all of the matching rules in the conflict resolution phase and decide which one to fire.

This decision can be made in a variety of ways. The first matching rule is usually fired first. You can sometimes choose one at random. In other circumstances, the rules are ranked and the one with the highest score is chosen. We fire the rule after the conflict resolution step is completed and a rule has been chosen. A rule’s then-part is simply executed when it is fired. In working memory, the rule might state some new facts. It could start an event or call another function to perform some sort of processing. The method is repeated until no more rules can be fired after these three phases have been completed. When this occurs, the working memory should store whatever the rule-based system can deduce based on the initial facts.

Backward chaining is the opposite of forward chaining. We still have working memory and rules memory, but we strive to match the then-parts of rules to working memory rather than the if-parts. To put it another way, in backward chaining, we start with an objective or goal and try to find out which rules must be fired to get there.

Some additional jargon regarding Neural Network and Genetic Algorithm

Neural networks have a number of advantages over more traditional AI techniques in games. First, by delegating important decision-making processes to one or more trained neural networks, game developers can simplify the coding of complex state machines or rules-based systems. Second, neural networks provide the game’s AI the ability to adapt as the game is being played.

Despite these benefits, neural networks are still not widely used in video games. Although neural networks have been employed in a few popular games, their use in games is still limited. This is most likely due to a number of variables, two of which I will discuss next.

  1. Neural networks excel at solving extremely nonlinear issues that are difficult to solve using standard methods. This can make it difficult to grasp exactly what the network is doing and how it gets its results, which can be alarming for a would-be tester.
  2. Predicting what a neural network will generate as output can be tricky at times, especially if the network is built to learn or adapt inside a game. Because of these two factors, testing and debugging a neural network is more complex than, say, testing and debugging a finite state machine.

It is the responsibility of the game designer to provide a demanding gaming experience for the player. In reality, balancing the game environment is an important component of game production. It must be sufficiently hard for the participants, otherwise, the game would appear too easy to them, and they will lose interest. If it’s too challenging, on the other side, the gamers will feel frustrated. Players can sometimes find vulnerabilities, or exploits, by which they can essentially cheat. This could be the outcome of a game design flaw that the makers failed to notice. Another issue with game design is that various players’ skill levels can be very diverse.

Creating a game that is properly balanced and challenging for players of various skill levels can be a difficult task. Genetic algorithms, fortunately, can assist. In a real computer game, a true genetic model is unlikely to be useful or practicable. Instead, the system we’ll talk about is simply based on a biological genetic system. It will be similar in certain aspects, but we will not be afraid to bend the rules. If it is beneficial to the game design process, rules may be broken.

You can break down the implementation of genetic algorithms in games into four steps.

  1. First Generation
  2. Rank Fitness
  3. Selection
  4. Evolution

Creating the first generation is the initial stage. A set of initial qualities is seeded across the entire population. We’ll need the means to rank the individual individuals as the populace starts interacting with its surroundings. This is how you rank your fitness. This informs us about the most successful people in the population. The ranking of fitness helps us with the following phase, which is choosing. We select specific individuals of the population to generate the next generation during the selection process. The most successful qualities of the previous generation are essentially used to produce the next generation. Evolution is the process of integrating these features to generate a new, and hopefully healthier, generation. Genetic algorithms are essentially optimization procedures in which we aim to identify the most suitable set of qualities in order to find the best solution to a certain problem.

In any scenario in which a computer-controlled adversary must respond and change in response to player activity, genetic algorithms are valuable.

 

Original post: https://swetankpathak.medium.com/artificial-intelligence-and-machine-learning-in-game-33ae7310e30a

Leave a Reply

Your email address will not be published. Required fields are marked *