Attack table

[Reinhard Scharnagl]

hi Zach,

first I see, that your Perft results are not at all bad.

No, I say legal move generators make it go faster because you do not have to make the moves on the last ply, ...

Let me mention, how my Perft might differ from yours:

a) (+) not expanding leaf nodes at the bottom of the tree
b) (-) instead of a) the legality of all moves is guaranted (at comparable costs)
c) (-) use of some slower 64 bit counters, (7 counters in total)
d) (-) the moves know, whether they are captures, check threats (-), matings (--), etc ...
e) (-) supplying the moves with a combination of MVV/LVA and positional preevaluation to make the movelist sortable, simultaneously handling detected predefined killer or optimal moves
f) (-) building up a complex statistic on that information from d)
g) (-) using unchanged DoMove and Remove functions which are updating material balance, hash address (32 bit) and verification key (32 bit), e.p. and castling rights, reordering two double linked piece lists, etc. ...
h) (-) a higher abstraction level (handling of 8x8 and 10x8 boards, Fischer castlings / FRC)
i) (-) principially handling two more piece types (archbishop and chancellor at several program places)
j) (-) using C++ language only, no parts rewritten in assembler

If I would be interested in a kind of Perft "cheating", there would be a lot of points, where I could "optimize". But I use Perft simply as an instrument of verification, and for that it is really usable. Especially splitting up the results into a statistic has helped me a lot in localizating some silly errors within my move generator. It would help others a lot, if they would also create and publish such statistics on some well known starting positions. I can recommend warmly the following one:

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

[Reinhard Scharnagl]

Hi Uri,

ideed to supply moves also with the information whether they are check threats (I distinguish between simply one check direction, double check or mate) is somehow time consuming. But I am convinced, that this could simplify a lot of procedures, and help to avoid some errors.

Whether someone would be a better programmer or not is hardly to decide. I am sure, that nobody who's program could generate more than 5 million legal moves each second should be called a weak programmer.

To go back to my data structure: may be I am not objective here (because of not having seen into a lot of other source codes), but I am sure, that the 14x15 board geometry and the double linked list structures have somehing to do with Smirfs good performance. But I am also sure, that there would be completely different but also efficient approaches. But seeing your splitted piece list let me agree with your assumption, that this might be solvable in a more performant way. (My structure is limiting the number of pieces simply by the number of fields: 64 in 8x8 and 80 in 10x8, where only exactly one king for a side has to exist.)

Regards, Reinhard.

[Roman Hartmann]

hello all,
I implemented a direction table (as suggested by Dan) and just wanted to share my results.
The table (int direction[120][120]) is initialized by startup with the proper values. I'm using a stripped down attack function to do that. As this is done only once at startup of the program performance doesnt really matter here.
When I'm generating a move now I only have to check if there is a connection between the square of the king and the square of the piece that is going to move. In most cases there is no connection (means direction[King_square][Piece_square] == 0) and the call to attack can be avoided.
In most positions the move generation process is now -after implementing this direction table- a good deal faster (10-30%). Thanks again Dan for the suggestion.

Code: Select all

(Initial position)
roce: perft 5
Perft 5: 4865609 (0.58s)
roce: perft 6
Perft 6: 119060324 (14.86s)
roce: perft 7
Perft 7: 3195901860 (371.36s)

roce: setboard r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -

roce: disp
8   {r} .  .  . {k} .  . {r}

7   {p} . {p}{p}{q}{p}{b} .

6   {b}{n} .  . {p}{n}{p} .

5    .  .  . [P][N] .  .  .

4    . {p} .  . [P] .  .  .

3    .  . [N] .  . [Q] . {p}

2   [P][P][P][B][B][P][P][P]

1   [R] .  .  . [K] .  . [R]

     a  b  c  d  e  f  g  h

turn: white
castling w:   Q:1, K:1 castling b:   q:1, k:1
king w: e1 king b: e8

roce: perft 5
Perft 5: 193690690 (18.77s)
roce: perft 6
Perft 6: 8031647685 (769.94s)


Roman

[Dan Honeycutt]

Hi Roman:

Glad the table helped. It gives not only pin candidates but

direction[square_of_piece][square_of_interest]

tells you for pieces other than the knight if any attack by piece on square_of_interest is possible. If the attack is possible it tells you how piece has to travel to get there. You will likely find use for the table when you get to king safety, static exchange and other situations where you need to know who attacks what.

Best
Dan H.

[Uri Blass]

Hi Reinhard,
I admit that my results are good relative to most programmers but I think that the secret is simply a better algorithm and not programming tricks.

My background is mainly mathematics and not programming.

I can clearly see possible advantages of finding if moves are checks or mates or double checks in the process of move generation

one advantage is in better order of moves and having mate first in the list and double checks in high place in the list can improve the order of moves.

Another advantage is that if I want to prune moves that are not checking moves and not captures in the last ply then I do not need to have an expensive function to check if a move is a checking move.

Uri

[Sven Schüle]

one advantage is in better order of moves and having mate first in the list and double checks in high place in the list can improve the order of moves.

Hi Uri and Reinhard,

if the move generator would find out statically that one certain legal move mates immediately then I think you could stop further generation and manage not to expand this node. Instead, you might return the appropriate mate value and set the mating move as principal variation.

But I'm not sure whether the effort to find an immediate mate during move generation is a good investment because statistically mate is quite rare, and most of the time you try to find a mate and find nothing. In my opinion finding mate, like finding other types of end positions, should only be done by the searcher and not by the move generator.

Sven

[Reinhard Scharnagl]

Hi Sven,

to enhance your position it would be good to describe an example, where you recognize a move to be a check threat and you are not interested to know, whether this move would be a mate or not. I think that in most cases it would of course be interesting to decide this, thus providing such information would not be a wasted efford.

It is another situation if you would argue, that it is not necessary to know, whether a move is a check threat or not. Well, then you would detect a mating situation only by a kind of "accident". But this is quite normal for chess engines with a pseudo legal move generator. But this - in my opinion - is like playing chess without knowing the rules, or to create an intelligent algorithm by first making it silly.

Well, I am not neutral in this point, I have decided to use a legal move generator and to have routines with more transparent logic. The majority of chess programmers (as far as I know) is using pseudo legal moves. So please excuse me for my minority position.

Reinhard.

[José Carlos]

Hi Reinhard, I think he means:
[diag]rnbqkbnr/pppp1ppp/8/4p3/6P1/5P2/PPPPP2P/RNBQKBNR b KQkq g3 0 2 [/diag]

If you know, at generate time, that Qh4 is checkmate, you don't need to generate any other moves.
Sounds logical to me at first glance.

[Sune Fischer]

Hi Reinhard,

It is another situation if you would argue, that it is not necessary to know, whether a move is a check threat or not. Well, then you would detect a mating situation only by a kind of "accident". But this is quite normal for chess engines with a pseudo legal move generator.

I do not see what that has got to do with legal or pseudo legal move generation.
The two generators are the same, except that a pseudo legal generator will on occation generate a few extra moves that are not legal due to the moving piece being pinned.
Detecting pinned pieces and check mates are of course two different things.

A pseudo generator is usually faster because checking for pins is expensive, but the search tree node counts should be identical between the two approaches, only the pseudo generator somewhat faster because the legality can be postponed until such a time when the move is actually needed.

What Jos? Carlos is talking about is different as I see it. Detecting mating moves at generation time can indeed save nodes.

I do not personally believe it is worth the trouble though, too few mates relative to the cost, and most mates will be found at shallow depths and then remembered either as hashmoves, killers or similar to be reused for the deeper searches anyway.

-S.

[Uri Blass]

Hi Jose,I think that the cases when smirf detect mate in move generation are rare so stopping the move generator after generating mate is not going to change much.

It may even do the program slower in the cases that it does not find mate because in these cases it is going to check the condition if there is a mate after every move that it generates and checking that condition may be expensive.


Hi sune, the advantage of detecting checks and mates in move generation is more information and I can easily see how more information can be used for many ideas.

For example you can use the fact that there is no mate for pruning when the remaining depth is 1 when it will be too dangerous to prune when you do not know that there is no mate.

I have the same opinion as Reinhard
I also have legal move generator in order to have more information but
I still did not do the steps of detecting checks and mate(detecting mates in move generation is probably the harder programming problem).

Note that the situation with most engines is even worse than not detecting checks in move generation and they even do not detect checks after making moves.

I know that a lot of engines can have some main line that ends with mate without seeing that it is a mate.

At least movei does not have that problem and it always evaluate mate as mate and stalemate as draw.

I think that it may be also interesting to detect stalemates in the move generator.

I guess that in most cases it may be possible to detect no stalemate easily by the fact that a lot of pieces can move and you cannot prevent all of them to move without attacking the king.

Uri

[Zach Wegner]

Hello Reinhard,

first I see, that your Perft results are not at all bad.

Thank you! I don't really care about perft results, but it's nice to have a fast one.

Let me mention, how my Perft might differ from yours:

a) (+) not expanding leaf nodes at the bottom of the tree
b) (-) instead of a) the legality of all moves is guaranted (at comparable costs)

This is not true, I think you misunderstood me. I generate only legal moves, just like you. That is why my perft is faster than e.g. Crafty using a comparable pseudo-legal generator.

c) (-) use of some slower 64 bit counters, (7 counters in total)

My node counter is 64 bits as well, but indeed there is only one.

d) (-) the moves know, whether they are captures, check threats (-), matings (--), etc ...
e) (-) supplying the moves with a combination of MVV/LVA and positional preevaluation to make the movelist sortable, simultaneously handling detected predefined killer or optimal moves

This is interesting to me, my move generator would need almost a total rewrite for this to happen. I use a quick pointer (*move++ = int) and generate movesort values for all moves in a seperate function. But as my engine is under constant construction, this is flexible, and I currently do not consider whether a move checks or not in my sorting. I am just not sure how much this would gain, so it will take a while before I try...

g) (-) using unchanged DoMove and Remove functions which are updating material balance, hash address (32 bit) and verification key (32 bit), e.p. and castling rights, reordering two double linked piece lists, etc. ...

I do this as well, although with different board structure.

j) (-) using C++ language only, no parts rewritten in assembler

Well I use only C code, so I guess I am a lot faster here

One important point that speeds you up a lot is the use of a hash table. I think I might implement this soon because it is easy and I would like to compare results with you. Now whether or not this is "cheating" is a completely different topic...

Regards,
Zach

[Uri Blass]

Hi Zach,

1)C++ is not slower than C.

I also use C++ and the only change that I did to do it C++ is simply changing my .c files to .cpp(I later added some cpp code that is not c(like having a class for time management) but it was done only for functions that I use rarely and has not effect on speed).

2)Reinhard is using hash tables and has result with hash tables and without hash tables.

Uri

[Reinhard Scharnagl]

Hi all,

discussing attack tables and how much information a generated move should have and whether it should be legal or pseudo legal seems to be a hot stuff. So let me add some more arguments for my (and probably Uri's) position:

If you are using only legal but fully informed moves the quality of information stored in transposition tables is getting more dense.

Here are some recent values (with only three important counters, Intel P4 2.8 GHz):

Code: Select all

FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

  +-*--b--c--d--*--f--g--*-+ MS Visual Studio C++ Version 13.10
8 |[r][n][b][q][k][b][n][r]|
7 |[p][p][p][p][p][p][p][p]| Perft Testseries
6 |   :::   :::   :::   :::|
5 |:::   :::   :::   :::   | (With TT Caching 320 MB / 4-fold)
4 |   :::   :::   :::   :::|
3 |:::   :::   :::   :::   | Test #:      00
2 |<P><P><P><P><P><P><P><P>|
1 |<R><N><B><Q><K><B><N><R>| Break Time 10.0 Sec.
=>+-*--b--c--d--*--f--g--*-+

Ply          Nodes         all (x)         all (+)   Seconds
------------------------------------------------------------
01              20               0               0         0
02             400               0               0         0
03            8902              34              12         0
04          197281            1576             469         0
05         4865609           82719           27351       0.1
06       119060324         2812008          809099       1.6
07      3195901860       108329926        33103848      18.9
------------------------------------------------------------


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

  +-*--b--c--d--*--f--g--*-+ MS Visual Studio C++ Version 13.10
8 |[r]:::   :::[k]:::   [r]|
7 |[p]   [p][p][q][p][b]   | Perft Testseries
6 |[b][n]   :::[p][n][p]:::|
5 |:::   :::<P><N>   :::   | (With TT Caching 320 MB / 4-fold)
4 |   [p]   :::<P>:::   :::|
3 |:::   <N>   :::<Q>:::[p]| Test #:      01
2 |<P><P><P><B><B><P><P><P>|
1 |<R>   :::   <K>   :::<R>| Break Time 10.0 Sec.
=>+-*--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       3.8
06      8031647685      1558445089        92238050      85.8
------------------------------------------------------------

It has been stated that an engine with a pseudo legal move generator would NOT have more nodes expanded in search. That is not to believe. The OPPOSITE seems to be true for me. You have to verify the legality of moves (by expanding), you have to get the information, whether a move is a check (seems to be done by previous expansion), you have to verify whether a check threat is a mate or not. Thus the expanding level has to be a complete ply deeper. Depending on your selectivity this means a factor of more than 3 additional nodes each move, thus at least 4 times nodes totally counted.

Regards, Reinhard.

[Sune Fischer]

Hi Uri,

Hi sune, the advantage of detecting checks and mates in move generation is more information and I can easily see how more information can be used for many ideas.

I don't really see what kind of information there extra, ie say we are on a typical node and you generate 38 legal moves and I generate 40 pseudo legal, 2 of them being illegal due to a pin on one of the pieces.

How do you use this information for something useful?

You have to find something, because you just spent three time as long time generating your list as I did mine.

For example you can use the fact that there is no mate for pruning when the remaining depth is 1 when it will be too dangerous to prune when you do not know that there is no mate.

A mate would require a check, so you can search all moves that are checks for one extra ply.
This is called a check extension and I use it

I have implemented a routine to see if a move gives check before it is made, just wanted to try it for move ordering. It doesn't seem to save that many nodes.

I have the same opinion as Reinhard
I also have legal move generator in order to have more information but
I still did not do the steps of detecting checks and mate(detecting mates in move generation is probably the harder programming problem).

I think that is one of the problems, it's quite hard to implement such a detector. Even if one could do it the question is if it would save more than 1% of the nodes. It would not take much to slow down the engine by 1% though.

I know that a lot of engines can have some main line that ends with mate without seeing that it is a mate.

I think this is because those engine collect the PV also in qsearch and their qsearch has no check extension or mate recognizer.

This should be impossible in a real search if a check is always extended by 1 ply.

****************************************

Hi Reinhard....

I'm not sure what you mean by:
"If you are using only legal but fully informed moves the quality of information stored in transposition tables is getting more dense."

What is a fully informed move and how does information get more dense?

Also interesting to note that we disagree on the definition of a pseudo legal generator

You _do not_ have to verify the legality of the move by making it (or by expanding as you call it). Indeed this would demand an extra node.
I'm sure there are some implementations that do this, but it is not a good implementation IMO.

The idea of doing it like this would be that you afterwards can check if opponent king is in check and then undo as the position is illegal.
However, it is much cheaper to simply check if the move you are about to make is illegal by pin (these are by design the only possible illegal moves in frenzee).

First of all it is faster in itself to see if a piece is moving illegally out of a pin than it is to do a full attack detect on the opponent king, secondly you save a make/unmake.

As a result you can toss out illegal moves as soon as you get to them, no extra nodes required at all.

-S.
[/quote]

[Reinhard Scharnagl]

Hi Sune,

well I have to learn that you obviously have an engine handling pseudo-legal moves untypically (but not bad), this has been new to me. Until that moment I have been convinced that using pseudo legal move generators would be caused by the wish to decide the legality of moves later by simply expanding them.

If you do it more sophisticated, you have already nearly all the software to transform your generator into a legal move generator (in contrast to more traditional pseudo-legal approaches - as far as I know). Then it would be interesting to know, what for you would be the advantage to delay that legality verification.

Verifying legality immediately would make some procedures a lot simpler and clearer to understand. There also would be knowledge on the amount of legal moves, stalemate situations etc.. If you should be thinking that verifying legality later would be applied in less moves, because there could be abortings of node evaluations, I am not convinced that you would be right here, because there would be a lot of illegal moves (especially within check threats), depending on your search already being even partially expanded. Also storing, sorting of generated moves and their preevaluation would need some more time and storage (with some little effects on internal CPU caching).

(Well, this moment I have seen another consequence: pseudo legal moves could be very counter productive in the task of detecting killermoves or optimal moves, because of errornously claiming to be such moves though they might be illegal in that situation.)

My conclusion on this thoughts is, that your approach will differ from mine only small in its principial performance, but has more complicated routines. But that only are assumptions.

So why you are not doing the full step to a legal move generator?

Regards, Reinhard.

[Sune Fischer]

Hi Reinhard

I can't say what a normal pseudo generator looks like, but there are the simple designs and the more advanced designs.

The simple design with the InCheck() at the next ply, is perhaps the most well known. It's not that bad to start out with in a new engine and improvements from there are not huge I think.

What I do currently one step away from legal generation, but I'm not sure if that last step is worth taking. It seems costly to validate all moves just to put them on the list.

Then again there are some simplifications one can do, some discount by doing it all at once. Perhaps it is worth it in the end after all, worth testing at least.
I just happen to believe in the C. Theron philosophy: don't do anything until you must, precomputed work is mostly wasted.

-S.

[Uri Blass]

Hi Sune.

You do not need to validate all moves in legal move generator.

If you find that a piece is not pinned then you can be sure that all of it's moves are legal.

The results of smirf suggest that the cost of generating the information is not high and I believe that information can be used(pruning based on the fact that there is no mate in the next ply is only one example).

I suspect that generating more information about moves(some flags that tell me which move threat opponent pieces and which move cause forks) can be also productive but it also make the task of the programming harder because generating a lot of information fast and without bugs is not an easy task.

I see that I looked only in your last post so I will also reply to your previous post.

1)In the case of movei I use the number of legal moves for evaluation and decisions about pruning.

There is probably better way to evaluate mobility than usingthe number of legal moves but today I still use the number of legal moves to do it.

If the side to move has a lot of legal moves then there is a good chance that this side has a good move.

2)I think that knowing that there is no mate in the next ply is a good reason for pruning based on evaluation and remaining depth.

You need to make all the checks to see maybe one of them is mate when a program with full information does not need to do it.

3)I do not believe that legal moves make the program 3 times slower in nodes per second and my guess is that it is clearly less than it.

Uri

[Reinhard Scharnagl]

Hi Uri,

You do not need to validate all moves in legal move generator.

that seems to be a semantic problem - I think it would need a sort of validation in any case.

If you find that a piece is not pinned then you can be sure that all of it's moves are legal.

With the exceptions of King moves, e.p. captures, and Fischer castlings, where the rook is pinned though it would move along the pinning line.

But to everything else I agree. There is a great benefit of having the full information to any move: capture, check with its direction, double-check, mate, e.p.-preparing double pawn step ...

Overmore the engine procedures will of course become more transparent.

Regards, Reinhard.

[Tord Romstad]

Hi everybody,

This is my first post in this forum. I hope it works.

I haven't had the time to read all of this very long discussion, but here are some comments:

Gothmog uses attack tables, which are calculated from scratch at every node in the tree. For purposes of move generation and legality checking, I think attack tables are not worth the price. However, they are very useful in the search and evaluation function.

By using attack tables, it is relatively simple and cheap to statically detect hanging pieces, trapped pieces, forks, and many common mating patterns. This kind of information can be used to do forward pruning and reductions without introducing too many tactical mistakes, and also to improve the accuracy of the qsearch.

In the evaluation function, attack tables can be used to evaluate things like mobility, space and king safety. With attack tables, safe mobility is not much more expensive than normal mobility. When evaluating space, it is nice to know the biggest piece for each side which can safely move to a given square. This can be done almost for free, by using a big precomputed lookup table or a small hash table. When evaluating king safety, it is very nice to have complete information about all types of pieces attacking and defending each square around the king, and also to be able to find and count all safe checking moves.

Attack tables are expensive to compute, but when you have them, you can add lots of complicated knowledge at very low additional cost. You can also (to a big extent) compensate for the slowdown by using the attack information to do more aggressive pruning.

Glaurung and Scatha (my new engines) do not yet have attack tables. Before I add them, I will spend some time trying to implement equally good search and evaluation functions without attack tables. My biggest problem so far is king safety; I have not yet found a good way to evaluate this without complete attack information for both sides. I have some vague ideas which I will try to implement later. If I find something really effective and not too expensive, I will of course let you all know.

I don't really understand the discussion about legal vs pseudo-legal move generators. As far as I can see, the difference has no practical importance. With a pseudo-legal move generator, I have to do an "if(is_legal(move))" before making and searching a move. I can't see why this single extra line of code matters.

Tord

[Reinhard Scharnagl]

Hi Tord,

still I am thinking on attack tables, still I am not convinced, but I am also still learning.

I don't really understand the discussion about legal vs pseudo-legal move generators. As far as I can see, the difference has no practical importance. With a pseudo-legal move generator, I have to do an "if(is_legal(move))" before making and searching a move. I can't see why this single extra line of code matters.

Does this "single" line (with some following calculations) help you when to decide a situation to be mate or stalemate? I think you are simplifying the problem, which - here I may agree - is more a philosophical / aesthetical problem.

Regards, Reinhard.