Author: Gerd Isenberg
Date: 08:55:21 07/01/04
Go up one level in this thread
On July 01, 2004 at 11:06:54, Tony Werten wrote:
>On July 01, 2004 at 10:52:09, Gerd Isenberg wrote:
>
>>On July 01, 2004 at 08:42:38, Vincent Diepeveen wrote:
>>
>>>On July 01, 2004 at 04:39:24, Gerd Isenberg wrote:
>>>
>>>>On July 01, 2004 at 02:50:35, Tony Werten wrote:
>>>>
>>>>>Hi all,
>>>>>
>>>>>although I like the principle of bitboards, it really bothers me that I can't
>>>>>seem to find a decent/fast way to evaluate weighted safe squares.
>>>>>
>>>>>Suppose I want to (simple) evaluate a rook, I generate a bitboard with all
>>>>>reachable squares and mask off the squares attacked by lower pieces (that's no
>>>>>problem).
>>>>>
>>>>>(This doesn't exacly generate safe squares, only the ones that aren't attacked
>>>>>at all by opponents pieces are, for the remaining squares one would need a SEE,
>>>>>but that's not the point )
>>>>>
>>>>>Now I can use this bitboard ( say rook on e4 ), mask the rank state, and look in
>>>>>a precomputed table how this rankstate scores on an e rank. No problem.
>>>>>
>>>>>But how to do the files ? If I use the rotated board, I need to have the
>>>>>opponents attackboard in this rotated board as well, wich would be very costly
>>>>>to compute (ie also for the bishops,queens ) and very complicated.
>>>>>
>>>>>Any ideas ? Am I missing something ?
>>>>>
>>>>>BTW, doing a popcount isn't a solution, since it violates the elegance of
>>>>>bitboards ( and is slow ?)
>>>>
>>>>Ok, bitscan traversing and psq-lookup is a even more violation IMHO ;-)
>>>>
>>>>For safe rook attacks one may look for boolean pattern/properties (depending on
>>>>the game state). Intersect the attack set with several small areas of the board,
>>>>like center, remaining extended center, squares near opposite or own king,
>>>>passers, squares behind passers or other movable pawns e.g. to support a
>>>>minority attack, squares on open/halfopen files, squares on some rook
>>>>trajetories to opposite king and what ever else.
>>>>
>>>>With those sets, look whether they are empty and if not, probably look whether
>>>>the population count is greater one.
>>>>
>>>>That may be implemented loopless and with some preconditions:
>>>>
>>>>if ( safeRookAttacks )
>>>>{
>>>> set = safeRookAttacks & someAreaOfInterest;
>>>> bunus += f1*(set!=0) + f2*((set&(set-1))!=0);
>>>
>>>2 times a 64 bits multiply AUCH. That's slow.
>>
>>oups bunus, hehe, of course "and" with -1|0 masks.
>>Or is there any compiler generating boolean muls here?
>>But agreed, i should make it more readable:
>>
>> bonus += (f1 & atleastOne(set)) + (f2 & atLeastTwo(set));
>>
>>with inlined
>>
>> int atleastOne(BitBoard set) {return -(set!=0);}
>> int atleastTwo(BitBoard set) {return -((set&(set-1))!=0);}
>>
>>>
>>>> ...
>>>>}
>>>>
>>>
>>>I assume Tony isn't doing such simple things as you propose here.
>>>
>>>Basically Tony might want to use some chessknowledge evaluating each square.
>>>
>>>And the reality is that scanning in bitboards is just too slow.
>>
>>With bitboards you have several choices, to count weighted attacks.
>>I agree that serialising the whole bitboard using some kind of piece square
>>tables is too slow. Disjoint population counting with some area bitboards is
>>possible. For small area sets, it is most often enough to check whether there is
>>one or more attack - that was my point, a kind of cheap popcount.
>>
>>Of course ranks attacks may be easily computed by extracting appropriate bytes
>>from several bitboards and to do some lookup into precalculated tables.
>>
>>
>>>
>>>>Of course such statements "cry" for MMX,SSE2,Itanium or AltiVec SIMD
>>>>instructions like pcmpeq to build -1|0 masks to "and" with. Itanium has popcnt
>>>>instruction, and there are rumors that AMD64 has undocumented popcnt too,
>>>>somewhere in the bt opcode range.
>>>
>>>So in a 32/64 bits programs you can execute with 3 instructions a cycle without
>>>any problems using 16 registers and skip complex patterns with a single 'if',
>>>and with your 'advanced SSE code' for the opteron you can do 1 multiply+add per
>>>cycle (note a multiply eats 2 cycles) in the meantime you must convert back and
>>>forth from SSE to normal registers.
>>>
>>>In short you cripple your program to something doing 1 instruction a cycle at
>>>maximum and you extensivly use 64 bits multiplications to achieve your goal and
>>>all kind of fancy tricks.
>>>
>>>But even the simplest pattern in C like asked by Tony you write unreadable code
>>>like :
>>>
>>> set = safeRookAttacks & someAreaOfInterest;
>>> bonus += f1*(set!=0) + f2*((set&(set-1))!=0);
>>>
>>>How do you plan to debug thousands of patterns?
>>
>>I don't see the point, where is the difference in debugging?
>
>Suppose you want to give a bonus if you attack a square, 1 away from the king
>and a smaller bonus for 2 away and an even smaller 1 for 3 away.
>
>If you loop over the squares (with fe 0x88) you will get some thing like
>
> bonus+=king_attack_bonus[king_dist[square-kingsquare+0x77]]
>
>I only need a k_dist table (used very often) and a bonus table wich I can keep
>at a different place
>
>With your method it would be
>
>if (attackbb & one_from_king[kingsquare]) bonus += F
>if (attackbb & two_from_king[kingsquare]) bonus += G
>if (attackbb & three_from_king[kingsquare]) bonus += H
>
>where a lot more gets stuffed inside the code and in addition some rarely used
>big tables.
>
>Tony
May be for such issues a (redundant) 0x88-board is faster
(but i doubt it ;-)
No loop and no branches, if you do it SIMD wise.
Runtime is independent on the population of attacksbb.
As a stubborn extreme bitboarder i would probably even generate the *_from_king
bitboards by some fill cycles ;-)
Cheers,
Gerd
>
>>
>>if ( condition ) bonus += F;
>>
>>versus
>>
>>bonus += F & ConditionMinusOneorZero;
>>
>>The latter is more SIMD-wise, so with SSE2 one may process 16-byte masks at
>>once, so pcmpeqb, pand, psadbw.
>>
>>>
>>>Another question, when do you get parallel with Isichess?
>>
>>I'm working on it. The problem is the 40h++ job.
>>Ready to take off, wake up time is half past four tomorrow ;-(
>>
>>Gerd
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.