Hey man. Things are ok?
I want to clarify what I mean by solved here - when I talk about solving chess, I mean solve as in solving an algebra equation, or solving Tic Tac Toe. I don't care if you put the Japanese Earth Similator supercomputer on it, I will remain undefeated in 100 human-speed tic tac toe games. There is an algorithm you can follow that will ensure you never lose in that game. That's what I want, or at least part of what I want. In my definition, chess will be solved when:
A: An algorithm is laid out, no matter how complex, wherein white (or black) always wins, and this is borne out by extensive testing. I.E., a set of practical theorems of playing chess which may not be PROVEN (in an academic, theoretical, book-l'arnin way) to be true, but for which no counterexample exists.
B. Conversely, an algorithm is laid out by which the game inevitably ends in a draw, which I think is likely. (Call it the Tic Tac Toe solution.)
Or, separate from the practical solutions above...
C. A solution is arrived at by mathematical methods, whereby it is demonstrably proved that white (or black) must win, or which proves that the problem is unsolveable - that is, a THEORETICAL solution.
I would far prefer the latter. There are more ways than you would think to pin down academically "there is no way to determine the answer to this question in the universe we live in - it is unsolveable." I would be satisfied (and even comforted) by that.
Another anecdote that supports the computers-take-over theory comes from my Grad project interview with Larry Christiansen, U.S. Chess Champ in 1980, '83, and '02. I asked Larry whether and when he thought machines would be unbeatable by the best human players. He said that they already are unbeatable in short games like blitz (5 minutes) or rapid (up to 30 minutes), because even the most experienced human player can't keep up with the computer's calculation speed in games as short as these. Using a standard tournament clock, humans can still compete, says Larry, but not for long; he thinks it will be 5-10 years before Human/Computer standard tournaments are moot.
Larry knows the programmers from the Big Blue team, and he said that there is nothing to Kasparov's claim that a temporary shutdown of Big Blue helped it win the final game.
So while chess may never be reduced to an equation, it seems to have been solved with speed.
I had the previous post (Um, OK... etc.) on my hard drive for something like a month or two. I wasn't sure what else I wanted to say, or whether I believed what I had already said. This goes counter to the blogging no-edit ethos, I'm sure, but nobody has taught me the blogging ethos, I'm just sort of assuming it - so I'm probably making it up anyway. It's my blog, I'll edit if I want to. Or something.
Anyway, I saw a Nova I think, or a Scientific American or some other show, but I think it was Nova. I just thought you might be interested to know that somebody thought enough of my ideas not only to do it, but to make a TV show about it. (Tongue in cheek, obviously. Not only does the following probably confirm that my ideas are pedestrian, but that they are considered obvious by most in the field.) They (Case Western, maybe?) made a physiq of water, came up with several tonkatoy type pieces that could fit together, move, and "joint" in different ways, an algorithm to join the pieces together more or less randomly, another algorithm (I would imagine) that told it to move in more or less all the ways it could move, and said, SWIM!!! Each creation graded itself on its swimming ability. Successful swimmers got to "breed" again. (Sounds too much like college now. Just kidding.) Some crazy-ass little swimmers came out, not least of which was one that could only be called sperm-like.
Another school did a similar thing with a land physiq, and told its creations to walk. Which they did - not very well, but they walked - some of them anyway. It was disconcerting to see what you would have to struggle not to call "an organism" born, struggle, squim and fall over, helpless, a dead-end in natural selection - except that it is patently not organic, and the selection is absolutely artificial. The birthing is fake, they raw materials are fake - but the physiq is more or less real, and the effort of the creation to execute its task is still compelling somehow. Even the most successful entries (so far) in this fake contest of life generally seem to me not to be walkers, but odd creations that were apparently "designed" for some other purpose, that could also move around a bit, like a tent frame that by moving its center pole could shuffle around a few inches. Curious. Limits of the initial conditions of the game, I would imagine. Anyway, these researchers weren't as impressive in the simulation arena imho as the swimming folk were, but they went one step further (or back, depending on how much you value the physical world - which by the way is the fault in the Ontological Proof of the existence of God... but that's for another time in another blog.) They attached their computer where the simulation lived to a sort of general manufacturing apparatus, sort of like a kiln combined with a pottery wheel, capable of creating out of some sort of molded plastic-like muck (polymer maybe?) the model that the simulation had come up with. (!) You open the door, and there is the precise construct you just saw on the computer screen. A human plugs in a little motor where the computer tells it to, which provides the muscle to make the joints move (which the computer did in the physiq, of course), and presto - the thing should walk. Then they melt the sucker back down so the thing can create whatever it thinks of next.
It's a little spooky, actually. The machine comes up with some never-before-seen construct that walks in some way or other - whether it's a mangled paper-clip looking thing limping along by a free wire, or a tall drink-o-water who decided its primary mode of transport would actually be to fall down - gracefully, fluidly, with some degree of rigidity and curve, so that the fall continued until it was upside down. It would then continue to fall down again a few times, slinky-like, until it was out of momentum. Anyway, whatever the creation that the "random" engine came up with happens to be - paper clip, neo-slinky, warped swingset with an extra leg, whatever - if it grades out well, machines whirr, plate spins, blades shape, heat bakes, and bing! Your walker is ready.
Most fascinating. Not sure if things like this encourage my thoughts or discourage them. But there it is.
Um, OK. I'm going to try to get some things down that have been rattling around in my head. Most have been rattling for some time, some just since I started reading Darwin Among the Machines, which, by the way, appears so far to be an ambitious book executed in a helter-skelter, ad-hoc way, with some great ideas and research mixed with some ambiguous lines of logic and fuzzy thinking. In other words, it seems to have aspects of greatness mixed with fallibility and some amateurish execution, which should do nothing but encourage everybody out there with an idea to write a book.
I have referred to an opinion I hold that the part of the practical beauty and creativity of AI would arise if we were able to present a problem to it in terms it can understand, and have it work out solutions unguided that we would never have thought of, with as few rules of thumb or guidelines or shortcuts or heuristics as possible. (The most ready application I can think of for this sort of problem solving would be in design, and so I tend to focus on that, though the ability to solve more general problems is also possible.) This has little to do with a Turing test or HAL 2000 or machines with self awareness, but since it has to do with knowledge representation and creative "thought" without human intervention, I'll continue to use the term AI with this.
This sort of AI design system would obviously have to have methods of attacking the problem built in, and some of them would no doubt be methodical, systematic problem solving methods that we have developed, like linear programming, statistical analysis, probabilistic methods, finite element analysis and structural methods, thermodynamics, all the branches of physical and theoretical science and math including algebra, geometry, calculus, graphical methods, differential equations, formal logic and so forth, and of course the old reliable brute force techniques. Reactive techniques like pattern recognition and data mining, that seek to make sense of existing data, would also be a part of the toolset I'm sure. Once you have this toolset, there is enormous challenge in programming a comprehensive "brain" or overmind to analyze the problem, coordinate the execution of these methods and weigh and combine the results, even to analyze a problem that is precisely and meticulously designed specifically for the brain, laid out in a format ideally suited to the brain's processes. If AI becomes widely useful in solving problems, I believe there will be "brain companies" that will have as their primary missions to arrange and publish these "brains" and their toolsets - like the Mathematica suites they used to make and probably still do. I know there are many many programs out there that consist of frameworks to present problems to a processor for analysis by one or several methods; this will be similar, but infinitely more flexible. The layout of these brains and their tools, and the design of the interface, would be a worthy life's work for any 10 bright inventors, I think. I don't mean to minimize this task.
However, I will again state my opinion that this would be a creative and flexible and useful application of current human methods, and nothing more. While this may comprise artificial intelligence by some definitions, and certainly would greatly increase the utility of processors in aiding the creative process, nothing would be gained by using this tool that enough trained people given a reasonable amount of time couldn't also do. It's a timesaver, essentially.
An order-of-magnitude breakthrough in the solution of problems by a largely independent technological entity, however, will necessarily involve the ability of a machine to theorize about solutions, test them out, and adjust its hypothesis based on the results. An iterative process is the likeliest way that a machine will be able to proceed in an extended creative analytical process without the intervention of a human to evaluate intermediate results, re-set the problem in light of the results and start the process again. (This is how we currently design things, typically - we come up with hypotheses, design plans using technology but directed by us, construct models using technology but directed by us, perform tests using technology but directed by us, and then rinse and repeat. This rinse and repeat - evaluating the results, tweaking or reworking the hypothesis, and resetting the process is often very time and labor intensive, and is often the limiting factor in how many design iterations are allowed before the engineers are shot and production begins.) This ability of an AI system to make theories and test them out is probably a requirement, but I see only two ways to allow the machines this luxury: First, program the systems with the ability to make models of their tentative solutions, allow them access to physical facilities with appropriate robots and the ability to program them, and access to whatever proving ground is required for the problem at hand, along with measuring equipment. This has obvious problems (although, for specific kinds of problems, this isn't as ludicrous as one might think at first.) That brings us to the second option: allow the computer the use of a virtual test bed, or a consistent logical sandbox it can use to test its theories without mucking around with our physical world with all its costs and limitations. Meaning, a virtual world to test its solutions on - or more accurately, in.
This is a huge jump.
What we're talking about is programming a virtual reality universe in which friction is proportional to mass, where gravity is inversely proportional to the square of the distance between two objects, and so on. Newton's laws of motion hold. Relativity holds. Quantum mechanics holds. Acids and bases react. Iron rusts. Brittle items break, while plastic items stretch. Things we don't understand the causes of but are observable (like turbulent fluid flow, dark matter gravity and electron spin symmetry) can be included too. The more complete the physics of the model, the more accurate the results, but for most applications, (designing an aerodynamic car, for example), quantum effects might not have much bearing (much less the gravitational pull of dark matter). For these applications, you might be able to buy a slimmer, less complete brain with less of our observable world built in. It is not necessary to present a visual interface for this space; in effect, it is a set of behaviors that describes in equations the forces that govern the behavior of our world. But the world has to be ready for any object you throw into it, and it has to respond similarly to the real world within the acceptable tolerances. With my limited experience, I haven't heard of such a thing, so in my little world I live in, I get to call it whatever crazy name I feel like. Let's call it a physiq - that is, a coherent, virtual universe for use in developing and testing theories, which includes a framework for introducing objects, behaviors, or systems of objects and behaviors, and which produces results analogous to the real world. (Kenley Technologies' "Milky Way Light," the easy, flexible, affordable physiq for everything you need to do, on sale now, only $1995!)
(By the way - this ability to automatically rinse and repeat is one of the reasons chess has been so successful and common as a playground for AI - it's a finite universe with discrete success and failure criteria - a win or a loss - and it's easily represented in the abstract. So, a system can be programmed with the rules, hypothesize, that is, put forth a possible move, and then analyze possible following moves, then do it again, all without having to actually do anything in the physical world. If the AI had to actually make all the moves it analyzes on a real chessboard using a robotic arm in order to analyze lines of play, the efficiency of the process would obviously be drastically reduced. Deep Blue gets to do the rinse and repeat of the design process without any human intervention at all.)
Now that we have a sandbox in which our "brain" can test its model, we get to tell our brain what we are looking for and set it to working. This "working" is key, of course. The toolsets and physiqs of our AI's will continue to improve, and are crucial to the efficacy of this process. But the manner in which the overmind proceeds with the designing of hypotheses and the corresponding models is where the real designing happens. Most "design" in whatever field comes from using rules of design we have learned, applying them in a way that meets design parameters and is pleasing, with the occasional dash instinct or playing to a hunch thrown in. Even when a Eureka moment occurs these days, it is often in the design or redesign of a small component of a larger system.
However, here is where our AI shines. Our AI, with its huge processing power and quick iterations, will, if we want it to, have the advantage of redesigning everything as many times as it wants, from the ground up. No assumptions, no taken-for-granteds. No dogma holding it back. We can ignore all the things we think we know, the assumptions we make about design. We can start our AI back in the figurative primordial ooze, saying here is a table of substances we know of, here are costs of labor and raw materials and energy, here is what we're trying to accomplish, now go at it.
The likely engine of this process? Evolution and related techniques. Mutation, randomness and survival of the fittest.
More on that at another time.
The ability of computers to provide a forum or a framework for the evolution of systems, combined with automated problem solving methods, an interative design process, an interface for presenting a problem and a productive overmind... Here we have not only the makings of artificial intelligence, but an automated system that fundamentally exceeds what a human brain could even theoretically achieve. It would be a combination of reason and nature.
Now we're talking.
A few thoughts and wild-a**-guesses after watching game 4 of Kasparov v. Fritz --
- GK played for a draw again, although I can hardly blame him. The game was sharp and white was ahead on development. Not to state the obvious, since GK took longer on this move than all the others, but taking 13 pxd5 rather than nxd5, while it reduced his attacking options and made one of the commentators look bad, dulled the game and avoided the dreaded queen sacrifice. Might have been a draw either way, but GK would have sweated through one of his elbow-patched sports jackets if he accomplished it. Taking with the bishop on the next move created a "bad bishop," covering white square pawns with a white square bishop, but it developed the bishop regardless, consolidated his defense, connected the queen and rook, removed the bishop from the scope of the invading white queen, reinforced his center and generally made things a lot more tenable and calm for the flustered GK. Half the variations went out the window right there. When Qxf6 a few moves later, suddenly the defense is solid, white's forward queen, while still causing havoc, is now also a liability, and all the weaknesses that GK used to have are now limited to a nominally weak bishop (although it was protected by exhange) and a pawn that, while also nominally weak, was centrally located, passed, and had the force of all of black's heavy armor watching over it. And, while the Queen is at first blush both blocked and stuck guarding lesser pieces, the diagonal is about to open up, and the connected rooks provide almost immediate attacking possibilities, switching from defense to offense quickly when the black Q opens the lines with qxp. Don't care what Yasser Seirawan says, black did the smart thing, not least of all because it got white out of it's opening book by move 14 - still late, but not as late as it could have been. Take the queen sacrifice, and it goes into the twenties, with Kasparov in deep waters and having already shot his proverbial psychological wad while the computer is merrily making moves every 5 seconds on a meticulously chosen line. Of course, it wouldn't have been merry, but it would have seemed that way to the sweaty, hives-ridden Kasparov and the chortling commentators if it pursued an obviously prepared line that late. (Mistakenly in my opinion - who cares if it's still book? Book means tenable for both sides, or else everyone would play the line or it would disappear.) Speaking of which:
- Funny how White's final game starts with a QP opening, of all things, leading directly to an opening line which happens to exactly mimic a QGA line from a game with who? Kramnik. Which, the first time around resulted in what? GK sacrificing the queen, which would be ludicrously risky against the machine. Here's the way I see the Fritz team's strategy - and of course, this is all human strategy, has little to do with artificial intelligence, and demonstrates why we still haven't seen a true man v. machine test:
Let's play for the draw on black and win on white. Meaning, let's cram in full, broad, 25 move opening books on a few of the sharp lines Kasparov likes to play, that are suicidal against a computer, like, oh, QGA, special, narrow packages for when we have white. We only play white twice, so we can concentrate on only two. If we spend a little less time on the other opening lines or on fine tuning the evaluation engine, who cares? As long as the payoff is that we come up with two lines out of all the lines out there that we like and that we know he'll follow us into, we'll likely win (unless he finds a way to blunt the lines and slow the game back down - see 13 pxd5 above). We'll let the standard engine more or less truck away on the black side and hope for a draw, but on white we'll custom tailor aggressive lines from obscure history on sharp openings that lead him right into our strengths - like for instance a line from a speed chess games he played against the nominal world champ. No mindf'ing there. GK could have shat when b-b3. He could smell Kramnik's cologne.
- As an appendix to the first paragraph - not to pick on Yasser, but taking with the pawn on f7 and ruining the pawn structure in front of his king would have been a serious mistake against a computer. In my humble 1500-ish opinion, taking with the queen instead was the second most important move of the game, and Seirawan missed it totally. (He made up for it by spotting black's mating possibilities many moves ahead though, and broadcasting them, despite Maurice's discomfort at the lengthy discourse.)
- ESPN obviously decided Jeremy Schaap (the MC from the Deep Junior match) was completely unnecessary. They were right on. I heard they were in intense negotiations until the last minute to get Maurice Ashley, and he did fine. Schaap tried to be enthusiastic, but he brought a spirit of bemused befuddlement that any ESPN anchor would likely have brought to chess, and it didn't play particularly well. Maurice handled the point guard duties just fine, although it was a little silly to hear one grandmaster ask another, "Can you show me some of the lines that Garry is facing here?" when he clearly knew them at least as well. Still, it certainly was better to have someone who knew the issues at hand and took it seriously be the one to dish out the straight lines, even if he would rather have been the one showing off and delivering the punch lines.
- I'll take credit for foreseeing the frustration Kasparov would have with the interface in crunch time. What I didn't fully appreciate, however, was that he's also the greatest living blind-chess player. When he got tired of the interface, instead of having to put up with it and losing his cool, he basically eschewed that riduculously expensive board setup altogether, taking the glasses off (!) for all of his serious thinking. Next generation virtual reality, ha - they could have sent him the moves via teletype for all the difference it made to him. Kudos to him for realizing that he might do better blind (with the help of prodding questions from the press after game 3) and moving seamlessly into his own head with minimum distraction to his personal carbon-based electrochemical Fritz in game 4.
- A star is born! Joel Laurien is the next big chess glamour boy. The crowd ate him up. He also will have better luck against machines, with his stoic demeanor. And he likes Fischer and speaks english like a native. Joel Laurien's even a good chess name.
- Kasparov, while he is by far the biggest star and is the only man alive who would have made this event what it was, objectively speaking, is precisely the wrong person to be defending the honor of mankind against an impassive mechanical opponent. He relies on agression, putting pressure on an opponent, going for the kill, playing mind games, and generally impeding the thought processes of his opponent by distracting him with other concerns - what Garry is doing, how much pressure there is on the king, why am I sweating down my collar, it's only move 15, why are his rooks next to my queen, I can't believe I'm playing this guy, is everyone watching me, why am I always on the defensive, and, oh yeah, what if I lose in spectacular fashion? This is exactly what the computer does to people. Not only does the computer not react at all to his ploys, which gradually makes him panic, but it uses his own tricks on him. Some of his best weapons rely on the emotion of (in this case) an emotionless opponent,or the imperfect lines of thought of (in this case) a perfect thinker. The computer plays like Kasparov about as well as Kasparov does, and the irony is that he is particularly vulnerable to his own brand of chess. Witness the ridiculousness of him reacting so emotionally to a move made by a computer chip! He looked like he wanted to cry. If you want to cry, do it after the match. It's only going to distract you now. Put your demons back in their boxes, and look at the board! It affects his play, and especially his endurance, and it always has.
Basically, I believe the best person to play a computer is the best person to play Kasparov, and vice versa. That person is not GK. It very well may be VK.
- Human chessplaying against machine opponents in 5 years will be a matter of frantically pruning trees, narrowing possibilities and hoping against hope for a draw. Assuming, that is, that there are still people willing to pay millions to produce a chess engine, and ESPN is still interested. If not, it may take another few years before it's reduced to that level of absurd defensiveness in the face of superior firepower. You simply must innovate, or play for a draw, if you are going against an extension of all existing chess knowledge.
Ray continues to flummox me. Among the things you'll appreciate, Rob-o...
"Kurzweil's latest work -- given the ominous title The Singularity is Near -- forecasts a century that he claims will see the merging of "biological" and "artificial" intelligence to the point that, by 2099, the two distinctions will have conjoined and perhaps even fused.
At the core of Kurzweil's thesis, summarized in his précis of Singularity, is what he argues is a double-exponential growth in technology to date..."
"Most people have a linear view of the future," he said. "People look at the 21st century, and they expect 100 years of progress at today's rate of progress. But because we're doubling the rate of progress every 10 years, we're actually looking at 20,000 years of progress during the 21st century. That's quite a difference in outlook. You get to a point where the rate of progress is so fast that it's virtually a rupture in the fabric of human history."
And this relates directly to some things we've discussed ...
"It's a continuum. If you look at how computers are designed today, human designers specify the top couple levels of parameters," he said. "But then the next 12 levels of design are done automatically by computers. Then the computers are assembled by computerized systems. It's very much a collaboration. If you compare that with how computers were first built, it was done entirely by hand."
Other interesting things. And here's a link to Bill Joy's anti-tech manifesto, if you or anyone else reading this hasn't read it, it's required reading. http://www.wired.com/wired/archive/8.04/joy_pr.html
Lots of commentary on this article, if you were unaware - many people taking sides with Joy or Kurzweil, ironic given the fact that they're both brilliant and both very similar thinkers in reality.
Your comments about AI in the wake of Kramnik's draw with Deep Fritz got me thinking...
(An interesting theory says that a creation can never exceed its creator - i.e. God could never create something greater than God, and we could never invent a brain smarter than our own brain. I hope that isn't true, at least in limited contexts - I believe we can give a machine a framework to create and innovate, test its own creative theories, and integrate new knowledge into its existing framework without human intervention, and that given a suitable process and framework to think and grow it could, um, evolve to be better than we are. Directed by our own efforts, no, I don't think our creations can exceed us. In that light, I offer the following.)
I think the Chess machines are limited by the same thing almost all "artificial intelligence" efforts are limited by these days - we make them think more or less like humans instead of like Gods. Both teams (Deep Blue and Deep Fritz) are efforts not to perfect chess or to add to chess knowledge, but to encapsulate an functional encyclopedia of what we know about chess - our conventional knowledge. Each piece is issued a point value (which changes a bit based on the situation, but not much.) Castled kings are better than uncastled kings. A square in the middle is better than a square on the edge. Covered pawns are better than loose pawns. Paired knights and bishops are better than one of each. Etc. etc. etc. They sought to use brute force to go through all possible positions - but they needed human evaluations to say "this position is better than that position" to direct the search. Rules are used for evaluating positions, and then other rules are used for pruning the branches of their search, so that they could discard branches unlikely to produce ideal moves. They go further with these rules, or heuristics, with extensive opening books and endgames, known gambits and lines of play, and even finetuning for individual opponents.
Heuristics are shortcuts. They make the project feasible at this point, but they also place a limit on the quality of the tool we produce. Given the current strategy of producing chess programs, the ultimate product is simply the perfect historical chess player. It will know every noteworthy game played, know every line, adjust values of positions and pieces based on the historical games of its opponents, and find positions and moves no human would ever have found, not because it thinks better than humans, but because it thinks FASTER and more perfectly. It never forgets, never gets confused in its thinking, is absolutely methodical. The perfect result of this endeavor would be the ideal exponent of current human chess theory. Would a person ever be able to beat that machine? Only if that person has knowledge the machine doesn't have, either because it knows more than the programmers, or because the person has innovated, that is, added to the available chess knowledge on Earth. And if the player innovated, could they win a game? Even a series? Sure, until the programmers analyzed the innovation, understood it and successfully added it to the program's repertoire.
This is where chess programs (and AI in general) fail in my opinion. They mimic our understanding of the universe in question (be it the reaches of space or an 8x8 board.) I think AI should answer the question, if God came down and took white, what would His first move be? I posit that we don't have that answer yet. The computer plays our best guess of moves. It uses our rules, our conventional wisdom, our understanding of the problem's universe to make decisions. AI will have reached a critical threshold when we find a framework to present the problem to it and it makes its own decisions about the game.
I believe first off that it is entirely possible that Chess is solveable. I also believe it is entirely possible (though somewhat unlikely) that the ideal first move is 1. Kn-A3 or 1. P-H4. I believe that much of our conventional wisdom on chess is correct; I also believe that even good rules have exceptions, and that not all of our rules are as good as we think they are. They appear good because they are greeted with typical, imperfect, human responses.
When Chess can be presented as a math problem to a mathematical processor, with the only human input being the rules of the game, THEN we will have a machine that can teach us Chess instead of the other way around. And when we have a processor imbued with the laws of physics, and the things we value as "good" as its inputs, that can treat (say) aerodynamics and engine design as a mathematical problem, that is the day we have cars that are environmentally friendly. What are the chances that the gasoline-powered internal combustion engine is the ideal choice for personal transportation? Nil. It's just the best one that occurred to us in the 100 or so years that people were thinking of such things. What are the chances that Ruy Lopez or Guioco Piano or any other line of play is the best of all possible lines of play? Slim.
So, will there ever be a machine we can't beat? Theoretically we will have the slimmest of chances as long as we have the ability to innovate beyond the machine's ability to deal with innovation. But until we eliminate the shortcuts, the human evaluations beyond winning is better than drawing is better than losing, our chess machines will always be cousins of "The Turk", the Chess Automaton containing a human being with all its frailties. And there will always be thinking people to play the Poe, trying to find and expose the charlatan inside.
Regarding Artificial Intelligence...