QNim
JavaFXpert opened this issue · 12 comments
Description
One of the first games in which a human played against the computer is Nim, so it is an interesting and fitting game to implement on a quantum computer. This Wikipedia article describes the game, strategies and variants: https://en.wikipedia.org/wiki/Nim
Deliverables
A game with a user interface conducive to a human playing Nim against an IBM Quantum computer, both a simulator and real device. The UI could be implemented, for example, as ipywidgets in the IBM Quantum Lab. One idea would be to create a UI or even build a device that emulates the Nimatron, which was first exhibited in 1940 at the New York World's Fair.
Solution requirements
- The human and QC (quantum computer) will play according to the rules for Nim misère play, in which the goal is to ensure that the opponent is forced to take the last remaining object.
- The starting game configuration will be four piles, each consisting of zero - seven objects. The default will be one, three, five and seven objects in the four piles, but must be configurable.
- Either player may make the first move.
- The QC's gameplay strategy must be based upon mathematical theory for Nim, played as a misère game. This strategy would be implemented when dynamically generating a circuit based upon the remaining piles of objects each time it is the QC's turn to play.
- The QC's move is based solely on measuring the generated quantum circuit. It is permissible to specify multiple shots in the measurement, and to take the most frequently occurring result. Whenever mathematical theory for Nim indicates that more than one winning move is available, the quantum circuit must make each of those moves equally likely to be the result of measuring the circuit.
- If the result of a measurement is a nonsensical move for the QC, then the QC automatically loses the game.
- The UI must indicate which player won the game.
Stretch goals
- Build a device, perhaps using a Raspberry Pi, switches and lights, that serves as a UI for this Nim game. The quantum circuit could be run locally using a Qiskit BasicAer simulator, or on IBM Quantum hardware.
- Compute the QC's move by using Grover's algorithm.
- Create a quantum circuit that implements mathematical theory for Nim, but isn't dynamically generated. The input to this circuit would express (perhaps using X gates) the remaining piles of objects for the QC's turn, but the circuit itself would not change, and would implement the QC's strategy regardless of input. Because of circuit depth, this circuit would currently only be practical for running on a quantum simulator. Also, it may not be practical to implement all of the requirements in the previous section (e.g. playing as a misère game, or making multiple winning moves equally likely measurement results).
Mentors details
- Mentor 1
- Name: James Weaver
- GitHub ID: @JavaFXpert
- What they do: Quantum Developer Advocate
Number of mentees
3
Type of mentees
- Mentee 1
- Required:
- Interested in game development
- Nice to have:
- Experience in game development
- Knowledge in quantum information
- Required:
- Mentee 2
- Required:
- Proficient in Qiskit
- Nice to have:
- Experience in Qiskit open source contributions
- Required:
- Mentee 3
- Required:
- Proficient some form of UI development
- Nice to have:
- Experience in ipywidgets
- Experience in creating hardware UIs (e.g. switches, lights, raspberry pi)
- Required:
Hi @JavaFXpert
Ritu here. This seems really interesting to me. Can we chat more about this project?
I'm very interested in this project, As I have a background in Game development and as it is a major in mu university. I would love to join this project as a mentee
@ritu-thombre99 and @hamzakamel1 Please reply to my message on Slack on when we can meet to discuss details of the project.
Please add your Checkpoint 1 presentation materials.
Link to the jupyter notebook - QAMP Checkpoint 1 - QNim
Checkpoint 2 update
Mathematical framework for QNim was completed for checkpoint 1, which included strategy development for quantum computer to play game of Nim against a human or a classical computer. A basic prototype UI using Kivy framework in python was also developed for QNim during checkpoint. Kivy framework is discontinued as it has very limited frontend configuration capacity. Since checkpoint 1, pygame, which is a game development library in python, is used to create a visually appealing UI with a retro theme. Nim board consists of 7x4 grid of bulbs similar to Nimatron, which was displayed during 1940 New York fair. The new UI has the following functionalities:
- Home page
a. Start new game button
b. Continue saved game button
c. Quit button - Configuration page
a. User can select how many bulbs they want to be in an on state. User can select from minimum of zero to maximum of seven bulbs for four different rows. At least one bulb (from 28 present on the board) should be in an on state in order to start the game. Default board configuration is 1,3,5,7 on state bulbs for the four rows.
b. User can select the turn i.e. which player will play first (either user themselves or quantum computer) - Game page
a. Turn button (selecting button with quantum computer image will trigger quantum computer to play the next move)
b. Game board which has bulbs in on/off state based upon selections made on configuration page. Bulbs in on state can be turned off by pressing them.
c. During quantum computer’s turn, an emoji animation will be displayed to show if quantum computer is happy or frowning depending upon whether it can play the winnable move.
d. Back button (current game state will be saved to play later)
e. Quit button
Plans for checkpoint 3:
Currently it is difficult to implement asynchronous behaviour in pygame. As a result, pygame will not register any clicks when quantum operations are happening in the background during quantum computer’s turn. This leads to game window becoming non responsive until quantum operations are finished. This may not be noticeable if local qasm_simulator is used as a backend, since it is local and faster. But the lag will be considerable if one wants to play against ibmq_qasm_simulator or a real IBM quantum computers.
To deal with this issue, we are planning to implement QNim as a web application through a client server architecture. Server will be implemented using flask REST API which can be called by a client. This REST API will take in the game board state and send the quantum computer move to client in a JSON format. Client will be developed using python frameworks (flask or Django) which have AJAX functionality to handle the required asynchronous behaviour of the QNim game.
Visual representation
Mathematical framework:
Experiment results:
Gameplay video - https://youtu.be/vqE8HICiBqA
QNim.gameplay.mp4
Game screenshots :
Home page:
Home page with current saved game:
Configuration page:
Player turn:
QC turn:
Player won:
QC won:
@ritu-thombre99 - please upload your Final Showcase presentation materials, and if needed, update the project Title and/or description.
Final checkpoint update
UI using pygame for QNim was completed for checkpoint 2. Since checkpoint 2, QNim is implemented in Roblox. The player's character enters the world and a QNim board is booted, which has a grid of 7x4 neon pink lights. During the player's turn, lights which can be switched off are neon green. To call the quantum computer to play, the player can type qc turn in the chatbox.
A REST API is created using flask which takes in the current board state through parameters in the URL and returns the quantum move. Lua code in the roblox will call this API using GET request when it is QC's turn to play.
Initially API was hosted locally and board state was passed in headers as follows:
Currently, the API is hosted on the Anvil server and can be accessed publicly. This version of API takes in the board state as params in the URL as follows:
Roblox UI:
Future plans:
- Implement a two-player version
- Create a quantum computer NPC represeted by a robot, which can interact with players, similar to emoticons showed in pygame version
- Using openai API and gpt, let player interact with quantum computer NPC. The player can tell QC NPC their move, for example if a player wants to turn off 3 bulbs in row 2, they can type it in the chat box and QC NPC can perform this action for the player. So the player can have two ways to play the game, using chatbox or button events (QNim board)
- As soon as the player is booted into the world, QC NPC can provide instructions on how QNim is played and ask the player if they want to start the turn.
Congratulations on completing all the requirements for QAMP Fall 2022!! 🌟🌟🌟