Implementing a Game Class (type, not course)

In the fall of 2009, I taught a software engineering course. As our on-going project for the semester, I had students code up a bunch of different combinatorial games. One of the major goals of the course is to teach students the benefits of employing object-oriented design. As I tack on new aspects to the project each week, code that follows more OO-principles will be easier to upgrade.

Together, this begs the question: how should a game be implemented? More generally, what should be common to the interface for all games? What methods should a Game class contain?

Looking at this from a pure mathematical perspective, there should be only two methods: getLeftChildren and getRightChildren. If those return collections of game objects, then you're done. Everything you really need to know about a game is contained there. Other convenience methods would probably exist, such as leftHasMoves and rightHasMoves, etc., but these two are sufficient.

In the practical view, however, this is a problem. Some games have a very limited number of possible moves from any single state, but other games, such as Phutball, can have an exponential number of children. Yikes! You would never want to generate that collection for big-enough games!

Instead, consider replacing getLeftChildren and getRightChildren with the methods isLeftChild and isRightChild that return whether a given game is a child of the subject game. Could this work as a proper interface?

One obvious advantage is that we do not have to find and return all possible child states. One disadvantage, however, is that for many games, returning that set might be easier to code up than determining the validity of a child. The easiest "cop out" of this argument is to generate those children, then test whether the passed child is an element of those children. This doesn't solve the efficiency problem, however.

Is that problem solvable, though? Again, using Phutball as an example, it is NP-hard to determine whether a player can win on a given turn. Is it also as difficult to determine whether a child of a game exists? It seems trivial that this must also be NP-hard; use a winning position of Phutball as the potential child and ask the same question.

This argument does not immediately prove the hardness, as in Phutball there are potentially an exponential number of final board positions that result in a win. We cannot just test whether the ball ends in the end-zone as our final child state, but must also include whether any prior-existing players also remain on the board.

What is the complexity of this problem? How hard is it to tell whether a game is a child of another game?

This ends the regular posts for the semester! I will make a few posts over the summer (especially if I get a sexier phone) and will return to a regular schedule in the fall. I apologize in advance if those posts are very teaching related...

Thank you to everyone who has chimed in, both via email and in comments! I got a lot of vital advice, including material I may be able to include in teaching next semester. I'll still be listening all summer long! :)