Attack table

[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.

[Sune Fischer]

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"?

Yes it probably is implementation dependent (hence the "YMMV"), but I believe you have to resort to some heavy attack calculations to make them worth while, more than there is in Crafty per node.

Crafty is perhaps not the best example, it having a relative "light-weight" search. One could imagine a program that did e.g. full evaluations at every node and similarly heavydudy stuff on the pruning/extensions.
In a program like that attack tables might pay off, but compared to the "raw speed" of e.g. Crafty a big slowdown can be expected.

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...

Yes it is all bitboards. So was the old program with attack tables, it had both attack-to and attack-from tables. They are incredibly expensive to update for the pieces in the endgame, even a knight can in one move attack 8 new squares, so a total of 16 squares changes attack status.

At the end of the day the idea of attack tables must be more speed, because everything they can do can also be done on the fly. So if the end result is a slowdown...

Of course there is some potential in the tables, but so far I have not managed to come up with anything heavy enough to make them worth while.

-S.

[Klaus Friedel]

I tried both (rotated) bitboards (Hagrid) and attacktables (Snitch).

The main reason i switched from bitboards to attacktables was because it's very easy to evaluate Board control with attacktables.
This is the most important positional evaluation term in Snitch and the main reason that Snitch is 50-100 points above Hagrid even with half the nps.

A fast isAttacked() or isCheck() is a nice gift of both bitboards and attacktables.

From the implementaion point of view attacktables are quite complex, bitboards are a litte bit easier and ray-casting is the easiest.

Imho attacktables only make sense if you use them for evaluation too.
They are too timeconsuming and to complex to only be used to have a fast isCheck().

Regards,
Klaus Friedel

[Zach Wegner]

I use bitboards, but use an array-style attack table generated during movegen. I use it for evaluation (hanging pieces, table-style king safety) and for SEE, which is used quite a lot (at least once for every move). My kind of attack tables cannot be easily generated on the fly, and I use them a lot at every node, so that's why they are persistent.

[Uri Blass]

I do not understand
the post of Reinhard Scharnagl from
Wed Oct 06, 2004 6:03 pm

Reinhard Scharnagl wrote:
"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 do not understand what it means and it may be good to have some example in diagram.

1)What is the threating piecefound at square a1?
2)What is the real piece itself at square a1?
3)What is the property of the real chess man?

I also do not understand why a king is able to threat only to 2 matching directions because king can threat between 3 and 8 directions.

Note that I thought that attack tables are needed for fast legal move generation but after seeing Smirf results I guess that I was wrong.

I explain the reason that I thought that attack tables are needed for fast move generation.

My explanation is probably wrong based on the good results of smirf but I will give it here.


1)If you want to generate legal king moves without attack tables you need to have a function that caluclates if the king go to safe square or to attacked square and it seems to me slow to check all the possible direction in every move.

2)I also need to know if a piece is pinned and without pin information that is updated incrementally every move I may need to do often expensive checks to check if a piece is pinned before generating legal moves of that piece.

attack tables can help to calculate if a piece is pinned faster(if it is not attacked then it is certainly not pinned to the king) so they can help me to be faster in updating my pin table.

3)I need to generate legal moves when the king is in check.
Without attack tables I may often need to calculate if I can capture the attacker by looking at all queen directions and knight directions only to find that I cannot do it and it seems to me expensive.

Example:after 1.e4 f6 Qh5+ I may need to look at all queen and knight directions to h5 in order to find that it is impossible to capture the queen at h5 without attack tables when I simply remember by attack tables that h5 is not attacked.

I also may need to look at all directions to f7 to find that no piece can move to f7.

Uri

[Sune Fischer]

Note that I thought that attack tables are needed for fast legal move generation but after seeing Smirf results I guess that I was wrong.

Yes I don't believe attack tables can help you much with legal move generation, it is very much overkill to use them just for that IMO.

Basicly, there are two cases, namely the positions where you are in check and those where you aren't in check.

For the sake of simplicity, let's say we aren't in check and that we want to generate the legal moves of a bishop.

First, check to see if the bishop-king square relations make a pin possible at all. This is the famous sqk-sqb+128 trick that can be done with 0x88 but it works just fine in 64 square notation also, only you need a [64][64] table.

Most of this time the table will tell you a pin is geometricly not possible, so you can just go right ahead and generate all the moves.

So assuming a pin is possible, the table value also indicated in what direction you should look for such a pin.

Looking for this is relative cheap, it's just one scan (or half an attack caluclation with bitboards). You must find the king at the one end of the pin direction and the appropriate attacker at the other end, otherwise there is again no actual pin (just a few masks with the bitboard).

Depending on the direction of the pin the bishop might have moves or not.
Ie. if the pin is in a diagonal the bishop will still have moves in the pinned diagonal.

I'm not sure if bitboards are faster here or not, might depend on the position, probably 0x88 would be a winner due to the small 1D table.

-S.

[Uri Blass]

Sune,

1)About pinned pieces,I know that one if may be enough to check if a piece is pinned in most cases but I still think that having if for every move in the move generator is not so cheap.

I found that one of the things that helped movei to be faster in generating moves is the fact that
I remember the number of pinned pieces at every ply and if the number of the pinned pieces is 0(happen in most cases) I can avoid all the if's in my move generator.

I do not remember exactly how much it helped.

I think that it was something near 10% speed improvement and not 50% improvement but still it was significant.

calling a function and not having only simple if for every piece in the board that I move could probably do it even more expensive.


2)I know that in most of the cases the king is not in check but you still have king moves that you need to check if they put the king in check.

checking if a square near the king is under attack should be done very often (more often than making moves for the calculation of perft considering the fact that you do not need to make the last move).

updating attack tables did not seem to me very expensive for perft because I update them during make move and big part of the time for calculating perft is done in generating moves(I may generate 30 moves for every make move).

Uri

[Sune Fischer]

Hi Uri

I think I forgot to comment on your good point with the generation of the king moves, indeed this is expensive.
Bitboarders can use Kogge-Stone to do multiple attack square detection.

Buf of course attack detection is faster with an attack table (doh!) there can be no question of that, the question is does the increased speed on generating fully legal king moves outweigh the "overhead" of keeping the attack table?

I think it doesn't, unless you want to do some otherwise insanely expensive board attack evaluations. Then again the question becomes is this really needed, is there no equivalent but cheaper alternative etc..

I always try and keep in mind that 95% of the positions searched and evaluated by a chess program is pure nonsense. This is probably why refutation strategies work so well, ie. look for a cutoff and when you have done that look for a cutoff and when you have done that look for a cutoff!

1)About pinned pieces,I know that one if may be enough to check if a piece is pinned in most cases but I still think that having if for every move in the move generator is not so cheap.

You don't need to check for this at every move, just once per piece.

-S.

[Uri Blass]

I still think that calculating the attack tables is not so expensive and maybe using them is the expensive part.

I profiled movei in perft mode when it calculates perft 6 from the opening position(I did not finish it because it took more than 10 minutes(when I profile it then it is some 100's times slower than normal movei that can calculate perft 6 in 4.078 seconds in perft mode on A3000).

Movei in perft mode does not calculate unnecessary information like hash keys or evaluation during making moves.

Here are the results of the important functions

You can see that 94.4% of the time was used for the perft function.
74.6% of the time, that means only 74.6/94.4 of the time that was used for the perft function, was used for generating moves and not for making moves or undoing moves

17.8% of the time was used for undoing moves and the rest of the time for other tasks
updating the attack tables happen during makemove and undomove so it seems that it is not something that cost me too much.

I see that generating pawn moves cost me a lot and maybe I can improve by incremental update instead of checking every time if a square is empty(I need usually to check some squares for every pawn because the same function check also if a pawn can move and if it can capture and maybe it is better to update incrementally list of captures and in most cases when the list is empty not to search for captures for pawns).

9510.780 14.0 16013.587 23.5 16440733 generateblackpawnsimple(int) (boardi.obj)
7290.067 10.7 48633.495 71.5 2153088 genwithoutpin(void) (boardi.obj)
5212.578 7.7 5212.578 7.7 22905167 gen_quietnopawns(int,int) (boardi.obj)
3609.263 5.3 3609.263 5.3 15832114 gen_quietblackslowpawns(int) (boardi.obj)
3177.942 4.7 5546.857 8.2 4376753 generatesimpleknights(int) (boardi.obj)
3031.729 4.5 3031.729 4.5 13333833 gen_quiet2squares(int,int) (boardi.obj)
2595.925 3.8 66805.473 98.2 1 xboard(void) (main.obj)
2571.370 3.8 5327.719 7.8 4284723 generatesimplerooks(int) (boardi.obj)
2560.422 3.8 6921.622 10.2 4282661 generatesimplebishops(int) (boardi.obj)
2418.373 3.6 7129.709 10.5 2201759 makemove(int) (boardi.obj)
2389.441 3.5 3423.601 5.0 6569687 generate7(int) (boardi.obj)
2321.344 3.4 3267.401 4.8 6570307 generate9(int) (boardi.obj)
2097.813 3.1 5757.301 8.5 2142012 generatesimplequeens(int) (boardi.obj)
1936.938 2.8 4967.669 7.3 2201754 undomove(void) (boardi.obj)
1894.905 2.8 2340.891 3.4 6572184 generate8(int) (boardi.obj)
1827.367 2.7 2880.510 4.2 4403513 updatepiece(int,int) (boardi.obj)
1728.039 2.5 1985.867 2.9 6572222 generate1(int) (boardi.obj)
1599.398 2.4 1599.398 2.4 4439686 pseudodelete(int) (boardi.obj)
1591.541 2.3 1591.541 2.3 4439718 pseudoadd(int) (boardi.obj)
1403.320 2.1 64208.186 94.4 1 perft(int) (perft.obj)
998.389 1.5 998.389 1.5 4234905 updatewhitepiece(int,int) (boardi.obj)
955.951 1.4 50707.558 74.6 2201763 gen(void) (boardi.obj)
918.920 1.4 1647.072 2.4 2216831 generatepinarray(void) (boardi.obj)
860.288 1.3 1173.175 1.7 2107039 generateking2(void) (boardi.obj)
689.786 1.0 689.786 1.0 2118197 generatepinblack(void) (boardi.obj)
381.359 0.6 647.588 1.0 666634 generatewhitepawnsimple(int) (boardi.obj)
0.003 0.0 64208.191 94.4 1 perft_command(int) (perft.obj)

[Reinhard Scharnagl]

Hello again!

Uri wrote

I do not understand the post of Reinhard Scharnagl from Wed Oct 06, 2004 6:03 pm

One thing I have noticed during my try to have a discussion on the need of attack tables has been, that though everybody should be talking from his own chess program, some components like attack tables seem to be common use. Having written a chess program on my own, there are a lot of different solutions and namings within that, than those from which I can read here. So it is not only up to me to try to understand your somehow standardized approach, even you may be asked to try a somehow changed way of thinking to understand my approach.

...As an example a king is able to threat like a pawn into two matching directions."
I do not understand what it means and it may be good to have some example in diagram.

Well, I errornously thought, my examples would be clear. So let me explain. In Smirf there is nothing like attack tables (as far as I understood from attack tables) but there are two (color specific) functions: a) ImSchach() and b) RiSchach(). a) is testing whether a square would be attacked and by which piece property this would be done, b) is testing from which direction a chess is threatening using 0x2c to encode a double check thread. Those functions are very fast and effective:

Code: Select all

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


The example above is a type a) testing. The check thread at position g1 is a black pawn type threat based on the black king at h2. In Smirf a king has that pawn threatening property because of performance reasons. A king has not only those two pawn like threats, he has his 8 king type threads but they would be testet later and thus not been found because one threat is enough to regard a square as been threatened. At h1, h3 and g3 this is the detected situation.

1)If you want to generate legal king moves without attack tables you need to have a function that caluclates if the king go to safe square or to attacked square and it seems to me slow to check all the possible direction in every move.

Of course I need such functions. I already have named both. But the rest of your statement is not quite correct. You have to decide whether to have a direction driven search for threads or a piece driven search. A direction driven search will get worse when more and more pieces will leave the board. But if the opposing color e.g. only has a king and a pawn you simply have to test the distance to te king and two possible places where a threatening pawn could be placed. A piece driven search will therefore become more and more effective the longer the match would last. Overmore the datastructure used by Smirf is optimized for to support such a piece driven search, which naturally helps a lot here and in detecting pinned pieces.

In my opinion a direction driven approach must be worse.

Reinhard.

[Sune Fischer]

You can see that 94.4% of the time was used for the perft function.
74.6% of the time, that means only 74.6/94.4 of the time that was used for the perft function, was used for generating moves and not for making moves or undoing moves

17.8% of the time was used for undoing moves and the rest of the time for other tasks
updating the attack tables happen during makemove and undomove so it seems that it is not something that cost me too much.

Perft is a test where the last thing to be done at every leaf position is a generation of a long move list (at least the way you do it).
Now you profile this and find that generating moves is more expensive than making them.
Surprise surprise, I could have told you that without seeing the profile

So I suspect that perft is not only irrelevant to profile, it can also be misleading.

What does the profile look like when it analyses a middle game position?
This would be more to the point, IHMO.

-S.

[Reinhard Scharnagl]

Here is a fine Perft test position:

Code: Select all

FEN: r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 25

  +-*--b--c--d--*--f--g--*-+ Perft Testseries
8 |[r]:::   :::[k]:::   [r]|
7 |[p]   [p][p][q][p][b]   | (without caching)
6 |[b][n]   :::[p][n][p]:::|
5 |:::   :::<P><N>   :::   | Test #:      01
4 |   [p]   :::<P>:::   :::|
3 |:::   <N>   :::<Q>:::[p]| Break Time 75 Sec.
2 |<P><P><P><B><B><P><P><P>|
1 |<R>   :::   <K>   :::<R>|
=>+-*--b--c--d--*--f--g--*-+

Ply     Nodes    all (x)   (e.p.)    all (+)      (#)    Promot.    Castl. Sec.
-------------------------------------------------------------------------------
1          48          8        0          0        0          0         2    0
2        2039        351        1          3        0          0        91    0
3       97862      17102       45        993        1          0      3162    0
4     4085603     757163     1929      25523       43      15172    128013    0
5   193690690   35043416    73365    3309887    30171       8392   4993637   10
6  8031647685 1558445089  3577504   92238050   360003   56627920 184513607  420
-------------------------------------------------------------------------------


Regards Reinhard.