What Are Steering Behaviours?

Steering behaviors are force-based influences used to navigate an agent within an environment based on stimuli. Each steering behaviours consists of a vector and weight to rotate an agent in a desired direction, if multiple forces are used, all are combined to generate the total steering force which will turn the agent towards the resulting vector.

Types of Steering Behaviours

Flee & Seek

Flee and seek are very similar behaviours, this usually calculated by subtracting one location from another and steering towards the resulting vector.

Evade and Pursuit

Evade and pursuit use seek and flee as a template for their calculations except an additional calculation of velocity is used of a given target to calculate where to intercept or evade from.

Group Movement

Group movement is a combination of multiple steering behaviours to generate a steering force for an agent within a group, this is generated by reacting to other agents and their current velocity/distance from the current agent as stimuli which allows for the current agent to calculate a desired force. Some common steering behaviours for group movement include, cohesion, separation and alignment, a group should separate an equal distance from each other but also travel in a group like manner, this would then be travelling in a similar direction as every other agent around (usually towards a target).

Steering Behaviour Discussion

A Steering behaviour model is more reactive than pathfinding algorithms, like A* or JPS, in terms of navigating other agents. With steering behaviours each agent will have to calculate their desired steering forces each frame and can react to changes around them quicker to alter the steering force which allows for a faster response to stimuli, whereas with an algorithmic approach using pathfinding is potentially slower due to recalculating an alternative path, for example, if something blocks the path that the agent is following it might get moved off its course and have must recalculate the correct route which can be expensive dependent on the algorithm used. The method used for locomotion entirely depends on the requirements of the system, but steering behaviours and pathfinding can both be implemented to provide a balance between path optimisation and reactivity.

Steering behaviours are simple and versatile because they use a force-based system, this enables a programmer to create multiple steering behaviours that can be developed independently of each other. When these steering forces are combined it provides a value which can be calculated to get the overall desired steering force. This allows for modularity of the agents.

Cost of steering behaviours is relatively less computationally expensive in comparison to pathfinding but can be computationally expensive when the system is scaled. For Example, if the scene contains lots of agents, and all the agents are running multiple complex steering behaviours it would be expensive. This is because the steering force is calculated each frame and having multiple complex steering behaviours calculated requires lots of operations, the more complex & unoptimised the scripts, the more computational power required. Although Steering behaviours can be cheaper, they are ineffective in finding an optimised path to a location, this is because there is no precomputed path data to follow which can lead to problems navigating into dead ends and less desirable paths.

Conclusion

Steering behaviours are excellent for agents to react in an autonomous manner using multiple stimuli to steer in a direction, although it may not be as complex as a pathfinding algorithm in calculating a path, it allows for reactive and predictable movement from agents with a lower computational cost.

Bibliography

Steering Behaviours: Seeking & Arriving – ‘Jb-Dev’ - Accessed :28th January 2024 - Available At: https://www.gamedev.net/blogs/entry/2264855-steering-behaviors-seeking-and-arriving/
Steering Behaviours for Autonomous Characters – Craig W. Reynolds – Accessed: 28th January 2024 – Available At: https://www.red3d.com/cwr/steer/gdc99/
Simon Coenen - (2016) Steering Behaviors in C# & C++ – Howest University

Chess is a complex strategy game which requires the player to think multiple moves ahead and plan to win, factoring the opponent’s moves into their decision making. Chess programming currently is a solved problem, and computers play chess better than humans can. Chess AI has come a long way since its earliest implementations with new algorithms being developed to make the computer think similarly to a human making it harder to beat by utilising heuristics.

Minmax

Chess is a non-perfect information game meaning that nothing is hidden from the other player meaning there is opportunity for strategic plays to be calculated ahead of time, this will allow for the computers to use a Minmax Algorithm. A Minmax algorithm is the method of choosing the best possible sequence of moves to achieve victory, in chess the nodes that minmax use are boards depicted as a best move number, this algorithm is impossible to calculate a perfect win every time, this is because there are more chess board combinations than the number of atoms in the observed universe. Alan Turing's evaluation heuristic for the minmax algorithm was a good starting point with the next potential boards score being the total of the “Score = White Pieces/Black Pieces” this put each piece at a point value, pawns the lowest, queen the highest. This was then later replaced by a slightly different evaluation of “Score = White Pieces - Black Pieces” as it can provide more accurate values to a piece worth when calculating a move.

Alpha-beta pruning

The popular Chess AI “Stockfish14” uses alpha beta pruning, a heuristic to reduce the number of nodes that a minmax algorithm will have to process, which increases efficiency. Alpha beta pruning involves using the minmax to calculate the nodes and discards the current node search if it yields an outcome that results in a score less than the previous node, this saves a fraction of computing on the nodes missed but as more nodes are calculated the fractional differences add up to a worthwhile time save whilst navigating through the complex decision tree.

Null Move

To further optimise decision making Null Move Pruning (NMP) is employed to calculate the opponents potential moves. By “passing” the current and evaluating the board the AI can anticipate the threat of a checkmate by pretending to be the enemy and see what moves they could make.

Machine Learning Integration

Machine learning has been utilised to improve chess AI throughout time by combining heuristics like the Monte Carlo Tree Search (MCTS) and neural networks. This is showcased in the AlphaZero project developed by DeepMind. This project focused on a self-play unsupervised Artificial intelligence. This approach removed the need for human data or playbook strategies forcing the AI to learn independently. The AI would undergo many trial and error games in this format and lead to a formidable playstyle that challenges opponents with the strategies acquired demonstrating the next big step in AI Evolution.

Conclusion

Chess AI has made significant milestones pushing the boundaries artificial intelligence capabilities. The Continuous refinements of algorithms and machine learning techniques outline a promising future for Chess AI potentially expanding beyond the gaming landscape, contributing valuable advancements in other technological fields.

Bibliography

Alpha Beta Pruning – Wikipedia – Accessed 23rd February 2024 - Available At: https://en.wikipedia.org/wiki/Alpha-beta_pruning
BetaCuttoff– Chess Programming Wiki – Accessed 23rd February 2024 - Available At: https://www.chessprogramming.org/Beta-Cutoff
GoogleDeepMind– AlphaZero – Accessed 23rd February 2024 - Available At: https://deepmind.google/discover/blog/alphazero-shedding-new-light-on-chess-shogi-and-go/
Monte Carlo Tree Search – Chess Programming Wiki – Accessed 23rd February 2024 - Available At: https://www.chessprogramming.org/Monte-Carlo_Tree_Search

Halo is a First-Person shooter game released in 2001 which enriches the world immersion through the intelligence of the enemies and allies' behaviour from implementing simple tactics like taking cover to searching for the player. The 2001 masterpiece achieved this through a new approach of behaviour trees.
Behaviour Trees
The use of Behaviour trees in other games at the time of Halo Combat Evolved’s release was unheard of. 343i and Bungee decided to implement this to create a modular system that could be placed on any AI which would save time in development. Each AI Class is assigned a tree that contains behaviours, the Covenant AI for Grunts and Elites are some of the more interesting trees. All Enemies have a Few Base Leafs, and they all lead into their own unique behaviour once the leaf has been followed.

Vehicle – If the chief is in a vehicle, get in one if possible

Retreat – The Chief has done something, Run away

Self-Preservation – Throw Grenade, Cover or Guard the position

Engage – This leaf will be enemy type dependant for behaviour

Post Combat – The chief has died, Shoot or Check the corpse

Idle – Guard the location

For the grunts they have an added behaviour that is Unique, once their group leader (An Elite) is killed the grunts will all flee from the chief, once they have got a good distance away or they have spent some time running they will return back to their Engage state, this allows for the player to be immersed as master chief being known as this toughened enemy to fight translate into the players actions instilling a wave of fear in the enemies to get them to run. The Allied marines change their behaviour once the player is in the vicinity, this swaps their decision making to appear more fearless when fighting, this is yet again to provide immersion and allow the player to feel like this unstoppable machine. Both of the opposing AI decisions can be primarily seen in the mission Silent Cartographer as the player drops onto the Southern beach with marines to fight a covenant force, the AI have no problem charging at the Covenant and the AI will run scared once their leaders are eliminated.

Memory issues were considered when working with behaviour trees as each AI would need to store data to have a tree work and with the Original Xbox containing 64MB of ram, each piece of temporary data stored had to be a necessity. This was solved by using a “Prop” which “can act as a convenient storage location for per-object per-behavior memory”. The prop method forms the majority of Halo CE’s AI knowledge despite being rudimentary due to its flat list of object references, it has some shortfalls in the case of only allowing potential targets on the list which could obfuscate other relevant objects such as weapons and pathfinding obstacles.

Conclusion
To Conclude Halo Combat evolved revolutionised gaming AI with behaviour trees shaping the future of decision making by implementing a simple method to create AI that reacts in accordance with the stimuli provided by the environment. Many engines now implement their own version of the behaviour trees.

Bibliography

https://c20.reclaimers.net/h1/engine/ai/ https://www.gdcvault.com/play/1022590/Creating-the-Illusion-of-Intelligence https://www.gamedeveloper.com/programming/gdc-2005-proceeding-handling-complexity-in-the-i-halo-2-i-ai#close-modal