Author: Robert Hyatt
Date: 11:07:31 11/30/97
Go up one level in this thread
On November 30, 1997 at 11:09:40, Chris Whittington wrote: > >On November 30, 1997 at 09:58:06, Robert Hyatt wrote: > >>On November 30, 1997 at 06:58:43, Chris Whittington wrote: >>> >>>Ok, let's take a concept that will be important for a knowledge program, >>>but would be generally ignored by a fast program: "what is the largest >>>piece that can be safely moved into this square ?". ie a swap-off / >>>exchange evaluation rendered slightly more complex ........ >>> >>>offset: you have pre-computed attack lists of all defenders and >>>attackers and x-rays onto the square. these attack lists are organised >>>as 16-bit fields with the largest piece values in the mosts significant >>>bits. You also know which pieces are pinned and by what. >>> >>>64 bitmaps: you have bit fields of all pieces. should you have >>>pre-computed attack maps on each square - yes, if Crafty does. should >>>you have pre-computed x-ray maps onto each square - yes, if Crafty does. >>>should you have pin knowledge - yes, if crafty does. (and "yes, if >>>crafty does" should refer to what the currect version of carfty actually >>>DOES, not what Bob claims it could do if he wanted). >> >>more below, but you need to get past a basic misconception: anything >>you >>do now is hard or impossible for bitmaps. > >No, I'm not saying that. I'm just asking the questions. It intrigued me >that you used to say theat Crafty would really fly on a 64 bit machine; >but then, when we saw the numbers, it didn't seem to be flying (and that >was comparing a 32-but emulation of the 64 bit code, with the actual 64 >bit code). So I thought, well lets take a look at these alleged bitmap >advantages ....... > OK, here's the math to answer this question. Bruce reported Ferret ran 1.75X faster on the alpha/533 than on the P6/200. Since the alphas seem to scale well based on mhz, Scaling this to 500mhz gives a 1.64X speedup when moving Ferret from a P6/200 to a alpha/500. Crafty gets a 3.1X performance boost using the same two machines for the speed tests, 80K on a suite of positions (P6/200) to 250K on the same suite on the alpha/500. 3.1/1.64 is roughly 1.9X. So Crafty runs 1.9X faster than Ferret when moving from the P6 to the alpha. Where does that factor of almost 2 come from? From the 64bit words on the alpha... > >>This is simply a false >>assumption >>based on lack of experience with bitmaps. > >Yes, its true. I'm a 64-bit virgin :) they take time to get used to. I wrote and rewrote things several times as I became more familiar with them. I'm probably still learning ways to do things quickly and also easily... > >> After using these things for >>3+ >>years now, I don't see *anything* I can do with offset that I can't do >>with >>bitmaps, > >Indeed, can we get past this one ? Its software, we can do anything any >way we want. I know. > >>and I see lots I can do more efficiently. > >Maybe, but the key is can you do intensive knowledge processing faster ? >Because, if you can't, and if its more laborious to code/execute; then >your paradigm is a design compromise that just about forces the designer >to shy away from intensive knowledge and towards bits, bytes and all the >other non-chess specific stuff. If you try this for a good while, you begin to see we aren't thinking about bits or bytes at all. Rather about "sets" of squares with some sort of commonality, such as all squares occupied by white pawns, or all squares attacked by a bishop on X with the board occupied as it is at present. Think "sets of squares" and not "bits"... And use macros to hide the AND/OR/XOR stuff and it becomes pretty readable as well... > > >> IE, the square of >>the >>pawn idea I mentioned is one trivial example that replaced dozens of >>lines >>of code in Cray Blitz by a single load/AND operation in Crafty... > >If you keep banging on about this one example only, forgive me for >thinking it might be the only example. I refer to this because both of us do it. We can take move generation: I can generate moves to *any* set of squares you'd care to mention, and *not* have to loop over the squares that are not members of this set while doing so. IE for captures, if a bishop can capture 3 pieces, the move generator for that bishop loops 3 times to take each of the three target bits and convert into a from/to/piece/captured sort of format, a step that might be avoided totally in the future but not now (for me). Swap()? It's easy to do. Partial pattern matching? (is this a true Stonewall? is this close enough to a Stonewall to be concerned? etc) is all easy and *fast*. Just pick something we *both* are doing so we can compare without one of us having to write a bunch of code to test... > >> >> >>> >>>Any offers to make the comparison ...... ? :) >>> >>>Chris Whittington >> >>I'm willing to compare *anything* you'd like... but I want to turn this >>around >>to show how "off-the-wall" your last paragraph is. Rather than my being >>able >>to use only what I now do, I suggest we *both* limit ourselves to what >>*I* do >>and no more. Why? Because I can add code just as easily as you can >>delete >>code, so why the nonsense limitation to "what I do now and not what I >>could do >>if I wanted?" > >Because if you need to add code to create the data that an intelligent >offset program already has, then you'll be slower still. I want to know >if thats going to be the case .... Isn't that "obvious"?? Anything *either* of us adds slows us down. I simply think that if we both add the *same* thing I will generally slow down *less* because of the efficiency of bitmaps. > >> >>*obviously* I now do what I need to do to run fast. So including such a >>pointless restriction basically means that the "comparison" won't work. > >No, no. You can have incrementally updated tables, just as long as you >include the computation timne to get there. And, I'ld like to know if >your tables are going to be 64 bitmaps - because if you want to generate >offset tables to perform the exchange calculations, then ...... :) Aha, you overlook a great word in computing, called "hybrid". I reserve the right to do whatever I do in the fastest way possible. IE Bruce found that detecting attacks is more efficient using bitmaps and he does this. I did the same in Cray Blitz in fact, while everything else was offset. There might be some things that are easier in offset, I don't know. But there are *many* things that are faster too, using them. I don't want to convert you... That's a choice you have to make on your own. But if you consider that 1.9X performance boost offered by 64 bit architectures, but *only* to those programs that are pumping 64 bits around internally, you might (or might not) decide that is something that you'd like to have in your arsenal as well. Of course, in a few years 128 bit architectures will be around, and I don't know exactly what I'll do about those, although I might join some of my 64 bit maps together so that *all* pawns are in 1 128 bit bitmap, or some such thing... > > >>And >>I fail to see the reason for wanting to compare anything like this. > >To get to the bottom of the question of whether bitmaps are as cool as >you say they are. > >> >>If we eliminate the above restriction, then we can compare. How do >>*you* >>create the list you are talking about? Incrementally or dynamically >>when you >>need it? > >Incrementally, at move time. I do some incremental stuff. But *not* attacks, because attacks are simple table lookups when using rotated bitmaps. My early versions were fully incremental bitmap programs, until I found a better/faster/easier way to do it... I am way faster without the incremental attack stuff than I was with it, *after* I discovered how to speed this up with rotated bitmaps. Most have the advantage (now) of not having to re-invent this cute idea again, since I've explained it carefully several times... > >> Because I can do *exactly* the same thing, depending on >>whether it >>is faster to compute as needed or to keep something incrementally >>updated. > >We know you *can* do anything, Bob. What's at issue is what you have >right now. What bitmaps and so on. if you want more data, that comes at >cost. And if you want more data, you'll need to decide whether its >bitmap or offset. I think you'ld be crazy to choose bitmap for piece >safety on square evaluations. I did that in my first version. "safe" mobility. "hung piece" term and so forth. Was very easy and fast. I replaced it later as I didn't like trying to evaluate hung pieces, and I don't believe mobility is important, I am convinced it is an "effect" of a good position, not a "cause". IE maximizing mobility doesn't necessarily produce winning chess, otherwise we'd all play a4/h4 immediately... > >> >>to compare these two approaches, we need something that is not horribly >>complex to compute, > >Some important chess knowledge - like a full analysis of piece safety on >moving into a square - just like I suggested. > >My contention is that you wouldn't want to do this with bitmaps. And, if >this is so, that the bitmap approach forces a lack of knowledge in chess >programs. ok... explain the idea precisely, exactly what you want to consider. IE can a piece move to square X? What pieces attack and defend X, are they pinned? Are they overloaded? What questions do we need to answer. The "pinned" part is trivial, however. How about let's do "legal move generation" instead, since this has to include pins, and so forth, which is somewhat related to your safe move above? > > >>otherwise I'm going to pick something I do that is >>easy, >>which would be hard for you to compute, and you will do the opposite, >>and we >>won't ever get an answer because neither of us will ever write the code >>to >>do the calculations. > >Which would suit a general obfuscation of the issue. Try the chess >knowledge suggested. Bitmaps or offset ? > > >> >>How about something we both do? Move generation? > >Takes 0.05% in CSTal, therefore irrelevant. > >> Some evaluation >>concept? >>Swap()? > >Piece safety: what is the largest piece you can safely move into a >square, taking into account pinned pieces ......... OK, this I can do. I have a Swap() function already. It simply enumerates a list of pieces, ordered by value, that bear on the target square X, a list for white, one for black. I then "minimax" this list. To do what you want, all that is needed is to take each piece and ask "is it pinned". This is easy to answer. For each diagonal, rank or file, I look in both ways at the same time, and see what is on the end of each diagonal or whatever. If I find your bishop on one end, my rook or queen on the other, then I simply adjust the value of this piece in the list to show that *if* it takes part in the capture, it potentially loses something else as well because it is pinned. If my piece is pinned on a king, I just toss it out as being unable to participate at all. I wrote this code a year ago. It was slower, but not by a significant amount (IE swap() is now < 10%, it went to about 13%) but I didn't think it was any more accurate and I tossed it out. Why is it so fast? Because most of the time, when I move a piece, there is no bishop or queen on either diagonal, and no rook/queen on either rank/file, so further testing is not needed, and finding out that there is no potential "pinner" is once again trivial... More details? Or does that give a good idea of how this works. The main point is you have to look down the rays to see if you find a possible pinner, while I simply ask "is there a bishop/queen on either diagonal or a rook/queen on either rank/file?" And those are two AND operations and a zero result takes me "out" of further work. While you are still looping down the rays to see what you stumble into. Different approaches, for certain... > > >> Partial pattern recognition (is this position a known >>Stonewall? Is >>it pretty close to a known Stonewall? etc.) However, I'm not going to >>write >>something grossly complicated that I don't intend to use, and I don't >>expect >>you to either. Therefore we need some common denominator that we both >>have >>and can compare. Move generation is certainly one, but most anything is >>comparable... > >Not interested. Useful and difficult chess knowledge please. The sort >that hardly any programs do ....... That would be the best test. > >Chris Whittington How many programs do "partial pattern matching?" And why don't they? Too expensive perhaps? Not to me... If partial pattern matching isn't useful, I guess we humans can't play the game at all, since we are *so good* at doing partial matching...
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.