100902-selim-akl-alice-wismath-by-kristyn-wallace

In the quantum chess computer game created by computer science student Alice Wismath (right), a piece that should be a knight could simultaneously also be a queen, a pawn or something else. Wimath based the game on an idea proposed by computer science professor Selim Akl, left. ((Kristyn Wallace/Queen's University))

The unpredictable nature of quantum physics has been mimicked by Queen's University computer scientists to invent a new version of chess.

In the quantum chess computer game created by undergraduate computer science student Alice Wismath, a piece that should be a knight could simultaneously also be a queen, a pawn or something else. The player doesn't know what the second state might be or which of the two states the piece will choose when it is moved.

"It was very weird," said Ernesto Posse, a Queen's postdoctoral researcher who took part in a recent "quantum chess" tournament at the university in Kingston, Ont. "You only know what a piece really is once you touch the piece. Basically, planning ahead is impossible."

Quantum quirks

According to quantum physics, very small particles behave according to principles that give them characteristics very different from the behaviour of larger objects. Here are a few properties of those quantum objects:

  • Quantum superposition: A quantum object may exist in multiple states at the same time.
  • Wave function collapse: An observer's interaction with a quantum object in a superposition of states, such as an attempt to measure its position or momentum, will make it "collapse" into a single state.
  • Quantum entanglement: Two or more quantum objects may be linked so that any change to one is immediately experienced by another, no matter how far apart they are from one another.

Wismath wrote the game based on ideas proposed by Selim Akl, a computer science professor at Queen's, in a paper that will be published in September in a special issue of Parallel Processing Letters. Akl is editor-in-chief of the journal, but not that special issue.

Computers can search all possible outcomes of all possible moves in conventional chess and beat even top human players, so Akl wanted to make the computation more difficult.

He decided to have the pieces mimic the behaviour of very small particles such as atoms and electrons, which follow the laws of quantum mechanics. According to the principle of superposition in quantum physics, such particles can simultaneously be in multiple states at once, but collapse into a single state when an attempt is made to measure their position, momentum or some other aspect.

"I thought of a game that provides the same kind of unpredictability to both players," Akl said. "The computer cannot possibly search all the possibilities because we can show there are an uncountable number of them."

Wismath, who is starting the fourth year of her computer science degree program in September, had to decide how the computer would deal with that. It was "pretty hard," she said.

tp-100902-quantum-chess

'You only know what a piece really is once you touch the piece,' researcher Ernesto Posse said after he tried the game. 'Basically, planning ahead is impossible.' ((CBC))

Normally, computers create "trees" of possible outcomes for each move, looking many moves ahead.

Each outcome is scored based on how many pieces each player has left on the board and their positions. The tree for quantum chess ended up being much more confusing, Wismath said, especially since the piece on any given square could become a pawn or a bishop or a knight.

"How do you score it when you're not sure what it is?"

She decided to limit the computer's calculations to the next possible move and the human response immediately after that.

Wismath also chose new rules to make the game workable with its quantum twist. For example, her version of quantum chess requires a player to capture the king, which never changes to another piece, instead of merely delivering a checkmate. Also, pieces change states only when they land on black squares.

Posse, who has been playing chess for 15 years, said the new game doesn't much resemble the classic contest he likes for its tactics, strategy and history: "I would say it's 'chess-inspired.'"

He was one of the winners in the tournament , but credits luck.

Room for strategy

"You try to apply some ideas of normal chess, but they rarely work out," Posse said.

But Chris Perez, a master's student in computer science who also took part in the tournament, said "there's still definitely a lot of room for strategy."

For example, he said you can use your memory to deduce which pieces are still hidden on the board and plan your moves to maximize the chance of turning a weak piece into a better one.

"Adding an element of chance makes things more fun," he said.

Perez hopes to help Akl create a non-computerized version of the game.

Akl plans to use the new game to teach students about concepts in quantum physics.

And he's already planning ways to make the game more complex, such as changing the probabilities for each state so they aren't exactly 50-50 and including rules to mimic other quantum physics concepts, such as entanglement.