3

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

Glorfindel
  • 24,745
  • 6
  • 67
  • 114
malocho
  • 161
  • 1
  • 5
  • 3
    What 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 Richerby Jan 04 '15 at 12:36
  • https://chessprogramming.wikispaces.com – Pete Becker Jan 04 '15 at 15:03

3 Answers3

3

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.

sardoj
  • 336
  • 3
  • 6
  • -1 this makes no sense at all. Move generation is a very simple routine in programming. – ABCD Jan 06 '15 at 00: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"? – sardoj Jan 06 '15 at 02: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 – ABCD Jan 06 '15 at 02: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? – sardoj Jan 06 '15 at 02: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. – ABCD Jan 06 '15 at 02:55
  • @StudentT You don't get the point, he is right. Move generation logic depends on board and piece representations. – ferit Apr 01 '16 at 19:22
  • @Sailbot Do you really know what you're talking about? I wrote the request was fine. I didn't say about the dependence. – ABCD Apr 02 '16 at 01:40
  • @StudentT I'm completely sure what I'm talking about. I'm a programmer. – ferit Apr 02 '16 at 14:57
1

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
Community
  • 1
Mike Jones
  • 5,151
  • 14
  • 19
1

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.

ABCD
  • 22,419
  • 2
  • 43
  • 82