Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Quantum chess

  1. Dec 28, 2003 #1
    Does anybody in this forum play chess? Or have an idea of how computer chess programs work?

    Even the very best of them, and lately they have gotten very, very good, work more or less the same way, and always have. In those algorithms, after the move generators and transposition tables and search pruning, are evaluation functions that I find arbitrary, and based on human judgement applied in domians without real theoretical justification.

    I have a different idea, but no clue about how to actually go about it. I wonder if it wouldn't be possible to model each chess piece as some kind of a quantum particle. The rules of the game would be entirely contained in these models (such as en passant, castling restrictions, etc).

    Then, in order to determine the best move, perhaps it wouldn't be necessary to look ahead at all. Perhaps it would only be necessary to allow the wave states of the pieces to interact and solve for the maximum overall energy for the right move to present itself.

    How would one go about creating a quantum wave function for the behavior of a chess piece? Is it possible?

    This idea might not work at all. Probably wouldn't. But if it does work, it might work very well. At least it'd be different, qualitatively different. And, it might be fun.

    And ideas?
  2. jcsd
  3. Dec 29, 2003 #2


    User Avatar

    Well, I lost you after does anyone play chess.

    I play chess.
  4. Dec 29, 2003 #3


    User Avatar
    Science Advisor

    I suppose you could consider every possible situation on the board as a quantum state and assign a value to that state, and have the computer move so as to attain the highest value state, but it would be judgemental as well. You could even break it down to smaller components, and consider things as independent. You could assign values to rooks on open files, doubled rooks, pins, forks, doubled pawns etc. But in the end, it remains judgemental.

    In order to avoid human judgement, the positions would need to be evaluated by exhaustive means. Each position would be played out in every conceivable way. That would take some computer. It would save the computer computation time during the game itself, but the computation ahead of time would be monumental.

    Last edited: Dec 29, 2003
  5. Dec 29, 2003 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    In principle, it would be possible for the computer to discover the heuristics for itself...
  6. Dec 29, 2003 #5
    That's exactly what I'm trying to avoid.

    See, I play chess. I'm no expert; actually I'm a class A player, more than a hundred points below expert level. What I like the most is to play blitz, that is speed chess (each side has five minutes to complete their game or lose be forfeit). Especially in blitz, but it happens in slower tournament play as well, it's good to recognize the best move instantly. Quite often, the best move is unmistakable.

    A psychological study of grandmasters done some time ago (I think by a Danish reseacher named deGroot) indicated they do not use a heuristic thinking ahead process (that is, they do not pick their moves by saying "if I do this, then he can do that or the other things, and then I might do this or that or that...). Rather, they only tend to look one move ahead, to the move they "want" to play, and mostly only think ahead to check that they're not falling into some overlooked tactical trap. But in general, their thinking is much more strategic and instinctual. So, my intent is to provide some kind of physical justification for defining that instinct.

    When I teach people to play chess, I stress that it's much more important to think backwards than it is to think ahead. Ask yourself "Why did my opponent play his last move" rather than "what sequences are possible from here?"

    Getting away from chess for a moment, let's consider a simpler problem. Say, an electron approaching a positively charged crystal. Hopw does the electron "know" how it's suppossed to move? If there's a crack in the crystal, the electron doesn't know that as a unique situation. The electron doesn't look ahead and say "if I bounce of that atom and then fit between those atoms I'll end up there." In fact, it really doesn't sense any of the environment except it's own immediate vicinity. It simply operates under it's own rules of interaction based on the cumulative effect the entire system creates in it's local field. This is entirely determnined by the electron's wave state and the potential field in the space around it. And of all of the possibel paths that it could follow, it always takes the one of lowest energy. And the potential state around the electron is a product of the waves states of all the separate particles in the crystal, right?

    So, let's say we could write a quantum model for a rook like we can for an electron. Since the rook can only move in straight lines along ranks or files, maybe it has some kind of intrinsic polarization. Since it's blocked by it's own pieces, maybe there's some kind of Pauli exclusion principle that applies. Etc... Would the minimum energy path for the rook represent it's best move (or maybe that'd be a maximum)? Maybe it captures by some kind of anniahilation transformation? How about a pawn? Maybe it's wave state decays a bit after it's first move, because it can only move one square after it's off it's original square.

    It might be a crazy idea, almost certainly is, and it might not be workable at all. But I have a feeling that if it does work, it might work spectacularly well. That's what's driving my speculations.
  7. Dec 29, 2003 #6


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It is not clear that this thread has much to do with Quantum Physics. Moving to "General" Perhaps should have put it in one of the technogly forums.
  8. Dec 29, 2003 #7


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Dutch, De Groot is a Dutchman from The Hague

    De Groot, AD (1965) Thought and Choice in Chess. The Hague: Mouton
    Unfortunately.. that's all I've got to add..
  9. Jul 2, 2007 #8

    Great ideas, Bob. I've been thinking much along the same lines myself.

    I've studied a little bit of quantum information theory and feel like I might have some additional insights to offer here. The advantage of working with quantum information theory is that this abstracts the relevant information-processing concepts away from specific physical implementations - much like modern computer science allows software to be developed independently of hardware specifics.

    Anyhow, the key resource at our disposal in the design of quantum algorithms is entanglement. Specifically, if an output register's state depends on the result of some computation performed on an input register, then measuring the output register's state will collapse the state of the input register to a superposition of only those states which give rise to that output.

    The trick in getting anything useful out of a quantum algorithm is getting desirable states to constructively interfere while undesirable states destructively interfere. So we need to tinker around with the relative phases in our output register such that only those components of the input register which we wish to examine remain in superposition upon measurement of the output register.

    Now let's consider the game of chess:

    1) Every chess position can be uniquely described by the position of pieces on the board, who's to move, the castling status of both sides, en passant status, how many times the position has been repeated (for 3-fold repetition draws), and how many moves have been made since the last pawn push or capture (for the 50 move draw rule).

    2) A game ends when one of the following situations occurs:
    a) no legal moves exist (mate or stalemate)
    b) there is insufficient material on the board for mate (draw)
    c) the same position has been repeated three times (draw)
    d) 50 moves have been made with neither a pawn push nor a capture (draw)

    3) Any position satisfying one of the situations in (2) can be classified into three disjoint sets: white wins, black wins, and draw. Furthermore, we can work our way backwards (as Bob has suggested) from any of these positions and consider which lines lead to which situations given optimal play by both sides (which I will shortly define). We can then place any chess position into one of our three sets, which I shall call W, B, and D.

    4) Optimal play is such that once we're in W, regardless of what black plays, on each move white has a move which keeps us in W. Similarly, once we're in B, regardless of what white plays, on each move black has a move which keeps us in B. Positions in D are a little trickier to assess. Optimal play here would be such that it maximizes the chances for a blunder by the other side.

    5) A blunder is a move which takes us from a position in one set to a position in a different set. Specifically, a white blunder is a move which takes us from W to outside of W; or from outside of B to B. Similarly, a black blunder is a move which takes us from B to outside of B; or from outside of W to W. White can never take us from outside of W to W on his move; Black can never take us from outside B to B on his move.

    OK...so given the above analysis, how can we assign phases to different positions such that positions resulting from blunders (as defined above) destructively interfere? If we could find a way to do this, then we could recurse down all possible games from a given starting position and end up with only positions from those games which remain in the same set as the starting position: W, B, or D. Then looking at any of the final positions that can result will immediately tell us to which set the starting position belongs.

    An oracle which can tell us to which set any given chess position belongs would allow for the construction of an extremely strong chess engine - an engine which never misses a theoretical win and never loses a theoretical draw. Furthermore, even when we're in set D, perhaps we can find a way to assess moves based on propensity for the other side to blunder. But even without this feature, in principle we can still build an engine which never loses and never misses a forced win. Moreover, an oracle like the one I've described might finally provide a definitive answer to the question of whether either side can force a win from the starting position or whether at best only a draw can be forced.
  10. Jul 6, 2007 #9
    Not a bad idea man. Sounds cool. Wouldnt it take an age to solve those equations though?
  11. Jul 6, 2007 #10
    Optimal play would maintain the D rating. For if white could change a D position into a W, it wouldn't be a D position would it? And if white's move changes a D position to a B, then the move isn't optimal. Same goes for black going the other way. So if a position is a D and both sides play optimally, it will stay a D. This same reasoning can be used to show that a W position remains a W and a B position remains a B under optimal play.

    The idea of assuming optimal play by both sides is encoded in an algorithm that is popular in game playing programs called minmax. The idea is that the program will evaluate positions based on the computer making the move of maximum benefit to the computer (the computer's optimal move) while the opponent will make the move of minimum benefit to the computer (the opponent's optimal move).
    Last edited: Jul 6, 2007
  12. Mar 1, 2010 #11
    I've been doodling with high performance compuring (TF+) for a while and simulating QC for just as long.

    Simulating a TTT-playing QC is pretty easy: just 22 qubits or so plays a "perfect" game (but, then, so does a small C program :).

    Playing chess is a bit trickier, but a first cut of a QC playing chess is presently running on my junkbox desktop machine (bought for $300 USD from ebay and various swapmeets).

    It's still rather slow -- despite the box running around 3 TF (what a diff a few years makes to computer h/w! :) -- but manages to do a presentable job against GNU chess (not a very good player, anyway).

    To play chess on a QC you need to work with sets of chess positions. If you have a LOT of qubits you could represent sets of all possible game boards using 768 qubits. Obviously, this is a few too many to even simulate. ;)

    The trick I'm using is to evaluate sets of moves. With 32 simulated qubits you can evaluate all possible sequences of moves from a given position down to around 10 ply. My eval function just "counts" (using repeated quantum "measurement" until we get a sufficiently accurate answer -- a basic statistical procedure) the number of winning vs losing positions resulting from a given move from a given position. C.f. the usual "materiel" eval function in most chess programs.

    When it's tinkered up to run well enough to beat GNU chess at approx the same depth setting I'll let y'all know. But to run it will require some weird h/w, let alone the s/w. :)
  13. Mar 1, 2010 #12


    User Avatar

    Staff: Mentor

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook