Attack table

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

[Uri Blass]

To Reinhard:

Movei also does not use standard attack tables.
Most programs that use attack tables have information about the attacking piece of every square.

My attack tables only give me information about the direction of attacks and the attacking square and not about piece that attack(If I need the piece I can get it from the attacking square).

I decided about the direction approach because of 2 reasons:

1)Originally I planned to write chess program as a private case of n*m board and only later I decided that chess is already hard enough and it may be better to concentrate in chess.

When I thought about supporting m*n chess I thought about things that are common and decided that directions are common.

2)There are not more than 16 possible queen and knight directions in every n*m board so I can get all the direction that a square is attacked by white by 16 bit integer and I store all the directions that a square is attacked by both sides by 32 bit integer.

It seems to me relatively cheap because by one integer I can know if a square is attacked and the directions that it is attacked.


This is the case for every dimension of the board so it may be possible to generalize by this appriach to a bigger board.

If you use piece properties you cannot get the by one integer




To Sune:
1)perft is clearly relevant here because I compated movei with smirf.

Reinhard Scharnagl has a fast perft function without attack tables and this surprised me.

It seems that smirf is even slightly faster than movei inspite of calculating more information.

In my case it seems that updating the attack tables is not expensive even when I use them to calculate perft.

In normal search I do things like evaluation and alhabeta so updating the attack tables even happens less time in normal search so it is not a problem.

I use for updating attack tables less than 5% of the time and for updating pin information only 2% of the time.

At the same time in normal search
I use almost half of the time for generating moves



2)You could not tell me that generating moves is more expensive than making them without seeing my profile and if updating the attack table is slow enough then it means that making one move is slower than generating 30 moves.

Uri

[Sune Fischer]

perft is clearly relevant here because I compated movei with smirf.

Reinhard Scharnagl has a fast perft function without attack tables and this surprised me.

It seems that smirf is even slightly faster than movei inspite of calculating more information.

In my case it seems that updating the attack tables is not expensive even when I use them to calculate perft.

I don't see why it is interesting to talk so much about perft. If you want to optimize it is better to do it for the real search.

In normal search I do things like evaluation and alhabeta so updating the attack tables even happens less time in normal search so it is not a problem.

I remember my attack tables slowed down the perft a factor 3, but this was the usual perft with a make/unmake at the end.

What you get in perft like that will be the upper limit on what kind of nps you can get out of the real thing. I only got about 2 Mnps with attack tables and I got 6-7 Mnps without, in perft.

As I benchmarked Crafty I got around ~1 Mnps, but this was a normal search with everything on. So I concluded that although 2 Mnps was faster than Crafty right here and now, there was only room for slowing it down a factor 2 before it would already be an obvious loss.

Running at 6.5 Mnps it could be slowed down more than a factor 6 and still be equally fast. This I believed I could do

That is why I today believe that the inital loss you get from doing an attack table is practicly impossible to get back in terms of speed.
You have to appreciate the irony here as the whole point of an attack table would be to do things _faster_

There are different designs of the attack table though, and you might have a very cheap one.

You could not tell me that generating moves is more expensive than making them without seeing my profile and if updating the attack table is slow enough then it means that making one move is slower than generating 30 moves.

Well I know what the profile looks loke in my own program when running perft this way, but even so it is usually a safe bet that whatever is in the inner most loop will also show up as a hotspot in a profile.

-S.

[GeoffW]

Hi Reinhard

Relevant or not, I was very impressed by those Perft numbers a few posts above, that perft is running at 19 million nps.
I thought mine was fairly fast at 3 million nps. What CPU is this running on ? Any tips on how you got it this fast ? Clever bitboard algorithms, big precalculated tables, assembler coding, new secret idea ?

Geoff

[Reinhard Scharnagl]

Hi GeoffW,

sorry about not being able to read your full name ...

First I have to say something on my traditional perft values:
a) hash-adresses and verification words etc. are updated (normal DoMove() and Remove() function calls)
b) my perft counts using 64 bit counters where appropriate
c) my perft indentifies and counts e.g. check threats and mates etc.
d) only legal moves would be generated (with full information)
e) the moves are generated with additional preevaluation data to be a sortable list, where sorting moves would be useful.

My configuration is a P4 at 2.8 GHz within MS XP Pro SP2, I used the MS C++ compiler from MS VStudio .NET. All parts are written in C++.

As I have mentioned at several places I do not use BitBoards, no precalculated tables (that moment, except of some direction stars) and no actualized attack-tables. Smirf's data structure is based on a 14x15 matrix of encoded pieces (therefore not at all related to bitboards). The pieces are simultaneously member of a double linked and sorted color specific list, where separated properties of the chesspieces are bit encoded. This facility enables Smirf now to also support piece types as archbishop or chancellor of Capablanca's piece set. With one unic engine it simultaneously supports 10x8 Capablanca board and piece set or the 8x8 traditional board driven by entered appropriate FEN strings.

Activating the transposition table (at reduced analyzing) would fasten the perft process like:

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]   | (With TT Caching)
6 |[b][n]   :::[p][n][p]:::|
5 |:::   :::<P><N>   :::   | Test #:      01
4 |   [p]   :::<P>:::   :::|
3 |:::   <N>   :::<Q>:::[p]| Break Time 400.0 Sec.
2 |<P><P><P><B><B><P><P><P>|
1 |<R>   :::   <K>   :::<R>|
=>+-*--b--c--d--*--f--g--*-+

Ply          Nodes         all (x)         all (+)   Seconds
------------------------------------------------------------
01              48               8               0         0
02            2039             351               3         0
03           97862           17102             993         0
04         4085603          757163           25523       0.2
05       193690690        35043416         3309887       4.1
06      8031647685      1558445089        92238050      97.5
07    374190009323     69479646226      8418124031    2693.9
------------------------------------------------------------


I think the 'secret idea' would be reated to my data structure.

Regards, Reinhard.

[Uri Blass]

Movei in perft mode has probably similiar speed to smirf in the relevant position.

It is twice faster than smirf(if I use perft mode in the last position that was posted) but I guess my hardware is also nearly twice faster (I use A3000 against PIV1800 if I remember correctly) and movei does not calculate all the information of number of checks and number of mates.

There are probably things to improve.

For example my pawn move generator checks for every pawn if it can capture and I believe that incremental list of pawn captures that will be often empty can be better.

Uri

[Reinhard Scharnagl]

Hi Uri,

Perft for me is relevant as a verification tool, which tells me whether my move-generator and transposition table are working correctly. The speed is (not yet) such relevant for me. Nevertheless I am happy to have a speed now looking quite sufficient to be able to compete.

There are a lot of places within my engine, where I have to do something until I would be satisfied with its performance. As I have mentioned at another place I try to have a new kind of Shanon B search implemented, but I think this would not be realized in Smirf's first release.

The pawn move generator indeed is somehow complex because of possible indirect pins during en passant captures and manifold indirectly opened check threats (if one is generating full informed legal moves only). Additionally I have to handle capablanca pieces during promotions etc. which seems not to be some of your goals this moment. Nevertheless it is interesting to read you have thought over non 8x8 boards already.

Regards, Reinhard.

[Zach Wegner]

The whole "secret idea" is actually generating legal moves. This sped my perft up by a factor of ~4 when I did it, because you do not have to make or unmake the moves on the last ply, but rather count the number of moves generated. Depending on how you use the information, it will likely slow down the actual engine.

[Reinhard Scharnagl]

Hi Zach,

what do you intend to say? That it would not give comparable Perft results when having chosen a legal move generator?

What is the difference when checking the legality of a move by another method than by expanding and watch the king survive? It is a free choice how to manage that task.

And it would be interesting - if you point to Perft results obviously being that important to you - to see your numbers, of course with similiar statistics on mates and other move types.

Regards, Reinhard.

[Sune Fischer]

GeoffW,

Don't worry about your nps, perft is not about nps as such, it originated as a debug tool but is now seen by some as a move generator benchmark.

To score better on this benchmark people have gotten creative in their perft algorithms. I think there are three basic designs in the workings.

1) There is the standard Crafty way which generates moves and then makes them, somewhat similar to what you would in normal search.

2) Then there is the Uri way, which also generates and makes moves, except for the last iteration where the moves are not "made" but only counted. This is a bit like the search + eval where the final counting might simulate a mobility term.

3) Then there is your garden variaty spinoffs, using a hash and other tricks to speed up the counting. One can say this helps in the debugging of the hash.

Counting moves is simply a lot faster than making moves, so method 2 and 3 will calculate perft quicker than 1.
If you mix 2 and 3 you have probably the fastest design possible for a perft, getting a 100 billion "nps" will be possible on some positions.

-S.

[Reinhard Scharnagl]

Hello Sune,

you are right - just as I had said: Perft for me is relevant as a verification tool ...

But nevertheless it is nonsense to ask a programmer using a legal move generator (gained with a lot of costs during move generation, also when supplying the moves with information whether they are check threats, captures or even matings etc.) to overmore make and unmake the moves of the last ply. This would be an unnecessary double calculation of the valid moves.

To have comparable results (for those who are interested in) I have provided two types of results: one more conventional split into counting of several move types including mates, and one using a transposition table to demonstrate that Perft is also interesting in verificating correct hashing.

Regards, Reinhard.