Beading The Allegations – Part I

Hi there, I'm Panda and lately I have been pondering a game of chess, played during the Sinquefield Cup in September 2022 between Magnus Carlsen and Hans Niemann. The game sparked controversy after Carlsen, the then world champion, accused Niemann of cheating, leading to one of the biggest scandals in recent chess history. In response, the internet — as the internet does best — fabricated the wildest theories on how one could cheat in an over-the-board tournament. Most (in)famously, it was suggested that information was relayed to the player by means of a vibrating device inserted in a most delicate place. Now, I am a pondering panda, not a drama llama, so I will not delve into the details of the scandal itself. Instead, we are going to spend our time today on determining the optimal way to transmit every chess move using as few vibrations as possible.

Note: I do not condone cheating and the below information is for educational and entertainment purposes only.

Setting up the board

• Budget beads only.

To keep things interesting, we will not use fancy devices with different modes and intensities that can be combined into unique signals for each square of the board, since that would trivialize the problem. Rather, our relay device can emit only two signals: one short and one long.

• Every move matters.

A grandmaster might need only one small buzz in the entire game to confirm whether an "obvious" line is actually playable or not. I want our method to be fully expressive, i.e. capable of communicating every possible move such that even a complete chess noob, who only knows how the pieces move, should be able to beat Magnus Carlsen. Meta-moves such as offering a draw or resigning are excluded.

• No sore winners.

To prevent fatigue, a move should be expressed by as few signals as possible. In other words, we are seeking a method that can convey every possible chess move in any and all chess positions with the minimum number of signals necessary.

The opening

To kickstart our investigation, we will use an existing chess notation system as a starting point, viz. the numeric notation of the International Correspondence Chess Federation. In numeric notation, files are numbered 1 through 8 from left to right, and ranks are numbered 1 through 8 from bottom to top (from White's perspective, see the figure below). Then, each square can be identified by a two-digit number, the first of which describes the file and the second describes the rank. A move is denoted by a pair of squares, the origin square from which the piece leaves and the destination square at which the piece arrives. Accordingly, each move can be represented by four digits. Since our device emits only two signals, we encode moves in binary, where 0 represents a short vibration and 1 a long vibration. The numbers 1 through 8 can be encoded by log2(8) = 3 bits so the total number of bits per move using numeric notation is 4 * 3 = 12.

However, there are some special moves in chess. Symbols for captures, en passant, and checks can be omitted without causing confusion, but castling and promotion require additional handling. Castling is written as a king's move and the position of the rook is implicitly inferred. For example, if Black castles queen's side, it would be written as 5838. The rook moving from 18 to 48 is implied. For promotion, a fifth digit is often added: 1 for queen, 2 for rook, 3 for bishop, and 4 for knight — but this would increase our total number of bits per move by 2. Luckily, there is a simple trick: in case of promotion, the rank of the destination square is always the same (8 for White and 1 for Black), so it can be omitted safely and we can use the freed up bits to specify the promotion piece. In doing so, we ensure every legal move can still be encoded by no more than 12 bits. But we can do better!

The middlegame

Numeric notation maps every square to every other square. This yields 64 * 64 = 4096 possible moves which require log2(4096) = 12 bits to encode. Note that a move can only start from a square which contains one of our pieces. Hence, instead of mapping every square to every other square, we can map every piece to every other square. Since you start a game with 16 pieces, there are only 16 * 64 = 1024 possible moves — which can be encoded with log2(1024) = 10 bits of information, 4 to identify the piece and 6 to denote the destination square.

Just as not every origin square matters, neither does every destination square. We need only encode the squares that can be reached by the currently selected piece. This works as follows: the first four bits identify the piece that will be moved, then, the player enumerates every legal move for that piece and labels them according to some pre-defined pattern, e.g. from left to right and top to bottom (see figure below).

The queen is the most powerful piece on the board and can reach more squares than any other piece, 27 to be precise. Accordingly, a maximum of log2(27) ≈ 5 bits are required to encode the destination square. Unfortunately, these changes do break our little promotion trick from before. Fortunately, pawns have a limited range of movement which can be expressed by a mere 3 bits, leaving the remaining 2 bits to accomodate promotion. Putting everything together, we need 4 + 5 = 9 bits to convey every legal move in any chess position. But we can do better!

The endgame

At this point, you may wonder, how much better? Well, the maximum number of legal moves in a chess position is 218 (proof by Tobs40). This gives us a theoretical lower bound of log2(218) ≈ 8 bits. In other words, any method we devise must be able to communicate 218 different moves, which requires at least 8 bits.

The above approach requires 9 bits, which means we are only one bit removed from the theoretical minimum. Now, there are some ad hoc modifications we could make to shave off one bit. For example, if we allow variable-sized encodings, only 4 bits are necessary to uniquely identify the destination square (2^1 + 2^2 + 2^3 + 2^4 = 30 > 27). While this works, I prefer to reserve such tricks for Part II. Therefore, I came up with a more elegant solution.

The core idea is to produce a list of all legal moves in a given chess position. To communicate a move, it suffices to transmit its index in the list. All that remains, then, is a method to enumerate the moves in a reliable and consistent manner such that both the player and the relayer obtain the same list. Below is a straightforward proposal of such a method:

1. The player scans the board in a pre-defined manner, e.g. from left to right and from top to bottom.
2. Whenever a square contains a movable piece, the player generates all legal moves for that piece and numbers them in a pre-defined manner (cf. the figure above), starting at 1 if it is the first piece or resuming the count from the previous piece.

The above procedure produces a list in which every legal move is assigned a unique number. Note that the list is guaranteed to be less than or equal to 218, since that is the maximum number of possible moves in a legal chess position. Consequently, we can now express every legal chess move in any position with only 8 bits of haptic feedback. But we can do better! Well, not in theory, but in practice we might. For that, however, you will have to wait for Part II.

I do have some bonus facts for you.

• Nenad Petrović already composed a chess position with 218 possible moves in 1964.
• The Rutherford code transforms chess moves into Latin words. Moreover, it allows you to transmit two moves at once, useful if you are cheating in a simultaneous exhibition or if you are communicating your moves by telegram through the 19th-century British Post Office.

That is all I have for you today. Thank you so much for putting up with all the cheeky puns and I hope you have a vibrant day!
Panda <3