Genetic Algorithm

Genetic algorithms are a kind of algorithm used to find approximations in search problems. Genetic algorithms are a class of evolutionary algorithms (algorithms that simulate evolution: each generation of solution is subjected to some kind of fitness function; those that survive are then recombined in some way to make the next generation of solution). 

The concept of genetic algorithms is a search technique often used in computer science to find complex, non-obvious solutions to algorithmic optimization and search problems. Genetic algorithms are categorized as global search heuristics, and have a wide variety of applications, particularly in generating useful Artificial Intelligence agents in computer games.

For decades, game theory has provided competitive, dynamic, often unpredictable environments that make ideal test beds for computational intelligence theories, architectures, and algorithms. Natural evolution can be modeled as a game, in which the rewards for an organism that plays a good game of life are the propagation of its genetic material to its successors and its continued survival. In natural evolution, the performance of an individual is defined with respect to its competitors and collaborators, as well as to the environment. More simply described, genetic algorithms are a simulation in which a population of abstract representations (called chromosomes or the genotype of the genome, after their biological counterparts) of candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem.

Candidates are evaluated and crossbred in an attempt to generate high quality solutions which would be non obvious and extremely time consuming to a human programmer. An evolutionary phase is initialized with a population of randomly generated entities (or human specified instances of high quality). The process is subdivided into different generations. In each generation, the fitness of every individual in the population is evaluated, and multiple individuals are stochastically (randomly) selected from the current population (based on their fitness), and modified (recombined and possibly randomly mutated) to form a new population. The new population is then used in the next iteration of the algorithm. The algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population.

Board games are a very relevant part of the area of genetic algorithms as applied to game theory problems. Much of the early work on computational intelligence and games was directed toward classic board games, such as tic-tac-toe, chess, and checkers. Board games can now, in most cases, be played by a computer at a higher level than the best humans, even with blind exhaustive search techniques (brute-force approaches). Go is a noted exception to this tendency, and has so far resisted machine attack. The best Go computer players now play at the level of a good novice. Go strategy is said to rely heavily on pattern recognition, and not just logical analysis as with chess and other more piece-independent games. The huge effective branching factor required for finding high quality solutions heavily restricts the look-ahead that can be used within a move sequence search.

Ggenetic algorithm can be also be utilized in computer games – for example, to allow an enemy opponent to adapt in order to cater against an effective but repetitive tactic exhibited by a human player. This allows for a more realistic game experience; if a human player can find a sequence of steps which, repeated in different games always lead to success, there can be no challenge left. Conversely if a learning technique such as a genetic algorithm for a strategist can avoid repeating past mistakes, the game will have increased playability.

The concept of having a full or partial view of the game changes the approach required significantly. An important point to note is that despite a computer obviously having a full view of the game state, making this fully available to the decision making process of an artificial player is going to make them behave unrealistically. Human-centered games are limited by what can easily be manipulated given human mental capacity and dexterity. Video games, on the other hand, operate under no such constraints and typically have a vastly more complex (internal) state space than even the most complex of human-centered games. This richer complexity encourages the development or evolution of more general purpose AI agents than are necessary for playing board or card games with sufficiently simulated skill levels.

Currently, most computer controlled players in games implemented using manual scripting, which is quite tedious and time consuming to develop and test. The use of computational intelligence techniques offers an interesting alternative to scripted approaches, whereby the agent behavior can be controlled using an evolved neural network (an artificial brain made of artificial neuron cells), for example, rather than being programmed. A neural approach may result in unique, novel behavior impossible to achieve with manual implementation. Evolved AI players tend to be excellent at exploiting loopholes in a game. Identifying and eliminating these elements (which are seen as problems by the players/developers) can be achieved by genetic algorithms. In addition to this, through the life of a game, human players will also discover exploits, giving them an unfair advantage. If an AI player can also take advantage of these, the playing field is leveled

These techniques must be developed very carefully, especially in cases where agent difficulty is curved to compete fairly with the player. It has been an established technique in such games for a human player to intentionally play badly earlier on in the game, thus easing the difficulty; which in the end will decrease the quality and longevity of the game. Unfortunately, players tend to blame the developer for allowing it to be possible.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.