Tuesday, October 8, 2013

A Concept Dependency Graph Analysis of Dominion

Just five years ago, Rio Grande Games published Donald Vaccarino's deck-building card game, Dominion, and it took the designer game world by storm. In short order, it seemed that every publisher was riffing on this new mechanic, and now, deck-building is an established game mechanism in any designer's toolbox. I include Dominion on my list of recommended games in my game design course because of its popularity and its influence in game design: this game provides the metric by which other deck-building games are judged.

Three recent situations inspired me to look at Dominion more critically—particularly, how one learns, teaches, and conceptualizes the game.

First, one of my game design students wrote a critical analysis of Dominion, and a significant portion of her analysis was based on the opinion that the rulebook was unclear. Specifically, she and her opponent were unable to determine when they were to discard their cards and draw new ones. I was surprised at this, in part because I had a student last year who upheld the same rulebook as a pillar of clarity. It may be worth noting that last year's student self-identifies as a "gamer," whereas this year's student had never heard of Dominion prior to taking my course. In any case, this was not the result I expected.

Second, I was recently with a group of friends who were teaching Dominion to a new player. They began by explaining actions and the chaining of actions and the strategic importance of this tactic, but before they had even taken any cards out of the box. This struck me as a particularly awkward way to introduce the game, since concepts such as "you're building your own deck" were not yet discussed, and it clearly was not resonating with the new player. In fact, his questions revealed that despite several minutes of accurate rule explanation, he had not built a coherent mental model of the game. This suggests to me that it wasn't a problem of accuracy, but of scaffolding—that is, giving the right information at the right time for the learner to advance.

Third, I was retelling the stories above to my lovely wife, and I explained that I thought it was important to focus on core gameplay when teaching a game. I justified that you cannot make sense out of peripheral game design elements without understanding the core, and therefore you should teach games from the core outward. She pointed out to me that sometimes she gets confused when I explain games this way because I don't give enough "big picture." Touché.

This got me thinking about the relationship between core gameplay and learning, and more specifically, how the dependencies among game concepts might reveal effective means for teaching the game. While many designers talk about "core gameplay," there is not consensus on where one draws the line around what is "core" and what is not. I decided to try mapping out the concepts required to play a game of Dominion as well as the dependencies among them, and this is what I came up with:

Concept dependency graph for Dominion.
This is a concept dependency graph, where the nodes represent gameplay concepts and the edges represent dependencies. That is, given AB, one needs to understand concept B in order to understand concept A. I will refer to terminal nodes with no dependencies as atomic concepts. I am only considering the original Dominion game—no expansions—and only those kingdom cards recommended for new players. I also omitted concepts that were not relevant to gameplay, such as the use of randomizers or the determination of starting player.

The graph was drawn using dot, part of the graphviz project. Dot generates layered graphs (that is, each node is in a discrete layer) and follows automatic graph drawing heuristics such as minimizing crossings, minimizing edge length, and maintaining aspect ratio. A quick look at the graph shows a potential "core" of the game emerging from the atomic concept "Each player has their own cards."

Concept dependency graph, detail of potential "core"
If someone had never played a deck-building game before, I think this sets up a compelling description: it's a game in which you have your own deck of cards from which you draw a hand, then you play actions and buy new cards from stacks on the table, and you cycle your discard pile back into your deck when it is exhausted. There's no mention here of what those actions actually are, or the "cleanup" phase, or even victory condition, but I think it's fair to argue that these aren't part of the core gameplay. Keep in mind that "core gameplay" is not rigorously defined; one could just as well argue that the victory condition should be in the core, and be justified. That is, I'm not saying that this is right, but that it satisfices.

The concept dependency graph has three atomic concepts: each player has their own cards; there are stacks of cards in the center of the table; and there is a trash pile. Of these, the last is almost certainly not part of the core gameplay: it's an design element that permits a small number of kingdom cards to permanently remove cards from a game. Like the numerous Dominion expansion, it is a design element that permits the introduction of more action variations. It is interesting that the computer-optimized drawing of this graph put the trash pile atomic concept on the periphery of the drawing, where as the fact that there are stacks of cards ends up "wrapped" within other dependencies.

Choosing only the ten basic kingdom cards allowed me to ignore Curse cards in my concept dependency graph. However, Moat is included in this set, and it required adding several concepts and dependencies. Without Moat, it doesn't matter that Militia is an Attack card, and so that concept could be elided. Moat is a Reaction, and so that requires an explanation. Moat is also the only card in the set that has two different actions on it, from which the player must choose one; in all other cases, the player does everything on the card when it is played. This provides some justification for not including Moat as a beginner card, despite its gameplay utility in foiling Militia. It would be an interesting study to compare beginners' ability to learn the game with and without Moat to see if there was any significant difference.

It is noteworthy that the "ABC" concepts—that your turn comprises Action, Buy, and Cleanup—are relatively deep in the graph. You cannot really make sense of ABC unless you know what Action, Buy, and Cleanup mean. However, my experience shows that it still provides a memorable peg on which to hang your hat when teaching the game. That is, I propose that the mnemonic is there because these are not atomic concepts. Similarly, the atomic concepts manifest in directly observable configurations: without knowing anything about how the game is played, one can see that players have their own cards (based on players' handling them and placing them in easy reach), you can see stacks on the table, and there is a single "Trash" card among these stacks.

I knew I wanted a hierarchical drawing of the graph because I was looking explicitly for layers of concepts. I was curious, however, as to whether a force-directed drawing would yield any further insight. The result of running the graph through neato is given below. There's no new insight to be had from this visualization, at least not as relates to finding a potential core gameplay.

Force-directed drawing of the concept dependency graph
The concept dependency graph provided an interesting tool for analyzing Dominion, particularly with respect to the search for core gameplay. I am curious as to whether this tool can be used on other existing games to similarly fruitful ends or whether this is a coincidence. What I have shared here is the third major version of my concept dependency graph for Dominion: the previous versions did not induce any visual "core", but they also contained what I considered to be mistakes in the concept and dependency articulation.

This project has made me wonder whether other graph formalisms might reveal new insights into game design. A propositional network, for example, permits separate reasoning about cards and the having of cards. I did a bit of work with SNePS in graduate school, and it might be a useful tool to deploy here. I know that Machinations presents a formal language for representing game design elements, but I know relatively little about it; it may provide some insight into the learnability of games and core gameplay as well. I am curious to hear from anyone who has tried either tool toward these ends.

If you find any other uses for this formalism in studying game design and learning, or if you know of any related work in the literature, please leave a note in the comments. Thanks for reading!

Tuesday, October 1, 2013

Two-Week Project Showcase

The focus of my sophomore-level Advanced Programming course (CS222) is a large project at the end of the semester. In the past, this has been a six-week project, delivered in two three-week iterations. It is a project of the students' own invention: they have to pitch a project to satisfy a set of constraints I provide. This semester, I decided to expand the project to nine weeks with three iterations. This goes hand-in-glove with the revised, achievement-oriented assessment model that I am using this semester.

Most students have never worked in a programming team prior to CS222, much less defined their own projects. To warm them up, I give a two-week programming project before starting the big project. The two-week project is done in pairs, and I provide the requirements analysis as user stories. This provides a model for them to follow when they pitch their own projects using user stories.

This semester, I gave a new two-week project that was inspired by my 2013 Global Game Jam project. The students were challenged to write an application that takes a word from the user and then hits Wikipedia's API to determine the last modified date of the corresponding page. The curriculum provides no prior exposure to Web programming or networking, and so I provided a very short sample program that demonstrated how to open a URL in Java and read the stream. This project touches on some very important ideas, including Web services and structured data.

In the past, I have evaluated the two-week project in a rather conventional way: I provide a grading rubric at the start of the project, then I check out students' projects from the department's Mercurial server and give each pair a grade. I wanted to do it differently this semester, in part because of the achievement-oriented assessment. The two-week project provides a vehicle for students to earn achievements and write reflections: I'm not evaluating the project itself but rather how students use it to explore course concepts as articulated through the achievements and essential questions.

I decided to devote a class day at the end of the two-week project to a showcase. Each pair had to have a machine running a demo alongside a summary poster. We rearranged the classroom, moving all the tables to the perimeter and clustering the extras in the center. In order to foster peer interaction, I printed some sheets whereby students could vote on which team had the best UI, the best poster design, the cleanest code, and the most robust input handling.

The students enjoyed this format. There was an energy in the room as the students explored each others' solutions, talking about implementation strategies and UI decisions. A few students had trouble getting their projects working at all, and I heard one student say how disappointed he was, because it left his team unable to fully participate in the activity. This represents positive peer pressure and project orientation, which can be starkly contrasted against instructor pressure and grading-orientation.

I had recommended two strategies in class: using Joda Time to handle time formatting and using Java's DOM parser to deal with Wikipedia's output. I was surprised to see that almost every team used Joda Time (and used it to earn the Third Party Librarian achievement) but only one team used DOM. Every other team read the output stream as a single string and then searched it using Java's String class. This provided an excellent opportunity to teach about input validation. My sample Wikipedia URL queried the "soup" page for its last modified time, and the result looks like this:

<?xml version="1.0"?>
    <revisions rvcontinue="574699285" />
    <revisions xml:space="preserve">Action 'rollback' is not allowed for the current user</revisions>
      <n from="soup" to="Soup" />
      <page pageid="19651298" ns="0" title="Soup">
      <rev timestamp="2013-09-27T05:20:10Z" />

Keep in mind that this is coming in as one continuous stream without linebreaks. Aside from the one group that did an appropriate and simple DOM lookup, students used String#indexOf(String) to search for "timestamp=", and then did manual string parsing using that reference point. This approach works for most cases, but it opens the application up to an attack that I'll explain in the next paragraph, giving the reflective reader a moment to consider it.

If you ask the application for the last modified info of the Wikipedia page "timestamp=", you get a phenomenon similar to an SQL injection attack: the indexOf operation picks up an unintended location, and the manual string manipulations fail. I had seen this when meeting with a pair the previous week who were working on their Advice Seeker achievement. They had thought their solution to be rock solid, and they were appropriately excited when I showed them how to crash it. They became my covert hitmen during the showcase, crashing solution after solution by finding holes in string parsing logic. So, while few students took the opportunity to learn XML parsing in the two-week project, maybe they learned something even better: the embarrassment of doing it the lazy way and seeing your system go down in public!

When I explained to the students what were doing at the showcase, I had expected teams to show up at their stations when I came by. However, it seems they were so excited to see each others' work that they didn't think about this. Since not every team had a person at their station when I came around, I was not able to give my expert evaluation to each group, nor was I able to model for the students how to give critical feedback. On the other hand, the students got a lot of peer feedback and I was able to meld into the group, becoming just one of many people interested in seeing demonstrations and code. I am not yet sure if I would do this part differently next time or not.

One aspect that is still unclear to me is the extent to which students were working for intrinsic motivation versus extrinsic reward. I was approached after class by a student from one of the teams whose solution was not working. During the hour, they had talked to other students and realized what they did wrong, which is an activity I certainly want to foster. The student asked, clearly in a state of agitation, if his group could fix their application even though it was due to be completed the previous night. I confirmed that this would be fine, and the student went away expressing joy and thanksgiving. I suspect his perspective was that he had just been given an opportunity to save his grade. What I really gave him was an opportunity to make his project work and feel good about getting it done, even if a bit late. I don't think he realized that there's no entry in the course grading policy for the two-week project, that the whole thing was just a fun context for us all to play and learn together. I hope that when he figures this out, he sees this as a reflective learning opportunity and not simply smoke and mirrors.

In conclusion, I am very happy with the showcase format. It was definitely worth using a class meeting for this event. I think this two-week project was particularly well-suited to the showcase format since it's fairly small, permits multiple solutions, helps students build better understandings of the modern computing ecosystem, and can have interesting failure states. Perhaps next time around I need to add an achievement related to XML parsing, since this seemed to promote students' use of Joda Time quite well.

(I have some nice pictures of the showcase that I took while standing on top of the teaching station, but I feel like I can't post them here without my students' permission. Sorry.)