Quantum computers and chess

Not sure what you mean by 'good' chess player. The computer allows people even if they are isolated to have challenging competition and somewhat more. But still, once you are in a tournament you do not have the computer with you - unless a round get adjourned - so you are on your own.

 

Log in or Sign up to hide all adverts.

Pluto2: Using a fork lift or a chain hoist will not make a person a better weight lifter. Using a computer will not make you a better chess player. People still enjoy competition with other people, even though machines could be designed to be better than humans at many competive activities.

How many people would watch a football game played by machines which could devastate a human team?

Are you suggesting a person should not engage in any activity not designed to make the world a better place?

Do not do crossword puzzles, play card games, listen to music, read fiction, have sex for fun instead of only for procreation, et cetera?

 

Log in or Sign up to hide all adverts.

For such a game winning algorithm to exist, a lesser algorithm must first exist:

I.e. there must be some way to chose the best next move when the configuration of the pieces on the board is given.

No one knows how to construct even a "best next move" algorithm. Thus your "argument" is only silly hand waving.

If you think otherwise, try to tell how one can make the "best next move" algorithm. I.e. give some guidance as to the principles that would be in the "best next move" algorithm.

To illustrate that your argument is just silly hand waving I will use it on another, simpler, more clearly mathematical, problem: The prime number generating algorithm:

"We are just assuming too many things about how to solve the problem of prime number generation mathematically. There can be brilliant solutions hidden to us that requires very little computation. ... Basically the argument is that prime number generation can be solved by finding an ingenius algorithm, and not necessarily using a monstrous computing machine."

 

Log in or Sign up to hide all adverts.

But if you use a very strong chess program (say Rybka 6) running on a very fast computer, say something like 12 fast cores to analyse your internet or tournament games in order to correct your mistakes and to find tactics you missed, will you not become a much stronger player or even one of the top 50 players in the world at some point?

Of course it takes time but analyzing your games with a fast computer running a top chess program or simply playing a lot of games against it will make you play much stronger chess at some point.

Music, recreation, hiking, football, riding a bicycle or any other sport and leisurous activity are all very important too. Where would we be without all those things? The world would be very dull and boring without all these things.

But just don't do too much of these things at the expense of other things. Find the balance.

 

Pluto2: A human cannot apply the methods used by chess playing computers.

You could learn by playing against a human who gave you advice. Chess playing computers give no advice & a human could not cope with a computer analysis of how it played. They will beat you without your ever knowing why unless you take lessons from a human or read some good books.

The following from a previous post by you is quite disparaging of chess playing.

When called on the above remark, you posted the following.

Why did you not post a toned down or qualified remark in the first place?

 

if there is no "next best move algorithm" then what would happen if 2 chess programs faced eachother? assuming they have the same computing power parameters set. would they clone eachothers moves or just end in stalemate (just kings or complete gridlocked board)? also if there was a best move algorithm then wouldnt that defeat the purpose of using it if both programs used it. this stuff makes my brain hurt but i can feel it grow lol.

 

Try reading Post 27 which describes the basic concepts in Deep Blue (& probably other) chess playing programs. To understand the issues discussed in this thread, a person should have an understanding of the design concepts of chess playing programs & some experience playing chess. I am not suggesting that you need to be better than a mediocre player or that you need more knowledge of chess playing programs than that described in post #27. I am only claiming that you need pertinent knowledge, which I suspect some posters are lacking.

When you understand the basic design of current chess playing programs you will have a better idea of the fundamental difference between human & computer chess playing methods.

The following are some valid comments on computer chess.

• The game is too complex for programs based on application of “if then else” logic. Such a program would be impossible for a human to devise & debug. Furthermore, no human (even grand masters) have a clue about how to organize such a program.
  
  Contrary to what most people think, Chess masters cannot provide algorithms describing why they make certain moves. For example in a famous game from 100 plus years ago, the winner had an inevitable mate in 10 or perhaps more moves starting with a major sacrifice (the Queen, I think). After the game he was asked if he saw the inevitable win. He said something like the following.
• Nobody understands chess well enough to design a program by applying ”Rules based” methods used by various so-called expert systems.
  
  
• If the game is a forced win for either White or Black, It is theoretically possible to develop a winning algorithm by using computers to build a file containing no losing positions (there are algorithms for building such a file). Once built, a simple program could be written to use the file to play a perfect game. The file would probably use more storage than that available on any current or future system. There is an upper limit to the amount of storage you can have on a system (EG: Suppose the storage required the use of all the matter in your solar system for use in the components of the storage system). The time required to build such a file for chess, is likely to require thousands of years of computer time & it might not be possible to devise an algorithm indicating when the file was complete.

I am not sure about the outcome if two identical programs as powerful as Deep Blue played each other. I think the initial move by white is based on a either a random choice from standard book openings or a choice of a book opening by a human running the computer. The program follows book moves until the end of the known lines or until the opponent deviates from the book line, at which point the mini-max algorithm is used.

For example I would expect the same result every time A Ruy Lopez (not sure of spelling) opening was played for several moves. For a given position, the Deep Blue algorithm is deterministic. If the repeatedly obtained result was a win for White, I would not consider this to be a proof that the Ruy Lopez opening is a guaranteed win for White. It is possible that modifying the program to use more plys would result in a win for Black or a draw.

 

Sorry for the late reply.I had connection problems.

Yes,what I am suggesting is similar to finding a prime number algorithm mathematically.But just because no one has ever found out one ,doesn't mean that such an algorithm does not exist.

 

Short answer: no.

Long answer: chess cannot be defined because it is an art form.

 

Proofs of non-existence do not exist outside of the realm of mathematics. So your POV applies to unicorns or to a buried gold nuggets with the mass of the empire state building, etc. I.e. your logic argues that they probably exist as no-one has been able to show that they do not exist.

In both chess and the search for prime number generating algorithm there have been many huge efforts expended for centuries trying to find them. Probably more total man-hours of searching than for very large gold nuggets. (You would not find such nuggets panning in a stream, etc. so those man-hour can be ignored.)

Thus it seems more probably to me that the empire state building mass gold nugget exists than that your chess winning algorithm exists as there has been less serious effort in looking for that large gold nugget than how to get an assured win at chess.

In the purely mathematical case of the prime number generation algorithm, I suspect that it may have been proven that none can exist but no-one can prove that your postulated chess winning algorithm does not exist (nor that the empire building massive gold nugget does not exist).

SUMMARY: I am much more inclined to think that large gold deposit does exist, probably as a melted mass deep in the earth, but that it has not yet been found due to technical limits on how deep man can deep than believe that your chess algorithm exists.

 

Here's a program my brother wrote, after many challenging games with myself, that plays decent chess on your pc:

http://chess.captain.at/

 

You give humans too much credit!
Humans aint that intelligent that they will just find every existing solution without any serious effort.Even the more intelligent of the species such as Einstein realised this and declared that "human stupidity is infinite".

p.s:searching for gold requires very little inteligence.

 

If I do, then that is close to proof your postulated algorithm will never be found, which is operationally indistinguishable from: "It does not exist."

BTW, the burden of proof is on the guy claiming something does exist, not on guy saying it probably does not as non-existence can never be proven, but existence can be. Try to give some reason why your algorithm might exist.

What gives you the idea that there has not been any "serious effort" in finding a guaranteed win procedure for chess?

 

Actually ,no.
In mathematics,there is proof that -
"In every discrete 2 person game with alternate moves satisfying the following criteria:
1>The game is finite(That is,a draw,win or loss is inevitable after a finite number of moves).
2>The game is non-random(The player makes the choice,not the dice).
3>The state of the game is perfectly visible to both players at any point(there are no hidden hands like in cards).

there is always a 'non-loosing' strategy for at least one of the players".

The proof is actually very simple.I am not going to prove it rigorously,but I will give you the basic idea.Let's call the first player A and the second player B.Let's say that this game must reach a conclusion after 10 moves(because of finiteness).Now let's say that for these 10 moves,B can maintain a non-loss state corresponding to every possible move that A has.(think of the move tree).If B can ,then B obviously has a non-loss strategy.If not,then for some move of A ,B cannot prevent loss.So that must be a winning strategy for A.So clearly,either A or B has a non-loss strategy.


Now,chess satisfies all the above conditions except for finiteness.But we can easily make it finite by adding an extra rule :- "if nobody wins after 300 moves,then it's a draw".Since no chess game ever lasts more than 300 moves,it's a decent rule.And therefore in chess ,at least one of the players must have non-loosing strategy.

So the question is not whether such a strategy exists ,but how to find out one.Are human beings clever enough?

As for the original topic of quantum computers ->Lets say each player has 20 possible move at each step(of course this is an over-simplification).And let's say that 300 moves is taken to be the upper limit in chess.In that case, the quantum computer has to calculate about 20^600 possible ways in which game can proceed to figure out the optimal strategies for both players.Of course,300 moves is a bit of an overkill as most checkmates are reached within 50 to 60 moves.If we take 100 to be the upper limit,the quantum computer needs to compute 20^200 moves(roughly 10^260).That's still pretty huge.

 

Repeat

 

What are you replying to (or commenting on)? Are you claiming that the burden of proof is not on the person making the claim for the existence of a chess winning algorithm? If not what are you talking about?

I think it obvious, without any of your conditions, that all two person games have a non-losing strategy for at least one of the players. That follow from fact game must end with one winner or in a draw, in which case both followed a non-losing strategy.

 

Lukas Cimiotti upgraded his chess playing computer cluster to 200 Intel cores. This is a big upgrade from the last three months when then he had only 128 Intel cores.

In about one year or maybe slightly more his cluster may reach 400 and 500 processor cores respectively.

 

There is a very simple finite game called Chomp. A draw is impossible & it can be proven that there is a winning strategy for the first player.

While there are known winning strategies for many special case games, there is no known winning strtegy for the general case.

If Champ has yet to be completely anlayzed, lots of luck with chess.

 

BTW: I think a computer can always win a particular game of Chomp by exhaustive analysis, assuming some limit on the size of the game.

As for chess, the computer uses brute force to win at Chomp without providing an algorithm for a general winning stratgey.