In this paper it is shown an application of an agent-oriented programming paradigm with a reasoning layer based on a logic programming. The presented solution was used to build bots in Counter-Strike video game. The software architecture for new bots has been presented and bene ts were discussed. This article does not discusses all the work in detail, but provides more general idea about research, which was done.
Counter-Strike (CS) is First Person Shooter game (FPS). Characteristic of this game genere is observation of a game world from rst person perspective (see. 1) [?].
Counter-Strike is a very popular video game, which is meant to be played exclusively in a multiplayer mode. In each game, players are divided into 2 teams - terrorists (TT) and counter-terrorist (CT). Both teams ght against each other using modern rearms. Each game lasts 30 minutes by default and consists of several 5 minute rounds. There are several map types which a ect goals for both teams.
AS assasination. One of CT's becomes VIP, which must reach the safe zone.
TT's try to eliminate the VIP.
CS hostage rescue. CT's try to move hostages to rescue zone.
DE bomb defusion. TT's try to plant a bomb, CT's may try to defuse it afterwards.
ES escape. TT's try to ee to the escape zone, CT's hunt them.
If team is successful in achieving its goal, then the team wins the round. Elimination of the entire opposing team usually also means a victory.
The gameplay of Coutner-Strike is very realistic, eliminated players do not respawn immediately as in most FPS multiplayer games and each player can be eliminated with only few well-aimed bullets. Therefore, Counter-Strike is a very team-oriented game, where cooperation is more important than skills of individuals players. Players do often form groups called clans, who play together against other clans. There are even organized tournaments in Counter-Strike. The game has rank of o cial sport in some countries [?].
Unfortunately, the game in its early versions was completely unplayable for a single player, because it was meant to be played entirely in multiplayer mode. Community of the game fans developed game extensions, which contained computer-controlled players - bots [?]. CS Bots creators had di cult problem to solve, because developed bots had to act as team and co-operate.
In this article it has been show extension of existing bot, using foundations of multiagent systems. Note that, concept of application agent-oriented programming in FPS video games is not a new one e.g [?], [?], [?]. However, there are di erent implementations of this concept leading to di erent bot architectures. One of the approaches to bot programming based on this concept is providing scripting language e.g [?], [?], so that it is easy to experiment with various behaviors, bot interactions and tactics. This approach relies on expert knowledge, which is merged into script or program source code. Completely di erent approach is to involve machine learning and let bots gain knowledge through interaction with other players. There is already some research in this area [?], [?], [?]. Due to complex nature of the problem ML techniques do not solve it entirely, but serve as support for techniques involving domain knowledge about game. In this work expert knowledge based approach is applied. One of the knowledge representations could be rst order logic. This representation is declarative, thus readable to human. This was main motivation for choosing Prolog as scripting language. Presented AI bots component is divided into main 2 layers: { reasoning layer - high-level decision making, corresponds to human declarative knowledge, { execution layer - low-level decision making, corresponds to human procedural knowledge. A similar approach could be found in autonomous robot programming, e.g in Robocup competition [?] [?]. 2 2.1
Let consider game environment state g at some moment xed in time t as set facts. Let F denote whole universe of possible facts. So that g(t) 2 P (F). Each agent bi 2 B has knowledge at any point of time about some subset of those facts. De ne
K : B
P (F) ! P (F) as knowledge operator. In this model internal states of bot agents could be fact pi which satisfy following necessary condition fact pi known to all bots satisfy following condition 9!bi 2 B
pi 2 K(bi; st) 8bi 2 B
pi 2 K(bi; st) Time passed from beginning of the round could be example of such fact. At each timepoint any of n bots bi can make decision di 2 D and next game state is dependent of all decisions made by bots. This transition is handeled by game enviornment, which could be described as a function Ge.
Ge : P (F)
D |
D
: : : {z n
D ! P (F) } Al : B
P (F) ! D fsuccess; fail; continueg | } action{zstatus Therefore low-level action is function and high-level reasoning is a function
Ah : B
P (F) ! f
Al |{z} current low level action
F |{z} motivation for action (Al | action }
{z continuation
F)? g [ f?g Let cont denote function returning continuation for given low level action and motiv function returning motivation for given low level action. Utilization of motivations is inspired by the BDI [?] architecture. Agent has exactly one high level reasoning function rh 2 Ah agent is also equipped in re ex reasoning function rr 2 Ah. Purpose of re ex reasoning function is to provide means of reacting quickly to environment changes. Agent can execute one action at the time t, but executed action could change. This changes satisfy following conditions: at+1 >>>>at <
c1 8 >>rr(K(bi; g(t))) if rr(K(bi; g(t))) 6= ?
if at(K(bi; g(t))) = (d; continue) >>>rh(K(bi; g(t))) if at(K(bi; g(t))) = (d; fail) > > >:rh(K(bi; g(t))) if :motiv(at) 2 g(t) cont(at)= if at(K(bi; g(t))) = (d; success) ^ (c1;:::;cn) These conditions aren't mutually exclusive, if con ict occurs rst satis ed condition is chosen. 2.2
Prolog is a general-purpose declarative programming language, which bases strongly on a rst order logic. Prolog uses notions of facts and rules, whereas execution of Prolog program is de facto a formal reasoning process. Therefore, it is very convenient to use in arti cial intelligence programming [?].
Often many types of logic could be used as underlying Prolog logic, e.g. fuzzy logic [?], modal logic [?], multivalued logic [?]. Those di erent types of logic are used to express reasoning process in way understandable to human and all of those languages are Turing complete.
Prolog displays following properties, which make it useful in multiagent programming.
{ declarative reasoning rules, { bots knowledgebase in a symbolic form - easy to understand and analyze, { no separation between code and data - rules could be used as data, e.g. bot leader communicating orders to another bot. 2.3
Counter-Strike gameplay is a simulated environment and bots can be seen as agents within this environment. They show typical traits of agents: { autonomy, { making intelligent decisions, { being mobile, { communication and collaboration.
CS emphasises the teamwork strongly, whereas collaborative problem solving is a main domain of multiagent systems. So using this paradigm is natural in this task. It's interesting that this methodology was even earlier used in noncollaborative games like Quake with good results [?].
Actions Al are implemented as hardcoded, but yet parametrizable, behaviors which can be acted by bots. Such behaviors may include going to a navigational point, climbing a ladder, aiming a sniper ri e, etc. Action is description which decision at each time point does bot make.
The decision layer rh is responsible for selecting proper actions in order to achieve bots goals. The decision layer could have di erent implementations e.g. behavioral networks [?], decision trees, neural networks [?], nite state machines [?] etc. In some cases decision layer could alone be decomposed into several components e.g. predictive planning, team communication, tactical navigation.
If decision layer forces bot to execute an action while it is already executing one. The old action is paused and may be resumed if new action completes. 2.4
Counter-Strike is a mod of Half-Life, while CS bots are modi cation of the mod. Counter-Strike itself is not an open-source software, however it has documented ABI1, so modi cations can be created as dynamically linked libraries. Those libraries are injected into running a game and the API hooking technique is used. In this work, existing open-source bots, called E[POD] 2 were modi ed as proof-of-concept of bots programmable in Prolog. SWI-Prolog [?] was chosen as the Prolog interpreter, because it was e cient and easy to integrate into the bots code. Whole solution was programmed in Visual C++ with help of the Boost library3. E[POD] bots was programmed in object-oriented way and it already provided some objects which acted as low-level actions, however reasoning layer was programmed as FSM. In this research low-level actions were reused and reasoning layer was replaced.
SWI-Prolog o ers two options of C++ and Prolog integration: 1. C++ to Prolog - code in C++ runs an instance of a Prolog interpreter and may run queries against it. 2. Prolog to C++ - there could be created library of Prolog predicates which execute natively and return its results into Prolog interpreter.
Second approach is typical for development of performance-demanding libraries, which are used by Prolog later. First approach is typical for solutions, where Prolog is treated as logic engine in an application. In the bots both of these integration types where used.
The Counter-Strike engine provides routines for checking bot sensors like eld of view, hearing, navigational map etc. Some of those routines were exposed into Prolog by means of native predicates. In rst versions of this work bots queried Prolog engine to get the answer which actions should be executed. The code for creating an action to be executed was moved into Prolog. Rationale behind such decision was to increase a programming exibility and code reuse. A decision to change current action can be made as result of not only logical reasoning, but also e.g. re ex or communication which are also handled by Prolog. Following
2 http://epodbot.bots-united.com/ 3 http://www.boost.org/ enhancements were introduced to E[POD] bots. It will be described how formal model, presented in section 2.1, was implemented.
Motivations Motivation can be associated with each action. A motivation is a logical expression. The action is executed as long as motivation is evaluated to truth value. The motivation can be constructed by SLD-resolution mechanism. Such solution improved bot control by Prolog scripts, because script could also interrupt native action execution. Introduction of this technique improved the separation between C++ code and Prolog scripts, because script creator does not have to know detailed speci cation of any particular action.
Example of a motivation: a c t i o n k i l l (
BotID , EnemyID , and ( b o t a l i v e ( Enemy ) , d a n g e r l o w ( Bot ) ) ) .
This action will make bot with identi er BotID try killing the bot with identi er EnemyID as long as enemy is alive and bot is not in danger. Continuations Continuations are form of simple planning and de ning complex behaviors consisting of sequence of several low-level actions. There could be assigned a continuation to any action. A continuation is a logical term which is executed after action is successfully completed. The result of executing continuation could be new action to be executed by a bot. The new action could have its own motivation and continuation.
For example: a c t i o n g o t o ( BotID , Wp, a l l c o s t , andThen ( a c t i o n h o s t a g e s (B , andThen (
X ) ) ) ) , a f t e r f r e e h o s t a g e s (X ) .
This action will make a bot with identi er BotID go to a waypoint with identi er Wp. The motivation for this action is the term allcost, which is always evaluated to truth. After reaching the waypoint bot will try to free the hostages. The action for freeing the hostages has also continuation, which is obtained by SLD-resolution and uni cation of variable X.
Re ex reasoning The reasoning mechanism is a deliberative process and it is computationally expensive. It runs occasionally. Bot agents also express reactive behaviors rr to respond for rapid changes in game environment, like bot being attacked by opposing team.
Prolog script has several predicates for handling signals send directly by the game environment. Those predicates have short SLD-resolution tree in order not to impede bot performance. The predicates may cause same e ect as regular reasoning process.
Communication Communication mechanism of E[POD] bots relayed on radio messages which was feature of CS itself. Such messages are simple imperative statements, e.g: Taking re, need assistance!, Follow me, Team fall back!.
Receiving such message is handled by the re ex reasoning.
Improved teamwork One additional task was added to set of existing bot tasks written in C++. The purpose of this modi cation was to enhance team tactics. All bots in one team were divided into smaller groups. Each group has its own leader, who can make tactical decisions. Other bots executing additional action was blindly obeying his decisions, with some exceptions for re ex reasoning.
This behavior was introduced, because teamwork of original E[POD] bots was more random chance than reasonable decision - bots were acting on their own grouping only occasionally. 2.5
Example reasoning process has been shown in gure 3.
In presented example decision is made, if agent should buy new weapon. Bot should buy it, if new round has started and it is respawning, because he has only a basic pistol. In presented example those conditions aren't meet and bot checks, if he is close to the buy zone and can a ord to have better weapon than he is carrying at the moment. In this case logical formula is satis ed and bot decides to buy new weapon. If buy zone is far away it may have been wiser to play with actual weapon.
In the example in gure 4 there has been presented goal selection. Navigational points can represent goals for bot. Each navigational point has associated metadata e.g. if it is t for camping 4. This reasoning is carried out by team leaders. The leader choses the waypoint not chosen by any other leader. Depending on waypoint type valid tactic is chosen for execution. In presented example, there was chosen waypoint with hostages. The leader decides to move 4 tactic involving holding static strategic position of advantage to the hostage waypoint. This action can have it's continuation. There is an option that bot will wait near this waypoint for terrorists to come and ambush them. This action would have it's motivation - it would be executed as long as bot senses any danger e.g. hearing gun re or enemy footsteps. In presented example bot doesn't decide to execute this action, because it is chosen with some probability. He decides to head back to base with the liberated hostages, instead. 3
The goal of this research was to validate if it is feasible to run bots using described architecture and provide some basic formal description, which could be improved upon in course of further research. Some parts of original FSM decision layer was converted to Prolog reasoning script. Then the game was run with 32 bots - 16 for each team. Game was working with same framerate as original one, as most of the time game engine spends in idle state in order to synchronize inputs, networking, display and events in the game environment. Experiment lead to following conclusions: 1. C++ bot code can be rewritten to Prolog, 2. Prolog bots can be used e ciently.
More detailed performance information could be found on bar chart 5. The gure depicts percentage of total game CPU execution time taken by 3 di erent system components: Counter-Strike engine, bot library and Prolog reasoning layer (compare with gure 2).
Most of a bot logic was direct translation of hardcoded C++ decision-making code into Prolog script, so it was initially expected that bots wouldn`t play any di erent than the original ones. However, new action was introduced to enhance cooperative team tactics. For that reason, additional experiments were run to verify if new bots play di erent than the old ones. Experiments was carried out by setting several games with di erent parameters setup on de dust defusion map with additional action enabled for one of the teams. One parameter included sizes of groups within team which has team action enabled. Those experiments lead to conclusion that new action boosts performance of team. The optimum group consists of 3 bots including the leader. Larger group makes maneuvering task more di cult and bots tends to stuck in narrow spaces. It makes them also prone to HE grenades. Group of 2 bots does not improve gameplay that much, as it can be overpowered easier, than group of 3 bots.
Unintended, but very positive outcome was ability to test reasoning layer independently of the game engine which was very complex system. During development of Prolog scripts standard Prolog test suites were created in order to carry out regression tests. Test were easy to create because it was easy to create a mock of game engine, which wasn't started during tests at all. The game engine injected to Prolog native predicates in order Prolog script was able to interact with it. In test scenarios instead predicates created by the game engine regular Prolog predicates were declared and linked with script execution environment. Usage of this test suite allowed to reduce amount of errors leading to divergencies in expected script behavior and declared one. Improving such testing suite framework may allow to incorporate test driven development methodology (see generally [?]) into bots AI development. 4
In future system will be expanded to more complete solution in order to cover more complex interactions between bots and provide rules for handling all CS map types. Also it is planned to change reasoning mechanism to one that supports basic properties of a default logic [?]. The 4QL language [?] is considered as a reasonable option. The default logic would allow to de ne hierarchical reasoning system in consistent way. E.g 1. general describing CS game rules and general facts, e.g
{ if you are attacked shoot back 2. more speci c rules describing rules speci c to game type, e.g { on AS maps T's aren't allowed to buy AWP5 ri e 3. exceptions to the rules and special rules for concrete map
{ on cs assault prefer SG552 than AWP 4. rules speci c to bot
{ if you courage is low always buy bulletproof vest before buying weapon
Such solution would allow construct modular reasoning architecture. The most speci c rules and facts associated with map would be replaceable. Even if there were no rules associated with map, bots would still be able to play using general rules, but they would omit some knowledge speci c to concrete map. So such map-speci c rules exist to optimize bot performance on given map.
Another part of research where more improvements are going to be done is formal description of bot decision making and collaboration - at the current stage there are few discrepancies between formal description and actually implemented solution.
At some point bots were enhanced to communicate using Prolog, e.g bots could exchange messages in form of logical formulas and then deliberate. This idea was implemented, but not used. However it was not abandoned completely, because it could be developed later. 5
We would like to thank my mentor prof. Jaroslaw Arabas for advices provided while writing this article.