1. icon for News
  2. icon for TCHOW


Tuesday, August 11, 2020

Interactive vs Generational Collaboration

My research group has been writing a lot of papers recently. Like any reasonable set of CS folks, we use LaTeX as our typesetting tool of choice. Of course, like any modern set of collaborators, we also all want to be editing the paper at the same time, changing words as others are writing, and completing each-others sentences.

To accomplish this, we have generally turned to Overleaf, which -- like LaTeX itself -- isn't a great solution to the problem, but it is the best solution we have. One of the interesting things about Overleaf is that it supports two completely different models of collaboration, which -- for the purposes of this post and without reference to any external sources -- I'll term "interactive" and "generational".

Interactive Collaboration

Interactive collaboration models a shared workspace. All changes are made simultaneously and with fine-grained (real-time) synchronization. Interactive collaboration seems to work best when edit operations are "local" -- generally modeled by granting participants a notion of a cursor or selection around which their edits are centered.

Interactive collaboration doesn't work very well with dependent or global edits (e.g., trying to make an overarching change to the order of sections). And -- as often happens on Overleaf -- it really doesn't work well when the synchronization system begins to bog down.

Generational Collaboration

Generational collaboration models... we'll, I'm not exactly sure what it models. Perhaps a series of independent artifacts, individually crafted, but with reference to other previously created artifacts? Regardless, changes are made individually, and merged non-real-time into a final artifact.

Generational collaboration works well for changes that don't overlap and (thus) can be merged automatically. It is, thus, a natural fit for global but distinct changes (e.g., changing all references to a figure; doing a global re-ordering of paragraphs in a the "Results" section while another collaborator works on the "Introduction" section).

Further, generational collaboration can operate in a decentralized and disconnected way, which are distinct advantages, especially on a paper deadline when nobody has time to wait on a slow server. (Or, e.g., on an airplane.)

Combining the Models

So, how do we combine the models to get the benefits of both?

Overleaf's approach is to support the generational collaboration model via git push/pull support, but to require that no interactive edits happen between a git pull and the subsequent git push. This, effectively, makes generational collaboration lower priority than interactive, making it incredibly awkward to leverage this model while others are using the interactive model.

My preference here would, instead, be to start with a decentralized generational model and build in some notion of interactivity. I tend to like disconnected/disjoint tools, so perhaps the way to do this is to have the notion of a multiplayer editor protocol that can work (optionally, in parallel) with a git repository.

Here's a sketch of how that might work:

When a multiplayer (text?) editor opens a file, it would check in the same folder (and parent folders) for a .multiplayer subdirectory and contained config file. (Similar to how git looks for a .git subdirectory.)

The .multiplayer config file would contain either the address of a responsible server and a project token to identify the project to that server, or a list of peers to contact directly. Any multiplayer-capable editor would -- after prompting the user -- get the list of peers to coordinate editing with (possibly via connecting to a server, possibly via direct peer entries). The server could also handle STUN to make peer-peer communications easier.

Regardless, said multiplayer-capable editor would now be connected to a peer cloud and could use peer-to-peer multicast techniques to keep the document synchronized, publish cursor state, and so on.

So that takes care of the interactive collaboration. How about the generational part? We could make it so the .multiplayer directory contains a reference to the most recent point in shared edit history at which an editor had synchronized to the peer cloud. If -- when your multiplayer editor connects -- your current file matches the recent version in the .multiplayer directory, then all changes between that version and the current peer cloud version could be automatically applied.

If, on the other hand, your current file differs from the reference version in the .multiplayer directory, then there's a generational change to merge. This is the classic "three-way merge" problem that (e.g.) git solves reasonably well. In the interactive setting, it might even make sense to allow you to request others stop for a second and help with the merge.

Of course, if your text editor of choice doesn't support multiplayer, you could still edit single-player and use a command-line utility to deal with the three-way merges. (Perhaps with a "hang on, let's do the merge together everyone" option to avoid the same problem that overleaf has.)

So, Who's Building It?

Perhaps the most surprising thing for me in my (scant) research around this topic is that nobody has built an interoperable interactive collaboration system that actually supports, e.g., cross-editor cursor sharing; at least not one that is still in action today (I seem to recall that google docs at some point had an API with cursors).

Perhaps the notion of a cursor is so editor-specific that it takes special sauce to do it. Perhaps the idea that you need to run a server makes people want to lock in users to finance said server. And perhaps I just haven't looked hard enough.

In the latter case, let me know! I'd love to try out something different with my group when we next have a big crop of papers ready to go.

Tuesday, July 28, 2020

Puzzle Nutrients and The Cubedex of Brass and Wood

The Cubedex Series of games were each designed as virtual puzzle hunt replacements. As such, they have a particular flavor that grew out of my puzzle hunt design strategies. In this post, I will describe what I look for in a cubedex game puzzle, and talk about how these relate to The Cubedex of Brass and Wood, which is forthcoming on Steam (indeed, there is a demo there now).

The Puzzle Nutrients

I tend to think of puzzle-hunt style puzzles as having a few different archetypes. In reality, perhaps they are more like ingredients -- in that they can be mixed and complementary -- or like nutrients, in that a healthy puzzle hunt should contain a balance of all of them.

They are, in no particular order:

Hidden Puzzles

Hidden puzzles present the player with an unknown artifact and ask them to understand the artifact in order to solve it. These are the bread-and-butter of puzzle hunts, and require a sort of logical twist wherein the player must hypothesize rules under which the puzzle might contain information and extract that information. Once the proper rules are found, the puzzle becomes simple to decode, and provides some sort of structure that convinces the player that their decoding is correct.

The simplest hidden puzzles are those that present information in a known encoding scheme -- like resistor color code, semaphore, or ASCII, to name a few -- lightly obscured by some sort of transformation (e.g., written in letters which are mirrored). More interesting encoding puzzles may present physical artifacts that need to be manipulated to produce the decoding effect (e.g., a literal decoder ring, a pattern that must be viewed through a color filter, or -- in one of my favorite examples -- a set of paper tiles, only some of which were treated with a fire-retardant chemical).

A prototypical encoding puzzle in The Cubedex of Brass and Wood is The Clock, which combines a decoder-ring-like device with another encoding scheme.

Combinatorial Puzzles

Combinatorial puzzles challenge the player to find a satisfactory solution from a large solution space. The solution space is generally abstract and generally contains very few satisfactory solutions. This makes brute force search infeasible (or, at least, tedious). However, in contrast to hidden puzzles, the quality of a solution isn't ever in doubt.

Typical puzzles of this sort include physical put-together puzzles (e.g., build a cube from these tetrominoes, fill a bird silhouette with these tangrams) and constraint-satisfaction puzzles like Sudoku. In The Cubedex of Brass and Wood, the prototypical combinatorial puzzle is probably The Balance, in which the player must fill a tray with masses so that it balances.

This puzzle type generally requires one to either constrain the search space by developing a higher-level understanding of the puzzle, or to write a computer program that searches and checks solutions for you. I think both of these solution methods can be really satisfying; indeed, sometimes they can be combined to produce a really, really satisfying solution -- like realizing that "Lights Out" can be solved by using linear algebra over finite fields, or that state equivalence via move reversibility allows for the creation of more efficient Sokoban solvers.

Performance Puzzles

Performance puzzles ask the player to interact with an artifact in order to manipulate it into a good state. Performance puzzles mix well with hidden puzzles and combinatorial puzzles, adding a layer of reflex- or precision-based challenge to the existing puzzle.

I think that performance puzzles are often neglected in a puzzle hunt context because they can be hard to run for a large group in person (for all that they can also be spectacularly fun). Virtual performance puzzles really open up more options in this regard.

The Cubedex of Brass and Wood's performance puzzle is The Maze, which requires reasonably fine control of the angles of mirrors to direct a beam of light to enable walls to be moved. The version of this puzzle you get in the retail game is actually a toned-down version relative to the original; in the version you'll be able to play, you get to trigger wall movement manually. In the original, wall movement was automatically triggered and any stray hand motion could cascade and ruin the entire maze setup. My testers found this incredibly frustrating, so I changed it.

The Machine is another Cubedex of Brass and Wood puzzle with performance elements, though it is in some ways also a hidden puzzle, given that the interaction rules are not clear. (Arguably, for some variants, it is also a combinatorial puzzle, as at least one tester [threatened to] use Z3 to extract a logical formula consistent with the device's behavior during their solution attempt.)

Building Puzzles

A building puzzle asks the player to assemble a device to overcome a challenge. Like a combinatorial puzzle, the building blocks and goal are generally reasonably straightforward. However, the solution often relies on a [simulated] physical task, rather than a discrete measure of correctness; and the solution space is generally large and open-ended.

Good examples of physical puzzle hunt building puzzles include building a bridge over an obstacle, designing a Lego gear box with a specific ratio, or building an autonomous vehicle that can cross a specific terrain. I use that last idea in The Cubedex of Brass and Wood in The Cart, where the player builds a line following robot using real[-ish] vacuum tube logic components.

One of the fun things about building puzzles is that the players can often design "cheesy" solutions that just barely work; The Cart is not immune to these sorts of solutions, but I think I've included at least one variant of the puzzle that will be hard to solve in an unintended way (prove me wrong! -- it's always fun seeing how these things can be broken).

A Balanced Puzzle Diet

These are the four basic puzzle nutrients that I think about when building a puzzle hunt or game. They can serve as a prompt to make sure the hunt is balanced, or as a lens to look through when attempting to solve a puzzle.

As I continue to polish and release the Cubedex Series, I hope you will look out for these puzzle types in the games. Every game aspires to be a complete meal, but they certainly have different balances of nutrients within them (e.g., The Cubedex of Boxes and Lines is almost entirely hidden puzzles with a performance element).