Insanely buggy move generator, please help

[vittyvirus]

This is my move generator code for black. Its insanely buggy, please help me find those bugs. I've fixed parts of white move generator code, but Black's movegen code is still buggy. So just not to confuse you guys, I've only posted White movegen code.

Code: Select all

#include "movegen.h"
#include "bitboard.h"
#include "func.h"
#include "move.h"
#include "names.h"
#include "const.h"

#define WHITE_OO_CASTLE 6
#define WHITE_OOO_CASTLE 112

inline BitMap whiteSinglePush(const UINT &sq, const BitMap &empty) {
	return ((1 << sq) << 8) & empty;
}

inline BitMap whiteDoublePush(const UINT &sq, const BitMap &empty) {
	BitMap singlePush = whiteSinglePush(sq, empty);
	return (singlePush << 8) & empty & 0x00000000FF000000; // 0x00000000FF000000 = rank 4.
}

inline BitMap blackSinglePush(const BitMap &bpawns, const BitMap &empty) {
	return (bpawns >> 8) & empty;
}

inline BitMap blackDoublePush(const BitMap &bpawns, const BitMap &empty) {
	singlePush = blackSinglePush(bpawns, empty);
	return (singlePush << 8) & empty & 0x000000FF00000000; // 0x000000FF00000000 = rank 5.
}

inline BitMap genBishopMoves(const UINT &square, const U64 &board, const U64 &target) {
	BitMap bishopMoves = 0;
	bishopMoves = arrDiagA8H1Moves[(square)][((board & arrDiagA8H1Mask[(square)]) * arrDiagA8H1Magics[(square)]) >> 57];
	bishopMoves |= arrDiagA1H8Moves[(square)][((board & arrDiagA1H8Mask[(square)]) * arrDiagA1H8Magics[(square)]) >> 57];
	bishopMoves &= target;
	return bishopMoves;
}

inline BitMap genRookMoves(const UINT &square, const U64 &board, const U64 &target) {
	BitMap rookMoves = 0;
	rookMoves |= (arrRankMoves[(square)][((board & arrRankMask[(square)]) >> arrRankShifts[(square)])]);
	rookMoves |= (arrFileMoves[(square)][((board & arrFileMask[(square)]) * arrFileMagics[(square)]) >> 57]);
	rookMoves &= target;
	return rookMoves;
}

inline BitMap genQueenMoves(const UINT &square, const U64 &board, const U64 &target) {
	return (genRookMoves(square, board, target) | genBishopMoves(square, board, target));
}


void Bitboard::GenWhiteMoves() {
	register int index, from, to;
	register CMove tempMove; // Stores the temporary generated move, then copied into Moves
	register BitMap targets, piece;

	/********************************************
	*											*
	*			White Pawn Moves				*
	*											*
	*********************************************/

	BitMap empty = (~Bitboard::occupiedSquares);

	tempMove.clearMove();
	targets = index = from = to = 0;

	tempMove.setPiece(WHITEPAWN);
	piece = Bitboard::whitePawns;

	while(piece) {

		from = lsb(piece);
		tempMove.setFrom(from);

		std::cout << "White Single Push, sq=" << from << " empty=" << empty << "returns " << whiteSinglePush(from, empty) << std::endl;
		targets = whiteSinglePush(from, empty);
		std::cout << "Targets now:" << targets << std::endl;
		std::cout << "White Doble Push, sq=" << from << " empty=" << empty << "returns " << whiteDoublePush(from, empty) << std::endl;
		targets |= whiteDoublePush(from, empty);
		std::cout << "Targets now:" << targets << std::endl;
		targets |= ((arrPawnAttacks[0][from]) & (Bitboard::blackPieces));

		if(Bitboard::epSquare) {
			if((from == (Bitboard::epSquare - 1)) || (from == (Bitboard::epSquare + 1))) {
				tempMove.setTo(Bitboard::epSquare - 8);
				tempMove.setFlags(WHITEPAWN);
				tempMove.setCapture(WHITEPAWN);
				Moves[index++].m_move = tempMove.m_move;
			}
		}

		while(targets) {
			to = lsb(targets);
			tempMove.setTo(to);

			if(to < 56) {
				Moves[index++].m_move = tempMove.m_move;
			} else {									// I've lately started to use K&R Style fromatting
				tempMove.setFlags(WHITEQUEEN);
				Moves[index++].m_move = tempMove.m_move;
				tempMove.setFlags(WHITEROOK);
				Moves[index++].m_move = tempMove.m_move;
				tempMove.setFlags(WHITEBISHOP);
				Moves[index++].m_move = tempMove.m_move;
				tempMove.setFlags(WHITEKNIGHT);
				Moves[index++].m_move = tempMove.m_move;
			}

			// Remove the least significant bit:
			targets &= (targets - 1);
		}
		piece &= (piece - 1);
	}

	/********************************************
	*											*
	*			White Knight Moves				*
	*											*
	*********************************************/

	tempMove.clearMove();
	tempMove.setPiece(WHITEKNIGHT);
	piece = Bitboard::whiteKnights;
	targets = 0;

	while(piece) {
		from = lsb(piece);
		tempMove.setFrom(from);

		targets |= (arrKnightAttacks[from] & (~Bitboard::whitePieces));

		while(targets) {
			to = lsb(targets);
			tempMove.setTo(to);
			tempMove.setCapture(Bitboard::square[to]);

			Moves[index++].m_move = tempMove.m_move;

			targets &= (targets - 1);
		}
		piece &= (piece - 1);
	}

	/********************************************
	*											*
	*			White King Moves				*
	*											*
	*********************************************/

	tempMove.clearMove();
	tempMove.setPiece(WHITEKING);
	piece = Bitboard::whiteKing;
	targets = 0;

	while(piece) {
		from = lsb(piece);
		tempMove.setFrom(from);

		targets |= (arrKingAttacks[from] & (~Bitboard::whitePieces));

		while(targets) {
			to = lsb(targets);
			tempMove.setTo(to);
			tempMove.setCapture(Bitboard::square[to]);

			Moves[index++].m_move = tempMove.m_move;

			targets &= (targets - 1);
		}
		piece &= (piece - 1);
	}
	/********************************************
	*											*
	*			White Bishop Moves				*
	*											*
	*********************************************/

	tempMove.clearMove();
	tempMove.setPiece(WHITEBISHOP);
	piece = Bitboard::whiteBishops;
	targets = 0;

	while(piece) {
		from = lsb(piece);
		tempMove.setFrom(from);


		targets = genBishopMoves(from, Bitboard::occupiedSquares, (~Bitboard::whitePieces));

		while(targets) {
			to = lsb(targets);
			tempMove.setTo(to);
			tempMove.setCapture(Bitboard::square[to]);

			Moves[index++].m_move = tempMove.m_move;

			targets &= (targets - 1);
		}
		piece &= (piece - 1);
	}

	/********************************************
	*											*
	*			White Rook Moves				*
	*											*
	*********************************************/

	tempMove.clearMove();
	tempMove.setPiece(WHITEROOK);
	piece = Bitboard::whiteRooks;
	targets = 0;
	while(piece) {
		from = lsb(piece);
		tempMove.setFrom(from);

		targets = genRookMoves(from, Bitboard::occupiedSquares, (~Bitboard::whitePieces));

		while(targets) {
			to = lsb(targets);
			tempMove.setTo(to);
			tempMove.setCapture(Bitboard::square[to]);

			Moves[index++].m_move = tempMove.m_move;

			targets &= (targets - 1);
		}
		piece &= (piece - 1);
	}

	/********************************************
	*											*
	*			White Queen Moves				*
	*											*
	*********************************************/

	tempMove.clearMove();
	tempMove.setPiece(WHITEQUEEN);
	piece = Bitboard::whiteQueens;
	targets = 0;

	while(piece) {
		from = lsb(piece);
		tempMove.setFrom(from);

		targets = genQueenMoves(from, Bitboard::occupiedSquares, (~Bitboard::whitePieces));

		while(targets) {
			to = lsb(targets);
			tempMove.setTo(to);
			tempMove.setCapture(Bitboard::square[to]);

			Moves[index++].m_move = tempMove.m_move;

			targets &= (targets - 1);
		}
		piece &= (piece - 1);
	}

	/********************************************
	*											*
	*			White Castling Moves			*
	*											*
	*********************************************/

	// White O-O Castling Moves:
	if((Bitboard::WhiteCastleOO) &&
		(!((Bitboard::occupiedSquares) & WHITE_OO_CASTLE)) &&
		(!(isBlackAttacking(2)))) 
	{
		Moves[index].setFrom(4);
		Moves[index].setTo(6);
		Moves[index].setPiece(WHITEKING);
		Moves[index++].setFlags(WHITEKING);
	}

	// White O-O-O Castling Moves:
	if((Bitboard::WhiteCastleOOO) &&
		(!((Bitboard::occupiedSquares) & WHITE_OOO_CASTLE)) &&
		(!(isBlackAttacking(32))))
	{
		Moves[index].setFrom(4);
		Moves[index].setTo(2);
		Moves[index].setPiece(WHITEKING);
		Moves[index++].setFlags(WHITEKING);
	}
	Bitboard::noOfMoves = index;
}

[/code]

[kinderchocolate]

Some remarks and hints:

1. When you code a bitboard generator like this, verify and verify about knights before moving to another piece type. Knight is the easiest because it isn't sliding. Are you sure your knight generation is correct? If not, focus only and only on it.

2. You don't need code for both colors. You should define a function for generation for each piece type. The function takes a color.

3. What's Bitboard::whiteKnights??? Is this a static bitboard? If this is static, how can you play a game?

Instead of debugging it for you. I'll advise you to do the following:

A. Write a function that generates a bitboard for a knight attacks for each square.

B. Write and test a function that returns a list or a bitboard of all knights from any FEN position.

Once you've done A and B. You can easily generate pseudo-knight moves by looping through each knight square. Please proceed only if you're confident your knight generation is correct.

[vittyvirus]

Some remarks and hints:

1. When you code a bitboard generator like this, verify and verify about knights before moving to another piece type. Knight is the easiest because it isn't sliding. Are you sure your knight generation is correct? If not, focus only and only on it.

2. You don't need code for both colors. You should define a function for generation for each piece type. The function takes a color.

3. What's Bitboard::whiteKnights??? Is this a static bitboard? If this is static, how can you play a game?

Instead of debugging it for you. I'll advise you to do the following:

A. Write a function that generates a bitboard for a knight attacks for each square.

B. Write and test a function that returns a list or a bitboard of all knights from any FEN position.

Once you've done A and B. You can easily generate pseudo-knight moves by looping through each knight square. Please proceed only if you're confident your knight generation is correct.

Hi!

1. The Knight Move generator is the most correct one in my program, weird enough. The more buggy parts are pawns.

2. Yes, I have. I just posted this to not confuse you guys, as I mentioned.

3. Bitboard::whiteKnights stores white knights on the board, and so does Bitboard::whitePawns, Bitboard::whiteQueens etc.

A. I use this function to generate arrKnightAttacks:

Code: Select all

inline BitMap calcKnightAttacks(const UINT &sq) {
	BitMap b = 1ULL << sq, KnightAttacks(0);
	KnightAttacks = noNoEa(b) | noEaEa(b) | soEaEa(b) | soSoEa(b) | noNoWe(b) | noWeWe(b) | soWeWe(b) | soSoWe(b);
	return KnightAttacks;
}

B. Done that too, already. I've a fen parser.

Cheers!
Syed Fahad.

[kbhearn]

The earlier comment with regard to Bitboard::whiteKnights was motivated by it being strange syntax (and i'm not sure if it's correct or not to be honest). Usually you would only use class::member to access a variable if a) you're not operating in the namespace already anyways (which you are because this is a member function) and b) member is declared static. since the function you're in is part of Bitboard:: already you can access the whiteKnights variable without any qualifier. And if it's not a static member (which i assume it shouldn't be in the event you ever want to have more than one copy of the class), to access it outside of the class you'd need to use 'variable.whiteKnights'.

Pawns and knights should be straightforward to debug. The cases you need to watch out for are where the square differences cause the board to wrap (what happens when a pawn on h3 tries to capture to the right). A note on your pawn generation: rather than looping through all pawns and individually testing for unoccupied/enemy occupied squares the normal way to generate pawn moves is in batch for each case (capture left, capture right, single push, double push), and then loop through the result of pawns that can execute the move in question.

As for your sliders, i'd recommend NOT using magics for your first move generator due to reliance on large data tables that are a pain to debug manually. One simple way to generate a slider attack is to use either bitscan forward or bitscan reverse on (ray & (occupied | perimeterofboard)) depending on direction to find your first blocker in each direction and just return the path between each pair of blockers, much simpler to debug. You can later switch to magics if you want and use the simpler move generator to do automatic testing of your mass of magic numbers.

[vittyvirus]

The earlier comment with regard to Bitboard::whiteKnights was motivated by it being strange syntax (and i'm not sure if it's correct or not to be honest). Usually you would only use class::member to access a variable if a) you're not operating in the namespace already anyways (which you are because this is a member function) and b) member is declared static. since the function you're in is part of Bitboard:: already you can access the whiteKnights variable without any qualifier. And if it's not a static member (which i assume it shouldn't be in the event you ever want to have more than one copy of the class), to access it outside of the class you'd need to use 'variable.whiteKnights'.

Pawns and knights should be straightforward to debug. The cases you need to watch out for are where the square differences cause the board to wrap (what happens when a pawn on h3 tries to capture to the right). A note on your pawn generation: rather than looping through all pawns and individually testing for unoccupied/enemy occupied squares the normal way to generate pawn moves is in batch for each case (capture left, capture right, single push, double push), and then loop through the result of pawns that can execute the move in question.

As for your sliders, i'd recommend NOT using magics for your first move generator due to reliance on large data tables that are a pain to debug manually. One simple way to generate a slider attack is to use either bitscan forward or bitscan reverse on (ray & (occupied | perimeterofboard)) depending on direction to find your first blocker in each direction and just return the path between each pair of blockers, much simpler to debug. You can later switch to magics if you want and use the simpler move generator to do automatic testing of your mass of magic numbers.

I find magics simpler to understand. But I'd surely work on your advice.

[zullil]

This is my move generator code for black. Its insanely buggy, please help me find those bugs.

One day I might use bitboards, and maybe even understand "magic" bitboards. For now, I use an array of 130 (thought of as 13 x 10) ints for my board representation. (It's a 12 x 10 scheme, with an extra "rank" that holds state information and king locations.) After two weeks of writing and debugging (twice finding = where I intended to have ==), I seem to have a working (legal) move generator:

Code: Select all

louis@LZsT5610:~/Documents/Chess/Kirby$ ./perft_new 
FEN string = rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq -
Depth = 6
Leaf nodes = 119060324
Time taken = 2353 ms

louis@LZsT5610:~/Documents/Chess/Kirby$ ./perft_new 
FEN string = r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -
Depth = 5
Leaf nodes = 193690690
Time taken = 2199 ms

Good luck getting yours working. I'm sure it will be faster than mine once you've killed all the bugs.

[vittyvirus]

This is my move generator code for black. Its insanely buggy, please help me find those bugs.

One day I might use bitboards, and maybe even understand "magic" bitboards. For now, I use an array of 130 (thought of as 13 x 10) ints for my board representation. (It's a 12 x 10 scheme, with an extra "rank" that holds state information and king locations.) After two weeks of writing and debugging (twice finding = where I intended to have ==), I seem to have a working (legal) move generator:

Code: Select all

louis@LZsT5610:~/Documents/Chess/Kirby$ ./perft_new 
FEN string = rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq -
Depth = 6
Leaf nodes = 119060324
Time taken = 2353 ms

louis@LZsT5610:~/Documents/Chess/Kirby$ ./perft_new 
FEN string = r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -
Depth = 5
Leaf nodes = 193690690
Time taken = 2199 ms

Good luck getting yours working. I'm sure it will be faster than mine once you've killed all the bugs.

If your move generator does perft 6 in under 3 seconds, it is fairly difficult to beat.

[zullil]

This is my move generator code for black. Its insanely buggy, please help me find those bugs.

One day I might use bitboards, and maybe even understand "magic" bitboards. For now, I use an array of 130 (thought of as 13 x 10) ints for my board representation. (It's a 12 x 10 scheme, with an extra "rank" that holds state information and king locations.) After two weeks of writing and debugging (twice finding = where I intended to have ==), I seem to have a working (legal) move generator:

Code: Select all

louis@LZsT5610:~/Documents/Chess/Kirby$ ./perft_new 
FEN string = rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq -
Depth = 6
Leaf nodes = 119060324
Time taken = 2353 ms

louis@LZsT5610:~/Documents/Chess/Kirby$ ./perft_new 
FEN string = r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -
Depth = 5
Leaf nodes = 193690690
Time taken = 2199 ms

Good luck getting yours working. I'm sure it will be faster than mine once you've killed all the bugs.

If your move generator does perft 6 in under 3 seconds, it is fairly difficult to beat.

But not for a world-class engine like the one you want to create!

Code: Select all

Stockfish 270714 64 SSE4.2 by Tord Romstad, Marco Costalba and Joona Kiiski
position startpos
perft 6

Position: 1/1

Perft 6 leaf nodes: 119060324

===========================
Total time (ms) : 758
Nodes searched  : 119060324
Nodes/second    : 157071667

[vittyvirus]

This is my move generator code for black. Its insanely buggy, please help me find those bugs.

One day I might use bitboards, and maybe even understand "magic" bitboards. For now, I use an array of 130 (thought of as 13 x 10) ints for my board representation. (It's a 12 x 10 scheme, with an extra "rank" that holds state information and king locations.) After two weeks of writing and debugging (twice finding = where I intended to have ==), I seem to have a working (legal) move generator:

Code: Select all

louis@LZsT5610:~/Documents/Chess/Kirby$ ./perft_new 
FEN string = rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq -
Depth = 6
Leaf nodes = 119060324
Time taken = 2353 ms

louis@LZsT5610:~/Documents/Chess/Kirby$ ./perft_new 
FEN string = r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -
Depth = 5
Leaf nodes = 193690690
Time taken = 2199 ms

Good luck getting yours working. I'm sure it will be faster than mine once you've killed all the bugs.

If your move generator does perft 6 in under 3 seconds, it is fairly difficult to beat.

But not for a world-class engine like the one you want to create!

Code: Select all

Stockfish 270714 64 SSE4.2 by Tord Romstad, Marco Costalba and Joona Kiiski
position startpos
perft 6

Position: 1/1

Perft 6 leaf nodes: 119060324

===========================
Total time (ms) : 758
Nodes searched  : 119060324
Nodes/second    : 157071667

You have a faster system:

Code: Select all

Stockfish 5 64 SSE4.2 by Tord Romstad, Marco Costalba and Joona Kiiski
perft 6

Position: 1/1

Perft 6 leaf nodes: 119060324

===========================
Total time (ms) : 939
Nodes searched  : 119060324
Nodes/second    : 126794807

But but, here's what Cheng (another strong engine) has to say:

Code: Select all

]
perft 6
119060324 nodes
took 2537 ms

[zullil]

But but, here's what Cheng (another strong engine) has to say:

Code: Select all

perft 6
119060324 nodes
took 2537 ms

For reference, here's what I get on my 2.0 GHz Intel Core 2 Duo Late 2007 MacBook:

Code: Select all

ProcyonLeo: ~/Documents/Chess/Kirby] ./perft_new 
FEN string = rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq -
Depth = 6
Leaf nodes = 119060324
Time taken = 5425 ms