If you prefer a simpler, less open version of the question: Could a grandmaster have trained with Deep Blue to regularly beat Deep Blue playing on its own?
The sci-fi version of the question is: Would cyborgs ever enjoy playing chess, or would it simply be a matter of whoever tosses the most hardware at the game?
Posted Oct 10, 2014, 2:03 AM UTC
The reality is, Chess is a game of finding the absolute best move in a search space. It's an astoundingly large search space, but it is well defined and we know the exact size of it.
Computers are incredibly good at searching. In fact, the biggest thing that slows them down are the amounts of memory they have to "keep things in their head" and the amount of different search paths they can take at once. Even if the computer were doing nothing more elegant than a brute force attack on the game, there will be a point where, given enough hardware, the human being will never be able to beat the computer at the game. Period. And Chess engines have much better algorithms for picking the best move than just brute force searching. Human beings simply will never have the neural capacity to keep up with computers at that scale.
Honestly, I have no idea what amount of hardware that will be, but I wouldn't be surprised if a clever enough mathematician could figure it out exactly given how well researched the game is and how relatively easy it is to calculate the state space. (Well, it certainly wouldn't be fast, even on today's supercomputers - or even a hypercomputer composed of every supercomputer we've built to date - but it's a more-or-less trivial thing to plug away at. Like trying to solve for any googolgoogolth digit of pi.)
But it's probably not a fantasy worth discussing as computers at that scale will have much better things on their minds. Like global thermonuclear war. Or the enslavement of mankind.
The reality is, Chess is a game of finding the absolute best move in a search space. It's an astoundingly large search space, but it is well defined and we know the exact size of it.
I think this is a bit misleading. Unless you've completely analyzed the game (which we can't do with chess, right now), it isn't about finding the absolute best move, since you can't know whether there's a better move in the space you've pruned out of the search space.
This is also a bit nitpicky, but we don't know the exact size of the search space either. We have some good estimates, but they sure aren't exact.
What are these algorithms that computers have now that are much better than just brute force searching searching deeply from the current position with alpha-beta pruning? I know we have some heuristics for refining the evaluation of a position that go beyond just material evaluation, but I haven't read anything about any significant improvements beyond brute-force searching, but maybe I'm just out of touch.
Edit: rephrased something that originally sounded like something else.
Alpha-beta pruning is as ancient as dirt and is better than brute force searching. It's not a heuristic either.
I'm talking about the min-value and max-value functions that alpha-beta pruning uses to decide what to prune. The simplest just considers whether a forced mate is possible and otherwise considers material, but to get more complicated you need a way of assigning values to peculiarities of the position. In my mind those are heuristics. For instance, see the heuristic improvements section of the Wikipedia page on Alpha-beta pruning.
When I said brute-force searching I didn't literally mean exhaustive search (though I can see how one could think I did), I just meant throwing lots of computational effort at the search, which isn't what chess masters (typically) do.
Edit: added links to Wikipedia
It's not as simple as calculating a winning solution, the best you can come up with is a set of the next possible moves where you CAN win. Stating that problems can be solved given enough raw computer power is simply not true.
There's no a priori reason why a human couldn't beat Deep Blue; they don't, but they could. Deep blue is basically just extremely fast at working out an algorithm that a human, given enough time and paper, could work out (just like all computers).
Put another way, you can treat a person as a Turing oracle. To my knowledge, we haven't yet proven that human intelligence is subject to the Church-Turing thesis, so it's possible there are classes of problem we can solve that computers can't. (I don't consider this likely, but it might be interesting for a sci-fi writer to tackle something like this.)
Saying 'working out an algorithm' is very misleading.
Why would you say that? My understanding is that Deep Blue generates possible positions, ranks them, and chooses the best. The fact that most of this is done in parallel isn't really relevant to whether it's an algorithm or not.
The generating of the possible solutions is the algorithm, the process itself. What comes out is a path through the state spaces, the output of the algorithm, not an algorithm in itself. It's also worth noting that all solutions are not generated, as this would be ludicrously inefficient. Instead heuristics / iterative search methods are used to follow promising paths through the tree of states.
All of those things you're saying are true, but I don't understand how Deep Blue's behavior violates the definition of an algorithm. Hell Monte Carlo Algorithms are considered algorithms. In what sense are you using algorithm?
There's no a priori reason why a human couldn't beat Deep Blue; they don't, but they could.
But that's just Deep Blue. Everything that we know about the game Chess suggests that it's a decidable game, but that it's state space is simply so large that computers can't currently search the entire thing.
Human beings are pretty good analog filters, so we're incredibly good at finding solutions in noisy state spaces like Chess. But that doesn't at all mean computers aren't better. In fact, they're better filters than we are, they're just much, much slower at it.
Chess is a game that can be attacked via pure information theory, so we can be reasonably assured that computers will, eventually, always be better at us than chess. But, then again, Chess is a relatively simple game. We can afford to give that one to the computers and focus on vastly more complex games like "love" and "art".
We can afford to give that one to the computers and focus on vastly more complex games like "love" and "art".
If you've never read it before, you'd probably enjoy Way Station by Clifford D. Simak.
But human brain is biological machine. You can emulate it in silicon. So, it's really not proven?
Source for that claim?
[deleted]
Even if this not possible to simulate laws of physics inside our universe(I don't know, and nobody knows because we don't know exact laws yet), our minds are most likely at the level of neural network, not lower. So you must emulate neurons. We can emulate neurons.
We will know for sure after first succesfull mind uploading.
We can emulate models of neurons, but we don't generally simulate neurons themselves in all of their depth, because the depth would cost a lot without letting us learn much.
You can simulate networked synapses, and that's great... When you want to simulate hundreds of types of neurotransmitters in a shared media, calculating diffusion patterns, gating effects, subtle long-term excitation and inhibition that certain receptors generate, etc.... Well, when you do that it's much harder to see anything through all of the noise.
Fair enough. You original comment was a little more definitive, though. Was hoping there was something I hadn't read regarding emulation of the brain.
[deleted]
I think a computer can always best humans in the computational aspect of chess; that is to make a move and then look at all possible moves after that and so on. However computers, as of how they currently work(logic/(true/false)/if/etc), can't reproduce biological spontaneity. Animals like humans and dolphins are not limited to the parameters of a program. They do have biological programming, but it is malleable unlike computers. Also, this biological programming can evolve on its own where as AI requires an external intelligence. I always like to refer back to the concept that computers are not smarter than humans, they are merely more efficient. In short I think a human plus a computer can potentially be better than a computer alone if the match was human and computer versus human and computer. If it was human and computer versus computer the human adds a layer of risk to his/her computer partner.
Also, what do you mean specifically? Like how is the match played? I wrote this comment assuming you meant that the human partner can't decide moves on his/her own, but can only and merely pick predetermined moves made by the computer rendering the computer in control of the computational aspect and the human in control of the "yolk"/spontaneous aspect of decision making.
If I were designing the system, it would present all of the preferred moves as arrows on the system, allowing the human to choose between these.. It could also show all of the blunder moves (red arrows).
On a mouse-over of a move, the computer would animate the expected flow of the game for the next few moves.
The interface may well show the levels of control of squares, and potential pins/reveals.
Basically, if a human picks moves that the computer considers mistakes (most available moves) more than a couple times the machine will stomp the human. For some fun go try lichess.org, register, play a game, and see what it thinks your doing wrong.
However computers, as of how they currently work(logic/(true/false)/if/etc), can't reproduce biological spontaneity
This usually is not at all true. Spontanerity can be easily reproduced... There just is usually no incentive to do so.
how??? I've just stepped into computer science. Can you link something about this??
Spontaneity is generally trivial.
if(rand()%1000==2) crash_horribly();
is spontaneous. There's nothing difficult about adding unpredictability or sudden impulses to a program. There are thousands of ways to do that. The issue is that unpredictability is almost never actually desirable for any task, either in computers or in humans. 'Spontaneity' usually means wasted time or sub-optimal choices. Computers proceed according to strict math and logic not because they have no other option, but because it's actually the best possible option in just about all cases that we use computers for. Despite media portrayals, randomness pretty much never wins out over logic out of sheer pluck.
Just about any learning algorithm is also going to be rather unpredictable and/or spontaneous, but, again, this isn't a spontaneity that is particularly desired. You want consistency, but you put up with it for the other benefits you get.
Where unpredictability is actually a desirable trait, it is humans who are hopelessly predictable. If you ask a human to hide something, the average human is going to be disastrously horrible at it.
What is actually difficult to make computers produce is new things which are both original and are intelligible, but in strict rule-based games, this is reasonably meaningless. You can't really come up with a brand new way to move a chess piece.
Thanks. That makes sense. What about creativity? I don't think a computer coming to something at random by using a given path to follow, ie. the line of code you wrote, can possibly reproduce the spontaneity of a painter. Then again the painter must have seen a mountain in order to paint one so I guess that is the same as a computer coming to a random number given a predetermined path. I didn't really pay much attention in philosophy class. Had s boring ass professor. Regretting it now.
Also, what exactly is the definition of spontaneity? I use a personal one that really isn't easy for me to put into words. It doesn't have much to do with randomness. However close it is to the conventional definition, but that can still cause miscommunication.
How long does it take a computer to "learn" chess without a programmer...
Counter point: How long does it take a human to "learn" chess without someone to explain it to them?
I appreciate this line of thinking.
I guess if you give the computer/human such signals as "illegal move" and "you win/lose", they'd be able to figure it out eventually.
Currently, chess is too complex for that. Computers can learn to play super mario bros., though!
Eh, is it? General purpose algorithms can be taught to play pretty good chess just by being fed records of previous games.
His point is Blue was built and programmed humans, so humans should get recognition in Big blue's achievement. Its funny how the chess opponent on games written in 1995 can beat me. The only thing that got better was the algorithm, but it's arms race of intelligence. Somewhere IBM made a mistake and that computer is beatable.
[deleted]
I doubt it. Neural networks are exactly what brains are.
well neural networks are fully programmable
But computer neural networks are not yet there. Things like self-organizing plastic neural nets are still in their infancy...so probably in a couple years. And still the specialized algorithm should be better
No, neural networks can be arbitrary size given enough computing power. Our brain is limited size
You said "efficient". Would a larger NN be more effecient? Algorithms beat the clock in chess. By that, I mean that they don't solve the chess problem at all, they just look up moves in a book, faster than a human can process the same moves. (In the early game and end game. Mid-game is more complex, but it's basically "shortcutting" everything.) More efficient by far than neural networks. NN aproaches to chess fall afoul the several things. One, they require training. Another, chess is still a very large problem. More =/= better with NNs. There is an optimum size for every NN problem. Even with computing elements the size of a grain of sand, it's been shown that a computer the size of the observable universe can't solve chess within a human lifetime. Ask r/theydidthemath .
You might be interested in reading about Advanced Chess, aka computer assisted chess, where each player has access to the same chess engine. Tournament play exists, so I'd bet that better players exist and win more consistently than others.
Thanks for that, I hadn't heard of it. The wiki page is a good start (http://en.wikipedia.org/wiki/Advanced_Chess). That lead me down the trail to the apparent answer (or at least the soon to be answer):
No. The human only gets in the way.
My impression is that with advanced chess, standard chess engines are used. Since those engines were not really built with the task of collaborating with a human in mind, they aren't terribly well suited to that task.
I wonder whether a better variant of a chess engine could be built which could interactively accept advice from a human by posing questions to the person, which are more suited to the human's skills. For instance, there are some forms of position that a skilled human chess player can see the outcome of pretty easily, which a computer has to search to some depth to properly evaluate (The Horizon Effect). If the computer had some way of relaying to the human part of the team that it had run into such a position which it pruned, in a way that the human could respond with advice that the computer should look deeper, the strengths of both human and computer could be better used. Unfortunately recognizing such situations and being able to solve them without help seems to be the same thing. Perhaps if the human had a way of telling the computer that when it is searching a particular part of the search space, it should check in with the human when it encounters positions with certain characteristics before pruning them. Perhaps we'd need to create a new, very expressive language for conveying such thoughts to the computer. This all seems to me like interesting and potentially useful work, and I sort of doubt that it has been tried to any great extent.
Understand that when I am talking about the engine asking the human for advice or feedback, I am not suggesting that it stop and wait for a response, I just mean that it makes a decision, continues, and if the human responds with advice to do something other than what it did, it is able to easily go back and say search deeper.
I think you'd run into two big problems:
1- Communication. Grandmasters evaluate lots of positions at a glance and intuitively select the best without barely even looking at others. Maybe the engine would need hundreds of advice to get a significant aid, which would be slow (no brain-machine interface yet :P).
2- Quantification. Even though the GM may know intuitively the strength of certain positions he may not be able to translate that intuition into an accurate quantity -- he can't say e.g. "this position is 2.3x as strong is this one"
Definitely they are big problems, and I'll bet that there are more than those two. But what a payoff if they could be solved, and what interesting problems! I'd be far more interested in research on them than trying to make a slightly faster 'traditional' chess engine.
I thought this wasn't really an issue with modern chess AI since they don't really do much depth searching - they mostly do pattern recognition and classification to predict outcomes based on the massive database of recorded human games.
That wasn't my understanding, though I could be wrong. The Wikipedia article on computer chess seems to agree that they work pretty much as I described above, sometimes (usually?) augmented by endgame tablebases. The latter isn't really pattern recognition but rather a straightforward lookup.
Do you have any citations of papers or articles that led you to this understanding? I'd be interested in reading about any such developments.
It needn't be true that a human always gets in the way. The highest rated chess engine as of right now, Stockfish, can evaluate some positions with closed pawn structures as a draw when an IM/GM can recognize them as advantageous or even winning, due to one side having a weakness that takes so much repositioning to undermine that it is outside the engine's search horizon. I'll admit these positions are very rare, and the human tends to simply recognize that the position may be winning, and then lets the engine play moves it considers good that also drift in the direction of the winning pawn break or sac on a weakened square until the weakness reaches the engine's search depth.
Granted, the usefulness of humans is hanging by a thread at this point.
Huh, interesting. I don't think that was case last time I went on a reading binge on this topic, though it's not that surprising.
[deleted]