Just another movegen

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
vittyvirus
Posts: 645
Joined: Wed Jun 18, 2014 12:30 pm
Full name: Fahad Syed

Just another movegen

Post by vittyvirus » Fri Nov 14, 2014 8:12 am

This is third rewrite of my move generator (yes. third). People here have witnessed me fighting against my extremely poor code, and I know much more.

When I started chess programming, I started with a dramatic goal to create a 3000+ engine. I thought it was easy.

Now, I know what actually is the base of a super strong engine. Its clean, concise, and well written code. Not that I learned that after 30+ years of experience, but it sounds quite obvious to me.

When I think of clean code, two engines come to my mind. Stockfish and iCE chess. Both are clean coded, and take advantages of STL.

Before, I took pride in having lines of code. move.cpp + movegen.cpp = 2000+ lines of code sounded elite. And now, the LESSer lines of code sound more elite. Without comprising on performance, you can use templates to generate sliding and non-sliding moves within one function.

And now, as you see, I've a movegen that's only 263 lines of code (due to classical formatting used by C4Driod).

I started with Silican Chess, and then rewrote it to Chress (not Chesser), and after losing all Chress codedue to display problem with my laptop, started from scratch with Yaka, using g++ with C4Driod on my Andriod

Here's the code:

Code: Select all

// movegen.h : Yaka's Move Generator
#ifndef INC_MOVEGEN_H_
#define INC_MOVEGEN_H_
#include "includes.h"
#include "move.h"
#include "position.h"

class MoveList
{
	Move mList[MaxMoves];
	uint index;

  public:

	  MoveList()
	{
		index = 0;
	}

	MoveList(const Position & pos)
	{
		index = 0;
		genAllMoves(pos);
	}
	inline void addMove(const Square from, const Square to)
	{
		mList&#91;index++&#93;.move = from | &#40;to << 6&#41;;
	&#125;
	
	template <Flag flag>
	inline void addMove&#40;const Square from, const Square to&#41; &#123;
		mList&#91;index++&#93;.move = &#40;from | &#40;to << 6&#41; | flag&#41;;
	&#125;

	inline void endList&#40;)
	&#123;
		mList&#91;index&#93;.move = 0;
	&#125;

	inline int legalMoveCount&#40;)
	&#123;
		return index;
	&#125;

	void dispList&#40;)
	&#123;

		for &#40;int i = 0; &#40;mList&#91;i&#93;.move != 0&#41; && i < MaxMoves; ++i&#41;
		&#123;

			std&#58;&#58;cout << "#" << i << "&#58; ";
			std&#58;&#58;cout << std&#58;&#58;hex;
			mList&#91;i&#93;.dispMove&#40;);
			std&#58;&#58;cout << " encoded as 0x" << mList&#91;i&#93;.move;
			std&#58;&#58;cout << std&#58;&#58;endl;
			std&#58;&#58;cout << std&#58;&#58;dec;
		&#125;
	&#125;

	void dispListInSAN&#40;const Position & pos&#41;
	&#123;
		for &#40;int i = 0; &#40;mList&#91;i&#93;.move != 0&#41; && i < MaxMoves; ++i&#41;
		&#123;
			std&#58;&#58;cout << "#" << i << " &#58; ";
			// mList&#91;i&#93;.dispSAN&#40;pos&#41;;
			std&#58;&#58;cout << " Encoded as " << mList&#91;i&#93;.move;
			std&#58;&#58;cout << std&#58;&#58;endl;
		&#125;
	&#125;

	inline move_t getMove&#40;int index&#41;
	&#123;
		return mList&#91;index&#93;.move;
	&#125;

	inline Move & operator&#91;&#93; &#40;const int index&#41;
	&#123;
		return mList&#91;index&#93;;
	&#125;

	FORCE_INLINE void genAllMoves&#40;const Position & pos&#41;;

	template < Square Delta >
		FORCE_INLINE void genPromotions&#40;const Bitboard promPawns,
										const Bitboard target&#41;;
	template < PieceType pt, Color GenFor >
		FORCE_INLINE void genMoves&#40;const Position & pos,
								   const Bitboard Target&#41;;
	template < Color GenFor >
		FORCE_INLINE void genKingMoves&#40;const Position & pos,
									   const Bitboard Target&#41;;
	template < Color GenFor >
		FORCE_INLINE void genPawnMoves&#40;const Position & pos,
									   const Bitboard Target&#41;;
&#125;;

template < Color GenFor >
	FORCE_INLINE
	void MoveList&#58;&#58;genPawnMoves&#40;const Position & pos, const Bitboard Target&#41;
&#123;
	const Bitboard FreeSquares = ~pos.PieceBB&#91;ALL_PIECES&#93;;
	
	const Bitboard pawnsOnRank7 =
		pos.PieceBB&#91;&#40;GenFor == WHITE&#41; ? WPAWN &#58; BPAWN&#93;
		& (&#40;GenFor == WHITE&#41; ? Rank7Mask &#58; Rank2Mask&#41;;
	const Bitboard pawnsNotOnRank7 =
		pos.PieceBB&#91;&#40;GenFor == WHITE&#41; ? WPAWN &#58; BPAWN&#93;
		& (&#40;GenFor == WHITE&#41; ? ~Rank7Mask &#58; ~Rank2Mask&#41;;
		
	const Square Right = &#40;GenFor == WHITE&#41; ? DELTA_NE &#58; DELTA_SE;
	const Square Left = &#40;GenFor == WHITE&#41; ? DELTA_NW &#58; DELTA_SW;
	const Square Up = &#40;GenFor == WHITE&#41; ? DELTA_N &#58; DELTA_S;
	
	const Bitboard enemyPieces = &#40;GenFor == WHITE&#41; ?
		pos.ColorBB&#91;BLACK&#93; &#58; pos.ColorBB&#91;WHITE&#93;;
		
	const Bitboard Rank3 = &#40;GenFor == WHITE&#41; ? Rank3Mask &#58; Rank6Mask;

	Bitboard b1, b2;
	Square to;

		/*--- Generate Promotions ---*/
	genPromotions < Right > &#40;pawnsOnRank7, enemyPieces&#41;;
	genPromotions < Left > &#40;pawnsOnRank7, enemyPieces&#41;;
	genPromotions < Up > &#40;pawnsOnRank7, FreeSquares&#41;;

		/*--- Single and Double Pawn Pushes ---*/
	b1 = shift_bb < Up > &#40;pawnsNotOnRank7&#41; & FreeSquares;
	b2 = shift_bb < Up > &#40;b1 & Rank3&#41; & FreeSquares;

	while &#40;b1&#41;					// Single Pawn Pushes
	&#123;
		to = pop_lsb&#40;&b1&#41;;
		addMove&#40;to - Up, to&#41;;
	&#125;

	while &#40;b2&#41;					// Double Pawn Pushes
	&#123;
		to = pop_lsb&#40;&b2&#41;;
		addMove&#40;&#40;to - Up - Up&#41;, to&#41;;
	&#125;

		/*--- Standard and En-Passant Captures ---*/
	b1 = shift_bb < Right > &#40;pawnsNotOnRank7&#41; & enemyPieces;

	b2 = shift_bb < Left > &#40;pawnsNotOnRank7&#41; & enemyPieces;

	while &#40;b1&#41;
	&#123;
		to = pop_lsb&#40;&b1&#41;;
		addMove&#40;&#40;to - Right&#41;, to&#41;;
	&#125;

	while &#40;b2&#41;
	&#123;
		to = pop_lsb&#40;&b2&#41;;
		addMove&#40;&#40;to - Left&#41;, to&#41;;
	&#125;

	// En-Passant Captures
	if (&#40;pos.epSquare&#40;) != NO_SQ&#41;
		&& &#40;GenFor == WHITE ? &#40;pos.epSquare&#40;) > H5&#41; &#58; &#40;pos.epSquare&#40;) < A4&#41;))
	&#123;
		b1 = pawnsNotOnRank7 & AttacksFrom&#91;&#40;GenFor == WHITE&#41; ? BPAWN &#58;
										   WPAWN&#93;&#91;pos.epSquare&#40;)&#93;;

		while &#40;b1&#41;	addMove<FLAG_ENPASSANT>&#40;pop_lsb&#40;&b1&#41;, pos.epSquare&#40;));
	&#125;
&#125;


template < Square Delta >
	FORCE_INLINE void MoveList&#58;&#58;genPromotions&#40;const Bitboard promPawns,
											  const Bitboard target&#41;
&#123;
	Bitboard b;
	b = &#40;shift_bb < Delta > &#40;promPawns&#41;) & target;
	Square to;

	while &#40;b&#41;
	&#123;
		to = pop_lsb&#40;&b&#41;;
		addMove<FLAG_QUEEN_PROM>&#40;to - Delta, to&#41;;
		addMove<FLAG_KNIGHT_PROM>&#40;to - Delta, to&#41;;
	&#125;
&#125;

template < PieceType pt, Color GenFor >
	FORCE_INLINE void MoveList&#58;&#58;genMoves&#40;const Position & pos,
										 const Bitboard Target&#41;
&#123;
	Square from;
	Bitboard pieceBB, b;
	pieceBB = pos.PieceBB&#91;&#40;GenFor == WHITE&#41; ? pt &#58; &#40;pt + &#40;BPAWN - WPAWN&#41;)&#93;;
	while &#40;pieceBB&#41;
	&#123;
		from = pop_lsb&#40;&pieceBB&#41;;
		b = pos.attacks_by < pt > &#40;from&#41; & Target;
		while &#40;b&#41;
			addMove&#40;from, pop_lsb&#40;&b&#41;);
	&#125;
&#125;

template < Color GenFor >
	FORCE_INLINE void MoveList&#58;&#58;genKingMoves&#40;const Position & pos,
											 const Bitboard Target&#41;
&#123;
	const Square kingSquare =
		lsb&#40;pos.PieceBB&#91;&#40;GenFor == WHITE&#41; ? WKING &#58; BKING&#93;);
		
	const CastlingRight cr = pos.castleStatus < GenFor > ();
	
	const Bitboard KingSideMask = &#40;GenFor == WHITE&#41; ? 0x60 &#58; &#40;0x60ULL << 56&#41;;
	const Bitboard QueenSideMask = &#40;GenFor == WHITE&#41; ? 0xE &#58; &#40;0xEULL << 56&#41;;
	
	Bitboard b = pos.attacks_by < KING > &#40;kingSquare&#41; & Target;
	while &#40;b&#41;
		addMove&#40;kingSquare, pop_lsb&#40;&b&#41;);

	if (!&#40;pos.PieceBB&#91;ALL_PIECES&#93; & KingSideMask&#41;)
	&#123;
		if (&#40;cr == OO&#41; || &#40;cr == BOTH_SIDES&#41;)
		&#123;
			if (!&#40;pos.attacks_to < &#40;GenFor == WHITE&#41; ? BLACK &#58; WHITE >
				  (&#40;GenFor == WHITE&#41; ? G1 &#58; G8&#41;))
			&#123;
				addMove<FLAG_CASTLING>&#40;kingSquare, &#40;GenFor == WHITE&#41; ? G1 &#58; G8&#41;;
			&#125;
		&#125;
	&#125;
	if (!&#40;pos.PieceBB&#91;ALL_PIECES&#93; & QueenSideMask&#41;)
	&#123;
		if (&#40;cr == OOO&#41; || &#40;cr == BOTH_SIDES&#41;)
		&#123;
			if (!&#40;pos.attacks_to < &#40;GenFor == WHITE&#41; ? BLACK &#58; WHITE >
				  (&#40;GenFor == WHITE&#41; ? C1 &#58; C8&#41;))
			&#123;
				addMove<FLAG_CASTLING>&#40;kingSquare, &#40;GenFor == WHITE&#41; ? C1 &#58; C8&#41;;
			&#125;
		&#125;
	&#125;
&#125;

FORCE_INLINE void MoveList&#58;&#58;genAllMoves&#40;const Position & pos&#41;
&#123;
	const Bitboard Target = ~pos.ColorBB&#91;pos.sideToMove&#93;;
	if &#40;pos.sideToMove == WHITE&#41;
	&#123;
		genPawnMoves < WHITE > &#40;pos, Target&#41;;
		genMoves < KNIGHT, WHITE > &#40;pos, Target&#41;;
		genMoves < BISHOP, WHITE > &#40;pos, Target&#41;;
		genMoves < ROOK, WHITE > &#40;pos, Target&#41;;
		genMoves < QUEEN, WHITE > &#40;pos, Target&#41;;
		genKingMoves < WHITE > &#40;pos, Target&#41;;
	&#125;
	else
	&#123;
		genPawnMoves < BLACK > &#40;pos, Target&#41;;
		genMoves < KNIGHT, BLACK > &#40;pos, Target&#41;;
		genMoves < BISHOP, BLACK > &#40;pos, Target&#41;;
		genMoves < ROOK, BLACK > &#40;pos, Target&#41;;
		genMoves < QUEEN, BLACK > &#40;pos, Target&#41;;
		genKingMoves < BLACK > &#40;pos, Target&#41;;
	&#125;
	endList&#40;);
&#125;

#endif
If you see speedups, do tell me. I've used Stockfish-like names, so this might look Stockfishy code. And here are perft results:

Code: Select all


Yaka 0.2.1 by Syed Fahad
Enter a fen String
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR b KQkq - 0 1
Enter depth.
5

 +---+---+---+---+---+---+---+---+
 | r | n | b | q | k | b | n | r |
 +---+---+---+---+---+---+---+---+
 | p | p | p | p | p | p | p | p |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 | P | P | P | P | P | P | P | P |
 +---+---+---+---+---+---+---+---+
 | R | N | B | Q | K | B | N | R |
 +---+---+---+---+---+---+---+---+
Side To Move&#58; Black
En-Passant Square&#58; &#40;none&#41;
#0&#58; a7a6 encoded as 0xa30
#1&#58; b7b6 encoded as 0xa71
#2&#58; c7c6 encoded as 0xab2
#3&#58; d7d6 encoded as 0xaf3
#4&#58; e7e6 encoded as 0xb34
#5&#58; f7f6 encoded as 0xb75
#6&#58; g7g6 encoded as 0xbb6
#7&#58; h7h6 encoded as 0xbf7
#8&#58; a7a5 encoded as 0x830
#9&#58; b7b5 encoded as 0x871
#10&#58; c7c5 encoded as 0x8b2
#11&#58; d7d5 encoded as 0x8f3
#12&#58; e7e5 encoded as 0x934
#13&#58; f7f5 encoded as 0x975
#14&#58; g7g5 encoded as 0x9b6
#15&#58; h7h5 encoded as 0x9f7
#16&#58; b8a6 encoded as 0xa39
#17&#58; b8c6 encoded as 0xab9
#18&#58; g8f6 encoded as 0xb7e
#19&#58; g8h6 encoded as 0xbfe
Took 0.963855 secs.
perft 5 = 4896998
nodes sec&#58;5080637
The incorrect results are okay, because movegen generates pseudo-legal moves, even those which put the king in check (i.e suicidal moves).
It should be not more than much slower than SF on 64-bit systems. No optimization for 32-bits is done, so it's almost 1.3 times slower than SF. Besides, it doesn't use PieceLists and all that.

One more thing, I've turned 14!

Did I mention you have a compile time option to use HQ?

User avatar
hgm
Posts: 23455
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Just another movegen

Post by hgm » Fri Nov 14, 2014 8:34 am

Just a thought:

wouldn't it be useful to have perft counts for 'King-capture Chess', which is just like FIDE except that there is no checkmate (or stalemate), and the game ends by King capture? Most engines use pseudo-legal move generation, so it would be far easier to establish correctness of their move generation by comparing to perft numbers for this variant.

The numbers could always be supplemented by the number of king captures at each level, as well as the number of positions where King capture was possible ('illegal positions'). By subtracting the perft(N).KingCaptures and perft(N+1).illegals from perft(N).pseudoLegal one should recover the normal (=FIDE) perft(N).

kinderchocolate
Posts: 408
Joined: Mon Nov 01, 2010 5:55 am
Full name: Ted Wong
Contact:

Re: Just another movegen

Post by kinderchocolate » Fri Nov 14, 2014 11:50 am

Happy Birthday.

You've surely read Stockfish well, and now your code closely resemble Stockfish's style! Even the function names and variable names are identical to Stockfish.

Don't worry too much about the speed of generation, you'll find more interesting area to optimization in the search. Do a legal move generation, compare with perft and start coding alpha-beta!



vittyvirus wrote:This is third rewrite of my move generator (yes. third). People here have witnessed me fighting against my extremely poor code, and I know much more.

When I started chess programming, I started with a dramatic goal to create a 3000+ engine. I thought it was easy.

Now, I know what actually is the base of a super strong engine. Its clean, concise, and well written code. Not that I learned that after 30+ years of experience, but it sounds quite obvious to me.

When I think of clean code, two engines come to my mind. Stockfish and iCE chess. Both are clean coded, and take advantages of STL.

Before, I took pride in having lines of code. move.cpp + movegen.cpp = 2000+ lines of code sounded elite. And now, the LESSer lines of code sound more elite. Without comprising on performance, you can use templates to generate sliding and non-sliding moves within one function.

And now, as you see, I've a movegen that's only 263 lines of code (due to classical formatting used by C4Driod).

I started with Silican Chess, and then rewrote it to Chress (not Chesser), and after losing all Chress codedue to display problem with my laptop, started from scratch with Yaka, using g++ with C4Driod on my Andriod

Here's the code:

Code: Select all

// movegen.h &#58; Yaka's Move Generator
#ifndef INC_MOVEGEN_H_
#define INC_MOVEGEN_H_
#include "includes.h"
#include "move.h"
#include "position.h"

class MoveList
&#123;
	Move mList&#91;MaxMoves&#93;;
	uint index;

  public&#58;

	  MoveList&#40;)
	&#123;
		index = 0;
	&#125;

	MoveList&#40;const Position & pos&#41;
	&#123;
		index = 0;
		genAllMoves&#40;pos&#41;;
	&#125;
	inline void addMove&#40;const Square from, const Square to&#41;
	&#123;
		mList&#91;index++&#93;.move = from | &#40;to << 6&#41;;
	&#125;
	
	template <Flag flag>
	inline void addMove&#40;const Square from, const Square to&#41; &#123;
		mList&#91;index++&#93;.move = &#40;from | &#40;to << 6&#41; | flag&#41;;
	&#125;

	inline void endList&#40;)
	&#123;
		mList&#91;index&#93;.move = 0;
	&#125;

	inline int legalMoveCount&#40;)
	&#123;
		return index;
	&#125;

	void dispList&#40;)
	&#123;

		for &#40;int i = 0; &#40;mList&#91;i&#93;.move != 0&#41; && i < MaxMoves; ++i&#41;
		&#123;

			std&#58;&#58;cout << "#" << i << "&#58; ";
			std&#58;&#58;cout << std&#58;&#58;hex;
			mList&#91;i&#93;.dispMove&#40;);
			std&#58;&#58;cout << " encoded as 0x" << mList&#91;i&#93;.move;
			std&#58;&#58;cout << std&#58;&#58;endl;
			std&#58;&#58;cout << std&#58;&#58;dec;
		&#125;
	&#125;

	void dispListInSAN&#40;const Position & pos&#41;
	&#123;
		for &#40;int i = 0; &#40;mList&#91;i&#93;.move != 0&#41; && i < MaxMoves; ++i&#41;
		&#123;
			std&#58;&#58;cout << "#" << i << " &#58; ";
			// mList&#91;i&#93;.dispSAN&#40;pos&#41;;
			std&#58;&#58;cout << " Encoded as " << mList&#91;i&#93;.move;
			std&#58;&#58;cout << std&#58;&#58;endl;
		&#125;
	&#125;

	inline move_t getMove&#40;int index&#41;
	&#123;
		return mList&#91;index&#93;.move;
	&#125;

	inline Move & operator&#91;&#93; &#40;const int index&#41;
	&#123;
		return mList&#91;index&#93;;
	&#125;

	FORCE_INLINE void genAllMoves&#40;const Position & pos&#41;;

	template < Square Delta >
		FORCE_INLINE void genPromotions&#40;const Bitboard promPawns,
										const Bitboard target&#41;;
	template < PieceType pt, Color GenFor >
		FORCE_INLINE void genMoves&#40;const Position & pos,
								   const Bitboard Target&#41;;
	template < Color GenFor >
		FORCE_INLINE void genKingMoves&#40;const Position & pos,
									   const Bitboard Target&#41;;
	template < Color GenFor >
		FORCE_INLINE void genPawnMoves&#40;const Position & pos,
									   const Bitboard Target&#41;;
&#125;;

template < Color GenFor >
	FORCE_INLINE
	void MoveList&#58;&#58;genPawnMoves&#40;const Position & pos, const Bitboard Target&#41;
&#123;
	const Bitboard FreeSquares = ~pos.PieceBB&#91;ALL_PIECES&#93;;
	
	const Bitboard pawnsOnRank7 =
		pos.PieceBB&#91;&#40;GenFor == WHITE&#41; ? WPAWN &#58; BPAWN&#93;
		& (&#40;GenFor == WHITE&#41; ? Rank7Mask &#58; Rank2Mask&#41;;
	const Bitboard pawnsNotOnRank7 =
		pos.PieceBB&#91;&#40;GenFor == WHITE&#41; ? WPAWN &#58; BPAWN&#93;
		& (&#40;GenFor == WHITE&#41; ? ~Rank7Mask &#58; ~Rank2Mask&#41;;
		
	const Square Right = &#40;GenFor == WHITE&#41; ? DELTA_NE &#58; DELTA_SE;
	const Square Left = &#40;GenFor == WHITE&#41; ? DELTA_NW &#58; DELTA_SW;
	const Square Up = &#40;GenFor == WHITE&#41; ? DELTA_N &#58; DELTA_S;
	
	const Bitboard enemyPieces = &#40;GenFor == WHITE&#41; ?
		pos.ColorBB&#91;BLACK&#93; &#58; pos.ColorBB&#91;WHITE&#93;;
		
	const Bitboard Rank3 = &#40;GenFor == WHITE&#41; ? Rank3Mask &#58; Rank6Mask;

	Bitboard b1, b2;
	Square to;

		/*--- Generate Promotions ---*/
	genPromotions < Right > &#40;pawnsOnRank7, enemyPieces&#41;;
	genPromotions < Left > &#40;pawnsOnRank7, enemyPieces&#41;;
	genPromotions < Up > &#40;pawnsOnRank7, FreeSquares&#41;;

		/*--- Single and Double Pawn Pushes ---*/
	b1 = shift_bb < Up > &#40;pawnsNotOnRank7&#41; & FreeSquares;
	b2 = shift_bb < Up > &#40;b1 & Rank3&#41; & FreeSquares;

	while &#40;b1&#41;					// Single Pawn Pushes
	&#123;
		to = pop_lsb&#40;&b1&#41;;
		addMove&#40;to - Up, to&#41;;
	&#125;

	while &#40;b2&#41;					// Double Pawn Pushes
	&#123;
		to = pop_lsb&#40;&b2&#41;;
		addMove&#40;&#40;to - Up - Up&#41;, to&#41;;
	&#125;

		/*--- Standard and En-Passant Captures ---*/
	b1 = shift_bb < Right > &#40;pawnsNotOnRank7&#41; & enemyPieces;

	b2 = shift_bb < Left > &#40;pawnsNotOnRank7&#41; & enemyPieces;

	while &#40;b1&#41;
	&#123;
		to = pop_lsb&#40;&b1&#41;;
		addMove&#40;&#40;to - Right&#41;, to&#41;;
	&#125;

	while &#40;b2&#41;
	&#123;
		to = pop_lsb&#40;&b2&#41;;
		addMove&#40;&#40;to - Left&#41;, to&#41;;
	&#125;

	// En-Passant Captures
	if (&#40;pos.epSquare&#40;) != NO_SQ&#41;
		&& &#40;GenFor == WHITE ? &#40;pos.epSquare&#40;) > H5&#41; &#58; &#40;pos.epSquare&#40;) < A4&#41;))
	&#123;
		b1 = pawnsNotOnRank7 & AttacksFrom&#91;&#40;GenFor == WHITE&#41; ? BPAWN &#58;
										   WPAWN&#93;&#91;pos.epSquare&#40;)&#93;;

		while &#40;b1&#41;	addMove<FLAG_ENPASSANT>&#40;pop_lsb&#40;&b1&#41;, pos.epSquare&#40;));
	&#125;
&#125;


template < Square Delta >
	FORCE_INLINE void MoveList&#58;&#58;genPromotions&#40;const Bitboard promPawns,
											  const Bitboard target&#41;
&#123;
	Bitboard b;
	b = &#40;shift_bb < Delta > &#40;promPawns&#41;) & target;
	Square to;

	while &#40;b&#41;
	&#123;
		to = pop_lsb&#40;&b&#41;;
		addMove<FLAG_QUEEN_PROM>&#40;to - Delta, to&#41;;
		addMove<FLAG_KNIGHT_PROM>&#40;to - Delta, to&#41;;
	&#125;
&#125;

template < PieceType pt, Color GenFor >
	FORCE_INLINE void MoveList&#58;&#58;genMoves&#40;const Position & pos,
										 const Bitboard Target&#41;
&#123;
	Square from;
	Bitboard pieceBB, b;
	pieceBB = pos.PieceBB&#91;&#40;GenFor == WHITE&#41; ? pt &#58; &#40;pt + &#40;BPAWN - WPAWN&#41;)&#93;;
	while &#40;pieceBB&#41;
	&#123;
		from = pop_lsb&#40;&pieceBB&#41;;
		b = pos.attacks_by < pt > &#40;from&#41; & Target;
		while &#40;b&#41;
			addMove&#40;from, pop_lsb&#40;&b&#41;);
	&#125;
&#125;

template < Color GenFor >
	FORCE_INLINE void MoveList&#58;&#58;genKingMoves&#40;const Position & pos,
											 const Bitboard Target&#41;
&#123;
	const Square kingSquare =
		lsb&#40;pos.PieceBB&#91;&#40;GenFor == WHITE&#41; ? WKING &#58; BKING&#93;);
		
	const CastlingRight cr = pos.castleStatus < GenFor > ();
	
	const Bitboard KingSideMask = &#40;GenFor == WHITE&#41; ? 0x60 &#58; &#40;0x60ULL << 56&#41;;
	const Bitboard QueenSideMask = &#40;GenFor == WHITE&#41; ? 0xE &#58; &#40;0xEULL << 56&#41;;
	
	Bitboard b = pos.attacks_by < KING > &#40;kingSquare&#41; & Target;
	while &#40;b&#41;
		addMove&#40;kingSquare, pop_lsb&#40;&b&#41;);

	if (!&#40;pos.PieceBB&#91;ALL_PIECES&#93; & KingSideMask&#41;)
	&#123;
		if (&#40;cr == OO&#41; || &#40;cr == BOTH_SIDES&#41;)
		&#123;
			if (!&#40;pos.attacks_to < &#40;GenFor == WHITE&#41; ? BLACK &#58; WHITE >
				  (&#40;GenFor == WHITE&#41; ? G1 &#58; G8&#41;))
			&#123;
				addMove<FLAG_CASTLING>&#40;kingSquare, &#40;GenFor == WHITE&#41; ? G1 &#58; G8&#41;;
			&#125;
		&#125;
	&#125;
	if (!&#40;pos.PieceBB&#91;ALL_PIECES&#93; & QueenSideMask&#41;)
	&#123;
		if (&#40;cr == OOO&#41; || &#40;cr == BOTH_SIDES&#41;)
		&#123;
			if (!&#40;pos.attacks_to < &#40;GenFor == WHITE&#41; ? BLACK &#58; WHITE >
				  (&#40;GenFor == WHITE&#41; ? C1 &#58; C8&#41;))
			&#123;
				addMove<FLAG_CASTLING>&#40;kingSquare, &#40;GenFor == WHITE&#41; ? C1 &#58; C8&#41;;
			&#125;
		&#125;
	&#125;
&#125;

FORCE_INLINE void MoveList&#58;&#58;genAllMoves&#40;const Position & pos&#41;
&#123;
	const Bitboard Target = ~pos.ColorBB&#91;pos.sideToMove&#93;;
	if &#40;pos.sideToMove == WHITE&#41;
	&#123;
		genPawnMoves < WHITE > &#40;pos, Target&#41;;
		genMoves < KNIGHT, WHITE > &#40;pos, Target&#41;;
		genMoves < BISHOP, WHITE > &#40;pos, Target&#41;;
		genMoves < ROOK, WHITE > &#40;pos, Target&#41;;
		genMoves < QUEEN, WHITE > &#40;pos, Target&#41;;
		genKingMoves < WHITE > &#40;pos, Target&#41;;
	&#125;
	else
	&#123;
		genPawnMoves < BLACK > &#40;pos, Target&#41;;
		genMoves < KNIGHT, BLACK > &#40;pos, Target&#41;;
		genMoves < BISHOP, BLACK > &#40;pos, Target&#41;;
		genMoves < ROOK, BLACK > &#40;pos, Target&#41;;
		genMoves < QUEEN, BLACK > &#40;pos, Target&#41;;
		genKingMoves < BLACK > &#40;pos, Target&#41;;
	&#125;
	endList&#40;);
&#125;

#endif
If you see speedups, do tell me. I've used Stockfish-like names, so this might look Stockfishy code. And here are perft results:

Code: Select all


Yaka 0.2.1 by Syed Fahad
Enter a fen String
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR b KQkq - 0 1
Enter depth.
5

 +---+---+---+---+---+---+---+---+
 | r | n | b | q | k | b | n | r |
 +---+---+---+---+---+---+---+---+
 | p | p | p | p | p | p | p | p |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 | P | P | P | P | P | P | P | P |
 +---+---+---+---+---+---+---+---+
 | R | N | B | Q | K | B | N | R |
 +---+---+---+---+---+---+---+---+
Side To Move&#58; Black
En-Passant Square&#58; &#40;none&#41;
#0&#58; a7a6 encoded as 0xa30
#1&#58; b7b6 encoded as 0xa71
#2&#58; c7c6 encoded as 0xab2
#3&#58; d7d6 encoded as 0xaf3
#4&#58; e7e6 encoded as 0xb34
#5&#58; f7f6 encoded as 0xb75
#6&#58; g7g6 encoded as 0xbb6
#7&#58; h7h6 encoded as 0xbf7
#8&#58; a7a5 encoded as 0x830
#9&#58; b7b5 encoded as 0x871
#10&#58; c7c5 encoded as 0x8b2
#11&#58; d7d5 encoded as 0x8f3
#12&#58; e7e5 encoded as 0x934
#13&#58; f7f5 encoded as 0x975
#14&#58; g7g5 encoded as 0x9b6
#15&#58; h7h5 encoded as 0x9f7
#16&#58; b8a6 encoded as 0xa39
#17&#58; b8c6 encoded as 0xab9
#18&#58; g8f6 encoded as 0xb7e
#19&#58; g8h6 encoded as 0xbfe
Took 0.963855 secs.
perft 5 = 4896998
nodes sec&#58;5080637
The incorrect results are okay, because movegen generates pseudo-legal moves, even those which put the king in check (i.e suicidal moves).
It should be not more than much slower than SF on 64-bit systems. No optimization for 32-bits is done, so it's almost 1.3 times slower than SF. Besides, it doesn't use PieceLists and all that.

One more thing, I've turned 14!

Did I mention you have a compile time option to use HQ?

User avatar
vittyvirus
Posts: 645
Joined: Wed Jun 18, 2014 12:30 pm
Full name: Fahad Syed

Re: Just another movegen

Post by vittyvirus » Sat Nov 15, 2014 7:30 am

@hgm
Well, I too think there's a need for it. Many engines like Yaka and winglet don't still use generate_legal(). These need a special isOtherKingAttacked() in perft. I have to spend much time counting each move suggested by SF and comparing the count with Yaka. Nad if the counts were different, I needed to manually verify which move is different. This was trouble, especially because it's difficult to convert e4e5 to SAN etc.

@Ted
Yaka is based on SF's types.h, but is still an original engine :-)
This is because typing everything manually is pain on a smartphone.

Also, I've spend hours to figure out the best way to do something (e.g. generating pawn move masks all at once) and then saw how Stockfish did it better. I was so impressed, that I thought SF code is optimal, and couldn't believe that it's yet being developed.

I also couldn't think of better names. But I occasionally used Pascl-style names (e.g colorOf(), typeOf() etc.)

It's also true that I have made a fairly good study of Stockfish code.

User avatar
vittyvirus
Posts: 645
Joined: Wed Jun 18, 2014 12:30 pm
Full name: Fahad Syed

Re: Just another movegen

Post by vittyvirus » Sat Nov 15, 2014 7:33 am

Just for comparison, Yaka would probably require ~1.3 secs to do perft 6 on a normal 64-bit PC.

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Just another movegen

Post by Evert » Sat Nov 15, 2014 8:49 am

vittyvirus wrote: Also, I've spend hours to figure out the best way to do something (e.g. generating pawn move masks all at once) and then saw how Stockfish did it better. I was so impressed, that I thought SF code is optimal, and couldn't believe that it's yet being developed.
I have no idea how Stockfish does it, but the most efficient/elegant way to do it is probably to enumerate bitboards as a1,a2…h7,h8 (as opposed to a1,b1,…g8,h8) and bulk-shift the pawn occupancy bitboard. Doing the enumeration the other way is good for capture generation because off-board attacks of edge pawns are automatically taken care off. A recent engine that does it this way is Senpai, but I'm sure there are more. Back in the day I used a union of a 64-bit integer and 8 unsigned chars to do essentially the same thing (shifting the chars when generating captures), but that has the disadvantage that the encoding is endianesse dependent.
This trick is old, by the way. I think Chess 4 or so used it too.

User avatar
vittyvirus
Posts: 645
Joined: Wed Jun 18, 2014 12:30 pm
Full name: Fahad Syed

Re: Just another movegen

Post by vittyvirus » Sat Nov 15, 2014 11:21 am

Evert wrote:
vittyvirus wrote: Also, I've spend hours to figure out the best way to do something (e.g. generating pawn move masks all at once) and then saw how Stockfish did it better. I was so impressed, that I thought SF code is optimal, and couldn't believe that it's yet being developed.
I have no idea how Stockfish does it, but the most efficient/elegant way to do it is probably to enumerate bitboards as a1,a2…h7,h8 (as opposed to a1,b1,…g8,h8) and bulk-shift the pawn occupancy bitboard. Doing the enumeration the other way is good for capture generation because off-board attacks of edge pawns are automatically taken care off. A recent engine that does it this way is Senpai, but I'm sure there are more. Back in the day I used a union of a 64-bit integer and 8 unsigned chars to do essentially the same thing (shifting the chars when generating captures), but that has the disadvantage that the encoding is endianesse dependent.
This trick is old, by the way. I think Chess 4 or so used it too.
Well, Yaka shifts the whole pawn BB at once in a specified direction.

Code: Select all

	b1 = shift_bb < Up > &#40;pawnsNotOnRank7&#41; & FreeSquares;
	b2 = shift_bb < Up > &#40;b1 & Rank3&#41; & FreeSquares;

	while &#40;b1&#41;					// Single Pawn Pushes
	&#123;
		to = pop_lsb&#40;&b1&#41;;
		addMove&#40;to - Up, to&#41;;
	&#125;

	while &#40;b2&#41;					// Double Pawn Pushes
	&#123;
		to = pop_lsb&#40;&b2&#41;;
		addMove&#40;&#40;to - Up - Up&#41;, to&#41;;
	&#125;

		/*--- Standard and En-Passant Captures ---*/
	b1 = shift_bb < Right > &#40;pawnsNotOnRank7&#41; & enemyPieces;

	b2 = shift_bb < Left > &#40;pawnsNotOnRank7&#41; & enemyPieces;

	while &#40;b1&#41;
	&#123;
		to = pop_lsb&#40;&b1&#41;;
		addMove&#40;&#40;to - Right&#41;, to&#41;;
	&#125;

	while &#40;b2&#41;
	&#123;
		to = pop_lsb&#40;&b2&#41;;
		addMove&#40;&#40;to - Left&#41;, to&#41;;
	&#125;
We can shift the Pawn BB by 8 if White and -8 if Black. and then '&' it with free squares for single pawn pushes. And then add moves using from = (to - Up). Similarly for captures, that need Right and Left (i.e. 7 and 9 for white) shifts and '&' with enemy pieces...

fogleman
Posts: 2
Joined: Mon Oct 27, 2014 6:55 pm

Re: Just another movegen

Post by fogleman » Mon Nov 17, 2014 10:06 pm

Here is the move generator for my engine, in case you're interested:

https://github.com/fogleman/MisterQueen ... /src/gen.c

User avatar
stegemma
Posts: 859
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Full name: Stefano Gemma
Contact:

Re: Just another movegen

Post by stegemma » Tue Nov 18, 2014 8:05 am

Your code seems very clean to me, you do an interesting use of templates. I've done something similar using macros in assembly... but that was almost unreadable ;)

Just to have a reference, in Satana i get perft 6 in:

without test for check at last leave: <4 seconds
with test for check at last leave: >12 seconds

So the difference, in my engine, is 3x without checking for king in check at the last ply.

I'm still working but i plan to stay under 2 seconds, for perft 6.

A thing that i've noticed is that you should avoid any if (ora ?: construct) anytime that you can, to speed up things. sometime the ?: construct would be resolved by the compiler at compile time but maybe you should take a look at the generated code, to be sure. For sample, the code "(pos.epSquare() > H5)" maybe could be sobstituted by an & with a mask, leaving to next "while(b1)" the job to exclude en-passant captures. This would avoid the "if((pos.epSquare....".

In Satana, the move generation is branch-less. For sample, i generate pawn moves this way:



Code: Select all

    boTo = &#40;boFrom >> 8&#41;;   boUpdates = boTo;  boTo &= pBoard->boEmpties;
    // eventuale spinta di 2 &#40;senza if&#41;
    uint64_t boToUp2 = &#40;boTo & BOARD_6_ROW&#41;>>8;  boUpdates |= boToUp2;   boTo |= &#40;boTo2 = &#40;boToUp2 & pBoard->boEmpties&#41;);

    boChecks = ((&#40;boFrom & ~BOARD_H_COL&#41;>>9&#41; | (&#40;boFrom & ~BOARD_A_COL&#41;>>7&#41;);
    uint64_t boEnPassant = &#40;pBoard->pEngine->pNode&#41;->objMoveDone.boOptionSquares
                         | &#40;pBoard->pEngine->pNode-1&#41;->objMoveDone.boOptionSquares;
    boEnPassant &= pBoard->boEmpties;
    boCaptures = boChecks & (*pEnemies|&#40;BOARD_3_ROW & boEnPassant&#41;); 
    boUpdates |= boChecks;
Only promotions needs a separate code but i get push, en-passant and other captures without any "if" or "?:". My engine generates pawn moves one pawn at a time (so it is not very efficient) and my code is not clear as your, of course.

PS: the code is for black pawns, the White ones have a similar code

tpetzke
Posts: 686
Joined: Thu Mar 03, 2011 3:57 pm
Location: Germany
Contact:

Re: Just another movegen

Post by tpetzke » Tue Nov 18, 2014 8:23 am

Hi Stefano,

I think in the move generator readability of code should come first. If this requires some "if" that's not so bad.

In iCE I even have the luxury of a fully legal move generator, because I find it messy to generate illegal moves. Probably I could speed up my move generator by a few % but iCE spends very little time in move generation overall so a small speedup here won't make a difference.

As reference iCE takes 1.1 secs for perft 6 on my laptop even with some "if" statements. (legal move generators don't need to execute the moves on the last ply but just count them so they are fast)

Thomas
Thomas...

=======
http://macechess.blogspot.com - iCE Chess Engine

Post Reply