Talisman

Software Engineering in ML

Helen Lin Huang, Ross A. Knepper, Carla Sereny, Jonathan Wildstrom

Carnegie Mellon University

Advisor: Dr. Frank Pfenning

December 14, 1997

Introduction. The goal of the Talisman project was to implement the role-playing game Talisman in the programming language ML. Talisman, is a multiplayer game involving a board with many spaces, cards, monsters, spells and battles. A game of this size and complexity is a substantial software engineering task. We chose to implement the project using ML primarily due to the language's functional nature and strong typing system. We hypothesized that these features would be an effective aid to the implementation of our game. Along the way we went through several revisions of the overall structure of the game. However, we strove through the entire project to provide general solutions to specific problems.

Game Overview. Talisman is a fantasy role-playing board game played by 2-6 players. The basic elements of the game are the board, characters, adventure cards, purchase cards, and spell cards. There are eleven different characters, each with unique special abilities. Different types of cards are drawn as the game progresses. Some provide the bearer with new abilities, while others represent monsters and other challenges to be overcome. The goal is to get to the center square (The Wizard's Tower) and defeat the Dragon King.

Game Setup. To begin the game, each player draws a random character from the pack. He places his character's token at the marked starting space for that character. Many characters begin the game with certain weapons or other objects. All players start with four lives, one gold coin, and no experience. Additionally, each player has an initial strength and craft, which are used in battle. All of these scores may vary throughout the game.

Taking a Turn. The turns proceed in a clockwise progression around the table. At the beginning of a turn, a player rolls the die for movement, and may move that many spaces in any direction. He selects a new space and moves his character token there. Then the player encounters the space by reading the text printed there and following the directions. Many spaces instruct the player to draw an adventure card, but there are a number of unique special spaces as well. Once the space has been successfully encountered, the player must encounter any cards on the space in the order of their priority. Cards may have been drawn this turn, or may have been dropped earlier by a player. If at any time the character loses a life, their turn ends immediately. Otherwise, it is over when the player has successfully encountered the space and all cards on it.

Fighting a Battle. Some cards or spaces tell the character to go into battle. There are three different types of battles. When fighting a monster, a high strength is desirable. When fighting a spirit, craft is important. When fighting against another character, you may use either score. Once a battle has begun, there are three stages. In the pre-battle stage, the player may declare any special items or weapons he wishes to use during battle. Next, dice are rolled for both sides, and the rolls are added to their respective scores. The winner is the side with the higher net score. After rolling dice, the player may try to prevent loss of life due to a loss in battle by using Armor, etc. If the character still loses a life, his turn is then over.

Language Overview. SML (Standard Meta-Language) is a functional language with a strong typing system. This combination has a number of advantages over C/C++, LISP, and other languages. Being functional, the language can take advantage of efficient recursion to simplify both programming and execution. ML's pattern matching facilities further increase the clarity of the code. Of course, being a functional language means that ML programs generally have no state and more importantly, no side effects. This simplicity reduces debugging time dramatically. The type system of ML is another great advantage of the language. It uses compile-time type checking to prevent many of the errors that would go uncaught in LISP or other run-time type checking systems. ML is also much more strict about types of data. For instance, while polymorphic types permit a function which operates on a generic list to accept a list containing any type of data, all the elements must still be the same type. This restriction prevents many errors which can occur with more type-lenient languages. Another feature which makes ML different from many languages is that it treats functions just like any other type. You can dynamically create functions and pass them around freely. The language also supports references, though common practice discourages their use unless necessary. Finally, ML has an object system which supports masking (signatures) and inheritance of structures (functors). These attributes make ML an effective language in which to implement a large project.

Original Problem Decomposition. We started our project by sitting down before the semester started and playing a four player, four hour game of Talisman. This helped to get our minds focused on the problem at hand and how the game should be presented. The initial meetings that we had before the semester started and hence before our meetings started with our advisor, Dr. Frank Pfenning, were brainstorming sessions where we came up with the following ideas.

Initially, we realized that we would need data structures to represent a collection of spaces (a representation of the board), spaces, characters, cards, and spells. We also knew that we would need a code engine to run the whole game and a display structure. For displaying our game, we had talked about how it might be implemented as a text-based game, and that perhaps if we had time near the end of the semester, Talisman could be implemented as an X-windows-based game.

During the brainstorming sessions, we made bubble diagrams and lists of items that we thought would be needed within each data structure. We decided to begin by having our data structures be a straight representation of what was printed on the cards, spaces, and characters. For example, every adventure card has one of "Leave," "Keep," "Discard," or "Attack" in the lower left corner, as a result, we decided to have a member of the structure keep track of this text. We also tried to categorize certain items within a group; for example, grouping together spaces into categories such as "draw x cards," "roll one die," "action depends on character alignment," and "choice: roll one die or do something else." Other data structures that we sought to categorize were cards with the four categories of "Tower," "Adventure," "Spells," and "Purchase." Even the "Adventure" cards could be categorized into seven different types of "Adventure" cards.

We also discussed other issues such as what the responsibilities of the data structures are. We determined that each structure was responsible for some part of the game: cards were responsible for handling their own text (whether it be an attack or other result); Spaces handled all effects of the space (drawing cards), as well as handling attacks between characters, arranging the cards by priority, and causing the character to encounter the cards on the space; characters were responsible for rolling their movement and determining where they could move on the board, and interfacing with the user to determine where the character wanted to move.

In addition to members of the data structures that came directly from the game, we also included some auxiliary members. The character data structures included within itself such elements as a description, but it also included a variable indicating the current space the character is on, base values (strength, craft, originating space), and a turn function. The board data structures was to include within it a lookup by name function and a lookup distance/charges function. The lookup by name function would return a space when it was given a name of a space on the board. The lookup distance/charges function determined the spaces that could be moved to from a given space and the charges that might be incurred by certain paths of movement. The board data structures had to be arranged in a certain order to reflect the actual physical representation of the board. The space data structures was to have a list of characters that were currently on the space, a list of cards currently on the space, a gold counter, a startup function, and an "encounter" function where the space would perform its function of drawing a card from the deck, rolling a die and then performing the consequences, etc.

Having brainstormed what the responsibilities of each part were, we turned to designing signatures. We realized that since one of our intentions was to keep the game expandable, we should avoid generic flags wherever possible. For example, if we were to implement flags for certain spaces that did not affect a character, there would be no way to have other spaces not affect a different character without rewriting large blocks of code to add a new flag.

We had originally planned our data structures to be signatures and functors and to have our variables be references. This way, each individual card would be a instantiation of the card functor. Each functor would include a "Name" string reference, a "Description" string reference, and an "ID" integer reference, as well as members detailed above. Originally, we had planned to pass along entire structures needed for each function (an instantiation of card, for instance). We implemented types and datatypes for specific data structures as needed. The following was used to restrict the character's alignment to only valid choices:

datatype AlignmentType = Good | Neutral | Evil

We decided that we should split cards and spells into separate functors. The rationale behind this was that cards had many parts that spells did not (an action, the possibility of fighting, the need to be used, as well as encountered, etc.) As a result, we decided that the card functors should include an encounter function and a use function (encounter was called when the card was on the space, use was called when the character wanted to use the card). Spells only had the use function.

Included in each functor was a display function and an init function that would initialize the data structure, since we were working with references; we needed to initialize the data structures. We wrote a signature, GAME, that was an implementation of the engine, which was never fully discussed in the brainstorming sessions. The GAME signature included multiple references to lists: regions (we had decided to break the board representation into three regions; each region would keep a list of spaces); characters who were playing; dead characters; unused characters; cards that could be drawn; discarded cards; purchase cards; spells; and discarded spells. The signature also included 3 functions: a shuffle function that would shuffle the lists; an initialization function; and a Main function that would be the main engine of our program.

After our first code review and meeting with Dr. Pfenning, we discussed the signatures and structures we had written. We learned that records would be more practical as data structures. We had not realized that, because signatures and functors did not work like classes in C++, different instantiations of them were completely different. Additionally, we could not have lists of structures, only of variables. So within the next few weeks, we changed our data structures to be records. After changing from signatures/functors to records, we found that we no longer needed "init" functions in every data structure. At this point, we discussed the possibility of writing compilers that would take text files and then convert them into usable ML code. However, we all decided that getting the engine and other data structures working was a higher priority, and the compilers could wait until other parts worked.

We also had problems with circularity. For example, the character records needed the space records (where the character was located), however the space records needed the character records. Because one of the two had to be loaded in first, we had to eliminate the references within one to the other. We ended up fixing the circularity problem by making all references to data structures be integers where the integers were unique identification numbers for each card, spell, character, space, etc. instead of lists of records (the actual data structures themselves).

Design Decisions. After deciding on the initial data structures, we began to code some preliminary cards, characters, and spaces in to verify that our records were complete and able to handle some cards without difficulty. After implementing some very simple cards and spaces, as well as a basic character (without any special abilities), we sat down to hold a meeting to discuss what other things were needed in the records. At this meeting, we went through a complete list of all cards, spaces, and characters in the game to see if they could be implemented using the records we had designed. At this meeting, we decided on many fundamental changes to our implementation of the game. Among these changes was the introduction of a structure (Lookup) that allowed us to find a card, space, character, or spell by ID number, and a Main structure that realized the game player (Engine) in our original design. We decided that we needed Lookup because we had to be able to reference all cards in the game by ID, and we had no way to find a given card. After implementing Lookup and part of Main and adding more cards and characters, as well as all the spaces (partially implemented), we sat down to another meeting, this time to discuss the remaining details we had not yet begun to implement (e.g. Character-Character fighting, Spells, Winning the game, Death). At this meeting, we decided on most of the major changes to the structures and records in the game.

In designing and implementing the Main structure, we made many changes from our original design. We had initially had the idea of a very minimalist Main (it was only supposed to call the init functions and then start the first character). As we discussed the high-level design, we determined that Main should actually handle all the actual running of the game. Main was designed to not rely on the characters to take their own turns or for the spaces to handle the cards on them. Instead, Main cycled through the characters (using tail recursion) allowing them to roll the die for themselves, but doing the actual interfacing with the user itself. It also allowed the spaces to draw their own cards, but ordered the cards and encountered them itself. This was done because we realized that the movement functions for the characters and the card encountering functions for the spaces were identical, and it made more sense to consolidate them in the Main engine.

One major change that came out of the first meeting was the introduction of several helper structures that allowed for accessing and changing records. These structures, SCard, SChar, SGame, and SSpace, included functions for adding and removing counters from cards, increasing or decreasing statistics of a character, adding cards to any record, drawing cards, etc. These functions are purely helper functions; they prevent constantly having to refer to individual parts of the record by allowing just the item to be changed to be passed in, all the breaking up and reconstructing the record was handled inside the structure. However, in order to allow the changes to be made more permanent, we added functionality to the Lookup structure.

The Lookup structure includes 4 major parts. First of all, it uses 4 global arrays to refer to characters, cards, spaces, and spells. These arrays are indexed by ID. The Lookup structure also allows the addition of cards, characters, spells, and spaces to these arrays. These functions looked into the record to get the ID of the object to be added and placed it in the correct slot of the array. We decided to use arrays for 2 reasons: they have the functionality to lookup an element by index built in, and they are a form of reference in ML, making them more permanent than lists. The addition functions were only intended to be called once for any given object, when the object was created. There were also Get and Set functions. The Get functions took an ID and returned a copy of the object associated with that ID and that array. The Set Functions took an ID and an object and set the array to contain that new object. This allowed us to reference everything by ID instead of passing entire records into functions.

In designing the parts of SGame that involved drawing cards, we decided that reshuffling the deck should be handled inside the function. In order to facilitate this, we wrote a Shuffle structure. However, since all "decks" are maintained as lists, and non-linear access to lists is difficult, we used a pair of functions to convert the list to an array and back. Since non-linear access to an array is easy, we implemented shuffling as a simple swap of a given position with a randomly generated one. In order to do this, we implemented a random number generator (structure Random) which uses large numbers and modulo arithmetic to give pseudo-random numbers.

The last major implementation change involved fighting monsters (see Figure 1 for the final structure of our implementation). Previously, fighting had been handled as a function of the cards (the cards encounter function). However, the rules of Talisman require that fighting enemies be done simultaneously. To achieve this end, we created a structure called a Sponster (short for Spirit/Monster). A "sponster" is created whenever a battle takes place, whether it be between the character and a card or the character and an enemy generated by the space or another card. We also needed to implement a Fight structure that handled all the details of fighting multiple enemies simultaneously.

Having made some general, high-level changes to the implementation of the game, we had to make the same changes in the records (Pre-/Post-battle lists, permission functions). We also added new fields, both data and functions, to the records to accomplish new goals. While many of the fields remained unused, they are in place to continue the project.

First of all, we modified the cards. We changed the use function to make it consistent with the idea of a sponster (i.e., "Use" had to be able to return a sponster, but also had to be able to function consistently with the old implementation). We also added a "Drop" function (as yet unused). When implemented, this function will be used to clean up any bonuses (or penalties) given to the character by an object or follower. Next, we added 4 special declarations to the WhenUse type (which tells us when an object can be used): Weapon, Headgear, Armor, and Shield. These declarations keep the character from using 2 helmets, weapons, etc. simultaneously and gaining the benefits from both. The Pile field was also added to keep track of whether the given card was an Adventure card or a Purchase card, and if it is a Purchase card, to keep track of its value. Finally, we added a Counter field to the card, for the cards that accumulate counters. This field keeps track of what type of counters and how many are on the card (for purpose of this field, cards and spells were considered counters, and instead of a number, the field kept track of which cards or spells were associated with the card).

Next, we changed the character record. In addition to adding the pre- and post-battle functions, we added pre-move, pre-turn, post-move, and post-turn lists. These keep track of general things that must happen at the beginning of the turn, after the roll, after the character moves, and after the turn ends (e.g., the blizzard has a function in the pre-turn list that will remove a function from the move roll list to allow the character to roll again). The "Roll" lists were another set of lists added to the character. These lists handle rolls for movement, fighting, and other rolls and deal with the special character-dependent cases (characters that get extra rolls, etc.) as well as adding any modifications (e.g., Jester, Horse). We also added two functions (as yet unimplemented): DoToMe and CastSpell; these handle checking if a card can be used by a character (if DoToMe returns false, we cannot use the given object on the character; CastSpell is similar). We also added StrMod and CraftMod fields. These fields were used to differentiate between strength and craft that was part of the character and strength and craft given to the character by objects or followers. Additionally, we modified the NotAffected lists to have booleans associated with the data. The boolean merely states whether or not the character has the option to ignore the space or the card. Finally, we added an Init function (which handles giving the character any items at the beginning of the game) and removed the Turn function (since the Main structure was handling turns).

Finally, we modified the space records. For the spaces, we first eliminated the MoveAcross function, as in our brainstorming session, we could not see when it would be useful. Next we modified the Encounter function to return a boolean stating whether or not the character's turn was over (if the character lost a turn in the Forest, for example). Finally, we added a RiverList field. The RiverList field is a list of integers denoting what space is across the river which separates the inner and outer regions. This list is used by cards that move the character across the river (e.g., the Ferryman).

There was one final change we made simultaneously with these changes. We had initially planned to have some form of a user interface (either text- or XWindows-based). To help with this interface, we designed a Display structure. This structure had two primary functions: 1) displaying information to the user, through Print, and 2) prompting the user for input, through Prompt and YNPrompt (YNPrompt is a special case of Prompt which asks for a Yes/No answer) At any given prompt, the user has 3 default options in addition to any passed in to the prompt function: The user can quit, get information on the current character, or print information on any object in the game. While we currently only have a text-based interface on one screen, we hope to implement a somewhat XWindows-based interface at some point in the future.

Analysis of Language Choice. Over the course of the project, we found that the functionality of the ML language proved to be both challenging and resourceful. At the start, the choice of language seemed poor, because the members of the group were accustomed to thinking in an imperative, object-oriented style and thus had difficulty adjusting to and taking advantage of ML's inherent features. However, once we surmounted the initial hurdles, the language provided us with the methods to implement the more complicated aspects of the game as well as the means to handle the broad spectrum of the task at hand through the use of its modularity.

One of the foremost difficulties that we had to begin with was the fact that most group members had not worked with the ML language for some time. Furthermore, the majority of the team was more familiar with C/C++ and therefore we often found that our brainstorming and design ideas had to be re-arranged to work with our current language of choice. A number of times, we found ourselves doing more work than was necessary, because we were failing to take advantage of the features innate to ML. For example, by failing to put our datatypes into structures, we ran into the problem of having to come up with alternate names for elements that were common to many datatypes, such as "CARD". Had we utilized the feature of inheritance of structures, we would have not run into such a problem.

The properties of the ML language impacted our research in many positive ways. Its strong type-checking aided us in cutting our debugging time, because it didn't allow for careless errors or mistakes to go by unnoticed. Furthermore, due to the fact that each piece of data had to conform to a certain type, we were forced as a group to think ahead of time to be certain that we would handle all cases when defining a particular portion of data. This was especially true when we were trying to code the more specialized cases of the cards, characters, and spaces. Another property of the language that we were able to use to code the trickier, more exceptional parts of the game was the fact that functions could be treated just as any other data type. More specifically, this allowed us to code the special abilities of the characters; we were able to code properties intrinsic to only certain characters through the means of lists of functions that had value to all of the characters.

However, some features of the ML language were not as useful to us. For instance, ML's lack of state was, at times, more hindering than supportive. Although it clearly made the debugging process easier, because there were no side effects to deal with that so often make life difficult in an imperative language, it also had a tendency to make coding somewhat exasperating. In almost every function that we wrote, we were forced to pass in and return the Game record so that we could preserve some semblance of state within the "current" version of the Game record. This frustration could have been alleviated, to some extent, had we taken more advantage of references within ML. Another negative aspect of the ML language with respect to our project was the fact that certain pieces of code could have been much more elegantly written had they been coded in an imperative language. For instance, the steps involved in taking a turn are inherently a linear sequence of events; thus, it was very clumsy to code them within the constraints of the ML language, which is innately recursive. We managed to maneuver around this and similar procedural events through the use of lengthy "let" statements, which simulated a linear procession of steps.

Despite any problems that we had with the language, we were able to successfully code a basic version of the game of Talisman. We utilized the features of the ML language to come up with solutions to many of the more difficult aspects of the game. In addition, ML's modularity allowed us to organize the game into succinct building blocks and thus aided us in thinking about the higher level design.

Analysis of the Group's Work. At first, the group had a bit of trouble getting started on the project; there was a general sense of what we needed to accomplish, but more time was spent discussing how to break up the game into reasonable parts than deciding on how to actually implement the project. To be fair, many of the meetings we had in which we talked about ways to assemble the various aspects of game play were useful, in that members of the group became more familiar with the game. Our slow start was due to several factors, including: problems regarding how to approach certain aspects of game play, difficulties deciding which team members should be assigned to which parts of the coding, as well as a general sense of being overwhelmed by the task at hand.

Nevertheless, once we began the coding process and started creating the basic building blocks of the game the group's resolve improved. This was largely in part to our advisor's assignment of deadlines, which allowed us to focus as a group and not be distracted by the numerous arguments we had regarding minute aspects of game play. For instance, there were times when an hour of a meeting would go by and there would be no consensus among the team members regarding an unclear detail of game play. By impelling us to concentrate on how to code the general game play, our advisor caused us to get underway on the project and produce a working version of the game.

Another major difficulty the group encountered had to do with code modification. We discovered that if a person changed a portion of the code, it sometimes "broke" the game until another person could make his changes. In other words, even though we each had control over a particular portion of the code, each individual piece was tied very closely to other pieces and thus significantly changing one part would have a domino effect on the other parts. This problem was solved through the introduction of CVS (Concurrent Versions System), which allowed us to synchronize changes to the game without disturbing what each team member was working on.

Conclusion. The team did manage to write a basic version of the game of Talisman in the language of ML and come up with the design specifications for most aspects of game play that we did not finish coding. Thus, we realized our original hypothesis, which stated: we believe that ML, with its strong type system and advanced module system, is a better language for the implementation of many computer games than is C.

Nevertheless, while ML was certainly a reasonable choice for the programming assignment we laid out for ourselves, it is not certain that ML was necessarily better than C with respect to the individuals involved in the implementation of the project. In many ways, this was due to the fact that the members of the group were not familiar with thinking about coding using ML as an outline on which to base design decisions. It is clear, however, that as the semester progressed and the group members refreshed themselves with the intricacies of the language, the task got somewhat easier and solutions to particular problems were not as difficult to solve. To illustrate, during one team meeting towards the end of the semester we were able to come up with answers to many of the more difficult programming tasks, such as the difficulty of sending a character on a quest upon visiting "The Warlock's Cave".

Regardless of any difficulties encountered along the way, it is certain that the features inherent to ML had a large role in our being able to implement a working version of the game as well as to design the complete game. Although it is clear that the game of Talisman could have been implemented in an imperative language, the functionality of ML was a key factor in how we approached the design and implementation of the game. In conclusion, we feel that the benefits inherent to ML outweighed any problems we encountered along the way.

The Talisman group would like to thank the following people for their good thoughts and good deeds on our behalf:

Dr. Frank Pfenning, our advisor, for his willingness to take the time to help us learn.
Games Workshop, for Talisman, and permission to work on it.
The Small Undergraduate Research Grant program, for their generous grant.
Daniel Singhal, for support since the beginning.
Mark Stehlik, for being ever supportive and helpful.

For more information about the project or the game, including source code, card texts, and progress updates, please see our web page.


Figure 1. Overview of game implementation structure.