Asking a Quantum Computer To Learn Chess
and waiting for its answer
For most people, quantum computers still are the next magical thing. A thing that is supposed to solve all our human problems. To prevent us from climate change, find new drugs, and predict whatever one wants to predict.
For a few people, quantum computers are more. A set of tools that classical computers can not offer. A challenging research landscape that still lives through its early days and needs creative ideas to find its fundamental applications.
For these people, the QHack event has been organized. A mixture of relevant talks on the topic of Quantum Machine Learning (QML), numerous challenges concerning basic and more sophisticated applications, and finally an open challenge that is hoped to yield new and creative ideas in the field of QML.
For this challenge, my teammate and I asked a quantum copmuter to learn chess. The process consist of three major parts.
- Initialization. Telling the quantum computer what the current chess board position looks like.
- Variational Circuit. Ask the quantum computer to make a choice between all legal moves.
- Training. Help the quantum computer to make better choices and eventually learn chess.
Initialization of the chess pieces
First things first, we have to tell the quantum computer about chess. Unbelievably, it never heard of it. Well. What does the board look like? Which pieces do exist? Which pieces are worth more than others and how do they differ? To be honest, I probably have to tell you as well.
That is not because I don't think you know the rules of chess. It is because I think you don't know the rules of Microchess. The board does not consist of 8x8 squares but 5x4 squares. We decided to play this type of chess because we identify each board's square with a quantum computer's qubit. As these are rare and, more importantly, very expensive to simulate on a classical computer we went for as few as possible.
In Microchess, all pieces from the standard chess game (except the queen) are used once. That makes five pieces with different value: king (∞), rook (5), knight (3), bishop (3) and pawn (1). On a classical computer it wouldn't be possible to differentiate more than two pieces on one bit because a bit only takes one of the discrete values 0 or 1. In contrast a quantum bit (qubit) can take infinitely many states. These states can be represented in spherical coordinates, namely states on the Bloch sphere.
Overall, we have to define 11 different states to represent any possible piece on a single square and thus, the complete 5x4 board with 20 qubits. The 11 states represent the 5 different pieces of the player, the 5 different pieces of the opponent and finally, the empty squares. The sketch above shows the qubit's state depending on the piece it represents. Note that the closer the state (arrow) to the respective pole the higher its value.
Variational circuit
The quantum computer now knows the pieces' configuration on the chess board. It is embedded into the states of each qubit. Now we want the quantum computer to make a choice. How does this work? As already said we have to ask him. Unfortunately a quantum computer doesn't speak English or German. Neither understands a quantum computer the language of classical computers. We can ask questions only in the language of quantum operations (words) to build up full quantum circuits (sentences). And we can listen to its answers in the form of measurements (Yes or No).
It's sad, isn't it? One qubit can represent infinitely many (in our case 11) states but all it has to say is Yes or No? It's true however. And we have to deal with it. Thats why we have to ask pretty good questions and listen to the answers carefully.
We ask our question in the form of multi-layer variational parametrized circuits consisting of two major parts. Without going into too much detail…
Discussion circuit. The first part consists of operations that entangle the qubits with each other forcing the quantum computer to consider the relations between neighbored squares and its pieces. As you surely can tell. That's pretty import for playing chess.
Yes or No. The second part helps the quantum computer to successfully answer the question in a simple Yes or No manner. We entangle the qubits of all squares with our one and only measurement qubit. This way, the quantum computer passes all the gathered information into our measurement qubit.
Answer. Finally, by measuring the state of the measurement qubit according to the (caution: technical term) PauliZ matrix we get our final answer. Yes or No. Depending on the answer we want the quantum computer to evaluate and decide which of all legal moves it wants to play. Mostly there are many more than one or two legal moves. Therefore a Yes or No answer is not enough for our purposes. But with a simple trick we get the quantum computer to tell us more. We just ask it a dozen of times. And tadaaa — the answer's probability tells us which move seems to be the best.
Training
As humans, a quantum computer doesn't play chess at a grandmaster level by birth. Humans have to train very hard to become better and ultimately beat their opponents.
On the one hand, they train by thinking of possible moves and evaluate which advantages and disadvantages every move has. They rank the different moves by value and build up a set of desired moves in their head. During time humans change their thinking and tend to come up with the better moves more often (supervised learning).
On the other hand, they train by playing against other players. Sometimes they loose. Sometimes they win. A player becomes better by replaying winning moves of successful games and avoiding loosing moves of unsuccessful games (reinforcement learning).
We try to replicate both human training methods when training our quantum computer .
Supervised learning. We define a rather easy success metric for each legal move and train our variational quantum circuit to choose the best move, respectively. For this, we optimize the parameters which define the operations within our parametrized circuit to yield the best possible result. (We do this by an optimization technique called Gradient Descent).
Reinforcement learning. The problem with supervised learning is that the student (quantum computer) can only become as good as its teacher (quantum nerds, yes, but chess newbies as well). We want the quantum computer to be better than us. To beat us. So we can start learning from it. Thus, we let the quantum computer play a slightly modified version of itself. That way it (hopefully) never stops learning as it either loses against itself or wins. Either way, it learn to play better next time.
So we asked the quantum computer an easy question. Which move would you play? We translated the question into its language. We even worked hard to enable the quantum computer to answer our question in its weird Yes or No manner. However, it seems to need a little bit more time to practice.
It is shy. It doesn't want to blurr out the wrong answer. And that's fine. We will wait. And we will be patient. Good luck our dear friend. We are looking forward to your answer. And we will provide you with better methods and maybe even better opponents along your way.
If you want to learn more, check out the GitHub repository here.
