Fast approach to detect attacked squares?

[joeyrobert]

Hi, I've just started working on a chess engine in C#, and I've come across a snag in my move generation. I was wondering what a fast technique is to detect which squares are attacked and by which side. The most simple method I can think of is *almost* generate all the moves for the other side. That's very costly in terms of speed though. I'm sure this information will be handy later in the evaluation function.

Any information would be really helpful, thanks!

[Dann Corbit]

Hi, I've just started working on a chess engine in C#, and I've come across a snag in my move generation. I was wondering what a fast technique is to detect which squares are attacked and by which side. The most simple method I can think of is *almost* generate all the moves for the other side. That's very costly in terms of speed though. I'm sure this information will be handy later in the evaluation function.

Any information would be really helpful, thanks!

If you want you can precalculate for every bitboard pattern by piece type.
Just have every occupied square on the board be one set of bits, and the other the rays from the sliders and the attack bitmaps of the other chessmen.

Then, one AND with enemy_chessmen will tell you which of the bits are attacks and one AND with friendly_chessmen will tell you which of the bits are defends (both pieces of information are equally valuable).

You can also incrementally do this action, by removing the influence of a piece when you pick it up, and adding the influence when you set it down.

You can additionally create an incremental eval in this manner.

[bob]

Hi, I've just started working on a chess engine in C#, and I've come across a snag in my move generation. I was wondering what a fast technique is to detect which squares are attacked and by which side. The most simple method I can think of is *almost* generate all the moves for the other side. That's very costly in terms of speed though. I'm sure this information will be handy later in the evaluation function.

Any information would be really helpful, thanks!

If you want to ask "is this square attacked by enemy?" then most use the "super-piece" approach. Put a "super-piece" (which moves like all pieces combined) on the square (virtually) by generating the moves for each piece type, from the square in question. If you generate knight attacks, and one of those attacks hits an enemy knight, then that knight is attacking the square you are testing. You can repeat for all 6 piece types and if any are hit, the square is attacked, otherwise no. I use this for "InCheck()" detection.

[sje]

Another idea that's used in some bitboard programs is to incrementally update vectors of bitboards that contain all square/square attack relation data. Yes, this is a lot of processing. But it has a lot of benefits as it provides much useful data at each node. Also, it makes pure legal move generation extremely fast.

Symbolic does this, and here's its one line check detection code:

Code: Select all

bool IsGKIC(void) const {return ColorAttacksSq(evil, GetGoodKingSq());}

Everything's inline; the above "calls":

Code: Select all

bool ColorAttacksSq(const Color color, const Sq sq) const {return atkbc[color].IsSqSet(sq);}

The inline method IsSqSet() operates on a bitboard:

Code: Select all

bool IsSqSet(const Sq sq)   const {return   bits & SingleBitBB(sq) ;}

And SingleBitBB() is just a macro:

Code: Select all

#define SingleBitBB&#40;sq&#41; &#40;1ULL << sq&#41;

[diep]

Hi, I've just started working on a chess engine in C#, and I've come across a snag in my move generation. I was wondering what a fast technique is to detect which squares are attacked and by which side. The most simple method I can think of is *almost* generate all the moves for the other side. That's very costly in terms of speed though. I'm sure this information will be handy later in the evaluation function.

Any information would be really helpful, thanks!

When programming a chess engine definitely the first 2500 elo you won't suffer from this, but please realize that you win a factor 4+ speed already with C over C# especially in this area. In theory C++ doesn't need to be slower, in reality i feel only Cozzie knows how to code fast C++ code. Maybe Pradu Kannan also by now

The rest really is slower in C++ than they would have been in C. Object oriented programming is slow! It just happens.

In diep i use incremental generated attacktables, that's by far quickest manner. If i would turn off evaluation, diep gets 1 million nps at a k7 2.1Ghz, this despite of course investing a lot of system time in things like ordering moves, qsearch selection and so on, in combination with incremental attacktables.

Evaluation turned on, nps drops to under 100k nps.

However this is in C code.

Considering attacks is a very important feature of evaluation function.

To know whether something is attacked i just need to do the test:

if( (attackmask=attacktable[xside][square]) )

That's all.

Number of attackers (very important) :
int attackers = attacktable[xside][square]&15;

I want to know whether i'm getting attacked by 2 enemy knights
and what the squares of them are?

Then i use a 'bitboard' trick, bits 15..30 in diep's attacktable are
indexing into the piecelist.

Want to know whether a knight attacks this square?

Goes similar to gnuchess 4.0 (great program datastructure technical
seen, just of course crappy coding in evaluation) :
if( attackmask&ctlN )

Try all this in bitboards, won't happen!

Of course having all this information is definitely a big LIMITATION of your nps. If you just need this once at 1 spot in your program, don't bother creating a big datastructure for all this; more interesting is to nonstop use all this info into your evaluation function.

Thanks,
Vincent

[Bill Rogers]

There are a lot of people here who are smarter than me and have more chess knowledge too.
I program in a very old language, ie. Basic and the one of the very first algorythms I had to write was a routine to see if my king was in check.
It turned out that subroutine could be used to see if any other man was also "in check" or being attacked or by reversing colors to see if one of my men was protected by another of my men.
Bill

[MattieShoes]

It depends a lot on what board representation you're using.

With an board[64], attacktable[from][to] is a nice way, though it consumes 4096 precious bytes of memory.

board[100] (10x10)or board[120](10x12), a "superpiece" approach or an attack table works, though attack tables are even bigger or require another level of indirection board[board64[from]][board64[to]] or some such.

board[128] (16x8, 0x88 scheme), "to minus from" is unique in terms of attack vectors with values of -119 to 119, so you can make a 240 byte attack vector array indexed by 119+to-from.

I think something similar is possible with board[144] (12x12) though I've not worked out the particulars.

I know nothing of bitboards. Though I've heard that bitwise operations are slow in C# (though it makes no sense to me WHY they'd be slow...) so your mileage my vary.

[MattieShoes]

Err, that was for detecting if a given side attacks a given square (for check detection, castling legality,etc). For keeping complete attack tables, I think it's fairly expensive no matter what, though for bitboards it's probably significantly cheaper. I think most engines that do things like that do it iteratively.

I've only used attack vector tables to answer more specific questions like check detection, is piece X pinned to the king, etc.

[sje]

As you can see, there is a difference of opinion between "incremental update of extensive database" and "calculate partial results on an as-needed basis".

My choice is for the former approach that's stolen largely from the Chess 4.x model. Is it slower than the second approach stolen largely from Crafty and the like? Well, the first technique is most certainly slower if all you're doing is perft() or relatively simple terminal node processing.

But you might want to have a lot of useful data when doing the very common tasks of move ordering (done at all non-terminal nodes), static exchange analysis (done often at terminal nodes and terminal node candidates, pin detection, legal only generation, extra king safety evaluation, etc. And having all of that handy attack data at each node supports using a slower but more extensive incremental update.

[hgm]

I want to try an approach in the engine that I am currently building where I update a list (or perhaps bitmap) of attackers only for occupied squares. That cuts down a lot on the effort needed to do the update. For one, only captures and pseudo-captures (= defending your own piece) have to be in the tables, and when a piece moves you only have to remove its captures from the old square (which might be an empty set, and in general only has very few elements), and add those that can be made from the new square (which unavoidably require some move generation, as these depend on the piece type of the mover). And you have to continue all slider moves that went to the from square, as these were discovered. But also there, you have the list available (as the from square was occupied), and the list is usually empty.

And if the move is a capture, that is really all you have to do: captures don't block any slider moves that were not already blocked by the victim. The piece just inherits the attacks and defenses on it from its victim. Which is automatic, as the lists are tied to the squares, and not to the pieces. And almost all moves made are captures, as almost all nodes searched are QS nodes. Only in the MakeMove of the full-width search you have to worry about non-captures blocking slider moves on a square you have no information on (as it was empty, and the lists of attacks tied to it miht be stale). So there you have to go through the tedious process of viguring out which sliders of both sides attacked it, by running through the slider lists and doing 0x88 attack test. But who cares what you do in the full-width search? That is only a small fraction of the nodes, and most of those do not get to the point where non-captures are searched, as null move or aptures are search earlier and will typically cause a cutoff.

Of course you do the update of the attacker lists in QS only after having decided you are going to search a move: if there is a stand-pat cutoff, or no captures, or only captures with negative SEE, or only futile captures, there is no reason to do it (so that you also don't have to undo it). you then simply return the eval. Of course generating the moves is now only running through the list of non-futile victims, to check if you have attacks on them.