Attack table

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

[Sune Fischer]

Hi Reinhard

The perft has several applications, I use it to verify node counts for all sorts of things, like hash, move ordering and of course the generator itself.

I don't much like the idea of using it as a benchmark though, it's a bit like optimizing the engine for scoring well on test suites.
I know for instance that my incremental generator is faster in games but it is slower on perft. It's just apples and oranges.

-S.

[Reinhard Scharnagl]

Hi Sune,

intersting to read ... - I myself have started with a sequential move generator. But even when I succeeded in generating killermoves first, today I am convinced, that move ordering abilities are worse there.

There might be an advantage in generating moves when answering a chess threat, because of being able to stop the generating of moves earlier. But I compensated that now by having a move generator split into two parts, one working within a check threat, one out of those. Having this now I do not see any advantage of a sequential generator, may be except of the situation to build a physical chess computer having only a very small amount of RAM - which today is a really exotic scenario.

But on the other side: why change a winning function? I have been happy to have two really different generators to be able to detect weaknesses of my actual one by calculating Perft tests and by comparing result details.

Regards, Reinhard.

[fierz]

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

gosh how i hate this forum! now i answer to an old post of uri's and it finishes up in a sequential list of completely unrelated answers! GRRRRR!

anyway; your comment uri about being 100s of times slower then that means you are doing something wrong: you are using an "old school" profiler which will give you COMPLETELY UNRELIABLE results. there are newer tools which do a much better job, and one is even free: it is the "codeanalyst" of AMD - you can download it on their webpage. get it. it's worth spending some time with, because this profiles your code properly - i.e. your program is running at nearly full speed, and not in some weird mode which has nothing to do with the real execution.

cheers
martin

[Uri Blass]

Hi Reinhard,

I also do not like sequential move generator and I even did not try it.
I use the number of legal moves to get some decisions in movei about evaluation and prunings and extensions and I cannot do it with sequential move generator.

I also may try to evaluate probabilities of moves to be best move and
I certainly cannot try to do it when I even do not know the number of moves.

Uri

[Reinhard Scharnagl]

Hi Uri,

your argument why to have an en block move generator is not fully convincing. But indeed, at a higher level of a decision and search tree it might be helpful to know the number of all moves. But you can use even a sequential move generator to get this. And because not being at a leaf node there, the performance would not be really affected by that.

Nevertheless if your idea would need such information even in the leafes of the tree, a sequential move generator would be counter productive.

To use a sequential move generator would normally help to avoid to produce unnecessary moves. But if a sequentially generated move would need about double of the time an en block generated move consumes, the sum of those would finally need more time. But I see still another exception, which is when writing a mating engine.

Reinhard.

[Sune Fischer]

Hi Reinhard

I'm not sure what you mean by sequential generator, if you mean move by move generation I don't think there is a great saving to be found there. Beyond the first handfull of moves a cutoff is rare.

Of course there would be no long move list to sort, but I don't see a way to generate the moves in the best order with a sequential move generator without having most of them and comparing them against eachother somehow.

-S.

[Reinhard Scharnagl]

Hello Sune,

a sequential move generator (as I have had implemented) has been a routine which creates a next move on demand. This has some consequences as the whole environment has to be absolutely unchanged after an undo of a move, which is not that easy if (as I do) you have two sorted piecelists and e.g. the undone move has been a promotion.

That generator was able to start his sequence at a predefined killer move, which then has been created first if possible. Cutoffs happen when the killer or the optimal move has been sucessful, or when inside of a check threat after a first possible move a mate could be excluded.

Instead of a sorting I had implemented a type of filter which buffered probably week moves for a second path and activated the probably better immediately. Therefore a relevant fraction of knots were only partially expanded. Thus there have been remarkable cutoffs.

I had long favorized this type of generator. Today I think that sorting moves coming from an en block move generator does make more sense.

Regards, Reinhard.

[Roman Hartmann]

hello,
this attack table thread caught my attention as attack tables might help to improve my move generation process too.
My own chess engine (not much more than a working movegenerator exists at the moment) is working with legal moves (board representation: 10x12) only and seems to spend most of the time checking if the the king is in check. With some profiling I figured out that attack takes about 70% of the CPU time. The problem seems to be that I check after every generated move if the king gets into check. I'm not too happy about this as the king doesn't get into check for most of the moves, of course and I'm wasting a lot of time here. So I'm thinking about using a attack table too to avoid most of the unnecessary attack calls. But I'm still a bit uncertain where I should update this table. Most logical seems to update it in domove()/undomove(). Anyone else doing (or tried this once) this the same way and could tell how well that works ?

Regards
Roman

roce: perft 5
Perft 5: 4865609 (0.70s)
roce: perft 6
Perft 6: 119060324 (16.63s)

Output profiler (CodeAnalyst) when running perft from the initial position
Symbol + Offset Samples Total % CPU0 32 bit
attack 133463 67.37 133463 133463
makemovelist 45279 22.86 45279 45279
t_mv_B_w 6864 3.46 6864 6864
t_mv_p_w 3927 1.98 3927 3927
undomove 1523 0.77 1523 1523
domove 1457 0.74 1457 1457
perft 393 0.2 393 393
t_mv_B_b 276 0.14 276 276
t_mv_k_w 255 0.13 255 255
t_mv_p_b 124 0.06 124 124
t_mv_k_b 7 0 7 7

[Reinhard Scharnagl]

Hi Roman,

as I already have told, I (still) do not use an attack table, because I (still) have not been convinced to do that.

Are you talking about a) checking whether the own king has been illegally left within a check threat, or b) checking whether the opponents king has been set into a check threat? [My move generator does a) and b).]

In case of a) you are multiply testing each piece (if that would be able to do several moves) whether it might be pinned or not. But a piece is pinned or is not pinned. There is no need and profit in testing this more than once.

The test a) is off course somehow different, when the own king already has been within a check threat before.

Reinhard.

[Roman Hartmann]

Hi Reinhard,
I'm currently only checking if the own king is in check (in makemovelist). Every pseudo legal move is then made on the internal board (but without updating any flags) and then I call attack to see if that position puts or leaves the own king in check. Only the valid moves are added to a a list then. If there are no valid moves left the function makemovelist gives back a 0 and the search decides then if it's either mate or stalemate. But because I'm checking after every move (in akemovelist) if a certain move brings or keeps the own king in check I have to call attack quite often. For most of the moves the king isn't in check anyway So I thought that a table of pinned pieces (or attacked pieces) might help to reduce the number of attack calls.

Roman

[Uri Blass]

Hi Reinhard,

The idea of tables is to save generating the same information again and again.

Did you try tables and found that they are slower for you?
I did not try not using attack tables and I believe that I may use more tables.

For example it seems to me stupid to check during generating moves again and again the colour of all the squares at distance one near the king when I may have a table of the empty squares near the king and a table of the squares near the king that have enemy pieces.

Uri

[Uri Blass]

Hi Roman,
I use tables for pins and for attacked squares and I update them in make move and undo moves.

My board is simply 0-63 when 0 is a1 7 is h1 and 63 is h8.

The point of Reinhard is that you can save time by having a function to find the pinned pieces before generating moves even without a table so in most cases after you find no pinned pieces you may avoid the attack function in moves that are not king moves and even if you find one pinned piece you do not need to use your attack function for move of other pieces when the only exception is the king.

Uri

[Reinhard Scharnagl]

Hi Uri,

comparable to you still having avoided to try not to use attack tables I still have not implemented my sort of attack tables to test them to be more performant.

But I have thought a lot over this problem, and i still cannot imagine that storing and refetching such calculated attack results could be more efficient than my calculating them at demand using my very special data structure. But I promise, that I will think this problem over for some hours again.

Regards, Reinhard.

[Reinhard Scharnagl]

Hi again Roman, hi again Uri,

only at king moves and e.p. capture moves there is a need to use something like attack tables. If you find other pieces being pinned by a sliding enemy piece, the pinned piece can move without additional tests along that pinning line but only there. Being inside a check threat things are a little bit more complex, but could be solved even without such attack investigations.

So only king moves and e.p. capture moves remain to be tested with more effort. And for those SPECIAL situations it seems not to save any time to ALWAYS keep a sort of attack table actual after each move, which overmore is mostly not followed by such a sort of move (king or e.p.).

Regards, Reinhard.

[Dan Honeycutt]

Hi Roman:

What you are doing (as you already know) is WAY too slow. Attack tables are one approach. Following is another option (when you say your board is 10x12 I assume you mean 10 wide x 12 high so you have a 2 square frame in every direction to keep a knight from leaping off):

Build a directions[120][120] table which will give you the direction from square 1 to square 2. Entrys in the table will be +1 or -1 for squares on the same rank, +10 or -10 on the same file, +/- 9 or 11 on same diagonal and 0 for all others.

When you are ready to generate moves for a piece you first look at
directions[piece_moving_square][own_king_square]

if the value is 0 (which will be the vast majority of the time) the piece moving cannot be pinned and you generate the moves without further ado.

If the value is non-zero the piece moving could be pinned. You could do your incheck test or, better yet, the directions table tells you where to look to find out if the piece really is pinned.

Good Luck.
Dan H.

PS - Do you need an opening book. I'm looking for beta testers.

[Roman Hartmann]

Hi Reinhard, Uri, Dan,
it seems to me (after rereading some posts here) that attack tables are not that easy to handle.

And yes I'm using a 10 wide x 12 high board (int board[120] to be exact) in order to keep the knights from jumping off the board.

Dan:
the idea with the directions[120][120] table sounds like a good (and yet simple to implement) idea and I will try that. Also the idea to make attack a bit more selective (scaning only in certain directions ...) is something I will take into account.

Regarding your opening book I have to say that I'm still working on implementing alpha beta properly and adding some stuff to my eval (which is currently based mainly on material). Might take some time before I can even think about adding a book to the engine.

Thanks a lot for the help!

Roman

[Reinhard Scharnagl]

Hi Uri,

to add some arguments that always calculating attacks targeting a square could be a really "cheap" live procedure, see following examples:

Code: Select all

FEN: R6R/3Q4/1Q4Q1/4Q3/2Q4Q/Q4Q2/pp1Q4/kBNN1KB1 w - - 0 1

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

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


FEN: r1bRN3/pk2pp2/3p4/K1pP3r/5R2/5B2/8/8 w - c6 0 1

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

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


FEN: cr5nr1/p1p1p1Pppp/3p2a3/PpPk4N1/1PC2P4/4BN1PA1/1Q2B3PP/1R3K2R1 w Q b6 0 1

  +-a--b--c--d--e--f--g--h--i--j-+ MS Visual Studio C++ Version 13.10
8 |[c][r]   :::   :::   [n][r]:::|
7 |[p]   [p]   [p]   <P>[p][p][p]| Testscenario searching for:
6 |   :*:   [p]   :::[a]:::   :::| undirected check threats
5 |<P>[p]<P>[k]:::   :::   <N>   |
4 |   <P><C>:::   <P>   :::   :::| Test #:      21
3 |:::   :::   <B><N>:::<P><A>   |
2 |   <Q>   :::<B>:::   :::<P><P>| Test Count:  750000*80
1 |:::<R>:::   :::<K>:::   <R>   | per Second:  66225165
=>+-a--*--c--d--e--*--g--h--i--j-+ Time:        0.906 sec

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


Even if in every move such a test would occur, Smirf would not at all slow down. Smirf can do about 70 million and more such complete live tests in a second. That an always to be kept actual attack table would be that performant has to be demonstrated first, before I would think it over to make a table implementation for testing purposes.

Regards, Reinhard.

[Zach Wegner]

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.

No, I say legal move generators make it go faster because you do not have to make the moves on the last ply, because you know they are legal. I do not think perft results are important at all really-but in the opening position on a 1.25 GHz G4 I get:

Code: Select all

(zct)1. perft 5
4865609 nodes 0.375 s 12.975m nps
(zct)1. perft 6
119060324 nodes 10.012 s 11.892m nps

[Uri Blass]

Hi Zach,
Do you have similiar statistics of number of checks and number of mates in your move generator?

In other word does your move generator check if moves are checks or mate?

Today I do not do it.
I can do it by making moves and undoing them but it is going to be stupid to do it in that way and it may be better simply to check the relevant squares near the king that changing information in them may lead to check.

generating information about checks will certainly do things slower but I guess that it will be only slightly slower because I find that updating a table that tell me for every square if I can get a check by adding a piece to that square or removing a piece does it only about 10% slower in the opening position.


I guess that Reinhard's advantage in perft is mainly because he is a better programmer.

I doubt if the decision to have board of 14*15 has something to do with his speed and other decisions to have linked list of pieces may be productive.

I guess that I may get some speed advantage by using more pointers but my piece list is simply:
int kingsquare[2];
int queens[9][2];
int rooks[10][2];
int bishops[10][2];
int knights[10][2];
int pawns[8][2];

I have also arrays that tell me the number of queens of every side and the same for other pieces.

Uri