How Good Would This Be?

[Joey Stewart]

I found out today they have been making obscenely powerful computers (not sure what their purpose could be as nothing in real life needs that speed of processing).
I even have a link for those haters that might doubt my words of truth: http://www.bbc.co.uk/news/technology-27974290

But then I had a moment of excitement - imagine if they could put this monstrosity to work on chess, do you think it would be capable of "solving" the game once and for all?

[Neil Graham]

I found out today they have been making obscenely powerful computers (not sure what their purpose could be as nothing in real life needs that speed of processing).
I even have a link for those haters that might doubt my words of truth: http://www.bbc.co.uk/news/technology-27974290

But then I had a moment of excitement - imagine if they could put this monstrosity to work on chess, do you think it would be capable of "solving" the game once and for all?

No - I bet it couldn't even sort out the Lancashire v Greater Manchester dispute though I suppose that's more difficult to solve than chess!

[MartinCarpenter]

Terrifying isn't it? Plenty of scientific simulation work that needs this sort of firepower.

Problem with an absolute solution to chess is evaulating/storing enough positions. Would need far more storage capacity than anything we can possibly build right now to do that.
(Quite likely impossible outright iirc but that's a dangerous word ).

A 'near' solution where you say accept that anything a really powerful computer evaluates as say 0.5 pts off optimum can be truncated rather than fully calculated out to a draw/win/loss ? That we might see at some stage.

[Michael Farthing]

Number of chess positions ~= 10^45 (slightly low estimate I believe)
Number of protons and neutrons in the Earth ~= 10^52 (slightly high estimate I believe)
Required storage device therefore at least 1 ten millionth the mass of the Earth assuming the somewhat unlikely proposition that a single proton can record the assessment of a chess position.
Quite a big device even so. It'll take a while.

[Roger de Coverly]

Number of chess positions ~= 10^45 (slightly low estimate I believe)

The number of plausible positions that you would have to evaluate is way smaller than that. There's around 6 to 10 million of games recorded in electronic form if you include all the rubbish, many fewer than that if you only take the ones believed to contain sensible play. So for an average of 40 moves a game, that's up to 800 million positions. I imagine you could evaluate each one and store the assessment. You could go astronomic if you started evaluating what might have been from each position, but again pruning on the apparent rubbish would cut it down.

I suspect on balance that the result is a draw, provided no-one lobbies to abolish stalemate as a rule.

There's a major weakness, in that the evaluations would be subjective, being based on what humans thought were valid weighting factors. Working backwards from the tablebase n-man endings is another approach, but storage and access requirements escalate rapidly unless you can again introduce some selectivity.

[Nick Grey]

The answer is in The Hitchhiker's Guide to the Galaxy

Answer 42 - deep thought

Relevant calculations for what that means - the computer is size & mass of the whole Earth

Slartibartfast designed the fjords of Norway

The answer is in Magnus Carlsen's brain but he does not know it yet.

Hopefully the mice will get it & let us know before the Earth blows up.

My guess is that it is 42 moves - but is it a win or a draw?

[Clive Blackburn]

Number of chess positions ~= 10^45 (slightly low estimate I believe)

The number of plausible positions that you would have to evaluate is way smaller than that. There's around 6 to 10 million of games recorded in electronic form if you include all the rubbish, many fewer than that if you only take the ones believed to contain sensible play.

This is precisely the problem though, how do you decide what are "plausible positions" and "sensible play"?

At whatever point you start to prune the analysis tree, you run the risk of missing an unexpected sequence of moves which completely changes the evaluation of the position. The more deeply that you analyse, the more the risk is reduced, but it will never completely disappear.

[Roger de Coverly]

This is precisely the problem though, how do you decide what are "plausible positions" and "sensible play"?

I don't think the estimates on what is sometimes termed the Shannon number validate the legality of positions and whether they can be reached from the standard initial position.

Some programmers have incorporated Monte Carlo methods into their creations, where the engines will play an extraordinary number of very fast games. So if all else fails with an evaluation, play 10,000 games and see how the percentages stack up. You could leave such a program running from the initial position and count how many games it stacked up. You would need to be able to filter for duplicates and have a means of playing second and third rate moves. If you used the monkeys and Shakespeare logic, perhaps it would take infinite time to reproduce even a single world championship game. To be practical, you might have to sample. So run it for a week and see how many existing games it managed to reproduce. If you included all the games played on-line on servers, at a guess there's ten million existing games recorded in electronic form.

It's an oddity of chess (and some other games) that at the beginning and end you get convergence. So openings have been played before, but so have endings, particularly those with few pieces.

[Michael Farthing]

This is precisely the problem though, how do you decide what are "plausible positions" and "sensible play"?

I thought of making this comment, Clive, but decided that those of us who had actually understand what the issue in this thread is would know this already and those of us who don't won't be convinced by anything.

[MartinCarpenter]

You'd have to define something entirely arbitary like, a difference of X in terms of computer evaluation after Y ply of consideration or some such.

Perhaps interesting to wonder how 'high' you could push X while keeping it computationally tractable. Put X to 0 and of course you're just letting the computer play a game against itself Of course, no one sane would have confidence in that

Manage to somehow push it out to say, 0.5 of a pawn? Then I think people would take it as quite strong evidence. Probably well off being able to do even that though.

I guess the next step would be when we reach the stage where computer + human isn't any stronger than a computer (so far from yet!). If you've got a computer that strong then the task of somehow challenging its pseudo perfect theory would be so hard as to potentially deter anyone from really doing it.

[Bill Porter]

Number of chess positions ~= 10^45 (slightly low estimate I believe)
Number of protons and neutrons in the Earth ~= 10^52 (slightly high estimate I believe)
Required storage device therefore at least 1 ten millionth the mass of the Earth assuming the somewhat unlikely proposition that a single proton can record the assessment of a chess position.
Quite a big device even so. It'll take a while.

Quantum computers are almost a reality now. They may already exist clandestinely as they could easily defeat private key /public key encryption.

You need as many qubits in the computer as you would would need conventional bits to encode a chess position plus a few more for processing.

Run all possible games in quantum superposition.

For each move in each game, check whether there are any variations where white always has a winning/drawing line for every subsequent legal black move or black has a winning line against every possible white move.
You can use a brute force approach as there's no problem in eg running 10^40 variations.

You can't look at the results directly as that would destroy the superposition, but there are claimed to be techniques for extracting them indirectly.

It might take years to create the software, but rather less than a second to get the results.

[Michael Farthing]

If you can program your quantum computer with software then the software to solve chess has existed for decades. The only problem is the processing and memory costs. Indeed, one could even throw away a large part of the coding that would no longer be needed - eg tests to avoid analysis of transposed variations; tests for quiesence to halt deeper analysis; oh - and the whole of position assessment! (with the exception of checkmate of course).

[MartinCarpenter]

Can't just port algorithms from standard stuff to quantum computers. Just a bit different in how they work Still, you'd also need a fearfully large number of qbits to solve chess as one giant entangled problem. If we ever get there, then the issues with programming them will be long, long since sorted.

You'd also need a fairly large one to break codes, much larger than anyone has really made as yet I think? DWave are selling a 'quantum' computer commercially right now but its a bit different to how they've currently been imagined to work and some live debate as to whether it quite counts as quantum or not etc.

[Bill Porter]

Can't just port algorithms from standard stuff to quantum computers. Just a bit different in how they work Still, you'd also need a fearfully large number of qbits to solve chess as one giant entangled problem. If we ever get there, then the issues with programming them will be long, long since sorted.

You'd also need a fairly large one to break codes, much larger than anyone has really made as yet I think? DWave are selling a 'quantum' computer commercially right now but its a bit different to how they've currently been imagined to work and some live debate as to whether it quite counts as quantum or not etc.

So solve chess as 10^40 or so very simple entangled problems, each of them using the same qubits.
Getting the useful results would be difficult, but I would think a similar approach to that planned for factorising very large numbers would work.
I don't know how you define 'a fearfully large number of qubits' but I think (far?) less than 50, including processing, would be required for chess.
Once a computer with say 8 qubits has been built ( with reliable error checking), it's unlikely to be hard to scale it up.
If there is a serious limit on the practical number of qubits, it should generally be possible to get round this with ( hard to write ) software.

Programming quantum computers is an abstract discipline at present, with an emphasis on the 'best' way to do it and I suspect that many issues with programming them will not be sorted until there are real computers to program.

DWave are selling a 'quantum' computer commercially right now but its a bit different to how they've currently been imagined to work and some live debate as to whether it quite counts as quantum or not etc.

Indeed, but if any government has indeed managed to develop a real quantum computer, it will be at a tremendous advantage in codebreaking etc as long as it's kept secret.

[Michael Farthing]

Can't just port algorithms from standard stuff to quantum computers. Just a bit different in how they work Still, you'd also need a fearfully large number of qbits to solve chess as one giant entangled problem. If we ever get there, then the issues with programming them will be long, long since sorted.

I had assumed that a quantum computer is not really a computer if no one had been able to develop the mechanism of enabling users to program via a high level language (in which event, surely, chess becomes a fairly trivial problem?).
[Obviously such a high level language might not be anything like existing ones].

Are you really saying that *all* problems have to be started from scratch, or were you simply saying that the hardware is currently way in advance of the software (which I suppose must actually mean we lack a sort of equivalent to an assembler-like instruction set)?

More philosophically, can we say chess is solved if, to whatever level of certainty, we can only get a probablistic solution?
This is a bit different from, say, integer factorisation, where we can check the answer conventionally.