Turn-Based Games Over Freenet

A Request for Comments
Version 0.4September 20, 2017

Table of Contents

Purpose

Basics

Procedures

Messages

Introduction

Game States

Disputes and Cheating

Effects of Cheating

Getting in Contact

Purpose

The high-latency nature of Freenet makes it almost perfect for turn-based gaming1, i. e. games that are not real-time and require each player to take turns one after another. Examples for turn-based games are manifold: board games such as chess, checkers, Settlers of Catan, or Risk; card-based games such as poker, Skat, or Magic – The Gathering; or dice-based games such as Yahtzee. All those games have strict rules for the order of possible actions and should be modelable using a turn-based gaming framework as proposed here.
Additional complexity is introduced by the requirement of a random or hidden element in each games, such as dice rolls, or a shuffled deck of cards, the state of which can only be exposed by all involved parties (in case of a deck of cards or a dice roll) and which must be immutable once they have been assigned (such as a hand of cards which should only be exposed to a single player but must not be modified by any player). It is however believed that these problems can be solved using algorithms from the cryptographic community2.
It is not yet clear whether TBGOF is best implemented as a separate Freenet plugin that game code can send messages to to control game-dependent state, or whether TBGOF should be a Freenet plugin that is itself capable of loading plugins which contain the games itselves, or whether TBGOF needs to be a Freenet plugin at all. It could just as easily be a separate application that performs all necessary operations on the network using Freenet’s FCP API and which does not put additional load on Freenet’s already strained memory requirements3. It could even be just a library that is used by other developers that are programming games for use with Freenet; in this way, TBGOF (The Library™) would not even require a graphical or text-based user interface at all.

Basics

TBGOF will follow the “usual” way of WoT-connected Freenet plugins: it will introduce its own WoT context and will use the WoT for discovery of other players.

Procedures

Alice and Bob want to play a game of checkers. Alice starts up TBGOF and selects “start a new game,” followed by the selection of checkers. (This will probably look different, depending on the implementation.) Her TBGOF plugin inserts a message into her subspace key that announces that she is looking for participants in a game of checkers. Now she waits.

Bob also starts TBGOF and browses the available games. He sees that Alice offers a game of checkers and decides to join it. So his TBGOF plugin sends a message stating that he wants to join Alice’s game. Now he waits.

After a short while (Freenet is not real-time, after all) Alice sees that Bob wants to join her game. She might also see that Carol and Dave want to join her game but she’s more intent on playing a game with Bob. So she selects Bob’s offer to join her, and her TBGOF plugin sends a message that the game has started and that Bob is player 24.

(Depending on the implementation Alice could also choose to start games with Bob, Carol, and Dave at the same time. However, care needs to be taken that each game gets its own Game ID even though it was started as a reaction to the same proposal by Alice.)

Bob receives the message that he has been chosen by Alice to join her in a game of checkers. There is much rejoicing, and the game begins.

First, it is determined which player actually makes the first move. For this, a random number (in the range of 0 x < 1) is generated5. If the random number is < 0.5, Alice starts; otherwise Bob is allowed to make the first move. We assume that Bob has been randomly selected as first player. He makes his move, and his plugin inserts the message with his move.

Alice’s plugin receives his move and displays it for Alice to ponder upon. After she makes her move, the plugin sends a message with the details.

This continues until the game is either won by a player, or a draw has been reached. We assume that Alice has won the game. The final game state that Alice’s plugin inserts contains the information that the game has ended; however, Bob’s plugin needs to insert a confirmation of this fact in order for other clients to see that the game really has ended and that Alice is really the winner, just as she said.

Messages

This chapter defines the on-network messages that different instances of TBGOF implementations will exchange with one another.

It is proposed that all messages are inserted under the subspace key of the playing user, using a site name of “TBGOF,” so all messages would be inserted under USK@<key>/TBGOF/<index>/<file>. Care needs to be taken that when inserting a new edition unchanged files are not inadvertantly removed by not including them in the new edition. However, they don’t need to be reinserted with the changed file each time; a redirect to the last inserted edition can be used.

It is not clear yet whether this will place undue burden on the TBGOF implementation and whether a different mechanism for distributing game states should be used; it would be possible to use a separate subspace key for each game. This would make it easier to insert new changes but would require more work on the receiving side which then needs to monitor more keys for changes.

Introduction

This message is inserted by all clients that wish to announce that a user is willing to play a game with somebody else.

<introduction>

  <games>

    <game>

      <id>2BFCA5AB</id>

      <plugin>NameOfGamePlugin</plugin>

      <plugin-version>26</plugin-version>

    </game>

  </games>

</introduction>

Technically it is not necessary to keep all active games listed in the introduction; each client knows which games it participates in, and the keys from which to expect updates. The <game> element is repeated for every game that is initiated by the player, i. e. for every game that a user wants to play. Games initiated by other players should not be listed here.

It is proposed that the introduction message is named introduction.xml. A client that parses the introduction message can choose to not display certain games: maybe a certain game plugin is not installed, or the locally installed game plugin does not have the right version (in which case it might be preferrable to show a message indicating that a newer version might exist), or because the player has blacklisted certain games that she does not care about.

Game States

Each game maintains its state separately from all other games played using the same TBGOF plugin. The game state contains all public information about a game; this includes things such as all actions chosen by either player, and the state of the board. In certain games this may enable a “watch mode” in which players that are not participating in a game can watch the game, maybe in order to learn about a player’s tactics.

Elements such as dice rolls or drawing a card from a shuffled deck may involve additional interaction with the other player or players. This will lead to additional round-trips between different plugin instances but can not be avoided due to the nature of the algorithms involved. So it may be possible that even though the game only visibly progresses by a player drawing a single card the plugins have exchanged several messages (turns) behind the scenes and without user interaction. Experience with other Freenet-based systems have shown that turn-around times of as little as 5 minutes can be reached for sending a message and receiving the reply to that message. As most of the interaction in case of these algorithms does not require the player’s interaction, it is expected that these additional round-trips do not noticably increase the time required for a player to make her move.

The game state is heavily dependent on the game in question. Some games have only public information, e. g. board games such as chess. For these games a simple list of all turns is sufficient to recreate the current state of the game. For other games additional state has to be included. This document does not specify how game state itself should be represented in game state messages.

Generally, game state should be contained in game state messages. These might look as follows:

<game-state>

  <turns>

    <turn>

      <number>0</number>

      <action>move-4-81</action>

    </turn>

    <turn>

      ...

    </turn>

    <turn>

      <number>24</number>

      <action>move-17-38</action>

    </turn>

  </turns>

</game-state>

The turns are numbered sequentially per game (not per client), starting at 0. Clients recognize that other players have made a turn by simply comparing the number of their latest turn with the number of the latest turn received in a game state message from another client.

Every interaction between participating plugins is modeled as a turn, including information exchanged for e. g. rolling a dice, or getting a card from a shuffled deck. Every game state message contains the complete game, making it easier for other clients to follow the game or replay it at a later point. Participating clients have to verify that the list of moves is the same it has stored locally; a deviation might indicate an attempt at cheating, or maybe a programming error. Failure to parse a game state message should be indicated in the user interface.

It is recommended to store the game state message in a separate directory in the same subspace key6 as the introduction messages, such as USK@<key>/TBGOF/<index>/games/ 2BFCA5AB/state.xml.

Disputes and Cheating

With systems that don’t have central authorities to watch that the rules of each game are kept, cheat detection must be done by each client. This is basically not a problem; each client knows how far each of his games has progressed, and what the current state should be. If a client receives a game state that has a state different from what it itself remembers the remote client might have tried to cheat. Invalid game states should simply be ignored or at most result in a notice being displayed somewhere: the differing state might also be the result of a programming error and not necessarily of malicious intent. It is, however, at this time not clear how such a situation should be resolved. It is possible that the only solution may be to discard the game and start a new one.

Effects of Cheating

Some plausible cheating scenarious include:

Most of these attempts can be detected easily by clients that have the same game plugin installed that is used in the game. And while it is easy to detect that there is something wrong with one side of a game, it is almost impossible to say which of the players is actually lying; after all, one player could have inserted a complete game that followed all rules and clearly shows him as a winner but which is not the game that was actually played.

Using more cryptography, e. g. for signing each turn and its state individually, could prevent the creation of fake games but a watching party still would need to verify a game using the data (such as public keys) from two different clients.

It is generally very hard to technically stop people from trying to cheat. If some players decide to play unfair, the most appropriate solution would be to use the WoT plugin to reduce their trust, and simply stop playing with them.

Getting in Contact

Contact me via my Sone, or Freemail, or FMS, or IRC, or regular, non-anonymous email:

I’m looking forward to hearing from and discussing with you.

1Of course that is complete bullshit. It’s just that Freenet is completely unsuitable for anything requiring real-time interaction with other players.

2The specifics of these algorithms will be detailed at a later point but I will mention the terms “mental poker” and “commitment scheme” here.

3Apart from the requests it creates.

4The TBGOF instance that initiated a game is always player 1, and it also assigns the player numbers for all other participants.

5This will probably involve more messages sent between the TBGOF plugins of both (or all) players of a game in order to be fool-proof.

6This is still subject to discussion; a separate subspace key might be recommendable to reduce work load at the insert side, at the cost of work at the requester side.