Author: Robert Hyatt
Date: 09:30:15 12/02/97
Go up one level in this thread
On December 02, 1997 at 11:47:13, Don Dailey wrote: >On December 01, 1997 at 11:25:35, Marcel van Kervinck wrote: > >>On November 30, 1997 at 06:41:25, Don Dailey wrote: >> >> >>Don wrote: >> >>>My position is that bit boards are "probably" better in the long run but >>>I will be willing to change my mind if it turns out I am wrong. I also >>>argue that dynamic knowledge is more easily and more efficiently >>>implemented >>>with bit boards. I don't mind taking a commital position here because >>>I >>>can always change my mind later! I would like to see this discussion >>>continue because there may be much to be learned. >> >>Could you elaborate a bit on the use of bitboards in CilkChess? >>Eg, how much did you gain in raw speed by converting to them on the >>alphas, and how does it compare to Crafty on the same hardware? >> >>The reason I ask is the silly test we did just after the last >>round in the Dutch open, yesterday. If I recall correctly, my >>non-bitmap program searched about 120 knps on your machine in >>the starting position. Based on the Sparc results, I would expect >>it to the reach 150+ in a typical middlegame position without any >>effort. I don't think it can run much faster than that, however. >>You said your program computed at about the same speed, but that >>there is quite some new knowledge overhead. Can it grow there? >> >>Marcel van Kervinck > >Hi Marcel, > >It sounds like we are computing about the same number of nodes per >second, but I'm using bitboards. I personally do not believe bitboards >are a big win if you just want a really fast program but perhaps Bob >or others will disagree (or agree.) Since I am new to bitboards it >could also be that case that I'm doing a few things wrong. I don't believe they are a big win *until* you reach 64 bit machines, but then they do have architectural advantages. Since we are forced to pump 64bit quantities around inside these chips, it is far better if all 64 bits are needed, of course... We really need a "64 bit test" to measure this. IE The note I wrote about Ferret gaining 1.64 when moving to the alpha/500, while Crafty sped up by 3.1. This is mainly attributable to the 32 bit vs 64 bit architecture.. > >A lot of people have been pressuring me to add a lot more knowledge to >my program. I did an autotest study which indicated a knowledgable >program will improve more with depth (which was the opposite of my >intuition.) > >So with the new Cilkchess using bitboards, I decided to not be overly >concerned about the overhead of lots of knowledge. This program has >more knowledge than my others (depending on how you count heavily pre- >processed stuff) I think it has been typical for my programs to spend >no more than a few percent of time on evaluation (maybe 15-20% ??) but >this one spends more than half its time. I think this was improved by >some of the local whiz kids here at MIT but it's still quite expensive. >I'm pretty convinced bit boards are the way to go for a knowledge >intensive >program but there is an ongoing debate about this and some would not >agree. I can state with confidence that this program would not have the >same QUANTITY of knowledge and still be reasonably fast if it were not >using bitboards. > I tend to agree. I did *not* start working on bitmaps, just to make a faster Cray Blitz. I did it as a "quest for knowledge"... to see if bitmaps offered anything that offset programming didn't. For the first 6 months to a year, the answer was "no". But then as the paradigm began to "sink in" I discovered things that were most useful. IE the rotated bitmap idea is one thing that makes bitmaps "work". Without this, the cost of incrementally updating things was high enough that there wasn't a lot of speed advantage. But the most important "gains" came from experience as I began to "think bitmaps" and discover efficient ways to do complex things. IE in Cray Blitz we *never* tried a legal move generator, as it was too slow. I have one that is perfect, and fast, in crafty... My profile runs show about 50% of my total time is spent in the evaluation code. This is slowly expanding. I'd like to take the time to go back and "tune" this as it could probably be done a little faster, but time has been scarce. I generally try to implement knowledge as something I can understand easily (code-wise) and then if it works out to be beneficial, I go back and start speeding it up (computing something incrementally when needed, or rewriting things to be faster...) >It is really difficult to define how much knowledge a program has. When >people talk about how many TERMS in their evaluation function or speak >of knowledge like it's a quantity (like I just did!) it can get >confusing. I agree. estimates might include my 50% above, multiplied by the NPS rate. This would (could) give a ms per eval. But that is difficult to compare, since some things in bitmap-land are instantaneous. > >A really good pre-proccessor can package up a lot of chess concepts into >a really tight package and there seems to be no reasonable way of >measuring >this. You cannot say, "my program has a IQ of 50 chess principles" and >it >mean much. I'm anti-preprocessing at today's speeds. I regularly search to 11-12 plies in the middlegame. What was true at the root might have nothing to do with what is happening at the tips. For this reason I do a full endpoint evaluation only, just as I did in Cray Blitz... > >But I am saying that I think I've captured a lot of chess concepts that >my >other programs ignored and it has proven to be somewhat expensive. A >lot >of it could be approximated cheaply with piece/square pre-proccessing. > >I'm going to persue this however, look for cheaper ways to say the same >things and we are now working specifically on recognizing compensation >for >a pawn or exchange. I hope the program does not slow down too much. > >I would like to see you experiment with bit boards if you feel inclined. >I think we need a lot of people doing this to answer the question of >which approach is better if any. If you decide to do this keep in touch >please. I'm interested in other experiences with them. I want to hear >from people especially who have done both. > >Does your evaluation comsume a lot of time? If not, your program >should >run much faster with bit boards than it did last Sunday on our Alpha. >It's hard to say however without either of us knowing too much about the >details of both programs. Like Crafty, we don't have any secrets here >and I'm willing to share the ideas and implementation details of our >stuff. > >Our program is still extremely new so I don't know how things will look >in the future. I think we are capable of much better than what we saw >in this tournament. Even though 9 1/2 and clear second seems like a >good >tournament, we had 4, 466 mgz Alpha's versus only Pentiums. Most >programs >would have done quite well too with our hardware. > > > >Don keep it up. When I read the chess 4.x stuff years ago, I thought that bitmaps were "well-understood." This was obviously wrong. The rotated bitmap idea came out of a meeting with several grad students that were interested in the original "crafty" version that incrementally updated things like chess 4.x did. But in explaining what I was doing to these students, I pointed out how easy it was to update the attacks along a rank by doing a lookup. Someone asked "why not along the files or diagonals" and I explained that the bits were not adjacent. We dove off into the idea of "rotating" the bitmap as needed, but that was hopeless unless I built a special-purpose machine (can you imagine a machine with three "rotate" instructions that simply take the base occupied-squares bitmap and re-route the bits to their correct rotated positions for this methodology? would be a 1 cycle instruction and would eliminate 75% of the make/unmake code that updates the rotated maps.) From that small jump, I made the large leap to incrementally update the rotated bitmaps rather than trying to rotate the one occupied square bitmap as needed. It worked and is still working for me... There are likely *many* other such ideas that will pop up over time. But someone has to get their feet wet to catch the disease. :)
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.