Comments/Ratings for a Single Item

~~Earlier~~ ⇧Reverse Order⇩ ~~Later~~

Roberto Lavieri wrote on Thu, Jul 21, 2005 08:15 PM UTC:

Computer super-programs can blunder!. This is taken from Chessbase:
After six rounds of the Mercosur Cup in Argentina: 

Lafuente,P (2435) - SHREDDER [The super-program, estimated close to 2800]
Mercosur Cup Vicente Lopez ARG (3), 16.07.2005
1.d4 Nf6 2.c4 e6 3.Nc3 Bb4 4.Qc2 d6 5.Nf3 Nbd7 6.Bd2 0-0 7.a3 Bxc3 8.Bxc3
Qe7 9.e3 b6 10.Be2 Bb7 11.0-0 Ne4 12.Nd2 Nxc3 13.Qxc3 c5 14.Bf3 Nf6 15.b4
Rac8 16.dxc5 dxc5 17.b5 Rcd8 18.Rad1 Rd6 19.Bxb7.

Lafuente has just captured a black bishop on b7, after which White must
recapture. But Shredder plays the unaccountable:
 
19...Rfd8??

The official bulletin says it was definitely not a mouse slip or any other
kind of operator error, but that Shredder thought for over three minutes,
initially analysing 19...Qxb7 to a depth of 20 ply but then switching to
the move it ultimately played. The evaluation showed a slight advantage
for Black. Only after the next move the value suddenly dropped to show a
decisive advantage for White. Afterwards the organisers tested the
critical position again with Shredder and diagnosed the problem as a 'one
in a million' error in the hash tables. (!!!). Lafuente won the game
without problems, but Shredder won the Tournament.

Greg Strong wrote on Thu, Jul 21, 2005 09:56 PM UTC:

Thanks for the very interesting post.

I know that hash tables (in chess programs, normally called a
Transposition Table) can lead to the program confusing positions, but I
have never heard of a high-profile case of this actually happening. 
Here's how the transposition table works...  There are different
sequences of moves that can lead to the same board position, and the
program doesn't what to re-consider a position it has already considered,
so it keeps a look-up table of positions it has already considered.  The
look-up table is normally indexed by a 64-bit value (the locations of all
the pieces on the board are 'boiled down' into a 64-bit number.)  Since
there are more than 2^64 possible board positions, some different
positions can equate to the same key value.  This leads to mis-evaluation
of the situation.  The chances against this happening, however, are
astronomical!  One-in-a-million is actually quite an understatement - it
is really more like one-in-2^64 (assuming Shreader isn't programmed in
some really silly way, and I'm assuming it isn't.)  Guess it had to
happen sooner or later! :)

Transposition tables also lead to other problems.  For one thing, the
table entry only tells you about the position, not how you got there. 
This is a problem when 3-time repetition is involved.  A position can look
really good the first time you encounter it, but the next time you
encounter it, your pre-determined response may actually lead to a 3-time
repetition, and therefore a draw!

These are known problems.  Absolutely every commercial chess program has
bugs.  Bugs that the programmers are well aware of.  But, the very
occasional problem with a transposition table is negligable compared to
the benefit, so they use them anyway...

Roberto Lavieri wrote on Thu, Jul 21, 2005 11:34 PM UTC:

Thanks for the explanation. If Shredder has been well-programmed (It seems
it might be the case, Shredder is considered a gem), I doubt we are going
to see another case like this in our life!, so we have seen an exceptional
event, a really incredible one. Lafuente must consider himself a very lucky
man, probabilistically speaking, but perhaps he could want win the lottery,
it could be much more easy.

3 comments displayed

~~Earlier~~ ⇧Reverse Order⇩ ~~Later~~

Permalink to the exact comments currently displayed.