On Philosophy in Computer Science

Recent events have given me the opportunity to spend some time with a colleague at the university from another department. He told me how, many years ago, he met a developer who told him about Linux, and it was the first time he realized that Computer Science involved philosophy. Really, how else would someone from outside the discipline know? 

The discussions involved making a distinction between two ways of looking at Computer Science. I identified myself as being in the "human-centric" camp, and a respected colleague identified himself as being in a "math-centric" camp. I believe that the distinction I made was between human-centric and technical- or formalist-centric. Interestingly, when he later recounted the distinction, he described me as "anti-math" and him as "math". That, itself, demonstrates an interesting sort of Manichean reasoning seen from his philosophy: that either you're for math or against it. I responded that I was not anti-math, but human-centric, and that one can do math in a human-centric way. This was a sort of distraction from the main purpose of our meeting, and predictably, the conversation did not go anywhere except to clearly establish that there are different ways of looking at the discipline.

As I have thought more about this, I think there's a clearer way to make a distinction between these philosophies. One of them sees mathematical formalisms as an ends in themselves: the math is beautiful, and you should study it and admire its beauty. Another perspective is to look at them as a means to an end: the math is a tool that allows us to do things we could not do without it. These have very different implications for curriculum design, which in large part is the most important thing that CS computer science departments have to do collectively.

It is import to note that most of the formalists that I know will also claim that the mathematical formalisms empower you: they are not just beautiful, but also useful. Indeed, the inciting incident of the conversation was a claim that studying algorithms helps you write more efficient, more effective, and more correct programs. This claim is ubiquitous in discussions of academic computer science, and yet I have never seen any evidence for it. Indeed, the educational theory that I know suggests that it is not true. Transfer is hard and is never free, so to suggest that studying one thing makes you magically better at a different thing is specious at best. Studying algorithms makes you better at algorithms, but if your goal is to get someone to be an efficient, effective, and correct programmer, you're much better off teaching them Test-Driven Development, Pair Programming, intellectual humility, and a love of lifetime learning. When I took this issue to Facebook, one of my alumni put it best: the most likely case is that there is a correlation between being a good programmer and being good at algorithms because both are difficult and can serve as a measure of intelligence and conscientiousness. That is, correlation is not causation. 

This is crucial when deciding, for example, where to place discrete mathematics, algorithms, and computational theory in a curriculum. I know many math-trained computer science faculty who claim that you cannot understand data structures unless you study discrete math first, but that claim is easily refuted by counterexample: we have plenty of students who drop and retake discrete math and yet have no problems with CS2. To steelman the opposition for a moment, it could be that the problem is that our courses do not draw enough upon their prerequisites, and indeed, I think that's a good point. We—collectively, as a discipline—have not distinguished clearly between what exactly we want students to know coming out of a three or four credit-hour discrete math course and how exactly it manifests in the follow-up courses. We are locked into a "course" model of higher education, where ideas come in neat, delineated packages, taught by people who focus on those areas or, in some cases, focus on no areas. A lot of faculty get uncomfortable at the very mention of shaking this up.

A few years ago, when our Foundations Curriculum Committee tried to look into the question of what elements of discrete math were needed for courses that listed it as a prerequisite, the answers we got were completely inactionable, being either "They need all of it" or "They don't need any of it." Indeed, I have led that committee for something like twelve years, and we have been constantly fighting against problems of how to improve the discrete math and algorithms courses, in large part because the people who teach those courses see nothing wrong with them.

The old joke goes like this: ask five computer scientists to explain computer science and you get seven different answers. I would like to know if other academic departments have this kind of culture war. Are mathematics departments hobbled by differences about whether math is a means or an end? How about physics? Biology? What about non-science fields such as Architecture, which I think some of us see as closer kin than mathematics.

I make the case when I teach CS222 that Computer Science is applied philosophy. While anybody can use computers, we are in the amazing position to be able to imagine worlds and then make them real. This is what drew me to the field. To be clear, I loved my Computational Theory course in grad school, but at the same time, I'm a melancholic introvert who loves ideas. I also loved reading The Design of Everyday Things, and I think it helped me much more in my day-to-day scholarly work than Godel, Escher, Bach. 

I think it would be interesting to try to measure the distribution of different philosophies among Computer Science faculty. It would be a challenge to develop a reliable and valid instrument for measuring such a thing. I know people at big schools and at small schools, and I'm not sure that the distribution of philosophies would be that different. I suspect you would find a greater concentration of human-centric computing at schools with a longer tradition of HCI research, and at places like Georgia Tech, where the media computing approach was born. That is, I suspect a human-centric approach to computing may be able to be grown.

Naturally, we need productive disagreements, but I think my field is hamstrung by a preponderance of activity on the formalist side. I have been on many search committees now, so I have some sense of what freshly-minted PhDs look like—or at least the ones who apply here. Most tend to have gentle words about student-centered teaching, but it is less common to find those whose scholarship is integrated. Of course, I don't think my work was integrated with my scholarly self either when I was fresh out of graduate school. But, if we continue to reward isolation and scientism, we will miss out on the opportunity to help scholars develop a real philosophy. I consider myself fortunate to have ended up, whether by chance or by grace, at a place that valued my interests in exploring a Boyer-inspired view of scholarship. Indeed, sometimes I wonder where I would be today if I had not taken the time to read Boyer and Glassick around 2007-2008.

How does this relate to Linux? Understanding the Free Software movement requires an integration of technical and non-technical aspects of computer science, in alignment with an understanding of economics and ethics. There's a lot of room under this umbrella, and it's not just applied math.

A formal proof that placing the Kingdomino castle in an interior cardinal position necessitates holes in the kingdom

The Problem

One of my family's favorite games is Kingdomino. This 2017 Spiel des Jahres winner is a tile-laying game in which each player builds a kingdom, scoring points for clever placement of similar terrain pieces. As of this writing, I have logged 57 plays of this game, making it one of my most played games. We especially like it with the Age of Giants expansion. The game accomplishes the admirable goal that my five-year-old and I can both enjoy it at our own levels. The strategy is interesting, there's an appropriate level of risk-taking, and it's not so cutthroat that a friendly player won't point out a good move to an inexperienced one.

Each player starts with a square castle piece and draws a 2x1 tile each turn. The tile must be placed adjacent to the initial castle or adjacent to another tile such that at least one terrain edge matches. If you cannot play your tile, you discard it. Your kingdom must fit in a 5x5 grid, and there are only enough turns in the game that, if you are never forced to discard a tile, you will exactly fill the 5x5 space.

Sample ending board with castle in the middle
(Image by sethOn on BoardGameGeek)

It does not have to be the case that your castle is in the middle of the 5x5 grid, although in the base game there is a bonus for this. Depending on what tiles you draw and what combinations you seek, the castle can end up in any position.

After playing the game a few times, we noticed that sometimes players would be forced to have 1x1 "holes" in their kingdoms. That is, we encountered situations where the 2x1 tiles were not covering the 5x5 space. For a long time, we chalked this up to bad play. We believed there must have been some decision made previously that left the player with the necessity for this hole.

The more we played, though, the more we wondered whether the placement of the castle within the 5x5 grid determined whether there had to be a hole. That is, was it less a matter of "bad placement" and more a mathematical necessity based on the position of the castle. I do not remember now who among us first thought of this nor whether it was noticing a pattern or intuition. Once we brought it up, though, we did some post-game experimentation. Sure enough, our experiments seemed to show us that if the castle ended up in one of the interior cardinal positions, you would end up with a hole you could not fill with a 2x1 tile.

Doomed Castle Positions

We took this as a kind of folk wisdom, but my Computer Science sense was tingling. Experimental evidence that these were doomed positions is one thing, but could I write a proof that these positions inevitably led to holes?

I let this sit on the back burner for some time. I have not written a formal proof since writing my dissertation, since that's just not the kind of Computer Science I do. I wrote a ton of them in graduate school, and I remember the general ideas but not many of the specific techniques. It feels to me that we're dealing with a kind of parity problem, that the Kingdomino problem should map to another, more conveniently solved problem. That's a very Computer Science Grad School perspective, by the way: show that your problem can be transformed into an easier problem, and solve that one instead. The lack of inspiration for a similar problem meant that I didn't make any headway on this problem at all. That is, until this morning.

Even though I had not thought of an elegant mathematical solution to the problem, it struck me last night that I could probably approach the problem via proof by contradiction. This one always felt to me like a sort of cudgel, but it works: assume the thing you want to prove false is true, demonstrate that it leads inexorably to an impossible situation, and conclude that it must be true instead. I sat down this morning with a handful of tiles and made my case.

The Proof

Let's assume for the sake of the proof that if we start with our castle in one of the interior cardinal positions (C2, B3, D3, or C4, as shown above as Doomed Castle Positions) that there exists a tiling that produces a full 5x5 kingdom. 

We can assume without loss of generality that the castle starts in position C4. Every other case is symmetric to this one, and for our purposes, starting in any other position is irrelevant. Keep in mind, of course, that at the time you start the game, the castle is not actually fixed in any cell of the grid: it is the placement of the tiles that determine where in the grid the castle ends up. Still, these are the only cases that are relevant to the claim, so we can take it as given.

Step 1: Castle at C4

The space C5 must be filled with a tile, and that tile must be placed horizontally. Assume without loss of generality that we place it over the spaces B5-C5. This covers any other case because of the symmetry of the board: covering C5-D5 would yield the same topology, mirrored.

For the sake of the proof, we will be ignoring the terrain types on the tiles. After all, our assumption is that there is a 5x5 tiling, and so we can assume the player has access to tiles that make these legal moves within the game. Similarly, the tiles could be played in different sequences, but they will yield the same result. Here, for example, the player could have played a piece at D3-D4 for example, but the fact remains that in order to make a complete tiling, they would have to play at C5, as in this step.

Step 2: Play at B5-C5

The space at A5 can only be covered by a tile that spans A4-A5, so that is our next move.

Step 3: Play at A4-A5

Similarly, B4 can only be covered by a tile covering B3-B4.

Step 4: Play at B3-B4

Continue this idea for the next several steps: play a piece into the most constrained position, where only one placement can satisfy the game rules.

Step 5: Play at A2-A3

Step 6: Play at A1-B1

Step 7: Play at B2-C2

Step 8: Play at C1-D1

Step 9: Play at E1-E2

That gives us enough plays to demonstrate the contradiction. There are now two clear positions that must be covered, but cannot both be covered: D2 and C3. Playing to cover D2 will cover D3, but then no tile can legally be played on C3. Playing to cover C3 will cover D3, but then no legal play can cover D2. 

Step 10: Impossible to Satisfy D2 and C3

We have a contradiction, which proves that our initial claim is false. That is, we claimed that there was a 5x5 tiling, but we have shown that it is not possible. Therefore, there is no possible 5x5 tiling of Kingdomino when the castle piece is in an interior cardinal position. Put another way, if your castle is in an interior cardinal position, you will necessarily have an unfilled hole in your final kingdom.

The Implications

One obvious implication of this is for the strategy of Kingdomino. If you desire a 5x5 tiling, ensure that your castle piece is not in one of the interior cardinal positions. Of course, the game is won by score, and so a savvy player might accept such a position if a tile placement yields adequate rewards, but at least this helps such a player fully understand the costs and benefits.

This proof technique still strikes me as inelegant because it doesn't tell us anything about any other board configuration. That is, if we wanted to show any other case, we would have to demonstrate it tediously in the same way. I suspect there are underlying mathematical principles at play here that I am just not seeing.

Thanks for checking this out. If you have some other insight into the topological qualities of the game, or if you have a story about how your own play group discovered this phenomenon, I'd love to hear about it in the comments.

The Update

After my initial post, I shared a link to this on BoardGameGeek's Kingdomino page. Those forums really are a great place to bounce ideas and inspiration around. Ori Artvalion (@SaltyHorse) posted some insights that lead to a much cleaner formulation. Here's a link directly to Ori's post, and I encourage you to check it out! Ori's observation suggests that there are other board positions that lead to a case as I describe above, just as I suspected but could not formalize. Also, that post pointed me toward the mutilated chessboard problem, which now I have a vague recollection of having encountered in grad school, but that was a lifetime ago.

Learning objectives for introductory game design: Continuing comparison against CS2013

I am giving a presentation in the Works-In-Progress session of the upcoming CCSC:Midwest conference. This short talk is connected to my post from April about mapping learning outcomes of game design to learning outcomes of Computer Science. Conversation on Facebook led me to understand that I had not fully explained my goals in that post, in large part because I had skipped the first part of the mapping: the learning objectives of introductory game design.

As far as I know, there is no standards body or recognized formal recommendations for game design curricula as there are with Computer Science, where we have the ACM/IEEE CS2013 curriculum recommendations. However, if you look at all the various introductory texts on game design, you will find significant overlap, although these are by their nature written along the lines of content rather than objectives. Each time I have taught game design as an Honors Colloquium or a Computer Science seminar, I have had to articulate the learning outcomes of the course; what I did this morning is reflect on this process in an attempt to pull out my current thoughts about what a student should learn from an introductory course. Here is my proposal:

After taking my introductory course in game design, a successful student will be able to:

• Apply common analytical tools to existing games, examples being MDA (Hunicke), Formal vs Dramatic elements (Fullerton), and Interactive Forms (Burgun).
• Identify positive and negative feedback loops in a game.
• Critically analyze existing games in order to understand their component parts and describe their interactions, including such components as rules, theme, and narrative
• Describe, apply, and justify iterative prototyping models to produce an original game.
• Describe and apply formal techniques of playtesting.
• Compose and present status reports.

I think this is a good number and granularity of items for how I like to introduce game design. Furthermore, having taught such courses for years, I think it's a good representation of the skills that students develop.

As I reflected on this list, though, I realized that there's another layer to the learning objectives. There are objectives that are implicit—objectives that are hiding in the cracks and in the details. Here's what I came up with as the shadow objectives:

A successful student will be able to

• Read, understand, and critique book chapters, essays, and articles on game design.
• Articulate specific, measurable design goals from ambiguous constraints and inspiration.
• Incorporate feedback to improve a prototype and reflect on that process.
• Incorporate feedback to improve analytical, compositional, and creative skills and reflect on that process.

The first one here is not to be overlooked. When I look at the design and goals of introductory computer science, learning how to read does not come up at all. I believe it also to be completely absent from CS2013. However, this is a crucial skill for someone who wants to be a lifetime learner.

The second is, perhaps, the most important skill that someone can learn in this class, and its transferable to any other creative domain. By "creative domain" here, I mean any that require creativity in the technical sense—the development of new ideas—so we can include all the sciences, engineering, and education along with the arts and humanities. More specifically, it is exactly this skill I want to see strengthened for nascent software developers and computer scientists: every day we have to manage ambiguity, transforming it into measurable goals and progress. Again, however, CS2013 has very little to say about this except for a couple of hours of requirements engineering. It may simply be a case that CS2013 is too deep into the weeds, but that's kind of my point: stepping back from the weeds, managing ambiguity and turning into concrete communications is something that a computer scientist does daily, but it's also something that is often ignored in curriculum and assessement, in my experience.

The third item is a clarification of the objective to apply playtesting techniques, but as above, there is something more potent here than just playtesting: it's about closing feedback loops to improve a product. Reflecting on this led me to compose the fourth bullet point, that it's not just about the feedback loops of the game but the feedback loops of the person. Maybe you might just call this "learning", yet I think there's not enough of this going on across our campus. For example, for a course to be considered a writing intensive course here has required that a student complete at least one draft-feedback-revise cycle. In my department, there are a few places where we practice this explicitly, and all of these are places that I have touched, which would not have this otherwise.

My next step in preparing for the presentation is to take this list, look back at my earlier post, and turn again to CS2013 to make sure that my points are clear. Right now, I have a feeling like the things I want to be emphasized by CS2013 are simply not in it at all, or at least not explicitly. It will be interesting to see the reactions of the generally-conventional conference attendees.

Questioning the value of CS2013

I recently had cause to re-read the ACM/IEEE CS2013 curriculum recommendations. This document is created by a large committee of content experts to provide guidance to Computer Science undergraduate programs. On one hand, it's a useful articulation of the body of knowledge that constitutes "Computer Science". On the other hand, well, let's take a closer look.

The CS2013 document breaks down Computer Science into knowledge areas such as Discrete Structures, Human-Computer Interaction, Operating Systems, and Software Engineering. Within the Software Engineering (SE) topic is a section called SE/Software Project Management. The section contains "2 core Tier2 hours", which means there are two recommended minimum contact hours on the topic, and they should be in a non-introductory course. For those who don't know the higher education jargon, "contact hours" means "students and faculty together in a formal meeting" such as a lecture. According to US financial aid legislation, and therefore according to practically every domestic institution of higher education, a student is expected to engage in two additional effort hours for each contact hour. For example, a student is expected to read, study, or work on homework for two hours for each one-hour lecture.

The core topics contained within SE/Software Project Management are as follows:

• Team participation
• Team processes including responsibilities for tasks, meeting structure, and work schedule
• Roles and responsibilities in a software team
• Team conflict resolution
• Risks associated with virtual teams (communication, perception, structure)
• Effort Estimation (at the personal level)
• Risk (cross reference IAS/Secure Software Engineering)
• The role of risk in the lifecycle
• Risk categories including security, safety, market, financial, technology, people, quality, structure and process

That's a lot of topics to cover in two hours of lecture and four hours of studying, but I could see it being all combined into a breakneck chapter of a Software Engineering textbook. Note that there are additional elective topics within SE/Software Project Management, but we won't consider those for this discussion.

Part of the ostensible value of CS2013 is that it doesn't just provide a topic list for each section of a knowledge area: it also provides learning outcomes. These are classified in a system inspired by Bloom's Taxonomy of the Cognitive Domain, so each outcome can be at the level of Familiarity, Usage, or Assessment. These are defined on page 34 of CS2013, and we can summarize them as basic awareness, ability to deploy knowledge concretely, and being able to consider from multiple viewpoints—as one would infer from the nomenclature. These, then, are the learning outcomes for SE/Software Project Management, as listed on page 177 of CS2013:

1. Discuss common behaviors that contribute to the effective functioning of a team. [Familiarity] 
2. Create and follow an agenda for a team meeting. [Usage]
3. Identify and justify necessary roles in a software development team. [Usage]
4. Understand the sources, hazards, and potential benefits of team conflict. [Usage]
5. Apply a conflict resolution strategy in a team setting. [Usage]
6. Use an ad hoc method to estimate software development effort (e.g., time) and compare to actual effort required. [Usage]
7. List several examples of software risks. [Familiarity]
8. Describe the impact of risk in a software development lifecycle. [Familiarity]
9. Describe different categories of risk in software systems. [Familiarity]

It's pretty clear to me that it's impossible to meet those nine objectives in two contact hours and four out-of-class work hours. Even if we assume that each student is perfectly capable of independent learning and studying, the time required to make any meaningful knowledge about these items is certainly greater than the recommended hours. I recognize that I am making assertions here and not arguments. In an earlier draft of this post, I tried a more rigorous argument, but I realized that a true skeptic could always counterclaim that they could meet these goals within the timeline. The real difference would not be the time required but our mutually exclusive definition of what it means to meet a learning objective.

It seems to me, then, that there are only two ways this could be approved by a committee. The first is that the committee has no functional understanding of contemporary learning theory. If that were the case, then why should anyone take their recommendations for curricula seriously? The second option is negligence, that the committee as a whole knew better, but they did not verify whether their recommendations and the learning objectives actually align. If that's the case, then why should anyone take their recommendations seriously?

On Measurement in Computer Science

In a chance encounter last semester, I befriended an undergraduate honors student who was not involved in any of my courses. She has become enamored of the notion of measurement—what it is and what it means. She asked me to contribute an essay on measurement in Computer Science for a collection that will become her honors thesis. It was an honor to be asked, and although I had plenty of inspiration, I found the actual writing to be difficult. After a few discarded drafts, I decided to focus on the paradox of the measurable and the unmeasurable within Computer Science, while trying to stay apart from political debate (we need more Computer Scientists!) or research loggerheads (agile vs waterfall). Without further ado, this is the final draft I sent to her yesterday, although I wonder if I may tweak it a bit before she publishes it.

The discrete and formal measurements of Computer Science reflect its foundations in mathematics and electrical engineering. Computer programs are composed of unambiguously parsed statements and expressions, which are compiled into atomic hardware directives. Information is transmitted over networks by measuring electronic pulses and radio waves, interpreting these as bits and bytes. Computational theory tells us that all computable problems belong to a single space-time hierarchy and that some problems cannot be computed at all. This leads us to the biggest question of Computer Science—the question of whether P=NP—which is fascinating not only because we do not know the answer, but because we also do not know if it is answerable.

These discretely measurable aspects of the discipline complement a more humanistic side. Creativity and ingenuity are required in determining what line of code to write, what proof technique to use, or what software architecture to follow. First attempts almost always fail, and so we learn to approach problems iteratively, using formal and informal heuristics to determine whether we are moving closer to a desirable solution. That is, we recognize that doing Computer Science is a learning process, that building a system is the process of learning how to build the system. Unlike in engineering and architecture, where models are built for others to manufacture, the computer scientist deals directly with the elements that compose the artifact. This creates a rapid feedback loop for the reflective practitioner, giving rise to the model of expert computer scientist as master craftsman.

Building any nontrivial software system requires a multidisciplinary collaboration, where the tools of the Computer Scientist are combined with approaches from the social sciences, humanities, and the arts. Research consistently shows that teams with strong communication practices produce better results; how to actually conduct these measurements is a perennial research question. Martin Fowler—a recognized industry leader software development—has gone so far as to claim that productivity cannot be measured at all, and that any attempted measurements will only produce misinformation.

My own scholarship involves building original educational video games with multidisciplinary teams of undergraduates. When interviewed about what most contributed to their successes, teams inevitably split their answers between the measurable and the non-measurable. They find that formal processes and communication patterns, quantitative feedback, and technical structure give them the confidence to build and revise complex software systems. At the same time, they recognize that empathy has the most dramatic effect on both team productivity and the quality of the product. These two sides, the scientific and the humanistic, are not opposed to each other: they form a synergy that can propel a team to success or, in their absence, drag a team to a near standstill.

This harmonious balance of the measurable and the unmeasurable characterizes Computer Science. Alistair Cockburn captures this paradox in his cooperative game principle in which he defines software development as a cooperative game of invention and communication. Both kinds of moves are necessary for the team to create a solution of value to stakeholders and, thereby, to win the game. A winning team must make measurable and unmeasurable moves, creating technical and artistic artifacts while continuing to build empathy, all the while reflecting on how they are learning through this process.

Computer Science: It's not just for dead women

How ironic that today is Ada Lovelace Day, as I just took a picture of her out of a Computer Science Department display case this morning.

Since I came to Ball State, we had a display case that showed four images of women in computing. I did not snap a picture of the display case, but here are the four individual images.

On one hand, one could argue that these images show that women can succeed in computing. On the other hand, I think there's a good chance that a modern young woman who walks by these will come to the conclusions that women could succeed in computing, ... back before color photography and pants. That's not very relevant to a generation that has grown up with the Internet, social media, games, and service learning, four factors that have been identified that get girls interested in pursuing Computer Science.

I got the blessing from my department to update the display case, which now looks like this:

The plaques on the left and right are awards from the 2008 and 2011 CCSC:Midwest Programming Competitions, in which teams from Ball State placed second and third, respectively. In the middle is a research poster put together by the students who were involved in both the Morgan's Raid and the Digital Archaeology project. The poster describes how we used Scrum and principles of agile software development and the lessons learned in the process.

One wouldn't know to look at the plaques, but both teams comprised of two men and one woman. The genders of these students was irrelevant: their success speaks for itself. Taking a closer look at the poster, you can see that although the teams have a male majority, there are women there too.

This is not as flashy as the University of Washington's excellent Why CSE page, which overtly demonstrates how underrepresented groups can and do succeed in Computer Science and Engineering. However, it does show that—right here and now—women are integral parts of successful research and development projects. Whenever I meet with a prospective CS major, we walk by this display case. I am glad that now I can point to these pictures of some of our most successful majors and show how they are working hard, together, and that they are proud of their work.

After all, Computer Science is not just for dead women.