Winboard Forum

Hi

I have been reading Ed Schr?ders page regarding calculating attack tables. I have coded up a version quite similar to that described by Ed. To test it and get it working I have currently just called the white & black table generation in my Eval function just after the lazy eval decision.
This allowed me to use it for a hopefully improved king safety calculation.
It wasnt a total surprise to find that it is very expensive on my nodes per second to generate this information. To make proper use of the time spent calculating the tables I really need to use it for more than just king safety. This is where I get a bit hazy and could use some advice please

Attack tables could be further used for

1) More Eval functions, eg Center control etc. The table generation can be left where it currently is for this addition

2) Fast in check and and checking move calculations. To make this work however I need to move the table generation earlier to maybe after the makemove function. This would cause more of a slowdown in nps

3) Further work could make the tables give a SEE feature, used for move ordering. The big snag with this is that table generation would have to be done for all moves at move generation. This means that we move the generation before any beta cutoffs and would cause a crushing slowdown in nps. If I moved this code into the move gen function I think I would need to measure speed in seconds per node

I wonder if Rebel does the attack table gen at move generation time, I am assuming it must do ?

I would be interested to hear if I am understanding these points correctly or any general advice and tips regarding attack tables ?

Thanks for your time

Geoff

Hi Geoff,

I have written one program with attack tables (Gothmog) and one without (Glaurung). I'll try to answer your some of your questions below.

GeoffW wrote:Hi

I have been reading Ed Schr?ders page regarding calculating attack tables. I have coded up a version quite similar to that described by Ed. To test it and get it working I have currently just called the white & black table generation in my Eval function just after the lazy eval decision.

This is similar to what I do in Gothmog, except that I have never used any kind of lazy eval.

This allowed me to use it for a hopefully improved king safety calculation.

If you end up finding attack tables useful for king safety and little else, you may want to have a look at the king safety evaluation in Glaurung. It is somewhat similar to Rebel's king safety, but does not use attack tables.

It wasnt a total surprise to find that it is very expensive on my nodes per second to generate this information. To make proper use of the time spent calculating the tables I really need to use it for more than just king safety. This is where I get a bit hazy and could use some advice please

Attack tables could be further used for

1) More Eval functions, eg Center control etc. The table generation can be left where it currently is for this addition

Yes, the evaluation function is by far the most important use of attack tables. If you don't find several good uses for attack tables here, they are not worth the price. Besides king safety, I have found attack tables to be particularly useful when evaluating space and mobility. In the space eval, you can do a table lookup to check whether a square is controlled by white, controlled by black, or neutral. In the mobility eval, attack tables can be used to compute safe mobility (pseudo-legal moves which do not lose material) almost as cheaply as plain mobility.

2) Fast in check and and checking move calculations. To make this work however I need to move the table generation earlier to maybe after the makemove function. This would cause more of a slowdown in nps

This point has very little importance. In check and checking move calculations can be done with almost zero cost, even without attack tables. You do this by looking at the last move made (or the move you are just about to make). For most moves, looking at the 'from' and 'to' squares is sufficient to see that the move cannot possibly be a check. For the remaining moves, it is only necessary to scan for attacks in one (or occasionally two) directions. Look at attacks.c in Glaurung if you want an example of how the code could look.

3) Further work could make the tables give a SEE feature, used for move ordering. The big snag with this is that table generation would have to be done for all moves at move generation. This means that we move the generation before any beta cutoffs and would cause a crushing slowdown in nps. If I moved this code into the move gen function I think I would need to measure speed in seconds per node

I wonder if Rebel does the attack table gen at move generation time, I am assuming it must do ?

Of course I have never seen Rebel's code, but I always assumed that it did attack table generation during or directly before evaluation (just like I do in Gothmog). I don't see any point at all in doing attack table generation at move generation time.

One more possible use of attack tables which you didn't mention:

4) Static mate detection. Many common mating patterns can be detected by using attack tables. For instance, if the black king is on g8, the g7 square is attacked by the white queen and at least one other white piece, and no black piece except the king defends g7, we can be almost sure that Qxg7 is a mate in one. Note that we cannot be 100% sure: The white queen could be pinned, or there could be an X-ray defence by a black piece through the white queen. It is therefore not safe to return a mate score. Nevertheless, this kind of static mate detection can be useful. You can use it in move ordering, by placing the move which is almost certainly a mate in one first in the move list. In the qsearch, you can decide to search the (probably) mating move even if you don't normally search all checks.

Tord

Hi Geoff,

perhaps you may also find some useful hints in another thread about attack tables in this forum:
http://volker-pittlik.name/wbforum/viewtopic.php?t=171

Sven

My advice would be to try computing the attack tables on the fly for the king safety squares until you are sure you want to use them other places. I also would recommend a different structure for attack tables, as the Rebel tables are very vague and can't really be used for much but attack patterns (BTW I'd suspect that Ed does eval, attacks and move generation all together). My current structure uses a sort of "compression":
No. of P attacks:0-2
No. of N/B attacks:0-3
No. of R attacks:0-2
No. of Q attacks:0-2
No. of K attacks:0-1
So there are 3*4*3*3*2=216 possibilities for the table value (you have to use an array lookup to calculate them, but it's small). I use the tables quite a lot (at least 4 times per move generated, more in eval), so it's worth it. I used to do full legal move generation and attack table generation together, but it's too slow. If you are using 0x88 or another array-based board representation, it could be acceptable, but with bitboards you have to increment the attacks on squares containing friendly pieces, which is just too costly.

Regards,
Zach

Hi Geof
This is an interesting post.
i have used Ed's attack tables successfully.
My advice to you, just pay the price once and get it over with.
No doubt you can have a superb king safety if you have attack tables at hand. That could be more than 50 elo worth which you can only gain by huge increase in nps.
I have used them for other things as well
- Safe or pseudo mobility calculation
- space control (opponent squares and centre)
- you can also use it for SEE
if you don't use lazy eval this will completely replace the conventional SEE in the quiescent search. so I have two SEE functions
one used in quiescent and one in main search.
i use this also in evaluation ,for passed pawn eval,
out posts and weak pawn.
- evaluation of hanging / pinned pieces
This can also be important to guide your full width search if you dare to call the big eval at evey node.


Now about check/in_check ,as tord pointed out, it is easier to look if the move gives direct/indirect check.

i made a little experiment using thsi.
1. one version uses the attack tables
2. anothe one uses fast square attack calls
- GetPieceSqAttack
- GetPawnSqAttack
3. collecting attack information of squares ONLY around the king
while looping throug the pieces. king safety is done at the end.

1 & 2 search the same number of nodes at a certain depth. I found out that 2's attack calls (note it is used only for king safety) are too much!! that their speed is almost identical.

i wrote 3 just to check if it is possible to have a cheeper king safety and
have the better speed. Speed is great but elo is very bad.

And after adding lazy eval and evaluation cache, 1 is faster than 2!
i still update the non attack table version just incase i find better techniques to do things with out attack tables. for example i left out using it for SEE in the previous version of danchess because it is a little riskier for my test and i wanted to use lazy eval more.

Hope this helps
daniel

Hi

Thanks to Tord Sven, Daniel, & Zach for all the feedback, lots of food for thought there. That old very long thread was interesting reading too.

Someone posted some results saying that an incremental Attack table calculation was about 4 times faster than doing it from scratch everytime.
That was a bit discouraging as I have just coded mine the slow way
It was quite a simple bit of code to do it from scratch, but it must be really tricky to work out incremementally, think I will postpone that one for now.

I am fairly happy to leave the attack table expense as it stands now as long as I dont have to move it too much earlier in the code and make the nps even worse. After adding the code I now get about 780knps from the opening position on a P4 2.2 Ghz, so not too unacceptable

The really infuriating thing is that a self test against the earlier non attack table version was much worse in real games, due presumably to the loss in nps. Yet when I tested again Kiwi the attack table version is much improved (20 points/32 with tables 15.5/32 without)
I hate it when that happens. Grrrrr

I think I need to do some more testing with it before figuring out what to do next. Thanks again for the advice

Regards Geoff

Hi geoff,

I was considering using attack tables myself. It will probably not hurt my engine much NPS wise as it is already slow. How much of an NPS hit (in %) did you guys take when you added attack tables to your programs?

Pallav

Hello Pallav

Just did a quick measurement for my benchmark position

Nodes per second of attack table version is about 2/3 of previous version. See below (P4 2.2 Ghz)

Regards Geoff


Without attack tables

Code: Select all

Ply  Eval   Time  kNode/s   Principle Variation
 1     71      0       1    f2f4
 2     44      1     275    g5e4 d6c7
 3     79      1     403    g5e4 d6c7 f2f3
 4     50      4     728    g5e4 d6c7 f2f3 c8b7
 5     72     14     870    c1d2 d6c6 f2f4 f7f6 g5e4
 6     55     40     930    c1d2 c8d7 g5e4 d6c7 f2f3 e6e5 d4e5 g6e5
 7     67    204     994    h2h4 d5f6 c2a4 h7h6 g5f3 d6c7 c1e3
 8     52    490     988    h2h4 h7h6 g5e4 d6c7 h4h5 g6e7 f2f3 c8b7
 9     71    864    1044    h2h4 h7h6 h4h5 h6g5 h5g6 f7f6 c2a4 d6c7 c1d2
10     49   4532    1049    h2h4 h7h6 h4h5 h6g5 h5g6 f7f6 c2a4 d6c7 c1e3 c8d7
Time: 45328 ms


With attack tables

Code: Select all

Ply  Eval   Time  kNode/s   Principle Variation
 1    106      0       1    f2f4
 2     74      1     255    f2f4 f7f6
 3     92      1     839    g5e4 d6c7 f2f3
 4     69      6     560    h2h4 h7h6 h4h5 h6g5
 5     95     15     638    h2h4 f7f6 g5e4 d6c7 f2f3
 6     72    100     706    f2f3 c8d7 g5e4 d6c7 c1e3 f7f5
 7     85    242     710    h2h4 d5f6 c2a4 h7h6 g5f3 d6c7 c1e3
 8     77    976     699    b2b3 b6b5 h2h4 h7h6 h4h5 h6g5 h5g6 f7f6
 9    100   1892     698    h2h4 h7h6 h4h5 h6g5 h5g6 f7f6 c2a4 d6c7 a4a3
10     84   6884     699    h2h4 h7h6 g5f3 c8a6 h4h5 g6e7 c1d2 a6b5 f3e5 e7f5
Time: 68844 ms

GeoffW wrote:The really infuriating thing is that a self test against the earlier non attack table version was much worse in real games, due presumably to the loss in nps. Yet when I tested again Kiwi the attack table version is much improved (20 points/32 with tables 15.5/32 without)
I hate it when that happens. Grrrrr

Hi Geoff,
please feel free to leave attack tables out and score <50% against Kiwi! At any rate, Kiwi has been able to use attack tables for several versions now and in my experiments I have found results quite similar to yours. However, in my case the version with attack table although much slower was just slightly worse than the version without, but usually considerably better against other engines.
When enabled, I use the relatively expensive attack generation only to evaluate board control and, in some measure, king safety, so there must be something important there that the current evaluation misses entirely. The reason no public version has this, I want to get rid of piece/square tables entirely and give a more important role to evaluation of dynamic factors, possibly based on attack tables. I hope this will make into version 0.5x...

Hi Allesandro

Yes Kiwi was proving to be a good opponent as games were pretty evenly matched. Well I am being slightly economical with the truth on that point. I was using Kiwi version 0.4b which I think is a couple of versions out of date now, also I was giving Kiwi less hash table too, who said competitions had to be fair
I tend to try and find about 3 opponents of similar strengh for my testing, currently using Kiwi, Knightx and GES for my tests. It is not working very well lately as results are all over the place. I tried running some tests on a higher spec PC (P4 3.4 GHz), again results seem to be patchy, but slightly better for attack tables than without.
I jotted down some figures with the faster PC, it gives a speed up of 25% to 30% compared to the clock scaling of 54%, but the attack tables slowed me down by 33%
Motto is. forget about CPU clockspeed, it is not as important as efficient algorithms and tight coding.

Regards Geoff

GeoffW wrote:Hello Pallav

Just did a quick measurement for my benchmark position

Nodes per second of attack table version is about 2/3 of previous version. See below (P4 2.2 Ghz)

Thanks. NPS of your program _after_ implementation of attack tables is still much better than Natwarlal! .

Hi Geoff!

GeoffW wrote:I am fairly happy to leave the attack table expense as it stands now as long as I dont have to move it too much earlier in the code and make the nps even worse. After adding the code I now get about 780knps from the opening position on a P4 2.2 Ghz, so not too unacceptable

780knps with full attack table computation, and you are only "fairly happy"? I feel ridiculously incompetent when I read things like this. Glaurung searched around 700knps on a P4 2.4 GHz at the time when the evaluation consisted of material and piece square tables alone. It's down at 250knps now, and the eval is still fairly simple. Adding attack tables would certainly bring me below 200knps.

Tord

Hi Tord/Pallav

Your post made me smile, it reminded me of this, see link below

http://www.storyarts.org/library/aesops/stories/tortoise.html

I played a few games against Glaurung but had to stop the match after 20 or so games as my program was getting slaughtered unmercifully.
Chess knowledge and a good bug free search is what is important, nps is secondary I think. As I was struggling to improve chess knowledge and search I was clinging on to the straw of fast nps. At least that might mean it has got potential for future improvement.

The most obvious difference between Glaurung and my program is the nodes taken per ply, Glaurung is an order of magnitude smaller, I really have no idea how such a huge difference is achieved !

I am not 100% sure if I increment my nodes count in the conventional way, I havent really checked other programs. I do it in 2 places only, once at the start of my search function and once at the start of my quiesce function.

Incidentally I decided to try and improve the 33% attack table slowdown by a rewrite of the movegen and attack table code to see if it improves calculation time.
A post here a few days ago about the idea of a precalculated square list and a skip table for movegen was interesting so thought I would give that a try. It is fairly simple to code, but I havent quite finished it yet.
If anyone is interested I could post some comparative results when I have finished it ?

Regards Geoff

1. Write a better hash

2. Write better move ordering

3. Do checks in q-search

4. Throw out all useless extensions esp. recaptures

That should improve your branching factor incredibly.

anthony

Yeah easy, in short write a better program

Anthony Cozzie wrote:3. Do checks in q-search

How does this improve branching factor?

4. Throw out all useless extensions esp. recaptures

Yes, I never managed to get something from recaptures except more code.

/Peter

Peter Fendrich wrote:Yeah easy, in short write a better program

Anthony Cozzie wrote:3. Do checks in q-search

How does this improve branching factor?

4. Throw out all useless extensions esp. recaptures

Yes, I never managed to get something from recaptures except more code.

/Peter

Recaptures is just another word for "quiescent search" no?

No wonder then, that a program with a good quiescent search sees very little benefit from recaptures [except singular recaptures, which are practically free since bf is 1.00]

Dann Corbit wrote:Recaptures is just another word for "quiescent search" no?

Not really. It is in the tree before the Qsearch is reached. The main idea is that equal exchanges can be extended. Such as: if ("this is a capture" && "parent was a capture of same value" && "materialvalue is re-established") depth += RecapExtend;

Not sure if this make sence but it's a try anyway...

/Peter

Dann Corbit wrote:

Peter Fendrich wrote:Yeah easy, in short write a better program

Anthony Cozzie wrote:3. Do checks in q-search

How does this improve branching factor?

4. Throw out all useless extensions esp. recaptures

Yes, I never managed to get something from recaptures except more code.

/Peter

Recaptures is just another word for "quiescent search" no?

No wonder then, that a program with a good quiescent search sees very little benefit from recaptures [except singular recaptures, which are practically free since bf is 1.00]

Not quite the same.

Off coarse all recaptures will be investigated in quiescence, but if you extend on them in normal search, a noncapture move could be after them, wich wouldn't be investigated (normally) in qsearch.

OTOH if there is a good noncapture move after the recapture that makes a big difference, it's very often a check, so an engine doing checks in qsearch doesn't need the recapture extensions so much.

Tony

OTOH if there is a good noncapture move after the recapture that makes a big difference, it's very often a check, so an engine doing checks in qsearch doesn't need the recapture extensions so much.

This agrees with my tests with TRACE. Older versions had no checks in qsearch and seemed to need recapture extensions more. Yesterday, I removed recap extensions and this reduced BF. But more importantly, the OTB results improved as well.... although not enough games to be too conclusive, yet.

Another thing, previously, I rewarded even recaptures with a 3/4 ply extension only if the search was within 3 ply of the horizon. This seemed to help with test suite results but I think overall it destabilises the search.

I need to run some more gauntlets but I think recaps (or the way I implemented them) was/is not helpful for TRACE.

Cheers,

Ross

what if that killer move after the capture sequence ends is not a check?
i think that the point of recapture extensions is to avoid delaying capture/recapture sequences anywhere in the tree,not just at the tips.
if cap/recap is done near the root, just to delay something bad at the tips(by some quiescent move),the one without recapture extensions wouldn't see it even if it does search all captures and checks.
one may also say singel response extensions are not important if you do
long checking sequence in qsearch. i also do this extensions for the same reason i do recap extensions.