Author: Robert Hyatt
Date: 10:37:06 07/15/03
Go up one level in this thread
On July 15, 2003 at 10:26:02, Uri Blass wrote: >On July 15, 2003 at 09:44:34, Robert Hyatt wrote: > >>On July 15, 2003 at 02:36:27, Uri Blass wrote: >> >>>On July 15, 2003 at 00:37:32, Robert Hyatt wrote: >>> >>>>On July 14, 2003 at 18:38:51, Uri Blass wrote: >>>> >>>>>On July 14, 2003 at 16:35:05, Robert Hyatt wrote: >>>>> >>>>>>On July 14, 2003 at 16:32:17, Robert Hyatt wrote: >>>>>> >>>>>> >>>>>>One thing more I should add. Cray Blitz searched about 20K on a single YMP >>>>>>CPU. On the genius PC (486/33) it could not hit 100 nodes per second. For >>>>>>a speed reference. >>>>> >>>>>I think that comparing the same program is misleading. >>>>>I guess that a programmer who needs to write the same algorithm for 486/33 is >>>>>going to write it in a different way. >>>> >>>>I think some of the things are simply _not_ going to be done. Too slow. >>> >>>What did you do in cray blitz that you believe that you cannot do on 486/33 >>>because of speed? >> >>1. Quality mobility. Take the set of squares a piece directly attacks. >>Instead of counting mobility = sum of squares, compute a "usefulness score" >>for each square on the board, and compute mobility = sum of usefulness scores >>for the squares attacked by that piece. It is computationally intensive, >>but very fast on a vector machine. > >How do you calculate the usefulness score? >I think that if calculating the usefulness score is not expensive then >calculating the sum of usefulness score is also not very expensive. Calculating the sum of N values chosen more or less randomly from a population of 64 values (mobility would attack a random number of squares on the board) is not fast. The usefulness score we used had several components. distance to opponent's king. centralization. attacking a square in front of a passed pawn so that it can be blockaded or captured if it moves. These were things we did while computing _other_ parts of the positional scores. We stuck these values in an array, then sucked them out with a vector merge once we knew which particular squares were attacked. > >> >>2. King safety. What pieces attack the area around the king, and how close >>to the king are the squares that are attacked? What about indirect attacks >>such as two rooks or rook/queen or bishop/queen in "battery"? How hard is it >>to get defenders over to help? Again, all pretty straightforward to calculate, >>but way slow. Unless you have vectors. > >I think that Ed attack tables are about similiar information and Rebel is not >extremely slow. I don't know how to compare them very easily, so I have to pass on trying to do so. I only know that I don't do some of those things today because when I first implemented them in Crafty, they cost too much. > >> >>3. Hash table. We did 8/16 probes. But not to consecutive table entries. >>We used another 9 bits from the hash signature to generate a random offset >>to probe to, to better distribute the entries and avoid clustering/chaining. >>Horribly slow on a PC. Absolutely free on a vector machine. > >This is not an evaluation decision sand I thought about evaluation. > It's an important aspect of the total search engine. In the case of Cray Blitz, doing this on a PC kills the NPS. >> >>I'm sure there are other things I have missed. One comparison. On the >>486/33, Cray Blitz ran at under 100nps. Well under. It varied from a low >>of about 10, to a peak of maybe 75-80. Crafty on that same machine would >>hit around 3.5K to 5K. Figure a speed difference of about 100X at least. > >> >> >>> >>>I mean to things that you think that the price in term of speed is more than >>>being 10 times slower because I assume that Crafty can hit at least 1000 nodes >>>per second on 486(I have not 486 to test so it is only a guess). >>> >>>Uri >> >>It's primarily a matter of a "different approach". Vectors allow things that >>are simply too slow with a PC, no matter what you try to do to make it >>efficient. On a PC, sequential memory addresses are _way_ more efficient >>than random accesses. On a vector machine this is not true at all. The first >>word of any vector is the slowest to access. The next N are free. And the >>next N don't have to be consecutive. They can be uniformly spaced through >>memory, or randomly spaced. > >I understand that the machines are different but I am not convinced so easily >that things are too slow without trying to do them on PC. I _have_ tried them. Remember that Crafty came directly from Cray Blitz. I tried most everything I did in CB, and eliminated those things that were too expensive for the gain they provided. IE hashing as in Cray Blitz was also the starting point for Crafty, but I discovered the PC was dying for memory bandwidth and I went to the Belle approach to control the bandwidth demand for hashing. > >there are a lot of things that it is possible to do faster by defining better >data structures. True. However Cray Blitz wasn't written in 3 months. It was a 20 year project so its data structures were _not_ ugly at all. > >Uri
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.