Delphi: A Regex Game

Delphi is an asymmetric game between two players:

• The Oracle (O) and
• The Machine (M).

Setup

To begin, O and M agree on a regular expression standard to use, including:

• legal operations and their definitions
  (e.g., Ruby-compatible, POSIX, Perl-compatible without backreferences, formal, etc.)
• character set
  (e.g., Unicode, ASCII printable, Latin-1, etc.)
• maximum length
• anchoring
  (e.g., none, implied ^ and $, etc.)

Then O constructs a regular expression R matching these criteria and transmits to M the following information:

• a hash of R,
• one string which R matches, and
• one string which R does not match.

Play

M then makes a number of plays, followed by a guess. Each play consists of the following exchange:

• M transmits to O five distinct strings, identifying for each one whether she believes R matches it.
• If all of M's classifications are correct, O must respond "Correct."
• If at least one of M's classifications is incorrect, then O must respond "Incorrect."

Deciding a Winner

Once M believes she knows R, she makes a guess S and transmits it to O, who will then reveal R (M may use the hash to verify this claim). If R and S match exactly the same set of strings, then M wins; if they differ, O wins.

A Symmetric Version

To play a symmetric version, simply play two games in parallel, with players playing opposite roles in each game (i.e., Game 1's M is Game 2's O). After the games have concluded, decide the winner by running through the following until a winner is decided. If no winner is decided at the end, the game is a draw.

1. The player who won both games is the winner.
2. The player who, in her capacity as M, made fewer plays is the winner.
3. The player who, in her capacity as O, constructed a shorter regular expression is the winner.
4. The player who, in her capacity as M, made more Correct plays is the winner.