Connected Sums Game

Connected Sums Game is a game I inveted for experimenting with web development frameworks. I have build identical implementations of this game with React, Angular 4, Scala.React and Scala.Angular. Building identical functionality with different frameworks is very useful to get insight in the merits of particular frameworks. The results of the comparison can be found here. The game however is interesting in its own right and therefore I will present a detailed discussion of the rules of the game, of mathematical properties of the game, and of strategies to play the game. Playing the game right away can by clicking here. Source code of an implementation of the game with React can be found here.

The game board consists of a configurable number of cells, configurable at the start of the game between 2 cells and 5 cells. Each cell contains one number, in the center, and four buttons, in the corners. The top two buttons are labeled + ; with these buttons the cell value can be incremented by one. The bottom two buttons are labeled – ; with these buttons the cell value can be decremented by one. The initial values of the cells are randomly chosen from a configurable value pool. The objective of the game is to reduce all cell values to zero.

The game would not at all be interesting if each of the cells could be incremented or decremented independently. The interesting factor in the game is that all cells are connected. If one particular cell is incremented or decremented by one with one of the cells buttons, all the other cells are incremented or decremented by the value of the cell in which the button is pressed. So pressing an increment or decrement button will affect all cells. The cell in which the button resides is incremented or decremented by one. All other cells are incremented or decremented by much larger values, depending on the current value of the cell in which the button is pressed. There are two plus buttons and two minus buttons in each cell. The difference is the relative order of increment / decrement the cell itself and adding / subtracting the rest of the cells. With the plus and minus buttons on the left side of the cell, the cell value is first added / subtracted to the rest of the cells, and after that the cell value is incremented / decremented. With the plus and minus buttons on the right side of the cell, the cell value is incremented / decremented first, and after that the incremented / decremented value is added / subtracted to each of the other cells.

Can it be fun to play a game with these rules unless you are a calculation wizard? Yes it can. You can play this game without performing any mental arithmetic at all. The only necessary thing to do is inspecting which values are positive and which negative, and to determine which value is the biggest positive, the smallest positive, the biggest negative, and the smallest negative one. Strategies can be defined in terms of tests like: “are there positive values?”, “are there negative values?”, “Which positive value is biggest?”, etc.

Fiddling with the game for a while gives one quickly a basic strategy to solve the problem. Pressing the left side plus and minus button of one cell in succession, order irrelevant, gives the net result of the cell value being unaffected, and the cell values of all other cells decremented by one. Doing the same with the right side buttons leaves the cell value unaffected again, and the cell values of all other cells incremented by one. It is easy to solve the game by cleverly combining a number of these “steps”, consisting of pressing the related plus and minus buttons in succession. However, this is a very inefficient strategy. This strategy is essential linear, meaning that if the size of the initial playing board is twice as big, the number of steps to solve it is also roughly twice as big. The size of the initial board is something that can be defined in various ways, but the definition that captures the real complexity of the problem to be solved best is the measure defined as the maximum of the absolute values of all cells.

It appears that solving the game is possible in logarithmic time with regard to the just defined complexity measure. If the complexity measure is N, solving the game can be done:

  • For 2 cells in about 8 log10 N steps.
  • For 3 cells in about 6 log10 N steps.
  • For 4 cells in about 13 log10 N steps.
  • For 5 cells in about 18 log10 N steps.

There is an optional hint mechanism build in the game that approaches these figures. For human players it is difficult to perform as good as or better than the hint mechanism.

There is an easy way to compute an optimal strategy for each set of cell values, but this is not feasible for cell values bigger than about 10 (in absolute sense). The algorithm is easy and straight forward. Construct a table that can hold entries for each number combination. Start with the combination of all zeroes, the final stage of a solved game. Now add entries to this table by backward stepping to entries that are one step removed from the final stage. Then proceed with adding entries to this table by backward stepping from entries one step removed from final stage to entries two steps removed from final stage. And so on. Each additional step starts with all entries that were reached in the previous step and adds entries one step further away from the final stage. If a certain number combination has an entry, this is the entry for the shortest path. This entry should not be replaced by a different entry with same or larger number of steps to final stage. Be sure to include in each entry a direction where to go for the shortest path to the final stage. For each additional step, the number of computations is the number of entries of the previous step times the number of buttons in the game, that is four times the number of cells in the game. The number of computations is obviously exponential in the number of steps. Notice that many computations will lead to existing entries, signifying that there are multiple paths from a certain number combination to all zeroes. We are only interested in one of the possibly multiple shortest paths. This means that the number of computations for all entries reachable in N steps is far less than the sum of B ^ n, with B the number of buttons in the game and n between 0 and N (inclusive). For 2 cells (8 buttons) the number of entries for 0 up to 12 steps is 200278, whereas 8 ^ 12 = 6871947674.