Telegram and table tennis challenges

At my workplace, we may play table tennis during the day. For this, we have one table, some paddles and balls. We also use a Telegram bot as a match-maker… just for the fun of it. To make or answer challenges, the “workflow” goes as follows.

  1. Player 1 wants to play and writes “ping” on a Telegram group chat for this purpose.
  2. The ping-pong bot asks for a challenger.
  3. Player 2 wants to play, too, and writes “pong”.
  4. The match between both players is announced by the bot.

Until recently, we’ve played singles exclusively. However, since the advent of a couple more paddles in the office, we can play doubles, although match-making on doubles hasn’t been implemented. So, for now, we’ll focus on singles.

Current implementation

The program we use today is a PHP service, which is called by a Telegram webhook attached to a bot. The bot was invited to an off-topic Telegram group, so it can read the messages sent to the group. Also, a SQLite database is used to persist the bot’s state regarding the match-making.

When a “ping” message is read by the bot, the database is truncated and the user who sent the message is stored. When a “pong” message arrives, the user who’s in the database is retrieved and the match between the players is announced. The database is cleaned afterwards.

Although this works well enough actually, this has a number of drawbacks:

  1. If users issue consecutive “ping” messages, only the last one in the sequence is remembered. The rest are forgotten, since the database is truncated every time a “Player 1” is recorded.
  2. If users issue consecutive “pong” messages, only the first one in the sequence is taken into account. Other users get an “error message” since there is no user recorded in the database after a “pong” has been successfully matched to a “ping”.
  3. If a “pong” message is issued as a response to a “ping” message with a delay of hours or days, the match will be announced. It’s more sensible to suppose that the original “ping” message has “timed out”, because Player 1 may be busy or out of the office.

So, before tackling these drawbacks in an ad-hoc way, let’s look at the actual problem. This may allow us to come up with a more appropriate solution.

Let’s not forget history

I’ll first make an observation: we’re processing a sequence of challenges with the following properties:

  1. Content. “ping” or “pong”. It could be a bit or a boolean value.
  2. User ID. An identifier for the players. (e.g. Telegram username)
  3. Date/time. A UNIX timestamp or ISO-8601 string.

The current implementation obviates the date/time property; we’ll see it’s going to be very important later. Next, we need to know these three conditions hold in order to match two challengers:

  1. The content of both challenges should make sense. (i.e. a “ping” is followed by a “pong” has most sense than the other three pairwise possibilities)
  2. The users can or want to play against each other. After all, one cannot play against oneself.
  3. The challenges should be close in time.

In a more algebraic presentation:

\[C_1 \text{ against } C_2 = (p_2 \text{ follows } p_1) \wedge (u_1 \text{ vs. } u_2) \wedge (t_2 \text{ close to } t_1)\]

A problem of certainty

I proposed to use the Bayesian view of probability to solve the problem. Instead of looking at the conditions as a boolean proposition, we shall consider how convinced the machine may be that the proposition holds or not. Thus, the proposition above could be written as follows:

\[\text{Pr}[C_1 \text{ against } C_2] = \text{Pr}[p_2 \text{ follows } p_1] \cdot \text{Pr}[u_1 \text{ vs. } u_2] \cdot \text{Pr}[t_2 \text{ close to } t_1]\]

About the “follows” probability, any function that holds the following equation should suffice:

\[\forall x,y\in\{\text{ping, pong}\} : \text{Pr}[\text{pong follows ping}] \geq \text{Pr}[x \text{ follows } y]\]

For example, we can thus define:

\[\text{Pr}[p_2 \text{ follows } p_1] = \begin{cases} 1.0 & \text{if } p_1 = \mbox{ping} \wedge p_2 = \mbox{pong} \\ 0.5 & \mbox{otherwise} \end{cases}\]

About the “vs.” probability, it’s necessary that it outputs 0.0 when both users are the same. Apart from that, it may encode preference for players who’d want to play against each other. For now, let’s keep it simple in the following example:

\[\text{Pr}[u_1 \text{ vs. } u_2] = \begin{cases} 0.0 & \text{if } u_1 = u_2 \\ 1.0 & \mbox{otherwise} \end{cases}\]

Exponential decay of history

This section is based on the eponymous blog post by David Barbour. You’d like to read it to learn about his insight on exponential decay of history and its potential applications.

“Closeness” of two timed events can be modeled using any descending function. However, the idea of attaching a “half-life” to messages is appealing. In easier terms, the messages’ relevance is cut in half after fixed periods of time. The formula for half-life is:

\[N(t) = N_0\cdot2^{-t/t_{1/2}}\]

where \(N_t\) is the value of \(N\) at time \(t\) and \(t_{1/2}\) is the half-life (i.e. the period of time in which the value of \(N\) decreases by half).

Thus, if we use maximum probability (i.e. 1.0) for \(N_0\), we may define:

\[\text{Pr}[t_2 \text{ close to } t_1] = 1.0 \cdot 2^{-(t_2 - t_1) / t_{1/2}} = 2^\frac{t_1-t_2}{t_{1/2}}\]

Before considering exponential decay, I explored other ad-hoc ideas, like using a linear function, other forms of inverse exponentials, and even logistic functions learned in AI courses. However, the exponential decay formula above is quite convenient as it is.

Putting everything together

Now that we have a way to compute the certainty about a match, we’ll focus on the bigger picture: the sequence of messages.

When a new message \(n\) arrives, we must determine which of the previous messages yields the highest probability (or certainty) when evaluated against \(n\). This can be written as follows:

\[\mathrm{match}(n) = \underset{m}{\mathrm{arg\,max}} \text{ Pr}[m \text{ against } n]\]

Effect on user interaction

Apart from solving the issues of the previous implementation, we can take advantage of the probabilities generated from the message processing. For instance, a different message may be shown depending on probability ranges for a new-found match. This is a richer way to interact with users, instead of the binary “Match / No match” messages we now have.

This also has the side-effect of demonstrating how mathematics can actually help to create a more meaningful service (albeit a very silly one in this case) with minimum development effort.

To-do list

  • Upload a sample Haskell implementation as soon as I retrieve it from my other computer.
  • Write its Spanish version.