the video is really worth watching. i don't know much about chess / computer chess, but it makes it very clear how the ability to prune well and so search deeper is leading to more "human" play.
The computer is seeing patterns that aren't apparent to humans. Patterns of time and momentum, with pieces scattered across the board. Non-local multidimensional high-complexity patterns.
Of course the best players also see deeper than the rest of us. But in hindsight the moves are rational and the patterns visible, because they're the kinds of patterns we can grok.
I wonder if this just a teaser, a taste of things to come. If we can model a situation we can simulate it. Weather, traffic congestion, etc. With a cost function and players, we've got a game engine. Cooperative or competitive.
So how does this evolve? Phone apps that organize flash mobs? Google cars that weave helter-skelter without stop lights on bi-directional lanes. Software that calls all the plays, coaches the game, generals the war, controls the money supply or the trading on a futures market.
Will we become the spectators, happily playing our side of an invisible gambit?
I'm going to have strange dreams now about our future... artificial intelligence so advanced that it doesn't see the point in destroying us when it can just relentlessly prank and troll the world. :)
The world of chess engines is the world of search algorithms. I've read that exploring a search tree is inherently serial, and while there have been large performance increases over the years (Houdini and other top engines are 3000+ ELO), it seems they have not substantially outstripped the single-threaded performance of modern CPUs.
There is a chess programming wiki[0] (which was possibly referred to in the article) which gives some examples of parallel search algorithms. There is also a chess engine written in openCL which is not terribly strong as yet. Those of you with greater knowledge of algorithms may find these problems interesting; if I had a dedicated GPU to hand I'd probably be hacking on it.
This is indeed very revealing on the interesting qualities/properties of the engine => "...and so I was watching how this game developed – Houdini sacrificed a pawn, two pawn, three pawns in a queen-less middle game, to end up winning the game in convincing fashion. During the game I wasn't sure at all that what we were seeing was a brilliant game – and not some obscure bugs I’d left in the engine… I don’t think any other engine could have played this game the way Houdini did..."
> During the game I wasn't sure at all that what we were seeing was a brilliant game – and not some obscure bugs I’d left in the engine
That reminds me of an interview I read many years ago with an author of one of the then leading chess engines. They were doing some last minute fiddling before a tournament, and they accidentally introduced a bug that effectively reversed the goal of the game. Their engine wanted to lose.
At first, you would think that this would readily become obvious. You might expect that once it got past the opening book, where it plays by rote, it would start leaving pieces undefended, not capturing enemy pieces that are open.
That is not what happened. Actually, it played well for most of the middle game. The reason is simple--when it evaluated the board in order to formulate a plan to lose, IT ASSUMED THE OPPONENT WAS ALSO TRYING TO LOSE!
To win a game of chess where the goal of both players is to lose, what you are going to have to aim for is a position where you have such a strong position that you can force the opponent into a situation where you can check him, and to get out of check he is forced to checkmate you. In short, you have to completely dominate the opponent in order to ensure you will lose--and this means you have to play a really really good middle game.
Interesting anecdote, but my guess is that your last sentence is an incorrect assessment of what was going on. Chess engines almost all perform a min/max search on the game tree to bounded depth with static evaluation used to evaluate the leaves of the search. My guess is that what was going on is that the really bad moves weren't noticed to be really bad because it assumed the opponent wasn't going to capitalize on the mistake. It seems implausible to me that the engine was somehow able to look ahead to the end game and figure out that the only way to win at misere chess is to be winning going in to the end game.
In my scholastic chess days I used to play a lot of suicide chess between rounds. What continually amazed me is how very few players could grasp the basics of how to play suicide. The nature of suicide chess strategy was too conter-intuitive I guess. I'd be capturing be after piece after piece and they'd get their hopes up only to have them crushed near the end when my superior force proved decisive. To lose at chess, one must first win.
I don't know about the internals of the chess engine you are talking about but it would be interesting to read about it.
Basically most engines are minimax (or proof-number search) and alpha-beta pruning based.
I guess that in the game you describe the algorithms are the same but it choses the worst scores instead of the best ones.
It's commonly called "suicide chess" and when two suicide-chess AI confronts, there are always strange results.
That's funny, I thought it was well understood that Houdart didn't write 99% of Houdini, but it's an improved version of the public domain Ippolit/Robbolito sources, the latter being GPL.
It's a bit like calling Alan Cox "author of the widely used Linux operating system".
There seems to be quite a lot of controversy over the lineage of quite a few of the top chess engines, from what I recall reading. I can't find the article I'm remembering this from right now, but I think it was focused on [a] decision to disqualify Rybka from some rankings.
Ippolit stands accused of using decompiled parts of Rybka, Rybka itself may[2] be using bits of Fruit, and possibly others.
I don't know enough to comment about the strength of the various allegations, but there are definitely conflicts over the exact authorship/heritage of a lot of the top performers.
(yt link just to video https://www.youtube.com/watch?feature=player_embedded&v=...)