Fighting Game AI
Authors: Avery Beardmore, Adrian Palidis, Roxy Promhouse
What is the problem?
Fighting games are a popular genre of competitive video gaming, involving two opponents who fight by proxy using established characters in the game. Each character in a fighting game may have a different set of executable actions - their "moves" - that deal varying amounts of damage to their opponent character. The object of the game is, of course, to inflict enough damage on your opponent to KO them before they can do the same.
The goal of our project is to explore building a general AI for playing a fighting game using logic programming. We would seek to design an AI that can, given the immediate game-state, query for the best possible set of moves to give itself an advantage.
We will be referencing the frame data and rules of Super Street Fighter 2 Turbo given here: http://wiki.shoryuken.com/Super_Street_Fighter_2_Turbo#Strategy
What is the something extra?
Although every brand of fighting game has its own unique mechanics, nearly all games of the genre involve the use of combos: a string of moves that either cannot be or is very difficult to be interrupted by the opponent. Every move has a number of animation frames, typically split into animation before, during, and after an attack (start-up animation, active animation, and recovery animation).
Combos are built from sequences of moves that don't have long recovery and startup animation, as well as moves that, when they connect with the opponent, force the opponent into a flinching animation for several frames (typically known as 'hit-stun'). If the opponent has little to no time to react after your attack, you may safely execute another attack. Executing a long combo successfully will deal massive amount of damage to an opponent, giving you a huge advantage in the bout.
Using animation frame data from Super Street Fighter 2 Turbo, we will create a Prolog ruleset for finding available combos for a given character. We will also allow Prolog to find combos that fit for a given context, such as when an opponent misses an attack (allowing for more frames to safely execute our first attack) or otherwise used a move with very long recovery animation. Our queries will also give us control for how "safe" we want our combos, such as a perfectly safe combo with zero frames for an opponent to react, or relaxing the condition to allow small openings as a tradeoff for higher damaging combos.
What did we learn from doing this?
Due to time constraints, the scope of the knowledge base was limited to moves from a single character, Ryu, and limited to ground-based moves only. We found success in this scope, and were able to produce viable movestrings under different game states. We believe implementing a full (if perhaps naive) AI in Prolog is feasible, but likely more time consuming and complex than we first thought due to the breadth of nuances.
The program could easily be expanded to allow for multiple characters, rather than a single one. The knowledge base would grow of course, but the same principles of combos can be applied to any character in Street Fighter 2. One new detail we would need to implement, however, is assigning moves to specific characters and expanding the game state to include which characters are in a bout.
Aerial combat is a more difficult implementation, because the frame data for aerial attacks behaves differently than ground attacks. In particular, most aerial moves do not have recovery frames. Rather, their frame data is handled by how character and when a character lands on the ground. There are also startup times for entering the air. Altogether, we would require additional rules for chaining between ground attacks and aerial attacks, and vice versa. We believe this is feasible to do in Prolog, however, and would require simply expanding upon existing predicates.
There are many other nuances to a fighting game, and building a better AI means incorporating more of these nuances into the interpretive model. Other factors not implemented, for instance, would include: at which frame does a move strike the opponent, whether the move can be blocked 'low' or 'standing', whether a combo will stun an opponent, and throws. Each of these elements require additional information to be incorporated into the game state as well as the details within moves and combos. However, their implementation is generally removed only by adding a single additional factor to the rules.
One drawback to using strictly Prolog, however, is the management of 'hitboxes'. Since Fighting games are very much a visually interactive medium, a character's sprite will behave differently between moves. All characters have a hitbox, and all attacks have an 'offensive hitbox', that determine whether an attack landed at all on an opponent. Some moves have high attack boxes, some low, and the size and shape of a character's hitbox changes depending on the character's state. Adding in such geometric detail to a single prolog program would be considerably inefficient as opposed to an object-oriented tracking program. In this sense, we believe tracking hitboxes in Prolog to be at the very least infeasible.
In conclusion, scripting a fighting game AI in Prolog is feasible, but there is progressive complexity in finding a complete model. Furthermore, a truly 'complete' AI would demand an element of computer vision over pure logical programming.