Attack table

[Anonymous]

Good morning,

could someone define what are exactly attacked tables ?
I suppose this is to speed up to know if a side is in check.
When are those tables updated, in domove(), undomove(), gen_moves(side) ?
Does it suppose a bitboard engine ?

Regards.

[Niyaz Khasanov]

Attack table is an array of 64 variables or a bitboard that contains information about whether this square attacked or not.
It can be used for check detection, move ordering, generating moves out-of-check etc.
They are time-expensive and therefore are not updated in gen_moves(side).
Some people update them incrementally in domove(), undomove(). Some make them from scratch every time.

[Peter Fendrich]

There are many different ways to keep information about attacks. It doesn't have to be a bitboard engine. On the contrary if you use "Rotated bitboards" you don't update any attack tables at all but generate attack bitboards whenever needed.
If you don't have a bitboard engine and don't use attack tables it will be extremely costly to calculate attack information every time you need it. In order to evaluate things like pinned pieces, SEE (static exchange evaluator), King in check, King safety and so on you don't want to re-calculate the same things over and over again. On the other hand if you pre-calculate all the attack information after every move you will do a lot of useless work becuase many moves doesn't need to be examined after a hash table hit for instance.
Don't calculate more than needed until you use it!
The balance between pre-calculate it all and no pre-caclulating at all is one of the keys to a successful engine I think.
Some sort of incremental updating and not before needed seems to be the optimal way of doing it.
You can implement it as all attacks from each sqaure or all attacks from each piece or all attacks to each square or piece or even a combination. There are many possible optimisations and smart solutions but it's better to start with something that works and then try to make it faster without losing in reliability.
/Peter

[Reinhard Scharnagl]

During which phases of a chess program you need attack tables? I have written a very fast legal move generator with acceptable presort of the generated moves, without having anything like attack tables.

If you are thinking on quiescence search, what may be the gain of using attack tables compaired to simpler methods e.g. using well preordered generated moves?

Reinhard.

[Anonymous]

In fact, i am wondering about a way to speed up the "is_attacked" function, because, when i do a move, if it let the king in ckeck, i abort it.
So, i call this function for each move played, and for extensions, it's a lot.

[Reinhard Scharnagl]

Hello Jean-Fran?ois,

my Smirf program structure is of course very different to others I prosume. I think the is_attacked function compares to my undirected check or chess threat function. I will add some testing results here:

Code: Select all

FEN: 3q2R1/2P5/1k1B4/4np2/1NPK1Pr1/1R6/PP1N1Q2/3q2b1 w - - 0 1

  +-a--b--c--d--e--f--g--h-+ MS Visual Studio C++ Version 13.10
8 |   :::   [q]   :::<R>:::|
7 |:::   <P>   :::   :::   | Testscenario searching for:
6 |   [k]   <B>   :::   :::| undirected chess threats
5 |:::   :::   [n][p]:::   |
4 |   <N><P><K>   <P>[r]:::| Test #:      00
3 |:::<R>:::   :::   :::   |
2 |<P><P>   <N>   <Q>   :::| Test Count:  750000*64
1 |:::   :::[q]:::   [b]   | per Second:  69767441
=>+-a--b--c--d--e--f--g--h-+ Time:        0.688 sec

   bR bR bR -- bR bR bR --
   bK bK bP bR bP bN bR --
   bK -- bK bR -- bR bR --
   bP bK bP -- -- -- bR --
   -- -- bN -- bP bR bP bR
   -- bR -- bN -- bR bR --
   -- -- bR bR bR bB bR bB
   bR bR bR -- bR bR bR --


FEN: 3R4/b1N1Q3/2B4K/r2P3b/pB1k2p1/1qR1p3/1Nn5/6n1 w - - 0 1

  +-a--b--c--d--e--f--g--h-+ MS Visual Studio C++ Version 13.10
8 |   :::   <R>   :::   :::|
7 |[b]   <N>   <Q>   :::   | Testscenario searching for:
6 |   :::<B>:::   :::   <K>| undirected chess threats
5 |[r]   :::<P>:::   :::[b]|
4 |[p]<B>   [k]   :::[p]:::| Test #:      01
3 |:::[q]<R>   [p]   :::   |
2 |   <N>[n]:::   :::   :::| Test Count:  750000*64
1 |:::   :::   :::   [n]   | per Second:  61381074
=>+-a--b--c--d--e--f--g--h-+ Time:        0.782 sec

   -- bB -- -- bB -- -- --
   bR -- -- -- -- bB -- --
   bR bP -- -- -- -- bB --
   -- bR bK bK bK -- -- --
   bR bR bK bB bK -- bP --
   bR bP bP bK bP bP -- bP
   bP bR bP bP bN bP -- --
   bN -- -- -- bN -- -- --


FEN: 3k4/8/8/2N4b/6n1/8/5P2/R3K2R w KQ - 0 1

  +-a--b--c--d--e--f--g--h-+ MS Visual Studio C++ Version 13.10
8 |   :::   [k]   :::   :::|
7 |:::   :::   :::   :::   | Testscenario searching for:
6 |   :::   :::   :::   :::| undirected chess threats
5 |:::   <N>   :::   :::[b]|
4 |   :::   :::   :::[n]:::| Test #:      02
3 |:::   :::   :::   :::   |
2 |   :::   :::   <P>   :::| Test Count:  750000*64
1 |<R>   :::   <K>   :::<R>| per Second:  93023255
=>+-*--b--c--d--*--f--g--*-+ Time:        0.516 sec

   -- -- bK -- bK -- -- --
   -- -- bP bK bP bB -- --
   -- -- -- -- -- bN bB bN
   -- -- -- -- bN -- -- --
   -- -- -- -- -- -- bP --
   -- -- -- -- bN -- -- --
   -- -- -- -- -- bN -- bN
   -- -- -- -- -- -- -- --


FEN: K1RBB1bn/1Q2p2q/pP4p1/k5r1/3N1pp1/2P5/1N1n4/r7 w - - 0 1

  +-a--b--c--d--e--f--g--h-+ MS Visual Studio C++ Version 13.10
8 |<K>:::<R><B><B>:::[b][n]|
7 |:::<Q>:::   [p]   :::[q]| Testscenario searching for:
6 |[p]<P>   :::   :::[p]:::| undirected chess threats
5 |[k]   :::   :::   [r]   |
4 |   :::   <N>   [p][p]:::| Test #:      03
3 |:::   <P>   :::   :::   |
2 |   <N>   [n]   :::   :::| Test Count:  750000*64
1 |[r]   :::   :::   :::   | per Second:  64000000
=>+-a--b--c--d--e--f--g--h-+ Time:        0.750 sec

   -- -- -- -- -- -- bR bR
   -- -- -- -- bR bP bR bP
   bK bK -- bP bB bP bP bR
   bR bP bR bR bR bP -- bP
   bK bP bB -- bN -- bR bR
   bR bB -- -- bP bP bP bP
   bR -- -- -- -- -- -- bR
   -- bR bR bR bR bR bR bR


FEN: 8/p7/8/1P6/4B3/P6p/5K1k/8 w - - 0 1

  +-a--b--c--d--e--f--g--h-+ MS Visual Studio C++ Version 13.10
8 |   :::   :::   :::   :::|
7 |[p]   :::   :::   :::   | Testscenario searching for:
6 |   :::   :::   :::   :::| undirected chess threats
5 |:::<P>:::   :::   :::   |
4 |   :::   :::<B>:::   :::| Test #:      04
3 |<P>   :::   :::   :::[p]|
2 |   :::   :::   <K>   [k]| Test Count:  750000*64
1 |:::   :::   :::   :::   | per Second:  146341463
=>+-a--b--c--d--e--f--g--h-+ Time:        0.328 sec

   -- -- -- -- -- -- -- --
   -- -- -- -- -- -- -- --
   -- bP -- -- -- -- -- --
   -- -- -- -- -- -- -- --
   -- -- -- -- -- -- -- --
   -- -- -- -- -- -- bK bK
   -- -- -- -- -- -- bP --
   -- -- -- -- -- -- bP bK


It is to notice that the threatening piece found at a square is not at all the real piece itself but may be a partially property of the real chess man. As an example a king is able to threat like a pawn into two matching directions.

I am performing that function without any attack tables. It would be interesting to see, which influence such tables would have to the average timing of that is_attacked function.

Regards, Reinhard

[Peter Fendrich]

During which phases of a chess program you need attack tables? I have written a very fast legal move generator with acceptable presort of the generated moves, without having anything like attack tables.

I'm sure that moves can be generated faster without attack tables. I'm talking about all phases where you need this information. I suppose that you don't want to generate the attacks first in the move generator and then the same attacks in the king safety function, in the SEE for quiesence, in the leaf evaluator function, in the search for pruning or extension decisions and so on.
Instead of generating the same attacks several times you save them the first time they are geneated.
/Peter

[Reinhard Scharnagl]

Well Peter,

before discussing where I would like to have attack tables or not, I repeat my basic question:

During which phases of a chess program you need attack tables? Why?

Regards, Reinhard.

[José Carlos]

before discussing where I would like to have attack tables or not, I repeat my basic question:

During which phases of a chess program you need attack tables? Why?

I don't use attack tables myself, but I can imagine they're useful for:
* Capture generation (in qsearch or in normal search if you separate cap/noncap gen)
* Evaluation (attacked squares around the king, weak points...)
* In check detection

[Reinhard Scharnagl]

Hello Jos?,

thank you for your contributions to "attack tables".

Capture generation (in qsearch or in normal search if you separate cap/noncap gen)

It is very unclear, how this should be accomplished.
a) how should this happen using a persistant table?
b) why are there advantages compared to use good presorted moves?

Evaluation (attacked squares around the king, weak points...)

I see the need to have such knowledge (dynamic), but:
c) what is the reason to use a persistant table here?

In check detection

I have a legal move only generator, where moves are fully informed whether they are captures, chess threats or mates. I see the need to have such a kind of information dynamicly during move generation
d) what is the reason to use a persistant table here?

Most of my questions targeting on the persistant nature of an attack table, which importance I cannot understand yet.

Regards, Reinhard.

[Peter Fendrich]

Well Peter,

before discussing where I would like to have attack tables or not, I repeat my basic question:

During which phases of a chess program you need attack tables? Why?

Regards, Reinhard.

I thought I made that clear in my previous post but if you want some code snippets you have to wait.
Let me clarify that I don't use attack tables in Terra which has rotated bitboards.
However, in my new program that is under development I'm thinking about various solutions and attack tables is one of them.
The implementation I'm thinking of will not be 100% accurate but it will help to taking fast decisions during search and evaluation. The move generation (and MakeMove) will suffer somewhat in performance but I think that in return search and evaluation will be faster with the same quality.

/Peter

[José Carlos]

It is very unclear, how this should be accomplished.
a) how should this happen using a persistant table?
b) why are there advantages compared to use good presorted moves?
c) what is the reason to use a persistant table here?
d) what is the reason to use a persistant table here?

As I don't use attack tables, I can't give a fully supported answer. Like most other techniques in chess programming, I see attack tables might have some potential or not, depending on the rest of the program. If my eval has lots of isAttacked() tests, attack tables migth be useful there, but in that case, I'd try generating them only in the nodes I evaluate, not incrementally.
In my private program, I tried a reduction based on attack maps. I use bitboards in Anubis and I generated attacks using Kogge-Stone-like algorithms, but if I was using something like 0x88 or mailbox, attack tables would have been useful there. Basically, I checked in what way a move modifies the attacks map of the board for both sides. If certain conditions were met, I reduced.
I discarded this idea after many tests :cry:

[Reinhard Scharnagl]

Hello again Peter,

code snippets might not be helpful (this moment). I primarily want to know about the INTENTIONS and IDEAS to use a persistent attack table.

Somebody must have the idea to use them BEFORE he had encoded some. I already have seen here some goals joined with the use of such attack tables, but I have not seen yet:

a) why attack tables have to be persistent?
b) how and why keeping them up to date?
c) why are there advantages compared to calculate things dynamicly?
d) what are advantages of the use of attack tables compared to other ideas, e.g. a good move ordering or the generation of fully informed legal only moves?

Reinhard.

[Reinhard Scharnagl]

Hi Jos?,

this moment I am thinking to stop asking questions on the theme of attack tables. It seems to me that there are some programers who use them, looking whether they might be useful for them or not, but do not at all know why they are using attack tables instead of thinkable alternatives.

I want to complete my Smirf engine using components I would fully understand. Therefor until now I have done all parts my own way, not asking which parts other programers are using. But naturally I am interested to UNDERSTAND the ideas and intentions of other people. It is not my goal to COPY anything.

Therefor I am not interested in implementation details. I simply wanted to know, why attack tables are useful compared to alternatives.

Reinhard.

[Sune Fischer]

Hi all

I used attack tables once. I did it because I thought it would be easier and faster in the long run.
Easier because the table could help answer a lot of questions that would otherwise need specially optimized routines.
Faster because computer chess is mainly about tactics like threats, attacks and pressure, a table would incrementally generate this information cheaper.

I now think I was wrong on both accounts, especially the "easier" part.
There is nothing easy about them, they take forever to implement and debug compared to a general attack routine, IMHO.

The real question to the hardcore chessprogrammer is of course if they are faster or not

Initially a table like that produces a big slowdown, probably a factor 2-3 in raw node speed. I think such a large speeddrop is hard to regain, but YMMV.

Some things that might benefit from attack tables is SEE, mobility and king safety eval and move ordering.

InCheck() detection also of course, although note it can be optimized pretty well by just looking at the attacks of the last piece that moved and its possible x-ray check.

Although all of those subroutines do become faster it's still the bottom line that counts, and at least in frenzee it is overall faster to use on-the-fly detection. Particularly in the endgame the attack tables seem like a poor investment.

-S.

[Peter Fendrich]

It's hard do follow a thread here!

a) why attack tables have to be persistent?

The only reason I can think of is performance.

b) how and why keeping them up to date?

That's the key question if you are going to use it!
IMO they should be saved when the information is first generated and that's normally in the movegenerator. I don't think one should try to keep them completely updated all the time. The trick is how to do this.

c) why are there advantages compared to calculate things dynamicly?

The only one I can think of is performance.
The drawback is complexity. The program becomes more complex and vulnerable to bugs.

d) what are advantages of the use of attack tables compared to other ideas, e.g. a good move ordering or the generation of fully informed legal only moves?

Different programs are written with different styles and ideas. What's good for one program mustn't be good for another.
These tables can be implemented in so many ways and must be evaluated for the specific program in mind.
The only way to find out if it's good is to test it.
The long and windy way...
/Peter

[Peter Fendrich]

Initially a table like that produces a big slowdown, probably a factor 2-3 in raw node speed. I think such a large speeddrop is hard to regain, but YMMV.

That's very implement dependent, don't you think?
What kind of attack table did you have? "attacks from a square/piece" or " attacks to a square/piece"?

Although all of those subroutines do become faster it's still the bottom line that counts, and at least in frenzee it is overall faster to use on-the-fly detection. Particularly in the endgame the attack tables seem like a poor investment.

Is Frenzee bitboard based? I have a feeling that for bitboards attack tables have less merits even if you don't use rotated bitboards.
In the endgame with sliding pieces they could still be usefule I think.
The sliding is longer so to say...
/Peter

[Reinhard Scharnagl]

Hi Peter,

it's hard do follow a thread here!

indeed, there is no tree view, which could help.

a) why attack tables have to be persistent?
The only reason I can think of is performance.

Obviously my problem is, that I do not at all see a claimed relation between the persistance of such tables and performance. Why should such persistent tables be better for performance than calculating such information on demand? E.g. to know secure fields near the kings position, mostly standing at the border, only need to check five squares. Keeping a table up to date for all 64 squares seems to be a lot more of work.

b) how and why keeping them up to date?
That's the key question if you are going to use it! IMO they should be saved when the information is first generated and that's normally in the movegenerator. I don't think one should try to keep them completely updated all the time. The trick is how to do this.

When they would not consequently been updated, why should such tables be kept persistently? How often is such stored information reused? How do you come to the conclusion that storing and updating mostly would not be wasted efforts? It is very clear to me that you will try to optimize getting and storing the calculated data. But it is unclear to me why you would prefere to store and update at all such data?

c) why are there advantages compared to calculate things dynamicly?
The only one I can think of is performance.
The drawback is complexity. The program becomes more complex and vulnerable to bugs.

I could think of a bundle of advantages or disadvantages. If you claim that it would gain performance, please specify, why compared to which alternative. I am thinking here e.g. at MVV/LVA methods.

d) what are advantages of the use of attack tables compared to other ideas, e.g. a good move ordering or the generation of fully informed legal only moves?
Different programs are written with different styles and ideas. What's good for one program mustn't be good for another. These tables can be implemented in so many ways and must be evaluated for the specific program in mind. The only way to find out if it's good is to test it. The long and windy way...

Naturally chess programs differ (or should at last for to avoid being clons of each other). But when an idea is good, it does not depend on the program it implements. Therefore that is just the point I try to investigate: is using attack tables a good idea or not?

Regards, Reinhard.

[José Carlos]

Naturally chess programs differ (or should at last for to avoid being clons of each other). But when an idea is good, it does not depend on the program it implements. Therefore that is just the point I try to investigate: is using attack tables a good idea or not?

I'm afraid this is not correct. Good ideas do not necessarily work in all chess programs. Null move is a clearly accepted good idea, however Junior does not use it. It doesn't work for Amir's program.
If the criterium for an idea to be good is that it works for many programs, I think attack tables are not a good idea. At least, AFAIK there aren't many programs using them.
One example of strong program using attack tables: REBEL.
One example of strong program calculating attacks on the fly: TIGER.

You choose... [/i]

[Reinhard Scharnagl]

Hello Jos?,

I'm afraid this is not correct. Good ideas do not necessarily work in all chess programs. Null move is a clearly accepted good idea, however Junior does not use it. It doesn't work for Amir's program.

well, may be I have to be more precise and claim this only for independent ideas. Null move pruning could not be seen isolated from other pruning methods it combines with. Attack tables seem to be independent from other ideas, but being not that familiar with it, I am not sure about that.

Reinhard.