Answers.Body: <p>I can't speak for the algorithm used for Deep Blue, but I'm going to try and explain the improvements in chess programming.  Speed is the greatest improvement.  Deep Blue used multi-processor dedicated computers, so a comparison isn't really possible.</p>
  
  <p><a href="https://chessprogramming.wikispaces.com/" rel="nofollow noreferrer">https://chessprogramming.wikispaces.com/</a> is a great source, but it's hard to navigate.  </p>
  
  <p>There are 3 main functions that are tweaked to improve a chess engine are the evaluation, move generation, and search functions.</p>
  
  <p>Evaluation is the hardest to program, as there are many exceptions to the rules.  With hard drive space getting cheaper, the eval function allows for more exceptions to be evaluated.</p>
  
  <p>Move generation, along with making and unmaking a move, consumes a lot of memory because it has to be preformed so many times.  The most common generation functions are mailbox, bitboard, 0x88, 8x8, extended boards (10x10, 10x12), and a predetermined move array/table  (*I use an indexed move table).  Current opinion is that bitboards are the faster, and using magic bitboards speed this by up to 30%.  Dr. Robert Hyatt, professor and creator of cratfy chess engine, claims no significant speed increase.</p>
  
  <p>The early search function was the primitive min-max functions.  Basically were you try to maximize the score of the side to move and minimize the opponent's score.  Alpha-Beta was the first improvement.  They reduced the number of moves being searched by transposition table, cut-off values, aspiration windows, and history heuristics.  These are depth-first searches.  There is also the internal iterative deepening search which tries to search the "best" move(s) the deepest hoping that searching other moves will prove to be fruitless.</p>
  
  <p>NOTE:  My index table.
  GNUChess and Jester both use an index array to generate their moves.  They initialize the engine by filling array with possible moves.  The take the six pieces and compute the legal moves that are available from each square.  So each piece had a [64][8] array.  I took this idea and compressed it to two indexes and a table.  The table holds a value which tells if the 16 moves are possible, one index holds the offset of the move, and the other holds the mask.</p>
  
  <p>offset[] = {-8, -1, 1, 8, -9, -7, 7, 9, -17, -15, -10, -6, 6, 10, 15, 17};</p>
  
  <p>mask[]   = {1, 2, 4, 8, 16, 32, 64, 128, 256, ...};</p>
  
  <p>Then the generation of a sliding move is as easy as looking up the validity of it's mask in it's allowable offsets against the move table.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-26T13:59:29.463Z
Answers.Text: This is answer is both wrong and too technical. While they are generally faster modern chess engines do not look at significantly more positions/moves than older ones. The main improvement comes from better evaluation and pruning. Very notably, stockfish 14 is actually a lot slower than stockfish 10 (as measured in nodes-per-second) but much stronger in playing strength: https://github.com/dkappe/leela-chess-weights/wiki/The-Great-Stockfish-NPS-Debate
Answers.UserDisplayName: blues
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-08-17T02:28:55.447Z
Answers.LastActivityDate: 2017-08-17T02:28:55.447Z
Answers.UserDisplayName: Fred Knight
Answers.Body: <blockquote>
    <p>Did the algorithms get better?</p>
  </blockquote>
  
  <p>Obviously, yes a little bit.</p>
  
  <blockquote>
    <p>or were the improvements mostly due to the same algorithms running faster
    thanks to faster hardware and software?</p>
  </blockquote>
  
  <p>Minor nit: If the algorithms got better then that is the software getting better so there is no "or".</p>
  
  <p><a href="https://en.wikipedia.org/wiki/Moore%27s_law" rel="nofollow noreferrer">Moore's Law</a> tells us that processor speed will double roughly every 18 months. That means it has doubled roughly 13 times in 20 years. That makes modern processors somewhere in the region of 8,000 times faster. So, far and away the biggest improvement in engine performance is due to faster hardware.</p>
  
  <blockquote>
    <p>If the former, are these algorithmic improvements public?</p>
    
    <p>And if so, what were the improvements? Where can I read about them?</p>
  </blockquote>
  
  <p>Well, it wasn't the former, it was the latter. Nevertheless the improvements are mostly open source and freely visible by <a href="https://stockfish.s3.amazonaws.com/stockfish-8-src.zip" rel="nofollow noreferrer">downloading the sources for engines like Stockfish</a>. Perhaps also worth giving the <a href="https://stockfishchess.org/download/" rel="nofollow noreferrer">general Stockfish download link</a> since the specific source code link will likely expire when version 9 comes out.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-26T14:04:30.223Z
Answers.Text: This is wrong and it's easy to test this: Let a modern chess engine play against a 10 or 20 year old one but give the old engine better hardware. Result: the modern engine overwhelmingly wins. Computers got much better at "understanding" chess, so they don't need to brute force analyze every position that much anymore.
Answers.UserDisplayName: blues
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-08-17T10:59:17.480Z
Answers.LastActivityDate: 2017-08-17T10:59:17.480Z
Answers.UserDisplayName: Brian Towers
Answers.Body: <p>Disclaimer: not an expert.</p>
  
  <p>The algorithms got better, and today's best engines running on 1995 (remember Deep Blue was 1999) hardware will handily beat Kasparov. As I understand it, there are two aspects of algorithms:</p>
  
  <p><strong>Search</strong>. If for example I take your queen with my queen, a human opponent will automatically look first at recapturing. For a computer however, it will evaluate every possible response to QxQ. Almost all of the time, this is wasted processing power. A good search algorithm cuts down all these "branches" since they're irrelevant anyway. </p>
  
  <p>The standard search algorithm is <a href="https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning" rel="nofollow noreferrer">alpha-beta pruning</a>, and it was used in the earliest chess computers. I don't know if Deep Blue used alpha-beta pruning, but modern engines don't. As a result their searches are "unsafe" - they can miss, for example, that some move other than recapturing the queen would've won the game. However, it's rare that this happens, and in return they push their depths very high. ("Depth" is a technical term for how deep the engine searches, so e.g. an engine that searches to depth 30 is likely to beat one that only searches to depth 20, all other things being equal).</p>
  
  <p><strong>Evaluation</strong>. This is the other prong of engine code. Given a particular position, is it better for white, black, or equal? This can involve all sorts of functions, e.g.</p>
  
  <ul>
  <li>If one side has extra material/space, give it a bonus to eval.</li>
  <li>If white has an advanced knight supported by a pawn, give white a bonus to eval.</li>
  <li>If black's king is stalemated, give white a bonus to eval.</li>
  <li>If white has a rook on the 7th rank, give white a bonus to eval.</li>
  <li>If it's an endgame (and there are algorithms to decide whether the position is an endgame) and both sides have opposite color bishops, impose a penalty to eval (i.e. push it towards 0.00).</li>
  </ul>
  
  <p>Today's engines evaluate positions much better than Deep Blue.</p>
  
  <p>As for whether the algorithms are public, Stockfish is currently the world's strongest engine and it's open source. You can download the code yourself from <a href="https://github.com/official-stockfish" rel="nofollow noreferrer">Github</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-16T04:04:37.380Z
Answers.LastActivityDate: 2018-11-16T04:04:37.380Z
Answers.UserDisplayName: Allure
Answers.Body: <p>It's all about algorithms.</p>
  <blockquote>
  <p>Taking on a human chess player took one of the most powerful computers in the world at the time. This brute force computing approach allowed Deep Blue to look around six to eight moves ahead. In a closely-fought contest, the machine eventually defeated Kasparov by 3 1/2 games to 2 1/2.</p>
  <p>Six years later, Kasparov was involved in another contest of man versus machine. This time he played against Deep Blue’s successor, Deep Junior. The result was a drawn series at three games all. The biggest difference was that Deep Junior ran on a machine with about one per cent of the computing power of Deep Blue. Chess-playing algorithms had improved to the point of achieving virtually the same result with a hundred times less computing power.</p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-15T11:29:05.247Z
Answers.Text: Welcome to Chess! You wrote the main portion of your answer as if it was a quote; could you please provide a source?
Answers.UserDisplayName: Glorfindel
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-15T10:52:56.647Z
Answers.LastActivityDate: 2018-11-15T11:28:23.953Z
Answers.LastEditDate: 2020-06-17T09:59:59.497Z
Answers.UserDisplayName: David Hambling
Answers.Body: <p>Maybe you can take a look at <a href="http://www.talkchess.com/forum/index.php" rel="noreferrer">TalkChess</a>, a forum dedicated to computer chess. I found a recent thread that might be interesting for you: <a href="http://talkchess.com/forum/viewtopic.php?t=62868" rel="noreferrer">Progress in 30 years by four intervals of 7-8 years</a></p>
  
  <p>A couple of matches between (former) top engines are played on the <em>same hardware</em>. The test suggests that in the recent years (2002-2017), the gain is mainly made by software improvements. In the test, Stockfish (2017) scored an impressive 94/100 against RobboLito (2009), while RobboLito, on its turn, crushed Shredder (2002) with 92/100.</p>
  
  <p>An important remark: as parallel computing is not implemented in the older engines, the test was performed on a single core. As a result, the hardware gain by parallel machines is not measured. On the other hand, you could argue that parallel computing is also a software gain: it is not easy to design and implement an efficient and well-scaling parallelization for the search algorithm.</p>
  
  <p>The <a href="https://stockfishchess.org/" rel="noreferrer">Stockfish</a> engine is open source, so the algorithmic improvements are public. A lot of documentation can be found on <a href="https://chessprogramming.wikispaces.com" rel="noreferrer">https://chessprogramming.wikispaces.com</a></p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-08-26T08:14:21.617Z
Answers.LastActivityDate: 2017-08-26T08:26:05.070Z
Answers.LastEditDate: 2017-08-26T08:26:05.070Z
Answers.UserDisplayName: Maxwell86
Body: <p>Computer chess engines have gotten better since Deep Blue beat Kasparov in 1997.</p>
  
  <p>Did the algorithms get better, or were the improvements mostly due to the same algorithms running faster thanks to faster hardware, etc.?</p>
  
  <p>If the former, are these algorithmic improvements public?</p>
  
  <p>And if so, what were the improvements? Where can I read about them?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-01-04T06:34:52.267Z
Comments.Text: My humble answer: https://chess.stackexchange.com/questions/19575/is-deep-blue-outdated
Comments.UserDisplayName: SmallChess
Tags: <engines><programming><computer-chess><chess-algorithms>
Title: How did the engines improve since Deep Blue?
ThreadText: # How did the engines improve since Deep Blue?
  
  (Asked by: username_0 on 2017-08-16)
  
  Computer chess engines have gotten better since Deep Blue beat Kasparov in 1997.
  
  Did the algorithms get better, or were the improvements mostly due to the same algorithms running faster thanks to faster hardware, etc.?
  
  If the former, are these algorithmic improvements public?
  
  And if so, what were the improvements? Where can I read about them?
  
  **Tags:** engines, programming, computer-chess, chess-algorithms
  
  > **Comments:**
  > **username_1**: My humble answer: https://chess.stackexchange.com/questions/19575/is-deep-blue-outdated  
  
  ---
  
  ## 5 answers
  
  ### Answer by username_8 on 2017-08-26. Score: 10 | Accepted answer
  
  Maybe you can take a look at [TalkChess](http://www.talkchess.com/forum/index.php), a forum dedicated to computer chess. I found a recent thread that might be interesting for you: [Progress in 30 years by four intervals of 7-8 years](http://talkchess.com/forum/viewtopic.php?t=62868)
  
  A couple of matches between (former) top engines are played on the *same hardware*. The test suggests that in the recent years (2002-2017), the gain is mainly made by software improvements. In the test, Stockfish (2017) scored an impressive 94/100 against RobboLito (2009), while RobboLito, on its turn, crushed Shredder (2002) with 92/100.
  
  An important remark: as parallel computing is not implemented in the older engines, the test was performed on a single core. As a result, the hardware gain by parallel machines is not measured. On the other hand, you could argue that parallel computing is also a software gain: it is not easy to design and implement an efficient and well-scaling parallelization for the search algorithm.
  
  The [Stockfish](https://stockfishchess.org/) engine is open source, so the algorithmic improvements are public. A lot of documentation can be found on <https://chessprogramming.wikispaces.com>
  
  
  ---
  
  ### Answer by username_2 on 2017-08-17. Score: 3
  
  I can't speak for the algorithm used for Deep Blue, but I'm going to try and explain the improvements in chess programming. Speed is the greatest improvement. Deep Blue used multi-processor dedicated computers, so a comparison isn't really possible.
  
  <https://chessprogramming.wikispaces.com/> is a great source, but it's hard to navigate.
  
  There are 3 main functions that are tweaked to improve a chess engine are the evaluation, move generation, and search functions.
  
  Evaluation is the hardest to program, as there are many exceptions to the rules. With hard drive space getting cheaper, the eval function allows for more exceptions to be evaluated.
  
  Move generation, along with making and unmaking a move, consumes a lot of memory because it has to be preformed so many times. The most common generation functions are mailbox, bitboard, 0x88, 8x8, extended boards (10x10, 10x12), and a predetermined move array/table (\*I use an indexed move table). Current opinion is that bitboards are the faster, and using magic bitboards speed this by up to 30%. Dr. Robert Hyatt, professor and creator of cratfy chess engine, claims no significant speed increase.
  
  The early search function was the primitive min-max functions. Basically were you try to maximize the score of the side to move and minimize the opponent's score. Alpha-Beta was the first improvement. They reduced the number of moves being searched by transposition table, cut-off values, aspiration windows, and history heuristics. These are depth-first searches. There is also the internal iterative deepening search which tries to search the "best" move(s) the deepest hoping that searching other moves will prove to be fruitless.
  
  NOTE: My index table.
  GNUChess and Jester both use an index array to generate their moves. They initialize the engine by filling array with possible moves. The take the six pieces and compute the legal moves that are available from each square. So each piece had a [64][8] array. I took this idea and compressed it to two indexes and a table. The table holds a value which tells if the 16 moves are possible, one index holds the offset of the move, and the other holds the mask.
  
  offset[] = {-8, -1, 1, 8, -9, -7, 7, 9, -17, -15, -10, -6, 6, 10, 15, 17};
  
  mask[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, ...};
  
  Then the generation of a sliding move is as easy as looking up the validity of it's mask in it's allowable offsets against the move table.
  
  > **Comments:**
  > **username_3**: This is answer is both wrong and too technical. While they are generally faster modern chess engines do not look at significantly more positions/moves than older ones. The main improvement comes from better evaluation and pruning. Very notably, stockfish 14 is actually a lot slower than stockfish 10 (as measured in nodes-per-second) but much stronger in playing strength: https://github.com/dkappe/leela-chess-weights/wiki/The-Great-Stockfish-NPS-Debate  
  
  ---
  
  ### Answer by username_4 on 2017-08-17. Score: 2
  
  > Did the algorithms get better?
  
  Obviously, yes a little bit.
  
  > or were the improvements mostly due to the same algorithms running faster
  > thanks to faster hardware and software?
  
  Minor nit: If the algorithms got better then that is the software getting better so there is no "or".
  
  [Moore's Law](https://en.wikipedia.org/wiki/Moore%27s_law) tells us that processor speed will double roughly every 18 months. That means it has doubled roughly 13 times in 20 years. That makes modern processors somewhere in the region of 8,000 times faster. So, far and away the biggest improvement in engine performance is due to faster hardware.
  
  > If the former, are these algorithmic improvements public?
  >
  > And if so, what were the improvements? Where can I read about them?
  
  Well, it wasn't the former, it was the latter. Nevertheless the improvements are mostly open source and freely visible by [downloading the sources for engines like Stockfish](https://stockfish.s3.amazonaws.com/stockfish-8-src.zip). Perhaps also worth giving the [general Stockfish download link](https://stockfishchess.org/download/) since the specific source code link will likely expire when version 9 comes out.
  
  > **Comments:**
  > **username_3**: This is wrong and it's easy to test this: Let a modern chess engine play against a 10 or 20 year old one but give the old engine better hardware. Result: the modern engine overwhelmingly wins. Computers got much better at "understanding" chess, so they don't need to brute force analyze every position that much anymore.  
  
  ---
  
  ### Answer by username_5 on 2018-11-16. Score: 0
  
  Disclaimer: not an expert.
  
  The algorithms got better, and today's best engines running on 1995 (remember Deep Blue was 1999) hardware will handily beat Kasparov. As I understand it, there are two aspects of algorithms:
  
  **Search**. If for example I take your queen with my queen, a human opponent will automatically look first at recapturing. For a computer however, it will evaluate every possible response to QxQ. Almost all of the time, this is wasted processing power. A good search algorithm cuts down all these "branches" since they're irrelevant anyway.
  
  The standard search algorithm is [alpha-beta pruning](https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning), and it was used in the earliest chess computers. I don't know if Deep Blue used alpha-beta pruning, but modern engines don't. As a result their searches are "unsafe" - they can miss, for example, that some move other than recapturing the queen would've won the game. However, it's rare that this happens, and in return they push their depths very high. ("Depth" is a technical term for how deep the engine searches, so e.g. an engine that searches to depth 30 is likely to beat one that only searches to depth 20, all other things being equal).
  
  **Evaluation**. This is the other prong of engine code. Given a particular position, is it better for white, black, or equal? This can involve all sorts of functions, e.g.
  
  * If one side has extra material/space, give it a bonus to eval.
  * If white has an advanced knight supported by a pawn, give white a bonus to eval.
  * If black's king is stalemated, give white a bonus to eval.
  * If white has a rook on the 7th rank, give white a bonus to eval.
  * If it's an endgame (and there are algorithms to decide whether the position is an endgame) and both sides have opposite color bishops, impose a penalty to eval (i.e. push it towards 0.00).
  
  Today's engines evaluate positions much better than Deep Blue.
  
  As for whether the algorithms are public, Stockfish is currently the world's strongest engine and it's open source. You can download the code yourself from [Github](https://github.com/official-stockfish).
  
  
  ---
  
  ### Answer by username_6 on 2018-11-15. Score: 0
  
  It's all about algorithms.
  
  > Taking on a human chess player took one of the most powerful computers in the world at the time. This brute force computing approach allowed Deep Blue to look around six to eight moves ahead. In a closely-fought contest, the machine eventually defeated Kasparov by 3 1/2 games to 2 1/2.
  >
  > Six years later, Kasparov was involved in another contest of man versus machine. This time he played against Deep Blue’s successor, Deep Junior. The result was a drawn series at three games all. The biggest difference was that Deep Junior ran on a machine with about one per cent of the computing power of Deep Blue. Chess-playing algorithms had improved to the point of achieving virtually the same result with a hundred times less computing power.
  
  > **Comments:**
  > **username_7**: Welcome to Chess! You wrote the main portion of your answer as if it was a quote; could you please provide a source?  
  
  ---
  
  