Why Is This Game Hard?

In the previous post we introduced the Integer Factorization game and also provided a JavaScript implementation so that you can actually play it online. We made the claim that this game is as hard as factorizing integers. In this post we'll show why this is the case and also show how to build hard to solve initial positions.

Each position encodes a (move invariant) number

Recall that the goal of the game is to reach a final position from an initial one by moving tokens on the top-left bottom-right diagonals (the "blue" moves) or duplicating them on the next-higher diagonal (the "red" moves). For a given position let's assign numbers to all diagonals as shown in the following image:

and then compute the "number" for this position by assigning to each token the value of its top-left bottom-right diagonal and then summing all token values. For example the above position's number is 1 + 4 + 8 + 64 = 77. It should be clear that moving a token on the same top-left bottom-right diagonal (the "blue" move) will not change this value. The "red" move maintains this number, too. For example, replacing the token on the diagonal "8" with two new tokens on the "4" diagonal will keep the invariant: 1 + 4 + 4 + 4 + 64 = 77.

The connection with the binary multiplication

In the following image you could actually see an initial and a final position that have the same invariant number:
1 + 4 + 8 + 64 = 1 + 2 * 2 + 2 * 4 + 2 * 8 + 16 + 32 = 77.


You might also observe that 77 = 11 * 7 and this equality in binary is 1001101 = 1011 * 111. If we shift the rows to left until diagonals become columns, as shown in the following image

should be relatively easy to see that the tokens in the final position are actually depicting the  1011 * 111  binary multiplication method taught in school:

  x 111

The conclusion

Based on the above observations we figure out that solving a game position is equivalent to factorizing the corresponding position's number. What we actually do when playing the game is the reverse of the binary multiplication method taught in school: we start with a position encoding a number in binary, for example 1001101, and we try to move or duplicate the tokens to arrive to a position representing some binary multiplication, for example 1011 * 111.

Hard initial game positions

Obviously the game as implemented here is not that difficult to solve as we cannot have initial positions encoding numbers larger than 215 - 1. Solving positions on larger boards is a different problem though. At the time of writing there is a $200,000 cash prize for factorizing this RSA-2048 number:

RSA-2048 = 2519590847565789349402718324004839857142928212620403202777713783604366202070

We can encode this number as an initial game position by using a chess board of size 1025 and, based on the fact no one managed to factorize RSA-2048 yet, this game position should be hard to solve.
But why is integer factorization a hard problem? We will discuss this topic in our next post.