A Question on Computer Chess
My son and I were discussing how computers can play certain games. I explained that a computer can easily “solve” Tic Tac Toe–meaning it can consider every possible future state of the board before making a move, and hence will never make a mistake.
However, with chess this is not possible (at least yet). I admitted I didn’t know for sure, but speculated that the computer relies on standard opening sequences, then in the mid-game relies on heuristics involving the “point” system (1 for pawn, 3 for knight, etc.). It was only near the end where the computer could once again revert to brute force and generate its (flawless) moves in an acceptable time.
Does anyone know if that’s right so far? If so, is it right to say that as computing power increases, the earlier in the game that “switch to brute force” becomes possible? In the limit, once that boundary had been extended to the very first move, then the computer would have solved chess. Any computer programmers and/or chess enthusiasts who can add specificity to my BS’ing would be greatly appreciated.
Also, since I was on a roll and just makin’ stuff up, I went this route with it: I speculated that in the middle game, the computer probably relied on a mixture of brute force and “common sense” wisdom from humans’ chess experience. So for example, when considering the various permutations following a particular move, maybe the computer wouldn’t bother chasing down the paths in which the opponent does something apparently “stupid,” like give up his Queen in exchange for a Pawn (with no checkmate imminent). So the computer doesn’t bother exploring those paths too deeply, in which case it might be vulnerable to a big sacrifice that leads to checkmate several moves later. Thoughts?
Your speculation on the computer strategies for the 3 game phases is essentially correct, though the mid-game heuristics involve a much more sophisticated evaluation function than the point system for captured pieces.
Near the end they use databases of solved positions. In the opening they use databases of recommended moves. For the rest they have fairly blunt evaluations of positions. More sophisticated than the basic points but not hugely so. They think by considering the value of reachable positions from the one in front of them by an extended minimax — extended over a series of sequential plays.
I thought this article was pretty interesting. It discusses the difficulties computers have with the game Go BS chess. http://www.wired.com/2014/05/the-world-of-computer-go/
*vs chess
I remember having a lot of fun at University learning about heuristics for using A* to solve mazes.
http://en.wikipedia.org/wiki/A*_search_algorithm
The limitation of computational power controls the number of positions you can evaluate in a given time. In principle heuristics are only necessary when you don’t have time to search all the positions, so if computers get sufficiently powerful we can forget about efficiency. However in practice the mid game does fan out quite rapidly, so you want to put the computational effort into something that is more likely to be useful… the purpose of the heuristic is to decide when to cut a branch of the tree and search elsewhere (i.e. when it looks like one side or the other is never going to choose this branch). Cutting a branch early saves a huge amount of searching, and yes the heuristic can be wrong so humans are able to beat computers by hiding a good move behind a bad move (but you have to be pretty strong to be able to do that).
This is the typical approach (for chess games):
http://chessprogramming.wikispaces.com/Alpha-Beta
The reason this fails for “go” is firstly that the game fans out much faster than chess, and secondly that in mid game go it is very difficult to figure out who is winning.
I might point out that most “real world” problems not only have very large fan out, but the introduction of possible moves itself requires intelligence (and creativity). Suppose for example you are at a shop buying vegetables and you think the price is too high, you can negotiate a lower price, but then you need to come up with strategies for negotiation, you can go search for another shop, you can decide to buy online, you can not eat vegetables and buy vitamin pills instead to make up the nutrition deficit, you could steal the food, you could beg for food, you could grow your own vegetables, etc. Each of these options itself would open up more variations.
Thus, chess playing algorithms are not usually applicable to real world situations.
Given the emphasis on energy efficiency these days, I’d like to see a Joule for Joule chess competition between computers and humans. The human gets to wear a breather apparatus to measure energy consumption, thus we compare chemical calculation efficiency against electrical efficiency.
Also, this one…
http://en.wikipedia.org/wiki/File:Minmaxab.gif
“so humans are able to beat computers by hiding a good move behind a bad move (but you have to be pretty strong to be able to do that).”
Without specifying the program and processing power, this statement doesn’t mean very much.
I very much like your idea of the joule for joule match-up. In the blue corner chomping on a plate of pasta is Carlsen. “How you feeling calorie-wise, Magnus?”
There are raw physical constraints that make brute-forcing in this manner highly unlikely, as emphasized in Ref #4 in this Wikipedia article, quoting from Philosophical Magazine:
This doesn’t rule out analytical breakthroughs, though.
The number of possible chess games is sufficiently large as to be for all practical purposes infinite.
Never is a dangerous term, but it is unlikely that Chess will ever be as determinate as Tic Tac Toe.
On a crude scale the rest of your explanation is correct.
But computers can have far larger databases of openings than even the greatest masters can be familiar with.
During the middle game, computers can evaluate far more possibilities than even the greatest grand masters can,
and during the end game they can see to the end far sooner than even the greatest grand masters can.
Further they have evolved past merely database and greater depth of analysis.
The best computer chess programs are starting to make speculative sacrifices with uncertain outcomes based on the probability rather than the certainty of a better result.
For all the complexity of chess – there are games even more complex.
And then there is life.
Chess is simple – even in comparison to what goes into making a pencil.
The best human chess players are frequently losing to the best computer chess programs.
But humans can do far more than play chess.
Kinda makes the stock market look silly, considering the super computers an complex algorithms used to trade.
Absent circuit breakers, I am convinced many stocks would trade down to zero on a daily basis, maybe the entire market.
The first “organic” lifeform hacked previous states of lifeless reality by solving what otherwise used to be dominant external forces that prevented its being.
Maybe the first “artificial” lifeform will do to organic life what organic life did to lifeless reality. Maybe all future life will be “artificial” and future computer program historians will look back and think that the first inorganic lifeform was a computer program that cracked the game of chess and solved what otherwise used to be dominant external forces (humans) that prevented its being.
Maybe all life arises in a game.
nate silver in his signal and noise had brilliant chapter on this one
As it happens I’m an expert in computer chess and have written several strong chess engines.
From an engines perspective there are indeed three stages – opening, middle game and endgame. In the opening and endgame the computer is really just accessing a large database. The opening database is a list of known good moves (of varying degrees of quality i.e. not perfect moves). The endgame tables are a list of known win / loss / draws. This leaves the middle game. You are correct in saying the computer uses heuristics to evaluate different positions and a form of brute force to search the alternatives. Over the years the heuristics have become more sophistated; the most important terms being material, mobility, passed pawn detection and king safety. However it is in the area of search where most progress has been made in the last 10 years. The best program (Stockfish), often selectively searches 35 moves deep in the middle game.
However, chess is far from being solved. There are an estimated 10^130 positions and even a selective search of 50 moves is far from adequate to bridge the gap between opening and endgame. However the strength of today’s engines is far above the best humans. Magnus Carlsen (the world champion) would probably score no more than 10% against Stcokfish on decent hardware and would struggle to win against Stckfish running on a meager iPhone.
Steve
Thanks Steve, very interesting. Maybe I’m 10 years out of date: You’re saying at this point, it’s no question that a supercomputer would destroy a human at chess? Back when I was into this stuff, the IBM team was just about to beat the world champ. But I guess the computer just keeps getting better while the best human doesn’t improve too much?
Yes – computer are without question better than the best humans. They have about a 500 ELO advantage, which correlates to winning 5% of the time.
There was an explosion in computer strength about 10 years ago. It was discovered that you could test changes to a program using very fast time controls (e.g. game in 5 seconds). In general the results scale to slower time controls. This enabled programmers to test lots of different evaluation functions and search strategies and figure out the best ones. In effect there was a shift from chess knowledge to statistical rigor. This strategy was extremely effective and raised the strength of chess engines to 3300 ELO, whereas the best humans are “only” 2800 ELO.
To give some idea of the strength of today’s engines, Deep Blue which beat Kasparov in 1997 was probably about the same strength as Stockfish is on an iPhone 5s!
Steve
To give some idea of the strength of today’s engines, Deep Blue which beat Kasparov in 1997 was probably about the same strength as Stockfish is on an iPhone 5s!
Holy cow. OK so when I said I was about 10 years out of date, I should’ve said 17. When I was into this stuff, Deep Blue had beaten Kasparov but the philosophers of mind (and pundits) tried to spin it as, “They basically designed a program that could beat Kasparov.”
If you have any anecdotes to add to my vague recollections that would be great. Your comments here are exactly what I was hoping for.
(BTW, you can’t explain why I lost my bet to David Henderson can you? Worth a shot.)
Deep Blue was specialized hardware and was created solely for the match. So it may have been tuned to play anti-human chess (i.e. lots of tactics and avoiding closed positions). Note also, it wasn’t until about 2007 when PC chess programs attained the same strength (i.e. just above the same strength as humans). Interestingly, we are at this stage now with Shogi (see here http://goo.gl/L1s8t), where the best computer engines are about the same strength as the best human Shogi players.
I’d suggest you download Stockfish onto your iPhone and have a play – it’s free (http://goo.gl/GZaruh).
Computer chess also highlights some interesting points about open source development and group creativity – but that’s for another time,
Steve
That’s fascinating.
So I was thinking of the “Equal Energy” challenge and I looked up that an iPhone battery contains approx 20kJ of energy. Presuming the iPhone could finish the game on one battery (let’s say the screen is switched off, etc… seems in the ballpark) so I asked a knowledgable friend how much carbs you get for 20kJ.
She said, about a quarter of a slice of dry toast.
Looks like the humans are a long way behind.
You’re correct that the computer uses brute force, that is its entire aim: to get at your king. But no, it doesn’t have a strategy or any sort of temporal intuition as the game commences. It merely calculates the odds of each move that has the best chance of not losing a piece, and then it makes it. It is only a coincidence that such moves have also been standards in the game of chess (but it makes sense).
While a computer chess opponent may seem to be on the offense, it is in fact always on the defense. That is its entire strategy.
Strategy is the wrong word. It’s programmed to not lose, but also to get your king. I’ve never played a computer that was not a defensive player.
Yeah, Computers can kick the butt of any human. ( I am a programmer ) Now for a real challenge computer versus computer, that is fun.
I am glad I read this. I lose at chess to my iPhone all the time. At a mediocre setting.
So—why build fighter jets and not drones?