Quantum computers and chess

If two quantum computers played each other it is theroatically a draw.

Assuming that these quantum computers can play perfectly there'd be little mistakes as to the outcomes of the opening; the opening used; the form used.

Chess is mostly theory now which is sad however I feel that this theory is mostly irrelevant to the individual that would take that advice.

 

Log in or Sign up to hide all adverts.

That is the natural intuition, but without knowing the whole extensive form of the game there is no real way to prove it. There are sequential two-person zero sum games of perfect information (which chess is) that give a definite win to Player 1 or Player 2 despite the fact that the games take a long time.

To take something simple enough to explain without match or diagrams, a sequential game of Chicken provides a first mover advantage. If you are player 1 and go first, you can choose to rush forward or swerve. If you rush forward, player 2 is left with a choice of rushing forward (causing a crash and killing you both) or swerving (letting you "win" but preserving player 2's life). Assuming player 2 is rational, he'll swerve, so player 1 always wins.

In a sequential version of Rock-Paper-Scissors, there's a second mover advantage.

In chess, it may seem that you can always reorient the board to force a draw, but seeing that you are doing that, it is possible that your opponent's next move can then always reorient it again towards a win. Which result will ultimately pertain can be complex and surprising.

Edit: As a side note, I was hoping to find the extended form of the game "Connect Four" as that is a "strongly solved game" where it has been proven that the player who goes first has an unbeatable advantage if he plays it right. Sadly, my google-fu failed me, likely because the extended form fills a small book.

 

Log in or Sign up to hide all adverts.

This "small book" wouldn't be needed in chess.

Chess theory is pretty well solved already; it is a matter of fitting it all together (finishing it).

 

Log in or Sign up to hide all adverts.

There is no reason to suppose that a quantum computer could cope with the game of chess at all. I am reasonably sure that quantum computers cannot be used for certain types of probems. They are not equivalent to a faster Von Neuman computer with more memory & disk storage.

For all practical purposes, the answer to the following question is no.

Current chess programs use brute force methods, not true logical analysis. Therefore the best current programs do not provide a complete analysis. They might lose when theorhetically they have a winning postion. More likely:They might beat a human playing who has a winning position, but does not make the correct moves.

Even if a computer could do a complete analysis of the game (not at all likely), a human could probably not use the results, nor be certain the the program had no bugs. The best you could do is allow the computer to play the game for you. Would you like to have a decision tree requiring a million tons of paper? Would you like to play the game following such a decsion tree on a computer screen?

I doubt that if-then-else like logic could be programmed for the game of chess. The current programs use a position evaluation algorithm and mini-max logic to choose moves.

 

I seldom play chess but wonder if it is known whether or not white (first to move) has in principle a possibility of forcing a win. I.e. is it within modern computational capacity to play all possible games? I doubt it is. Would it be possible to do that with a "quantum computer"? -I also doubt it as it seems to me all a quantum computer could do would be consider all possible moves in parallel permited with the current board configuration. It could then consider all possible responses to each in parallel, and their responses, etc. but some where there must be huge storage (and some "indexing system" for it) to keep track of this exploding data set or an imperfect evaluation system to terminante the explosive growth of possibilities.

I have a friend who is very good at chess - plays with others in contest on internet etc. has at least 25 books on the subjects etc. He is strongly of the opinion IBM cheated with "big blue" i.e. that yes it evaluated lots of positions but that a human, very skilled, help in the selection of the chosen move. He points out that Big blue was retired immediately after the match and never was its code given out. During the match some irregularities happened. - I forget what they were. It was even suggested during the match that it was not just "big blue" alone.

Anyone know any more on this? or is my friend just part of (or victim of) some anti-IBM conspiracy set/group? Any opinions, more facts? more details?

 

Billy T: I have a fair knowledge of the basic methodology used for Deep Blue, which I think it the correct name rather than Big Blue. I hope the following describes it well enough to make sense. Mini-max strategy is simple when you grok it, but not easy to describe to another person. At least I have had trouble explaining it to intelligent people who probably understood it in spite of my poor description rather than because my description was so clear and precise.

After much experimentation and consultation with master chess players various position evaluating algorithms were developed. Such an algorithm assigns a numerical value to a given configuration of chess pieces. A simple example of such an algorithm would be the following.

• Assign a value to each piece suggestive of its usefulness. Then multiply the value assigned by the number of squares the piece can move to without resulting in an unfavorable exchange of material. Add up the products for both black & white. Then subtract to obtain a single numeric value.

The above at least suggests which player has an advantage in a given position. Far more sophisticated algorithms have been developed for use by Deep Blue.

I believe there are at least three algorithms used.

• One for use immediately after the opening.
• One for use in the middle game.
• One for use in the end game.

Known openings are used for the early moves and special case algorithms are used for various end games.

Given the above, the following illustrates the strategy for one move and a counter move by the opponent (This is called one ply).

• Build a 2D matrix with each cell containing the value derived by the current position evaluation algorithm. Each row corresponds to a possible move by Deep Blue. Each cell in a row corresponds to a possible replying move by the opponent.
  
  Search each row for the worst possible position as indicated by the value assigned to each cell in that row.
  
  Some row has the worst case which is best for Deep Blue when compared to all the worst cases for other rows.
  
  Choose the row with the best worst case. Id est: Choose the row containing the maximum of the minimum values from each row.

The above assumes that the opponent will always choose the best possible move in any given position. If he does not, so much the better. This is called mini-max strategy: Choose the maximum from among all the minimum values.

I think that Deep Blue generates a matrix of values resulting from considering all possible positions after at least 6-7 plies and might do it for ten or more plies. Assuming analysis of possibilities after ten plies, I think there is special case logic to stop after less than ten or continue beyond ten plies. For example:

• If a move results in the check of the opposing King and the opponent has only 1-2 allowable counter moves, the line might be followed beyond ten plies (perhaps there is an inevitable check mate).
  
  
  
• If a ply results in the loss of significant material, that line is not analyzed further.

Note that the above is a brute force number crunching methodology which would not be considered AI by most people.

BTW: It reminds me of what Jack Nicklaus (I think it was he) said about golf.

Id est: Try to have the best possible worst shots (mini-max) rather than the best possible best shots.

 

to Dinosaur: Thanks for the details on Deep Blue, but my real questions were:

(1) Is there support for my chess friend's claims that Deep Blue helped a human in the loop?

(2) Is it possible now, in principle, to know if either white or black has a path to a guarenteed win, or only to a draw? This is more a question about current computers and storage capacity I think, than chess. I guessed it is not, even with "quantum computers."

 

Billy T:I think that it is possible in principle to know whether chess is a forced win, loss, or draw for White. In practice, I do not think this issue will ever be resoved. I think there is a theorem relating to complete information games which might be applicable to chess. This theorem might not be applicable to chess, which allows for a draw. I am pretty certain that it is applicable to any complete information game which cannot end in a draw.

Prior to about 1890 or so, it was believed possible in principle to determine the exact details of the future and the past of our universe. At that time they believed that the details of the future and past of the universe could be calculated given the position, mass, & velocity of every particle in the universe. However, nobody expected that it could be done in practice.

I think that chess presents an anolgous problem. In principle, yes; In practice, no. I suppose that two future versions of programs like Deep Blue might result in strong evidence. Suppose that hundreds of games between two future computers always resulted in the same result: A win, loss, or draw for White? This would be strong evidence, but not a proof.

After each game with a grand master like Kasporov, Deep Blue programmers analyzed the game & sometimes tinkered with the software prior to the next game if they had time to do so.

Once they had a good basic program, further development was based on analysis of games against top level players.

I do not believe that a human was actively involved during the play of any game between Deep Blue & Kasporov or any other opponent. The Deep blue staff did not include any player that was as good as either Deep Blue or Kasporov. Some Grandmasters (I think Spasky was one) were consulted and got involved with the development of Deep Blue, but I do not think any grand master was a regular member of the staff. although some grand masters were consulted during the development of the software.

I think the program was tinkered with once or twice during the Kasporov match, but I am not sure of this. The tinkering (if any) was done between games. At the time of the Kasporov match, Deep Blue was formidable enough that I wonder how it could be improved in the short time between games.

 

I tend to agree with your first paragraph partially reproduce above. My friend thinks that Deep Blue offered several ranked moves in each reply and which was "Deep Blue's" response was human selected, more to make sure that no "stupid accident" happened. I do not know how the Deep Blue move was actually communicated to the chess board. I suspect that some human, who knew the ranked list made by Deep blue, actually made it with his hand. (He could have used "choice two" etc.)

There clearly is some “psychology” in that level of chess – i.e. trying to "rattle your opponent" in many ways, some as simple as a well timed cough or unexpected smile.

As far as second Paragraph here is the first from my essay on free will (and my Real-Time simulation model of how perception really works), IMH(crackpot)O:

"... Before the advent of Quantum Mechanics, the future appeared to La Place to be exactly determined by the past state of the universe, even if it was clearly unpredictable. Chaos theory and measurement errors plus ignorance about small asteroid orbits, rupture stresses in tectonic faults or vascular systems, etc. makes La Place’s future unpredictable, perhaps fatally so in only a few seconds for some individuals. Quantum Mechanics destroyed La Place’s deterministic world. Thus, thanks to QM, a “probabilistic will” is at least possible. I.e. we can have the illusion of making “choices” that are actually made by the chance results of QM; however, Genuine Free Will, GFW, i.e. real choices made by one’s self, still appears to be impossible without some violation the physical laws that govern molecular interactions in our complex neuro-physiological processes. ..."

As you tell me about Laplace's POV in 2nd paragraph I quoted, perhaps you have never read my essay at:
http://www.sciforums.com/showpost.php?p=1294496&postcount=52

If you have not, please try to find time to and comment -you often have a good point or two to make.

 

Never saw a "frelling circus." If not a typo, I am sure they exist. An expert on language like you can not be challenged, but my dictionary does not have "frelling." What does it mean? (I will add it in the margin

Please Register or Log in to view the hidden image!

Please Register or Log in to view the hidden image!

)

 

There is no reason to say that. Perhaps there exists a path to a guaranteed win for white, first to move.

 

I do not need proof to only note a currenly unknown POSSIBILITY why your unqualified declarative statment may be false.

For example, if one were to declare, without qualifications: "No enirely liquid planets exist." I do not need proof to observe, as I did, "There is no reason to say that."

Especially when I continue on citing why your statement may be false. Such
"There could be one somewhere in the universe." or "There could be a path to a guaranteed win by white"

The burden of proof is on the one making an unqualified declarative statement, not the one illustrating conditions under which it could be false. I.e. I do no need to tell where that liquid planet is, or give the guaranteed win path. I merely note they may exist. Until YOU HAVE PROOF they do not, there is no reason to make your unqualified statement, claiming or implying they do not exist.

 

The following indicates one who knows a bit about software development.

Early in my career, I was one of those cowboys.

I have often seen remarks similar to the following.

They remind me of remarks like

The implication is that there is no limit to the power of computers nor to human knowledge.

There are definite limits to the power of computers. The computations required to solve some problems grow either exponentially or like a factorial. Computing power is subject to diminishing returns rather than exponential growth. I do not think that Moores’s theorem is still applicable. Furthermore, people often believe that this theorem relates to computing power when it actually relates to the density of solid state devices. Computing power has not come close to doubling every 18 months.

Comparing our current knowledge with that of 500 years ago and suggesting an analogous growth in the next 500 years has no basis in reality. Except for cosmology, there have been little, if anything, new in theoretical physics in the past 70 years or so. Chemistry has had no new theoretical developments for perhaps 100 years or more. We have had a lot of new technology (Id est: applications of theory), but very little new at the theoretical level compared to the advances starting with Newton, who was probably the first theoretical physicist.

BTW: Quantum theory suggests limitations to what our brains can comprehend, even if there are still some discoveries to be made in theoretical physics.

The following does not seem fair.

For example, there is a simple game called Chomp which by its definition must result in a winner in a finite number of plays. There is a simple proof that there must be a winning strategy for the first player. The game has never been completely analyzed and might defy any attempt to determine the winning strategy for all possible starting configurations. While understanding the proof for Chomp is a no-brainer, proofs for other games which can result in a draw are generally very difficult to devise or understand.

Another example of simple conditions causing problems for proofs: There are some theorems which were easily proven for a torus, but which were extremely difficult to prove for a sphere because of the problems with coordinates systems at the North & South poles. Analogous problems occur with Mobius strips & Klein bottles, for which you cannot specify a unique direction for a perpendicular.

I can remember proofs in differential geometry & topology whose hypotheses excluded surfaces with ambiguous coordinate points (North pole on sphere)) or the lack of an orientable perpendicular (one-sided surfaces). Intuitively, such conditions do not seem to cause problems for a good proof.