I am looking for an efficient (fast) program to generate next moves for all pieces.
I need it in C++, because I will program in C++.
-
3What do you want this for? Are you attempting to write your own chess engine? The move generation code is one of the easier parts of writing an engine: if you can't do that part, there's very little chance that you'll be able write the rest of the search routine. It's like saying, "Hey, I need to fly this plane. Can somebody taxi it to the end of the runway for me?"– David RicherbyCommented Jan 4, 2015 at 12:36
-
chessprogramming.wikispaces.com– Pete BeckerCommented Jan 4, 2015 at 15:03
Add a comment
|
3 Answers
http://support.stockfishchess.org/discussions/questions/1422-generation-of-next-moves-for-all-pieces
You should use Tord (the person who wrote Stockfish)'s C++ move generation code. It's easy, simple, fast and good. It uses magic bitboard.
answered Jan 6, 2015 at 0:52
I think it is unreasonable to ask for this as a stand-alone program because its implementation will be very dependent on the design of your program as a whole. In particular, it completely depends on how you are storing each position: how are you representing the board and pieces? How do you keep track of where each piece is after each move? How do you know which squares a piece can move to (is there a piece there already? Is there a piece blocking the bishop's movement as it goes from c1 to f4?)?
Of course, once you have a implemented all of the above perfectly then the problem of generating the moves that each piece can make becomes quite easy: simply iterate over every piece and for every piece iterate over all of its valid moves (how you store moves is, again, entirely up to you).
Finally, this is a great resource that gives a good overview of some important topics in chess programming.
-
-1 this makes no sense at all. Move generation is a very simple routine in programming. Commented Jan 6, 2015 at 0:51
-
2@StudentT Did I say anywhere that generating moves is not simple? My post was addressing the challenge of integrating this simple task into a complete chess program which is considerably more challenging. Also, could you elaborate on why my post "makes no sense at all"?– sardojCommented Jan 6, 2015 at 2:14
-
1. It's a reasonable request to ask for a stand-alone program. 2. The poster requests for a C++ solution while the link is not being very helpful Commented Jan 6, 2015 at 2:27
-
2@StudentT In the comments of the link that you posted the replies reference the move generation in the Stockfish codebase -- how does that disprove my statement that you can't expect move generation in a single program? Having all your move-gen code in a file called movegen.cpp does not make it a "stand-alone" program because that code will completely depend on the rest of your program. That is the point of my post: how can we provide OP with move-gen code when we don't know how the rest of his program is designed?– sardojCommented Jan 6, 2015 at 2:52
-
Of course you could. movegen.cpp is a engine-optimized source file. But the code written by Tord also provided in the link is actually a standard-alone C++ library for move generation and validation. It's not related to the engine. Commented Jan 6, 2015 at 2:55
Representing Moves found via BitBoards, applying them, and removing them provides a good overview of move generation using the fastest method.
I use a different method relying on three arrays.
key[] = {1, 2, 4, 8, 16, 32, 64, 128, ...} // bit test aligned to movement.
movement[] = {1, -1, 8, -8, -9, -7, 9, 7, -17, -15, -10. -6, 6, 10, 15, 17}
movementkey[64] = {...} // bit set if move is possible.
This array is setup in such a way that if the bit is set, the corresponding movement is allowed. For example, if the third bit is set in the movementkey array, represented easily by key[2], then movement[2] is a legal square.
Loop through the pieces.
P: check based upon color
N: loop through last eight indexes.
B: call Slider function with index value of 4.
R: call slider function with index value of 0.
Q: call slider function twice, with 0 and 4.
K: simple one square movement.
check for EP, and castling.
The Slider function:
tosquare = fromsquare
loop from index to index + 4
if bit is set fromsquare += movement
if empty addmove and continue
else
if NotOwnPiece addmove
break
