Tic Tac Toe Protocol 1.0¶

Summary¶

Describes a simple protocol, already familiar to most developers, as a way to demonstrate how all protocols should be documented.

Motivation¶

Playing tic-tac-toe is a good way to test whether agents are working properly, since it requires two parties to take turns and to communicate reliably about state. However, it is also pretty simple, and it has a low bar for trust (it's not dangerous to play tic-tac-toe with a malicious stranger). Thus, we expect agent tic-tac-toe to be a good way to test basic plumbing and to identify functional gaps. The game also provides a way of testing interactions with the human owners of agents, or of hooking up an agent AI.

Tutorial¶

Tic-tac-toe is a simple game where players take turns placing Xs and Os in a 3x3 grid, attempting to capture 3 cells of the grid in a straight line.

Name and Version¶

This defines the tictactoe protocol, version 1.x, as identified by the following PIURI:

did:sov:SLfEi9esrjzybysFxQZbfq;spec/tictactoe/1.0

Key Concepts¶

A tic-tac-toe game is an interaction where 2 parties take turns to make up to 9 moves. It starts when either party proposes the game, and ends when one of the parties wins, or when all all cells in the grid are occupied but nobody has won (a draw).

Note: Optionally, a Tic-Tac-Toe game can be preceded by a Coin Flip Protocol to decide who goes first. This is not a high-value enhancement, but we add it for illustration purposes. If used, the choice-id field in the initial propose message of the Coin Flip should have the value did:sov:SLfEi9esrjzybysFxQZbfq;spec/tictactoe/1.0/who-goes-first, and the caller-wins and flipper-wins fields should contain the DIDs of the two players.

Illegal moves and moving out of turn are errors that trigger a complaint from the other player. However, they do not scuttle the interaction. A game can also be abandoned in an unfinished state by either player, for any reason. Games can last any amount of time.

About the Key Concepts section: Here we describe the flow at a very
high level. We identify preconditions, ways the protocol can start
and end, and what can go wrong. We also talk about timing
constraints and other assumptions.

Roles¶

There are two parties in a tic-tac-toe game, but only one role, player. One player places 'X' for the duration of a game; the other places 'O'. There are no special requirements about who can be a player. The parties do not need to be trusted or even known to one another, either at the outset or as the game proceeds. No prior setup is required, other than an ability to communicate.

About the Roles section: Here we name the roles in the protocol,
say who and how many can play each role, and describe constraints.
We also explore qualifications for roles.

States¶

The states of each player in the protocol evolve according to the following state machine:

When a player is in the my-move state, possible valid events include send move (the normal case), send outcome (if the player decides to abandon the game), and receive outcome (if the other player decides to abandon). A receive move event could conceivably occur, too-- but it would be an error on the part of the other player, and would trigger a problem-report message as described above, leaving the state unchanged.

In the their-move state, send move is an impossible event for a properly behaving player. All 3 of the other events could occur, causing a state transition.

In the wrap-up state, the game is over, but communication with the outcome message has not yet occurred. The logical flow is send outcome, whereupon the player transitions to the done state.

About the States section: Here we explain which states exist for each
role. We also enumerate the events that can occur, including messages,
errors, or events triggered by surrounding context, and what should
happen to state as a result. In this protocol, we only have one role,
and thus only one state machine matrix. But in many protocols, each
role may have a different state machine.

Messages¶

All messages in this protocol are part of the "tictactoe 1.0" message family uniquely identified by this DID reference: did:sov:SLfEi9esrjzybysFxQZbfq;spec/tictactoe/1.0

NOTE 1: All the messages defined in a protocol should follow DIDComm best practices as far as how they name fields and define their data types and semantics.

NOTE 2 about the "DID Reference" URI that appears here: DIDs can be resolved to a DID doc that contains an endpoint, to which everything after a semicolon can be appended. Thus, if this DID is publicly registered and its DID doc gives an endpoint of http://example.com, this URI would mean that anyone can find a formal definition of the protocol at http://example.com/spec/tictactoe/1.0. It is also possible to use a traditional URI here, such as http://example.com/spec/tictactoe/1.0. If that sort of URI is used, it is best practice for it to reference immutable content, as with a link to specific commit on github: https://github.com/hyperledger/aries-rfcs/blob/ab7a04f/concepts/0003-protocols/tictactoe/README.md#messages

`move` message¶

The protocol begins when one party sends a move message to the other. It looks like this:

@id is required here, as it establishes a message thread that will govern the rest of the game.

me tells which mark (X or O) the sender is placing. It is required.

moves is optional in the first message of the interaction. If missing or empty, the sender of the first message is inviting the recipient to make the first move. If it contains a move, the sender is moving first.

Moves are strings like "X:B2" that match the regular expression (?i)[XO]:[A-C][1-3]. They identify a mark to be placed ("X" or "O") and a position in the 3x3 grid. The grid's columns and rows are numbered like familiar spreadsheets, with columns A, B, and C, and rows 1, 2, and 3.

comment is optional and probably not used much, but could be a way for players to razz one another or chat as they play. It follows the conventions of localized messages.

Other decorators could be placed on tic-tac-toe messages, such as those to enable message timing to force players to make a move within a certain period of time.

Subsequent Moves¶

Once the initial move message has been sent, game play continues by each player taking turns sending responses, which are also move messages. With each new message the move array inside the message grows by one, ensuring that the players agree on the current accumulated state of the game. The me field is still required and must accurately reflect the role of the message sender; it thus alternates values between X and O.

Subsequent messages in the game use the message threading mechanism where the @id of the first move becomes the ~thread.thid for the duration of the game.

An evolving sequence of move messages might thus look like this, suppressing all fields except what's required:

Message/Move 2¶

This is the first message in the thread that's sent by the player placing "O"; hence it has myindex = 0.

Message/Move 3¶

This is the second message in the thread by the player placing "X"; hence it has myindex = 1.

Message/Move 4¶

...and so forth.

Note that the order of the items in the moves array is NOT significant. The state of the game at any given point of time is fully captured by the moves, regardless of the order in which they were made.

If a player makes an illegal move or another error occurs, the other player can complain using a problem-report message, with explain.@l10n.code set to one of the values defined in the Message Catalog section (see below).

`outcome` message¶

Game play ends when one player sends a move message that manages to mark 3 cells in a row. Thereupon, it is best practice, but not strictly required, for the other player to send an acknowledgement in the form of an outcome message.

The moves and me fields from a move message can also, optionally, be included to further document state. The winner field is required. Its value may be "X", "O", or--in the case of a draw--"none".

This outcome message can also be used to document an abandoned game, in which case winner is null, and comment can be used to explain why (e.g., timeout, loss of interest).

About the Messages section: Here we explain the message types, but
also which roles send which messages, what sequencing rules apply,
and how errors may occur during the flow. The message begins with
an announcement of the identifier and version of the message
family, and also enumerates error codes to be used with problem
reports. This protocol is simple enough that we document the
datatypes and validation rules for fields inline in the narrative;
in more complex protocols, we'd move that text into the Reference
> Messages section instead.

Constraints¶

Players do not have to trust one another. Messages do not have to be authcrypted, although anoncrypted messages still have to have a path back to the sender to be useful.

About the Constraints section: Many protocols have rules
or mechanisms that help parties build trust. For example, in buying
a house, the protocol includes such things as commission paid to
realtors to guarantee their incentives, title insurance, earnest
money, and a phase of the process where a home inspection takes
place. If you are documenting a protocol that has attributes like
these, explain them here.

Reference¶

About the Reference section: If the Tutorial > Messages section
suppresses details, we would add a Messages section here to
exhaustively describe each field. We could also include an
Examples section to show variations on the main flow.

Collateral¶

A reference implementation of the logic of a game is provided with this RFC as python 3.x code. See game.py. There is also a simple hand-coded AI that can play the game when plugged into an agent (see ai.py), and a set of unit tests that prove correctness (see test_tictactoe.py).

A full implementation of the state machine is provided as well; see state_machine.py and test_state_machine.py.

The game can be played interactively by running python game.py.

Localization¶

The only localizable field in this message family is comment on both move and outcome messages. It contains ad hoc text supplied by the sender, instead of a value selected from an enumeration and identified by code for use with message catalogs. This means the only approach to localize move or outcome messages is to submit comment fields to an automated translation service. Because the locale of tictactoe messages is not predefined, each message must be decorated with ~l10n.locale to make automated translation possible.

There is one other way that localization is relevant to this protocol: in error messages. Errors are communicated through the general problem-report message type rather than through a special message type that's part of the tictactoe family. However, we define a catalog of tictactoe-specific error codes below to make this protocol's specific error strings localizable.

Thus, all instances of this message family carry localization metadata in the form of an implicit ~l10n decorator that looks like this:

This JSON fragment is checked in next to the narrative content of this RFC as ~l10n.json, for easy machine parsing.

Individual messages can use the ~l10n decorator to supplement or override these settings.

For more information about localization concepts, see the RFC about localized messages.

Message Catalog¶

To facilitate localization of error messages, all instances of this message family assume the following catalog in their ~l10n data:

When referencing this catalog, please be sure you have the correct version. The official, immutable URL to this version of the catalog file is:

https://github.com/hyperledger/indy-hipe/blob/fc7a6028/text/tictactoe-protocol/catalog.json

This JSON fragment is checked in next to the narrative content of this RFC as catalog.json, for easy machine parsing. The catalog currently contains localized alternatives only for English. Other language contributions would be welcome.

For more information, see the Message Catalog section of the localization HIPE.

Implementations¶

The following lists the implementations (if any) of this RFC. Please do a pull request to add your implementation. If the implementation is open source, include a link to the repo or to the implementation within the repo. Please be consistent in the "Name" field so that a mechanical processing of the RFCs can generate a list of all RFCs supported by an Aries implementation.

Name / Link	Implementation Notes
Verity	Commercially licensed enterprise agent, SaaS or on-prem.
Pico Labs	Open source TicTacToe for Pico Agents