Partake, A Formal Language for Board Games

Abstract

TODO: update

Board games are not just for fun: they seriously exercise our reasoning abilities and prepare players for “real-world” activities that require problem solving.

There is much recent interest in complex games that include large libraries of cards and scenarios that combinatorially increase gameplay diversity. Regarded as formal systems, these games are a legitimate challenge to represent using software.

We introduce a language, Partake, which allows for compositional development of games using programs that match the conciseness of natural language. Going beyond traditional monist object-oriented systems, Partake recognizes a basic duality between situations and actors, which clarifies the role of each in specifying gameplay. Game rules typically specify complex situations in which players act, so we focus on the task of specifying situations. Situations unfold over time into choice-points to be decided by various actors, be they people, randomizers, rulings, or strategic heuristics. We present a temporal semantic model based on episode segments that naturally group together these choices. We introduce two intertwined new languages: a declarative relational language for defining concepts and a procedural one for episodes.

Finally, our approach allows us to decouple low-level input/output issues like event handling and rendering from the high-level input/output specified by game logic. We demonstrate this with a novel GUI generation algorithm, which provides a way of smoothly interpolating between a minimalist menu-based GUI all the way to fully custom GUIs, while significantly reducing the effort needed for practical board-game style GUIs.

Relational Model Design

We propose a relational object-oriented model for defining games and other interactive software.

summary of the aspects of board games as a model of computation that we must capture in the language:

Objects

(Comparison to traditional OO model)

The original Smalltalk system was designed to support the human creative spirit by attempting to reflect human communication patterns onto those of the computer. The central metaphor was that of the physical object, a restricted area of space with definite affordances. A central focus was on formally capturing affordances and needs; any object with affordances appropriate for a particular need could be used to satisfy that need. For instance, many file-system implementations might be hidden behind a particular interface that represents a need to list files within a directory and access particular files by name. Uniformity of representation was emphasized by ensuring that all programmer-facing value types were objects todo.

Game objects, however, do not have a function-oriented nature, instead being purely symbolic. The collection of game objects takes on meaning based on rules that impose particular relationships among them and between them and the players’ goal(s). A typical game token is an entity without internal structure: it is merely distinct from other tokens and occupies some physical space. However, it may take on an arbitrarily large salience due to attributes granted it by game rules.

In order to design a programming language that reflects the natural way that people combine and learn about game rules, we must begin by reflecting the basic values that rules refer to and manipulate.

In light of the reasons and examples just given, we propose that a relational model for game entities is necessary. Relations do not impose a fixed up-front structure on entities. For instance, the statement

token P
located P -> L

asserts merely that P is a token with a location L. Additional facts may or may not be asserted and updated later:

health P -> 10
has-ability P 'attack-right
has-ability P 'flee
...
health P -> 8

Syntax note: We use the traditional logic-programming style syntax for tuples and queries (e.g. predicate(X, A+B)) except written “Haskell style” (e.g. predicate X (A+B)).

State

A second core observation about the board game domain is that almost the entirety of the game state must live on the board. This is a simple reflection of human short-term memory limitations: a well-designed game and game board should impose minimal unnecessary cognitive burden on the players.

However, there are two issues that conflict with this:

However, a high-level view of gameplay suggests that typical games require players to make choices and then promptly unfold the consequences of those choices as determined by the relevant game rules. The process of unfolding the rules takes time, and we note that the intermediate points may not always have a literal board representation. For instance, when playing a card that says “draw a card, then discard a card from your hand”, it is clear that

The computational state needed to carry out this action is simple for a player to carry mentally, and we wish to reflect this in our mechanism for representing rules.

Procedural languages have a simple notion of time during execution: the program counter and call-stack. Reasoning about program behavior at this level is notoriously tedious, but programming an application such as a board game engine requires carefully mapping game time onto execution time in some way. The procedural model is poorly suited to the task of representing computations mainly consist of cycles of interaction between several actors.

Instead, we propose an objective representation of time that captures a basic way that people group situations into periods of time. We refer to a period of time formally as an episode. Episodes can contain other episodes (such as when a player’s turn consists of two phases) and may be ordered temporally (such as when a player’s turn must fully elapse before another player’s turn may begin). Episodes can also be concurrent (such as when two players in a cooperative game may take their turns in an arbitrarily interleaved fashion) (or in a simultaneous moves game, where players must make certain decisions and then reveal them simultaneously).

More formally, we assume an infinite set E of episodes, and equip them with the following structure:

Examples

(ignore)

Rules that match one attribute need not refer to others:

has-ability P 'attack-right, located P -> L,
adjacent-right L L', located P' L'
-----------------------------------------
may-attack P P'.

But may if they wish to:

has-ability P 'flee, health P -> HP, HP > 5
---------------------------------------
may-flee P.

The most important consequence of this choice is that rules combine commutatively.

Story Design

Design of features in story language (main rule language; each rule unfolds into episode)

Evaluation

language part

challenges to demonstrate:

GUI generation

Observations

Games as computation:

https://cutfree.net