Just curious if a powerful home PC and chess program are a match for the 1997 version of IBM’s Deep Blue that beat Kasparov?
Are current PC chess programs powerful enough to beat the Deep Blue program that beat Kasparov in 97
I’m no chess expert, but the question brings up two informative websites.
The Computer Chess Rating Lists website shows the top ranked program Houdini with an Elo ranking of 3256 using a 4 core 64bit processor.
According to Wikipedia, Magnus Carlsen has an Elo rating of 2872. Kasparov’s highest rating was 2851.
I’d hazard a guess that a powerful desktop computer would outclass 1997’s Deep Blue.
[QUOTE=Wikipedia]
Deep Blue, with its capability of evaluating 200 million positions per second, was the fastest computer that ever faced a world chess champion. Today, in computer chess research and matches of world class players against computers, the focus of play has often shifted to software chess programs, rather than using dedicated chess hardware. Modern chess programs like Houdini, Rybka, Deep Fritz, or Deep Junior are more efficient than the programs during Deep Blue’s era. In a recent match, Deep Fritz vs. world chess champion Vladimir Kramnik in November 2006, the program ran on a personal computer containing two Intel Core 2 Duo CPUs, capable of evaluating only 8 million positions per second, but searching to an average depth of 17 to 18 plies in the middlegame thanks to heuristics.
[/QUOTE]
They are saying that the PC software searches less positions per second.
Pretty much they are saying they don’t bother making Deep Blue software since its pointless having a software that is impossible to beat.
Well the PC software looks more moves a head but does a less thorough search by missing (assumed) useless territory.
Deep blue did chess steps at the rate that a 3 million MIPS regular computer would, but it was custom , somewhat chess specific, hardware so it wasn’t actually a 3 GIPS CPU system.
A modern intel cpu with 4 cores is only 100,000 MIPS. Double that for 8 cores, and you can get servers that run 32, 64 cores… and you can inflate the MIPS a little because they are 64 bit , if you are comparing to 32 bit data or 16 bit data CPU , but that for the same program, it won’t help. (software has to be re-written for 64 bit. Well the old rule was 90% of the program is in 10% of the code, so you could get gains by rewriting 10% of the code, but that may well be significant… and can’t in anyway be “automatic”… you can’t 64bitify an old executable or even the source code just by clicking “fix” !)
See
Ratings are the better measure here than instructions per second or positions per second. The latter measurements might indicate in some sense how much power you have, but don’t address how well you’re using that power. Ratings, though, just deal with the simple question of whether you win or lose games, and against which opponents.
Nowadays, it’s the GPUs on the video card that have the most power in better PCs. You can have thousands of cores working in parallel. Not very powerful each, but good enough for simple alpha-beta searching.
If they were to get a program like Houdini to utilize a top end video card, the result would be amazing.
What would happen on a Deep Blue vs. Modern Computer software on 8 cores and 64 bits game?
There was one critical difference in Deep Blue vs Kasparov – Deep Blue had at least one GM operator (Joel Benjamin, I think). They were able to pre-program certain opening lines in anticipation of Kasparov’s repertoire, and they, during the game, they could “force” Deep Blue to make the move that, at any time, was being evaluated as the best. So GM Benjamin was able to use his human intuit as to what move was best, or when to let Deep Blue keep on searching for a better move. This is a big difference vs a stand-alone engine.
(As a very good (but not great) player, I find top chess programs very frustrating to play, because they cheat! If you’re able to negotiate all the pitfalls to an even ending, the engines then just access an end-game encyclopaedia, instead of having to calculate. I know chess endings very well, but it takes time to recall the proper techniques. I would be much more accurate if I could rely on all my end-game manuals to compete.)
Chess Engines offer nothing to me, except for training purposes. Their is no fair play.
It’s a slight sidetrack, but as an internationally-rated player I’d like to comment.
The ‘end-game encyclopaedia’ is known as a tablebase and is created by collecting all possible positions with a maximum of x pieces on the board (currently they’ve finished with 6 and are working on 7.)
Once all positions are stored, they are classified - first into mates in 1 move, then all positions that lead to the mates in 1 and so on.
The result is a database that simply uses a look-up to tell you (with best play) whether a position is mate in x moves or drawn.
So a computer program that reaches a position with 6 pieces left uses a tablebase to play perfectly without doing any analysis.
I don’t think of this as cheating - rather just having a better memory.
But as Bellhorn rightly says, tablebases are very useful for analysis and understanding of endings.
You can find them here:
Consider these rook ending positions (all Black to move):
White: Ke6, Ra7, pe5
Black: Ke8, Rf1
White wins whatever Black does.
White: Ke6, Rh7, pe5
Black: Ke8, Rf1
Only 1. … Kf8 draws.
White: Ke6, Rh7, pe5
Black: Ke8, Re1
Now both 1. … Kf8 and 1. … Kd8 draw.
That’s got to help players understand these sort of important positions. 
They have just updated the list, and now Stockfish is #1, with a rating of 3265.
Amazingly, it’s open source, and the source is full of helpful comments. If you want to learn how to code a chess program, this should do it.
A few years ago, I was tired of always losing to chess programs like Fritz, so I decided to write my own. I figured that since I didn’t know much about it, it wouldn’t be very good, and I’d be able to beat it.
I was half right. It wasn’t very good, but I still wasn’t able to beat it.
Without a doubt, modern chess engines, like stockfish, komodo and Houdini, running on a good desktop would beat Deep Blue soundly. The reason we know this is because Deep Blue barely beat Kasparov. Remember, Kasparov won the first game and only lost the match by one point. And in the game he lost, the computer made a move which totally surprised Kasparov because it wasn’t the kind of move chess engines normally find. In fact, I think it’s been said that no engine since Deep Blue has suggested that particular move. Therefore, Kasparov thought there might be some funny business behind the scenes, like Grandmaster intervention to override the computers move.
Kasparov was flustered after this and demanded to see the computer’s evaluation to know for sure that the computer had come up with that move. (As a side note, at the end of that game, Kasparov actually had a chance to draw it but missed the combination of moves which would have forced a draw.) In any event, Kasparov definitely held his own against Deep Blue, losing only by a point (one game). This means (with the little data we have) that Deep Blue wasn’t significantly better than the top grandmaster. However, chess engines today are supposed to be way superior to even the top GM. The only problem is that there aren’t any high profile GM vs. Computer matches today, so we can only assume that the top chess engines would destroy even the best GM today. However, I think it’s a pretty good assumption.
Also, someone mentioned the vast difference in rating. However, we can’t rely on this because, since humans and computers don’t compete against each other, their respective ratings fall into two totally different fields with no way to directly compare one to the other. For all we know, an engine with a 3000 rating might only be rated 2800 against humans. Then again, a 2800 human player might have a 2600 rating against computers. We simply have no way to know.
The only way to really solve this conundrum is to have a high profile match between the best human player and the top Engine. However, unless some billionaire is willing to fork over a whole lot of cash for it to happen, it’s unlikely that we will ever see it.
Just a curious observation about the changes in machine architecture. There is an interesting advantage in moving to a machine with a native word size of 64 bits. With 64 bits you can represent a bitmask for the entire board in one machine word - or register. This means a fundamental unit of representing the underlying mechanics of the move engine can sit in a register, and be operated upon in a single instruction. Compared to doing the same thing on a 32 bit machine this is a big win. So, I would expect the move to a native 64 bit machine to have had a much bigger effect on speed than most programs see. Also, cache size will have a huge impact, the moment the main data structures (which seems to mean the move engine’s lookup tables) all fit into cache the thing will take off speed wise. Caches and data fit are the key to speed-up and super-linear speed-up in parallel codes. When these effects occur simple comparison of machines by MIPS or some other naive speed metric are useless.
Indeed the nature of building a chess engine make the usual metrics of machine speed a bit useless. Many GPUs will be a very poor fit as well.
What can you do with just a board bitmask, though? What you really want is a data structure that can store a board position, which is a few times larger than that (precisely how much larger depends on how you’re storing it).
Bitmasks can convey things like -
all the positions a particular piece can move to
all the location that are theatened
all the locations that are occupied
all the locations that are threatened in x moves
Then you can perform logical operations on them - essentially building an algebra of the entire board. If the move engine works with this sort of representation it can churn a lot of moves very quickly. This is especially true if there are lookup tables for the bitmasks. For instance a 64 entry table of bitmasks can return a bitmask for every possible move for a piece in a single index lookup. XOR it with a bitmask of your own pieces locations, and then again with a bitmask of all threatened locations and you have in about five instructions a bitmask of all safe moves for a piece. And so on.
Clearly a fully populated board would need 32 bitmasks to represent the location of every piece, which is not minimal. But you fast start to build up much more valuable bitmasks, ones with much more useful content than a simple location of a piece.
Hm, yes, I was just thinking of a bitmask showing “occupied” or “vacant”, and if that were all you had, it’d be of pretty limited usefulness. It didn’t occur to me to have separate bitmasks for the legal moves of each individual piece, or the like.
IANASEWWCABIAASE* and I don’t think the bit masks would improve overall performance by much. I would think the overall processing would be so complex that having a bitmask in a single register (as opposed to two registers) would be such a small piece that it would hardly be measurable.
-
- I Am Not A Software Engineer Who Writes Chess Algorithms But I Am A Software Engineer.
Chess players like this aren’t complex programs. The usual structure is pretty simple. You need a search heuristic driver, an evaluation function, and a move generator. The bit that takes the most time is the move generator, which spits new positions out, and drives deep into the search space. The evaluation function works out whether a final position is much good - but it does this with a pretty simple set of rules, as simple as assigning a points value to each piece left on the board, but maybe with some improved rules that weight some locations better than others. You don’t want a complex rule, and by definition, the evaluator does not concern itself with possible next moves - that is the job of the move generator and search engine.
The search engine probably does the least work computationally, and is usually some sort of overarching system that prunes off bad looking branches of the search tree - such as an alpha beta pruning algorithm.
Openings and endgames are driven differently, and both are amenable to table lookup. Endgames can be distilled down to a set of known algorithms - ie two kings and a knight/bishop/rook have easily expressible rules that require no real effort.
The biggest part of this style of game playing is the ability to generate positions a long way down the search tree. Pruning off bad branches lets you go further down, but you are still generating a gazillion positions. Both the move generator and the evaluator will use bit masks extensively to represent what they need. Moving from32 to 64 bits on an x86 gets you a fantastic increase in speed if your basic atom is 64 bits long. It would be interesting to compile Stockfish for both 32 and 64 bit ISAs on the same hardware and benchmarking them. I would not be surprised to see a 50% speed bump in favour of the 64 bit version. Likely more.
As glee already pointed out, this is in no way “cheating”, and from an AI perspective I have to disagree with you even more emphatically. The fact is that almost everything a chess-playing program does is different than what a human player does. What matters is the final result. “Cheating” would be if the chess computer had a little man hidden inside it who made the moves.
AI in its early years was criticized on the preposterous grounds that it wasn’t “really” intelligence because it was “just a program” employing algorithms and heuristics and was fundamentally different than human thinking. Guess what – modern aircraft fly, but they don’t flap their wings. So what? It’s still flight, and they fly faster, higher, and farther than birds.
I wonder - the number of extra choices involved with each move means that doubling your processor power won’t allow the program to look twice as deep - I would imagine it might barely get you half a move more. It’s exponential, not linear.
(OTOH, that half a move extra might make all the difference)
Yeah, something like that… Though we’ve also a lot more than doubled since the days of Deep Blue. So, a few moves further depth, not just one.
It is brutal, which is why chess is interesting. The heuristics that make such a chess playing program viable are all about culling the search tree, and keeping the exponent small. The increase remains exponential, but if you keep the constant low, you can keep it under control for a deeper search.
The down-side is that you won’t see “brilliant” out of the blue moves as the the pruning will discard sub-trees that don’t seem promising early, and will concentrate on those that seem to maintain a better outcome. Early programs didn’t have very sophisticated position evaluation and tended to rely upon their ability to search a reasonable depth. This tended to yield a program that was very good at combinations, and would play quite aggressively, quickly forcing a reduction in pieces and moving to an endgame where it (hopefully) held a piece advantage. Positional play (as exemplified by better players anyway) would counter the effectiveness of such behaviour.
The position evaluation functions now do a lot more work on evaluating the quality of the position - and going back to the value of bitmasks - you can represent useful things like threat zones, location of pinned pieces, coverage by a piece, each in a single bitmask. Logical operations, or evaluating a weighted metric of goodness can happen quickly. The value of the weights applied are probably the other bit of magic. They embody a lot of experience (either human, machine learnt, or statistically derived from analysis of many games) that is not visible in the program, but is a key part to its success.