Introduction, Algorthims and Heuristics

Introduction

Artificial intelligence (AI) makes up a huge part of most of the computer games that we know and love. Some AI has been poorly designed, whilst others provide such an immersive experience that we can often forget that we are even playing a game. Further on in this document I will be explaining the core concepts and techniques that construct AI in games.

Algorithm

An algorithm is a simple set of rules, or as (Deangelis, 2017) defines it: a set of “Mathematical instructions.” These mathematical instructions will contain a starting point and an end goal. An example of this would be the recipe for baking a cake. Each ingredient that you add is an instruction, the end goal is turning those ingredients into a cake. Algorithms contain steps which, when executed, should reach the goal intended.

Heuristics

Heuristics are the “criteria, methods or principles for deciding which among several alternative courses of action promises to be the most effective in order to achieve some goal.” (Pearl, 1984). These are rules of thumb or guidelines that we use to make decisions based on past experiences. It’s our way of learning from our mistakes and exploring different options to reach the goal that we desire. We use heuristics in our day-to-day life, it’s part of our decision making. Let’s take driving to work as an example; we consider the route; how long it will take; whether there are traffic jams / roadworks. Another example provided by the user (headlessprofessor, 2010) he explains the way heuristics can be used to build a (3x3x3) soma cube. The algorithm that he uses for his heuristic are shown in [fig. 1]. These are rules that he follows when building the cube. When applied to AI, these “guidelines” are what will be followed when constructing an algorithm for pathfinding.

Figure 1: Heuristic vs algorithm

(Headlessprofessor, 2010).

Heuristics need to follow four basic principles:

- They should be as optimal as possible. i.e. the correct algorithm should be used to ensure that the heuristics aren’t overly complicated. Over complicated algorithms require more resources from the hardware.

- They should be complete and accurate. The correct solution must complete the end-goal within a reasonable margin of accuracy.