Hi, I am currently developing a standard bitboard-based chess engine. I have just implemented the perft (calculate the number of nodes up to a certain ply) command, and noticed that the move generation speed of my program is very slow compared to other chess engines (66 times slower than crafty to be specific), but the results are correct. Of course, I don't think my program can ever become as fast as crafty, but 66 times slower seems a bit too slow. My program uses loops to generate sliding moves instead of rotated bitboards. Note that I am only benchmarking the move generation speed, so transposition tables or prunning technics wouldn't matter. My initial guess was that the reason is because I am not doing make and unmake, but creating new boards to apply moves instead. So I rewrote it to do making and unmaking moves. However, much to my surprise, the speed not only did not increase, but even decreased a little bit. I think I am not implementing unmake very efficiently. In my implementation, I store variables that is needed to unmake moves in a struct (lastMovedPiece, lastCapturedPiece, lastSrc, lastDst, lastEnPassantSquare, and castling availability), and construct this struct and push it onto a FILO when a move is made. When unmaking a move, this struct is popped from the FILO, and the board reversed accordingly. I have to do this because in minimax, many moves will be made at once and then unmade due to the recursive nature of the algorithm. Is it because of this implementation of make/unmake that my engine is generating moves slowly, if so, if there a better way to implement this? I understand that it is difficult to give help when so little information is given, but I don't know what else information to include. If you need more information, please ask. Thank you very much.

The people best placed to answer this are probably in the AI forum, so I'll move this there.

Have you profiled?

I suggest that it is the looping for sliding pieces that is killing you..

In any event.. I am presuming that you have at least 16 indexable bitboards per position .. that is you can reference them via a numeric index into an array which contains them..

The boards I would use, at a minimum:

0: black pawns
1: white pawns
2: black knights
3: white knights
4: black bishops
5: white bishops
6: black rooks
7: white rooks
8: black queens
9: white queens
10: black king
11: white king
12: black pieces
13: white pieces
14: all pieces
15: enpassant square
16: other info (castling rights..)

One make/unmake strategy:

When changing one of these bitboards during a move you can push the original uint64 and then push its index .. or have two paired stacks and push the index as an int32 on the second stack instead of as a uint64 on the main stack

Then its just a matter of putting a guard flag onto the first board index that gets modified during a move so that during unmake you know when to stop popping

Castling rights and so forth can be respresented as 4 bits within a uint64 as well (#16 in my list)


I dont know if this will be better than your methodology.. but it is the one I would employ first

Thank you very much for your help.

Quote:
Have you profiled?

Yes, I profiled and found out that 80% of the time is in move generation.

Quote:
I suggest that it is the looping for sliding pieces that is killing you..

I would guess so, too. However, I don't know how to do sub-function level profiling.

Quote:
In any event.. I am presuming that you have at least 16 indexable bitboards per position .. ...
16: other info (castling rights..)

That is pretty much how I am doing it.

The strategy you suggested sounds a lot better than mine. I will try to implement it and see what happens.

Thank you

Quote: Original post by cyberfish

I would guess so, too. However, I don't know how to do sub-function level profiling.

http://www.google.com/search?source=ig&hl=en&q=codeanalyst&btnG=Google+Search

http://www.google.com/search?hl=en&q=vtune&btnG=Search