Hash Tables Deep Blue

Discussion of anything and everything relating to chess playing software and machines.

Moderators: hgm, Harvey Williamson, bob

mjlef
Posts: 1279
Joined: Thu Mar 30, 2006 12:08 pm
Contact:

Re: Hash Tables Deep Blue

Post by mjlef » Fri May 19, 2017 11:54 pm

hammerklavier wrote:
Murray Campbell reported to me that each SP had 1 GB or ram (A lot for its day). There were 32 nodes, so a total of 32 GB.
Thanks Mark!
32Gb is really fantastic ! in 1998 the most common configuration was 64Mb ram in Pentium MMX/Pentium II
Yes it was pretty awesome for its day. I believe each SP node only had access to the 1 GB it had. Probably communications overhead between the "nodes" would take too much time.

Lyudmil Tsvetkov
Posts: 6031
Joined: Tue Jun 12, 2012 10:41 am

Re: Hash Tables Deep Blue

Post by Lyudmil Tsvetkov » Sat May 20, 2017 4:42 am

CheckersGuy wrote:
mjlef wrote:
hammerklavier wrote:How much Hash tables memory did Deep Blue use?
I sent your question on to Murray Campbell. While we wait, I know that part of the search in Deep Blue was done in software. The software had access to Hash tables. At the end noes of the software search a hardware search would be sent to the special chips. The hardware part of the search did not have Hash tables:

http://ac.els-cdn.com/S0004370201001291 ... 47f33639d8
I really wonder what techniques the top engines like stockfish/Komodo use which weren`t used by Deep Blue. Did DB use Null-Move/LMR/ProbCut ? Would be really intresting to know :P
I do not know about the search in particulars, but while browsing the net, I found a page with Deep Blue evaluation and, next to SF and presumably Komodo, Deep Blue evaluation is fully basic.

Not much to gain from hardware these days.

syzygy
Posts: 4167
Joined: Tue Feb 28, 2012 10:56 pm

Re: Hash Tables Deep Blue

Post by syzygy » Sat May 20, 2017 12:57 pm

Cardoso wrote:
I really wonder what techniques the top engines like stockfish/Komodo use which weren`t used by Deep Blue. Did DB use Null-Move/LMR/ProbCut ? Would be really intresting to know Razz
DB didn't use Nul Move, and probably didn't use LMR and ProbCut.
DB's pruning techniques were less intensive that the ones we have today.
In a speech Murray said DB's branching factor was 3 or 4, so as you can see there was not much intense pruning going on on DB's search.
DB did not prune beyond alpha/beta and that was a conscious choice. They were afraid of losing a game to Fritz or so due to a low-depth oversight.

Of course DB would have been much stronger even if they had only added null-move pruning.

kgburcham
Posts: 2009
Joined: Sun Feb 17, 2008 3:19 pm

Re: Hash Tables Deep Blue

Post by kgburcham » Sat May 20, 2017 1:05 pm

Lyudmil Tsvetkov wrote:
CheckersGuy wrote:
mjlef wrote:
hammerklavier wrote:How much Hash tables memory did Deep Blue use?
I sent your question on to Murray Campbell. While we wait, I know that part of the search in Deep Blue was done in software. The software had access to Hash tables. At the end noes of the software search a hardware search would be sent to the special chips. The hardware part of the search did not have Hash tables:

http://ac.els-cdn.com/S0004370201001291 ... 47f33639d8
I really wonder what techniques the top engines like stockfish/Komodo use which weren`t used by Deep Blue. Did DB use Null-Move/LMR/ProbCut ? Would be really intresting to know :P
I do not know about the search in particulars, but while browsing the net, I found a page with Deep Blue evaluation and, next to SF and presumably Komodo, Deep Blue evaluation is fully basic.
basic enough to make a world chess champion cry.
no chess program was born totally from one mind. all chess programs have many ideas from many minds.

duncan
Posts: 6492
Joined: Mon Jul 07, 2008 8:50 pm

Re: Hash Tables Deep Blue

Post by duncan » Sat May 20, 2017 10:49 pm

mjlef wrote:
hammerklavier wrote:How much Hash tables memory did Deep Blue use?
I sent your question on to Murray Campbell. While we wait, I know that part of the search in Deep Blue was done in software. The software had access to Hash tables. At the end noes of the software search a hardware search would be sent to the special chips. The hardware part of the search did not have Hash tables:

http://ac.els-cdn.com/S0004370201001291 ... 47f33639d8
would you know how many plies would a deep blue with today's hardware get ?

Cardoso
Posts: 272
Joined: Thu Mar 16, 2006 6:39 pm

Re: Hash Tables Deep Blue

Post by Cardoso » Sun May 21, 2017 2:13 am

syzygy wrote:
Cardoso wrote:
I really wonder what techniques the top engines like stockfish/Komodo use which weren`t used by Deep Blue. Did DB use Null-Move/LMR/ProbCut ? Would be really intresting to know Razz
DB didn't use Nul Move, and probably didn't use LMR and ProbCut.
DB's pruning techniques were less intensive that the ones we have today.
In a speech Murray said DB's branching factor was 3 or 4, so as you can see there was not much intense pruning going on on DB's search.
DB did not prune beyond alpha/beta and that was a conscious choice. They were afraid of losing a game to Fritz or so due to a low-depth oversight.

Of course DB would have been much stronger even if they had only added null-move pruning.
I understand, a single loss to Fritz would make the DB team look so bad, I mean with all that mighty hardware, yes, it would be bad for them.
I really wonder if DB had NM, would Kasparov win that single game?
And just imagine if DB had that agressive pruning of stockfish's NM/LMR/LMP.
It makes me wonder what the Kasparov match would have been if DB had these pruning mechanisms.
Nevertheless it was a great chess machine for the time, and it's a pitty so few games were played against it, both with kasparov and other grandmasters and also Fritz. It was a real magician trick IBM made, now you see it, now you don't :)

User avatar
Nordlandia
Posts: 1973
Joined: Fri Sep 25, 2015 7:38 pm
Location: Sortland, Norway

Re: Hash Tables Deep Blue

Post by Nordlandia » Sun May 21, 2017 4:59 am

Was 13 the average depth in the opening / middlegame?

Lyudmil Tsvetkov
Posts: 6031
Joined: Tue Jun 12, 2012 10:41 am

Re: Hash Tables Deep Blue

Post by Lyudmil Tsvetkov » Sun May 21, 2017 5:42 am

kgburcham wrote:
Lyudmil Tsvetkov wrote:
CheckersGuy wrote:
mjlef wrote:
hammerklavier wrote:How much Hash tables memory did Deep Blue use?
I sent your question on to Murray Campbell. While we wait, I know that part of the search in Deep Blue was done in software. The software had access to Hash tables. At the end noes of the software search a hardware search would be sent to the special chips. The hardware part of the search did not have Hash tables:

http://ac.els-cdn.com/S0004370201001291 ... 47f33639d8
I really wonder what techniques the top engines like stockfish/Komodo use which weren`t used by Deep Blue. Did DB use Null-Move/LMR/ProbCut ? Would be really intresting to know :P
I do not know about the search in particulars, but while browsing the net, I found a page with Deep Blue evaluation and, next to SF and presumably Komodo, Deep Blue evaluation is fully basic.
basic enough to make a world chess champion cry.
yeah, at 200 000 000 nodes/sec.

I do not know if I am right to assume that hash tables with the eval of Deep Blue would perform much worse than hash tables implemented in a much more refined engine(retrieving wrong eval would not be very helpful, you know)

Cardoso
Posts: 272
Joined: Thu Mar 16, 2006 6:39 pm

Re: Hash Tables Deep Blue

Post by Cardoso » Sun May 21, 2017 3:01 pm

Nordlandia wrote:Was 13 the average depth in the opening / middlegame?
Yes the software part could do about 12 ply depth for the nominal depth (non extended), however on some forced move positions, extensions could make it go to around ply 40.
Their search was a solild one without holes.
Todays searches on top programs, have many holes in them, but they are more than compensated by the increase of general depth.
Null Move, and specially LMR make a lot of assumptions and that can cause some holes in the search, but in practice they allow more general depth and as a consequence ELO increase.
Also move ordering on todays top engines are very good, SF is doing some great move ordering tricks, and this reduces immensely nodecount (for fixed depth searches comparisons) .
The chess chips of DB, didn't have killers and hashtable (so no hash move for move ordering).

Alvaro

Post Reply