Winboard Forum

by **Reinhard Scharnagl** » 17 Oct 2004, 18:55

Hello Zach,

as I prosumed you are using attack tables. And it is quite normal, that this would consume time. I use a P4 2.8 GHz. My preevaluated moves in perft are about 20 million / sec., your moves would be from 1 million to 10 million a sec.. And seeing the effect of integrating weak and strong squares found, that would be fast enough.

I am wondering about the big timing range at about factor 10. What would be the reason for those partially weaker timings? Is it (like with Smirf) simply when generating moves when being in a check threat? (Smirf is slowing down then to about 1/6 of speed in the extreme example.)

Within a deescalation / quiescence search sorting would about double my time consumption. Whats about your engine? Do you perform a real sort (like Smirf does) or do you have other "tricks"? I decided to make a complete sorting after knowing that more than half of all knots would be completly used.

Regards, Reinhard.

by **Zach Wegner** » 17 Oct 2004, 20:45

Hello Reinhard,

Yes, the attack tables slow this down a lot, but I use them a lot in other parts (mainly eval), so there is a tradeoff. Yes, one problem with both of ours is the weakness of generating evasions. I still have to loop over every piece to see if any of them have any moves, when in the position you posted only the king could move. I slowed down a lot (1/10) I presume because the attack tables are a more linear thing that still takes the same time even when there are no piece moves. But for my move ordering, my move type is just an int, which includes all information (to, from, piece, capture, ep, castle, promotion piece, and the prescore). I also do a full sort, although I think I could speed it up by trying the hashmove and then scoring the moves. Actually, I might be able to not even generate moves until after the hashmove. I will have to look.
I have to go now, just got a good idea.

Regards,
Zach

by **Reinhard Scharnagl** » 17 Oct 2004, 22:50

He Zach,

my move generator creates pairs of move and preevaluation, which both are 4 bytes long. Thus I have something more to move during a sort. But I am wondering, where in your move a check threat is stored. In my move encoding there is a byte reserved to store a check direction or zero or a double check code or a mating code. There is also a flag combination signaling that an e.p. move may be possible after that move. The other information you mentioned is included too.

Regards, Reinhard.

by **Reinhard Scharnagl** » 18 Oct 2004, 12:24

Hello Uri and other interested,

during the last hours I had to learn that the verifying, whether a check threat would be a mate or not, could cost up to 33% of performance. Therefore I make that investigation an option within calling my move generator.

Within my perft tests I have replaced the counted matings by counted double check threads. With that I get now:

Code: Select all: FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1 +-*--b--c--d--*--f--g--*-+ MS Vis. Studio C++ Vers. 13.10 8 |[r][n][b][q][k][b][n][r]| 7 |[p][p][p][p][p][p][p][p]| Perft Testseries 6 | ::: ::: ::: :::| 5 |::: ::: ::: ::: | (without caching) 4 | ::: ::: ::: :::| 3 |::: ::: ::: ::: | Smirf Test No.: 00 2 || 1 |<R><N><Q><K><N><R>| Break Time 75.0 Sec. =>+-*--b--c--d--*--f--g--*-+ Ply Nodes all (x) (e.p.) all (+) all (++) Promot. Castl. Sec. ------------------------------------------------------------------------------- 01 20 0 0 0 0 0 0 0 02 400 0 0 0 0 0 0 0 03 8902 34 0 12 0 0 0 0 04 197281 1576 0 469 0 0 0 0 05 4865609 82719 258 27351 0 0 0 0.2 06 119060324 2812008 5248 809099 46 0 0 4.8 07 3195901860 108329926 319617 33103848 1628 0 883453 127 ------------------------------------------------------------------------------- FEN: r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 25 +-*--b--c--d--*--f--g--*-+ MS Vis. Studio C++ Vers. 13.10 8 |[r]::: :::[k]::: [r]| 7 |[p] [p][p][q][p][b] | Perft Testseries 6 |[b][n] :::[p][n][p]:::| 5 |::: :::<N> ::: | (without caching) 4 | [p] :::::: :::| 3 |::: <N> :::<Q>:::[p]| Smirf Test No.: 01 2 || 1 |<R> ::: <K> :::<R>| Break Time 75.0 Sec. =>+-*--b--c--d--*--f--g--*-+ Ply Nodes all (x) (e.p.) all (+) all (++) Promot. Castl. Sec. ------------------------------------------------------------------------------- 01 48 8 0 0 0 0 2 0 02 2039 351 1 3 0 0 91 0 03 97862 17102 45 993 0 0 3162 0 04 4085603 757163 1929 25523 6 15172 128013 0.2 05 193690690 35043416 73365 3309887 2645 8392 4993637 8.0 06 8031647685 1558445089 3577504 92238050 55014 56627920 184513607 331 ------------------------------------------------------------------------------- FEN: 8/PPP4k/8/8/8/8/4Kppp/8 w - - 0 1 +-a--b--c--d--e--f--g--h-+ MS Vis. Studio C++ Vers. 13.10 8 | ::: ::: ::: :::| 7 | ::: :::[k]| Perft Testseries 6 | ::: ::: ::: :::| 5 |::: ::: ::: ::: | (without caching) 4 | ::: ::: ::: :::| 3 |::: ::: ::: ::: | Smirf Test No.: 02 2 | ::: :::<K>[p][p][p]| 1 |::: ::: ::: ::: | Break Time 75.0 Sec. =>+-a--b--c--d--e--f--g--h-+ Ply Nodes all (x) (e.p.) all (+) all (++) Promot. Castl. Sec. ------------------------------------------------------------------------------- 01 18 1 0 0 0 12 0 0 02 290 0 0 52 0 212 0 0 03 5044 144 0 310 0 2232 0 0 04 89363 194 0 15360 106 42120 0 0 05 1745545 46745 0 161249 246 544556 0 0.1 06 34336777 406616 0 6021556 58370 10977688 0 1.6 07 749660761 22632801 0 87618216 114543 165649936 0 34.7 0816303466487 337063298 0 2990354989 29875834 3731200972 0 737 -------------------------------------------------------------------------------

Regards, Reinhard.

by **Uri Blass** » 19 Oct 2004, 01:37

Hi Reinhard,

Your result encourage me to think again about speed imprvement in my move generator.

I have some questions about your move generator.

1)Do you have some list of pawn captures that is updated incrementally?

I think that it is a waste of time to check if every pawn can capture to the left side and to the right side after every move and it is better to have some table for that purpose but it is possible that my intuition is misleading and the only way for me seems to be to check and try it.

I think about the following ways to save checks if square are empty:
1)having array pawninfo[64] when
pawninfo[sq]&1 if pawn at square sq can move 1 step forward.
pawninfo[sq]&2 if pawn at square sq can move 2 steps forward.
pawninfo[sq]&4 if pawn at square sq can capture to the right side.
pawninfo[sq]&8 if pawn at square sq can capture to the left side.

This is not exactly a table of captures and I still need to check for every pawn if (pawninfo[sq]&12) but it seems faster than what I do now to find if pawn can capture when I do special check for every pawn if it can capture to the right side and if it can capture to the left side.

Another idea is to have a list of captures
pawncapture[16][2] that is updated incrementally after every move is an option but maybe it is faster to have linked list for that purpose and not array.

seeing some source code for solving a similiar problem(not has to be inside a chess program) may be productive for me.

2)Did you consider to have list of moves for both sides that is updated after every move(The idea is that you do not need to generate again and again moves like a3 and if a3 is on the list of moves in the initial position
then it is also in the list after 1.e4 e5

Example in the opening position you generate list of 20 moves of white and black.

After 1.e4 you do the following steps:
1)adding e5,Be2,Bd3,Bc4,Bb5 Ba6,Qe2,Qf3,Qg4,Qh5,Ke2,Ne2 to the list of moves of white
2)deleting e3,e4 from the list of moves of white
3)Not changing the moves of black.

After 1...e5 you do the following steps:
1)adding Be7,Bd6,Bc5,Bb4,Ba3,Qe7,Qf6,Qg5,Qh4,Ke7,Ne7 to the list of black moves.
2)deleting e6,e5 from the list of black moves
3)deleting e5 from the list of white moves.

I believe that implementing this idea without bugs is hard and I even did not try to do it but it is possible that somebody can come with faster move generator if (s)he implement it.

by **Reinhard Scharnagl** » 19 Oct 2004, 06:39

Hi Uri,

to 1) I do not (yet) have any to be maintained table (except the board representation itself), everything is calculated dynamically, in my data structure the type of information you have mentioned easily could be fetched from the board representation;
to 2) I do not have any secondary move lists, may be I have something misunderstood here.

but

to 1) this may change for nodes above quiescence / deescalation search
to 2) calling the move generator en block will itself create a move list to any node, so I do not really understand, what is your intention, sorry. To check the existence of a special move within a list and to reverify its legality seems to cost more efforts than to recalculate it.

I am not sure whether pieces of source code might help you. Please specify, which problem you intend to focus. I will try to find something which might support your thoughts (but I am very sure that source would be very different, as it probably is not related to any published code).

Regards, Reinhard.

by **Uri Blass** » 19 Oct 2004, 08:30

1)If I guess correctly then your board representation include more information than information about the piece and the colour of every square so claiming that you have not tables may be misleading because your tables may be compressed into your board representation.

2)About the second idea the number of moves that are added and substracted for both sides is usually smaller than the number of legal moves so I can imagine that updating list of moves incrementally may be
faster than generating the same move every time.

3)About solving a similiar problem I meant to the problem of implementing linked list instead of array when I want to do a loop on all the elements and it can be productive to see
if it is faster to have linked list and not to have array and how much it is faster.

Uri

by **Reinhard Scharnagl** » 19 Oct 2004, 09:43

Hi Uri,

1)If I guess correctly then your board representation include more information than information about the piece and the colour of every square so claiming that you have not tables may be misleading because your tables may be compressed into your board representation.

No, your conclusion might be understandable but is definitely wrong. Nevertheless I have bit encoded properties of the pieces at the place where a piece is stored (I already have mentioned that). But those informations are CONSTANT and would not be changed each move. And to find out e.g., whether a pawn could capture a neighboured piece costs me not much RAM accesses, thus a separate (moreover to be actualized) table would not at all improve my move generator.

2)About the second idea the number of moves that are added and substracted for both sides is usually smaller than the number of legal moves so I can imagine that updating list of moves incrementally may be faster than generating the same move every time.

I hope I understand right: if one is calculating pseudo legal moves, the idea to maintain lists of legal moves should be able helping to improve the performance of finally legal moves (!?). It might be founded in my personal disliking of additionally to be maintained tables. But I am still not able to see any advantage in using such tables. Nevertheless I am thinking on such approaches AFTER and ABOVE the quiescence / deescalating search. But that would not target move lists but data necessary for positional evaluation. I am very interested to learn whether the use of attack tables even during the quiescence search would pay off. May be we should compare average timings of getting stable node values by applying a deescalation / quiescence search.

3)About solving a similiar problem I meant to the problem of implementing linked list instead of array when I want to do a loop on all the elements and it can be productive to see if it is faster to have linked list and not to have array and how much it is faster.

Using linked piece lists alone would not help much. I got the actually visible improvements by being able to put all necessary information into ONE integer each piece. And this is already much more as I have been willing to tell on my approach ever before.

Regards, Reinhard.

by **Uri Blass** » 19 Oct 2004, 11:10

Hi Reinhard.

If I understand correctly one of the following 2 possibilities are correct

1)You have by a single integer, information about the content of more than one square in your tables, so you may find that a pawn cannot capture or maybe even that some pawns cannot capture only based on some bits of a single number.

2)You need to check for every pawn except maybe pawns in the a file and in the h file that they cannot capture left and cannot capture right so you have 2 if's to do for every pawn or almost every pawn to find pawn captures.

I guess that the first possibility is correct(otherwise I cannot understand your objection for having tables for pawn captures) but maybe I simply do not understand and inspite the fact that tables with information about pawn captures are less calculations they are still more expensive from computer point of view.

Uri

by **Reinhard Scharnagl** » 19 Oct 2004, 11:45

Hi Uri,

If I understand correctly one of the following 2 possibilities are correct

well, I am not sure on this. Either I am not able to express myself understandable (which might be possible even because i do not open every detail), or you really misunderstood what I have tried to explain. It possibly seems to me a method to get more detail information as I am willing to open :-) . Nevertheless I try to explain again.

My board structure is a physically one but logically two dimensional array of 32 bit INTEGERS. Each integer is representing the content of a board position, which could be an encoded piece. The pieces simultaneously are forming a DOUBLE LINKED LIST and e.g. covering CONSTANT bit encoded properties of their nature and abilities, etc..

Because of the constant nature of the encoded information your idea 2) is very near to what happens, except that I have not to care, whether a pawn is standing outermost at the a-file or h-file (or j-file at the 10x8 interpretation of the board). So I have no tables about pawn captures, which should be clear because such tables always have to be kept updated, which I have definitely declared not to do. Sorry if I would have told you something misunderstandable about that.

Thus I would need logically 1 to 2 IFs to get that information, with an average of 5/4 or less down to 1 during a game. This might be able to explain why I am not sure that dynamicly to be updated tables would help me to reduce that work unter those 1/4 additional IFs or less in average.

Regards, Reinhard.

by **Uri Blass** » 19 Oct 2004, 12:56

Hi Reinhard,Thanks for your information.

I see that I explained myself wrong in the previous post:

I wrote about possibility 1:
"You have by a single integer, information about the content of more than one square in your tables"

I meant in the board and not in your tables in the possibility that I suggested.

I still do not understand why you need only an average of 5/4 if's or even less than it in a game.

most pawns are not in a or h file so it seems that you need to check 2 different conditions for most of the cases.

In order to check if white pawn at b2 can capture you need to check
both the square a3 and the square c3 so it seems to me that you need to check 2 different elements in your board structure unless you store information about both a3 and c3 in one integer of your board structure that is what I meant by possibility 1.

Uri

by **Reinhard Scharnagl** » 19 Oct 2004, 13:47

Hi Uri,

I still do not understand why you need only an average of 5/4 if's or even less than it in a game.

That effort is for testing whether a pawn can capture AT ONE FIELD.
The procedure is independent from the file the pawn is actually standing in.

I am just about to think over my bit structure whether it might be possible to always finish that test after using only one IF.

Reinhard.

by **Reinhard Scharnagl** » 19 Oct 2004, 20:21

Hi Uri,

after an intensive thinking phase I have been able to overlay two bits into one. Thus there is now only still ONE IF to answer the question of pawn captures to one field. But the bonus in timing I got was nearly irrelevant. That is on the other side a good verification for my estimation of average usage of the IFs there. The bonus which I finally got is in the now somehow simplified program part concerning pawn captures, which has had more IFs that at the other piece types. Current times are now:

Code: Select all: FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1 +-*--b--c--d--*--f--g--*-+ MS Vis. Studio C++ Vers. 13.10 8 |[r][n][b][q][k][b][n][r]| 7 |[p][p][p][p][p][p][p][p]| Perft Testseries 6 | ::: ::: ::: :::| 5 |::: ::: ::: ::: | (without caching) 4 | ::: ::: ::: :::| 3 |::: ::: ::: ::: | Smirf Test No.: 00 2 || 1 |<R><N><Q><K><N><R>| Break Time 2.0 Sec. =>+-*--b--c--d--*--f--g--*-+ Ply Nodes all (x) (e.p.) all (+) all (++) Promot. Castl. Sec. ------------------------------------------------------------------------------- 01 20 0 0 0 0 0 0 0 02 400 0 0 0 0 0 0 0 03 8902 34 0 12 0 0 0 0 04 197281 1576 0 469 0 0 0 0 05 4865609 82719 258 27351 0 0 0 0.2 06 119060324 2812008 5248 809099 46 0 0 4.7 ------------------------------------------------------------------------------- FEN: r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 25 +-*--b--c--d--*--f--g--*-+ MS Vis. Studio C++ Vers. 13.10 8 |[r]::: :::[k]::: [r]| 7 |[p] [p][p][q][p][b] | Perft Testseries 6 |[b][n] :::[p][n][p]:::| 5 |::: :::<N> ::: | (without caching) 4 | [p] :::::: :::| 3 |::: <N> :::<Q>:::[p]| Smirf Test No.: 01 2 || 1 |<R> ::: <K> :::<R>| Break Time 2.0 Sec. =>+-*--b--c--d--*--f--g--*-+ Ply Nodes all (x) (e.p.) all (+) all (++) Promot. Castl. Sec. ------------------------------------------------------------------------------- 01 48 8 0 0 0 0 2 0 02 2039 351 1 3 0 0 91 0 03 97862 17102 45 993 0 0 3162 0 04 4085603 757163 1929 25523 6 15172 128013 0.2 05 193690690 35043416 73365 3309887 2645 8392 4993637 7.8 -------------------------------------------------------------------------------

Regards Reinhard.

Winboard Forum

Thoughts on Move Generation

Re: Thoughts on Move Generation

Re: Thoughts on Move Generation

Re: Thoughts on Move Generation

Re: Thoughts on Move Generation

Re: Thoughts on Move Generation

Re: Thoughts on Move Generation

Re: Thoughts on Move Generation

Re: Thoughts on Move Generation

Re: Thoughts on Move Generation

Re: Thoughts on Move Generation

Re: Thoughts on Move Generation

Re: Thoughts on Move Generation

Re: Thoughts on Move Generation

Who is online