Constructing a viable army for Warhammer Fantasy Battle is a very complicated problem that entrails choosing between many races, many di erent units and equipment. In many ways, the construction of a viable army is a constraint satisfaction problem. There are many hard constraints based on the game mechanics and many soft constraints, such as the number of miniatures available, the capabilities of the enemy and the style of playing; and the fact that any choice made in uences all the other choices possible. The work presented here presents an initial case-based reasoning implementation in jColibri for construction armies in the Warhammer domain.
Constructing a good army for Warhammer Fantasy Battle (WHFB) is a very complicated constraint satisfaction problem. Choosing a successful army is naturally not the only requirement for actually winning a battle; mastery of that army and tactics are obviously also important. As warhammer includes dices and di erent strengths and weaknesses of the troops some level of probability and statistics do play a role. However, a clever general can easily shame the math. The rst step is showing up with a viable army. Choosing an army has many constraint, not only what is legal. Constraints might include available miniatures, tactical consideration, properties of the opponent, or playing style, such as infantry heavy, fondness of cavalry, or being partial to artillery or magic.
The work presented here is a decision support system for constructing viable armies that the player can bring to the table by applies case-based reasoning (CBR). That is, the decision support system is only involved in constructing the roster all actual game playing is in the hands on the player. The application developed uses the relevant domain knowledge from the game together with cases describing actual battle fought to suggest an army to a player, using his preferences and constraints. Applying CBR takes the army constructing problem beyond probabilities and statistics, which are used solely in (commercial) available solutions. We argue that applying a lazy learner instead of rule induction captures the many di erent constraints that can occur.
The rest of the paper is organise as follow: Section 2 gives a short introduction to the Warhammer Fantasy Battle game mechanics; Section 3 gives a short overview of related work on CBR and constraint satisfaction problems; Section 4 shortly describes the domain model used; Section 5 describes how the four steps in case-based reasoning is used, in particular how similarity is calculated; Section 6 shortly describes the use of jColibri; Section 7 describes the evaluation; Finally, the paper ends with a summary and outlook on future work. 2
Warhammer Fantasy Battle is a turn-based miniature gure board game, where each player leads an army to battle against another player There are 15 di erent races to choose from and each race have many di erent units that can be used. The game is played using miniatures made by plastic or pewter on a 25mm scale and each units sits upon a square or rectangular base.
Strict rules govern the game play and army creation process. On the battleeld the individual units strength and abilities are matched against the opponent, and in conjunction with the lay of the land and the roll of the dice determine the winner. This essentially mean that the same two armies can do battle several times and the results will most likely be di erent each time.
Each of the 15 di erent races have a host of di erent units that can be bought and added to the players collection; additionally one unit may have di erent equipment from another unit of the same race and type. Classi cation determines what type of unit it is, and is divided into many categories, such as: infantry, monsters, cavalry and war machines.
Additionally some units are either a lord or a hero, these are powerful units which leads the army to war. They are not separated in their own classi cation, but can belong to any classi cation (usually infantry with the ability to purchase a mount). Lords are the most powerful unit in an army, with fearsome martialor magical might. Heroes are lesser in might than lords, but still worth a score of ordinary warriors.
Characteristics describe all the aspects of a unit through nine associated attributes. Each attribute have a numeric value in the range from 0 to 10, all these attributes are uniquely described in a table for each unit and associated classi cation. Attributes includes: how many attacks a unit has, how fast it can move, how courageous they are and how much damage they can sustain. Table 1 exempli es the di erence between a dwarf lord and a dragon (higher is normally better). Each individual unit have a base cost associated with it, this cost represents how good the unit is. As the player adds better equipment, e.g.: weapons and armour to the unit, the cost increases.
When preparing for a battle the two players determine the total army points for each player to be used during the game. Common values are between 1000 and 4000, where 2500 point is the de facto standard. To create the army the player selects the units she wants to use for the battle while using as many points possible, but still under the total allowed points. As it is di cult to use exactly all the points, both armies are usually of a di erent value, but as close to the limit as possible.
There are however a few rules that must be followed when creating the army, you cannot choose ten of the meanest unit there is and be done with it. The player should rst select a General, which represents the player and leads the army on the battle eld. The rest of the army is selected based on rules governing the following unit categories: Lords, Heroes, Core Units, Special Units and Rare Units. All equipments and/or mounts purchased to individual units or groups, counts towards the total point usage within each category (see Table 2).
Lords and heroes are powerful leaders of armies, thus only 25 % of the agreed upon points can be spend on each. Core units are the basic units of your army and the ones you will have the most o , e.g.: basic footmen and cavalry. You must use a minimum of 25 % of the army points on core units. Special units are elite troops which perform great on their own or, as motivators for lesser soldiers. You can spend as much as 50 % of the points on these units. Rare units are very powerful units, e.g. monsters, weird war machines and elite solders of unsurpassed skill. You can use up to 25 % of the points on these units. 3
At the time of writing the authors are not aware of any research applying casebased reasoning to army build in Warhammer, or in any other strategy game. However, the problem of constructing a viable army is not disjoint from any other research area. In many ways, this problem resembles a constraint satisfaction problem (CSP). There are di erent constraints on the number of di erent type of units that can be used (see Table 2) and the di erent ways of building each unit (e.g. equipment and special troop types). All of these constraints must be satis ed, whilst still building an army that can beat the opponent.
I can be argued that the adaptation phase in case-based reasoning resembles
a constraint satisfaction problem in general, and dynamic constraints satisfaction
in particular [
Others have investigated the use of case-based reasoning as the main tool for
solving constraints. This includes manufacturing, where for loading autoclaves
[
The approach presented here draws inspiration from applying case-based reasoning to constraint satisfaction problems. However, contrary to most related work we do not include speci c CSP solvers. 4
The domain model developed consists of two parts: the o cial rules for warhammer, both the core rules and the speci c rules for the races; and date from real battles fought and recorded by Trondheim Warhammer Club (WarTrond). The data from the o cial rules constitutes the general domain knowledge, whereas the data from WarTrond constitutes the cases.
The domain model was developed through three iterations of modelling, implementation and testing. After the three iterations the domain model was nalised. The nal entity-relationship model is depicted in Figure 1.
The main information about the cases are stored in Cases and Armies, which together represent the player race, opponent race, outcome, player unit and points. Each of the armies in the case contains a number of units described in Unit. This class is modelled based on the general characteristics of a unit, such as attacks, movement and weapon skill, as well as the information about the unit
OpponentRace Outcome
ArmyPoints
Army_Unit_Utility Army_unit_ID Untility_ID
Army_Unit Army_ID Unit_name NumberOfUnits Army_Unit_Equipment Army_Unit_ID Equiptment_ID Name Cost Required NumUnits PromotionUnit Movement WeaponSkill BallisticSkill Strength Toughness Wounds Initiative Attack Leadership UnitType
Equiptment Name Cost Range Modifier UsableBy ItemType DefaultEQ
Unit_Utility Army_Unit_ID Equiptment_ID
Unit_Equiptment Unit_name Equiptment_Name
Unit_Rule Unit_name SpecialRule_ID Rule SpecialRules
Equiptment_Rules Equiptment_ID SpecialRule_ID type, such as minimum and maximum number of troops and weapon type. The Unit Rules and Special Rules, which contains any special rules for the unit, the information about the unit is complete. The nal information about unit is their equipment, which is contained in Equipment. Together these classes contain all relevant information about units. The UtilityUnit class is used to inform the program that this is attached to another unit, such as war machine crew. 5
Following the domain model described in Section 4, queries to the case base must at least contain features describing which race the player wishes to use, the opponents race and the number of points. Whilst this is su cient to retrieve suitable cases more speci c information will restrict the number of cases and give the similarity function more to work with; thereby (hopefully) enhance the result. There are no restrictions on the number of constraints used.
The case-based reasoning component follows the four steps in the CBR cycle
as described in [
The case base contains all valid cases following the domain model in Section 4. The similarity is calculated using k-nearest neighbour. This approach was chosen as it quickly can distinguish between cases.
The similarity is calculated based on a weighted sum of the three parameters: army, opponent and outcome. Equation 1 calculates the weighted average of the three parameters, where A = 'Army', AW = 'Army Weighted', O = 'Opponent', OW = 'Opponent weighted', Ou = 'outcome', and OuW = 'Outcome Weighted'.
Similarity =
P A
AW + O OW + Ou P AW + OW + OuW
OuW (1)
Each of the components in the above equation has their own simple similarity function tailor made to the speci c part of the case. 5.2
The reuse phase in this implementation consists of two steps: rst a retrieved case is passed through a nave and secondly it may be passed through a more exhaustive adaptation. The nave adaptation is used to substitute data in the query with data from the retrieved case.
Once the nave adaptation phase is done the exhaustive adaptation process is started. This process may perform adaptation of the case. This adaptation investigates the query case to see if any of the army construction rules (see Section 2) has been violated, such as "no general", "too few core unit points", or "too many units in group".
The adaptation phase uses its own similarity function when calculating unit similarity. It simply calculates the di erence between the parameters describing each unit (characteristics, unit type, army type, cost and weapon type). The characteristics are calculated as the average of the similarity of the nine individual characteristics. The cost is calculated as an interval similarity. The unit type, army type and weapon type is calculated from look-up tables where the similarity between di erent the di erent types has been estimated. For unit type, e.g. two infantry units has the similarity of 1.0, monstrous beasts and monstrous infantry as the similarity of 0.8, and cavalry and war machines are not similar.
At the end of these two adaptation phases the query case now contains the most similar retrieved case along with any adaptation necessary to t the original requirements from the user. 5.3
The revise phase in Mymidia is a completely manual task for the user. The user is able to change almost any aspect of the case. There are two types of limitations on the possibilities of revision: limitation and invalidators. The former is changes that the user interface cannot change, yet if changed would not invalidate the results; whereas the latter is the player race and army points, which would invalidate the result.
Once the user is satis ed with the the case in question and wants to test it in a battle the case is stored in the case-base in a case vault. This initial stored case in the vault cannot be accessed by the retrieve phase. The retain phase is a pseudo manual phase, where the user must add the result of a battle for case. Based on this result the following actions can be carried out: { If the case results in a victory or a draw that value is updated in the case base. This moves the case from the vault to the normal case base, thus making it accessible to the retrieve phase. { If the case results in a defeat that case is deleted.
{ Finally, if the result remains unknown the case remains in the vault. 6
The system was implemented in Java using the jColibri framework together with the Apache Derby database and Hibernation mapping tool. This section will shortly describe how jColibri was used in the implementation. The details on Apache Derby and Hibernation is outside the scope of this paper.
jColibri is a CBR framework that is fully implemented in Java. It includes
several out-of-the-box features and interfaces that allows developers to create
new functionality or tweak existing functionality. jColibri is easy to set up and
integrate into a project. JColibri also supports a wide range of databases through
Hibernate. Ontologies can be included through OntoBridge, which simpli es the
use of ontologies to create knowledge intensive CBR application [
Through the use of interfaces in all core components of jColibri any
application speci c class can easily and seamlessly integrate into and used in conjunction
with out-of-the-box features. The similarity calculation is divided into local and
global similarity functions [
The changes to jColibri in Myrmidia is primarily related to the local and global similarity functionality (see Section 5) and the distinction between the problem description, solution and justi cation of the case. In our implementation this distinction has been left out as there are no distinction between the problem description and the solution. This has been done for the following reasons: 1. It was di cult to categorise the features as either being a description or a solution; 2. As it was di cult to categorise the features the most cost e cient solution with respect to minimise number of code lines was to have the problem description and solution in the same case hierarchy; 3. It felt restrictive and impairing on the functionality and the users' possibilities to de ne the perfect query. 7
Since only a limited number of races has been modelled and the number of cases is limited, a thorough performance test is di cult to conduct. However, each of the components and functions have been tested one their own. 7.1
In order to maximise to unit similarity calculations (see Section 5.2) and adaptation matching results the associated weights for unit similarity can be set accordingly. This test was conducted by calculating two relatively dissimilar units, within the same race, with every possible weight con guration. The result of these calculations were not very surprising since the calculations is based on di erent features of the unit. Once the "best" weights were found they were used to calculate the similarity between one unit and all the others within a race. The results were then evaluated as either satisfactory or not and the ration between these two were calculated. The results showed that one universal unit similarity weight con guration is di cult, if not impossible to nd. This is based on the observation that what is "good" from some units are far from accurate for others. 7.2
The case adaptation stage is quite a complex function with several random elements. This makes it unpredictable and di cult to control. To verify that neither random elements or rule set veri cation was involved a specialised test was conducted. This specialised test posted a static query to the system that returned ve cases and sent each case through the adaptation 10 000 times, totalling 50 000 trials.
The results of theses tests indicated that in cases that required much adaptation (e.g. cases with few army points begin used as the basis for cases with many army points) are prone to add the same unit several times. This is clearly a result of searching for the most similar unit several times. This type of unit a nity impacts the diversity of the army and may impair the overall e ectiveness of an army. This is an open question and requires real gaming tests to clarify.
Another issue that arose is the fact that lords and heroes uses more that the allowed 25 % of points. Theses o ending lords and heroes have a tendency to loose all their extra equipment. Thus, it is clear that this part of the adaptation requires some redesign. 7.3
An interesting side e ect of this application is the ability to create a new army from scratch by basing it on an existing army from another race. This functionality was developed to act in the event that one or more of the kNN results are of another race than the target race. This occur if: there are no cases with the target race available; the existing case is less similar that other cases with a di erent race; or if k is larger than the number of cases with the target race.
Table 3 shows an example of a user asking for a Dwarf army to play High Elves. However, there are no Dwarf cases in the case base, so an existing High Elf case is adapted to suit the queried race. If the resulting army is investigated by a domain expert the Dwarf units substituting the High Elves units would appear reasonably, within reason and keeping in mind that substitutions are based on actual armies. The only notable di erence is that "Teclis", "Caradryan" and "Korhil", who are all named characters1 are substituted with run-of-the-mill Dwarf lords and heroes. 8
The work presented here is very much work in progress. Currently only three of the 15 di erent races are actually modelled in the domain model (Dwarfs, Empire and High Elves); further, not all race speci c magical items has been modelled; nally, none of the recent published 8th edition race books has been modelled, only the 8th edition core rules. In addition, the current case-based only contains 10 cases (2 Empire, 5 High Elves and 3 Dwarf). Obviously this is a very incomplete set of cases (105 cases would be required to cover all combinations). However, the cases re ects the current and actual available domain knowledge.
There are still quite a few points where future work is required: i ) improve the knowledge in the case-base; ii ) improve the adaptation process in order to reduce the number of needed operations, perhaps by looking at the possibility of using a CSP solver as described in Section 3; iii ) Implement a partly automated 1 Named characters are special lords and heroes who often have extra special abilities compared to standard lords and heroes. revise process; iv ) make the system available as a web-based solutions, thereby ease the acquisition of cases and domain knowledge.
The authors would like to that WarTrond |Trondheim Warhammer Club| for their time and e ort providing us the initial data for the case base.