Building a Quantum Nim Game
Introduction
Nim is a math game where two players take turns removing objects from piles. Each turn, players remove at least one object, and they can move multiple objects if the objects all come from the same pile. The goal of the game is either to be the one to take the last object or to force the other player to take the last object.
Nim misère is the version where the player who removes the last object loses. In this article, we will be discussing how IBM Quantum Computer (or Simulator) can play the Nim misère game.
During 1939–1940 New York World’s Fair, the Westinghouse Electric Corporation presented Nimotron, an electro-mechanical machine that played Nim. That machine had four rows of seven light bulbs in front of the player, as well as on four sides of an overhead cube. You could say that the Nimatron was one of the first computing devices dedicated to gaming. 80 years later, we live in a pioneering new era of computation: the era of quantum computers. We have an excellent opportunity to develop a quantum version of the Nimatron.
In this article, we will discuss he mathematical framework used by quantum computers to play Nim. We will also demonstrate the quantum computer’s gameplay using a UI similar to Nimatron developed using pygame (python library).
2. Classical Nim Strategy
2.1 Winning move possible
Consider the following scenario of the Nim game. There are 1,3,4, and 7 objects in piles numbered 1,2,3,4, respectively:
+ - - - - - - + - - - - - - - - - +
| Heap Number | Number of objects |
+ - - - - - - + - - - - - - - - - +
| 1 | 1 |
| 2 | 3 |
| 3 | 4 |
| 4 | 7 |
+ - - - - - - + - - - - - - - - - +Let heap denote the array where heapᵢ denotes the number of objects present in the ith heap. For the example shown in the above table, heap = [1,3,4,7]
To find how many objects to remove from which heap, we perform the following steps:
- Step 1 — Calculate nim sum
nim_sum = heap₁ ⊕ heap₂ ⊕ …. ⊕ heap_n, where ⊕ is a logical XOR operation.
For the example above, nim_sum = 1. - Step 2 — Perform XOR between nim_sum and heap which results in a new array xor_heap
xor_heapᵢ = heapᵢ ⊕ nim_sum.
For the above example, xor_heap = [1⊕1,3⊕1,4⊕1,7⊕1] = [0,2,5,6] - Step 3 — Compare heap and xor_heap. The idea is to leave the board state with nim_sum=0 for our opponent. If xor_heapᵢ < heapᵢ then it is possible to remove (heapᵢ-xor_heapᵢ) objects from heapᵢ.
For the example above, heap₁, heap₂ and heap₄ are reduced from 1,3,7 to 0,2,6 respectively in xor_heap.
Therefore, there are three possible moves we can make against the opponent for the given example, which are [1,3,4,7] ⟶ {[0,3,4,7],[1,2,4,7],[1,3,4,6].}
It can be observed that nim_sum for all {[0,3,4,7],[1,2,4,7],[1,3,4,6]} is 0 - Step 4 (Misère step) — Instead of going to Step 3, this step is performed for specific board states satisfying the following conditions:
– Condition 1: heapⱼ > 1, for any one j ∈ [1,n]
– Condition 2: heapᵢ = 1 or 0, ∀ i ∈ [1,n] and i ≠ j
In this case, remove objects from heapⱼ so that opponent is left with an odd number of heaps with one object left in them.
For example,
– [0,0,3,0] ⟶[0,0,1,0] i.e. remove 2 objects from pile 3
– [1,1,2,0] ⟶[1,1,1,0] i.e. remove 1 object from pile 3
– [1,1,4,1] ⟶[1,1,0,1] i.e. remove 4 objects from pile 3
2.2. Winning move not possible
Consider the following case where our opponent leaves us with a board with 𝑛𝑖𝑚_𝑠𝑢𝑚=0
+ - - - - - - + - - - - - - - - - +
| Heap Number | Number of objects |
+ - - - - - - + - - - - - - - - - +
| 1 | 1 |
| 2 | 3 |
| 3 | 5 |
| 4 | 7 |
+ - - - - - - + - - - - - - - - - +Since, nim_sum = 0 already, heap = xor_heap, as a result, no heaps can be reduced by the logic mentioned above. One of the logical steps is to leave our opponent with a maximum number of objects on the board, i.e pick up one object from any one of the piles. Therefore, [1,3,5,7] ⟶ {[0,3,5,7],[1,2,5,7],[1,3,4,7],[1,3,5,6]}
3. Quantum Nim Strategy
- We implement the quantum version of Nim (QNim) using dynamic circuits. Reducible heaps and the amount of objects to be reduced is calculated using the classical strategy shown above.
- We create superposition in the cases where multiple moves are possible, and the result of the measurement of superposition dictates the quantum computer’s move.
- We create superposition by applying Hadamard gates, and the amplify the amplitude of the relevant moves using Grover’s diffusion algorithm.
- Arithmetic operations are performed using the QFT (Quantum Fourier Transform) adder.
- We use dynamic circuits because of their shorter depth. The static circuit would become very large and measurement results would be vastly skewed due to noise caused by the large depth and a large number of qubits.
3.1. Data Encoding
Similar to the Nimatron, we are implementing QNim using 4 configurable rows, with a minimum of 1 to a maximum of 7 objects allowed in each row. Therefore, 3 bits will be sufficient to represent the number of objects present in any row, 3 bits for the address which denotes the row to pick an object from (ideally, 2 bits should have been enough, but due to the nuances of Grover’s algorithm we require 3 bits) and 1 bit used as a flag. Hence, a 7 qubit quantum circuit is enough to implement a mathematical framework of the QNim game.
- Quantum registers:
– 3-bit address register to store the address of heaps
heap₁ ⟶|001⟩, heap₂ ⟶|010⟩, heap₃ ⟶|011⟩, heap₄ ⟶|100⟩
– 3-bit register to store the number of objects to remove from heaps
– 1-bit flag register used for diffusion operation performed on the address register - Classical registers:
— 3-bit register to measure address bits
— 3-bit register to measure the number of objects to remove from the measured heap address
3.2 Quantum Nim Strategy
There are two possible cases when it is the quantum computer’s turn to play: a single winnable move is possible, or multiple (winnable or not) moves are possible.
- If only a single move is possible, the address of the reducible pile, which is obtained from the classical Nim strategy, is directly encoded into the address register. The amount to reduce, which is also calculated classically, is encoded into the corresponding register.
- If there are multiple moves possible then:
— We place the address register into a complete superposition by applying Hadamard gates
— The Flag qubit is converted into the -|1⟩ state by applying the X gate first and then the Hadamard gate
— Piles that are reducible are marked using an oracle, which uses classically obtained results to mark the corresponding addresses
— Amplitude of marked states is amplified
— The amount of objects to be reduced is added to the corresponding register using a controlled QFT adder, control being the marked address states
We measure the quantum circuit, and after some post-processing, the results we obtain will be quantum computer’s move against its opponent.
3.3. Results
Let’s continue the example from above where heap=[1,3,4,7], and it is the quantum computer’s turn to play with this board state.
The histogram above, obtained after measuring the circuit on IBM Quantum Simulator, shows three possible moves for the quantum computer — their corresponding states have amplitude significantly greater than the other states.
001 100, 010 100, and 100 100 have the highest amplitudes. The first three numbers of each bitstring denote the address of the pile for the quantum computer to remove from, i.e. 001,010,100 correspond to piles 1,2 and 4, respectively. The latter three numbers denote the number of objects to reduce, here all of them have 100. This is actually in a reversed state, and therefore represents one object to pick from piles 1,2 or 4.
The quantum computer will play the move that has the highest count after measurement. In this case, 001 100 has the highest count, therefore it will pick 1 object from pile 1.
Resources and Acknowledgement
This project was implemented as a part of the Qiskit Advocate Mentorship Program (QAMP) Fall 2022 under the guidance of James Weaver from IBM Quantum. I am thankful for all the support and guidance he provided me throughout the program.
You can find the code to develop mathematical framework resources in this repository. Additionally, here is a link for the pygame UI and chat UI.
