Problem with bitboard knight attack generator

[ZirconiumX]

@Sven - That is probably what I will go for.

@All - I am currently attempting to deflate the size of my move struct - would you suggest an extra bit in case the compiler decides to complain?

Matthew:out

[lucasart]

@All - I am currently attempting to deflate the size of my move struct - would you suggest an extra bit in case the compiler decides to complain?

Can you show us your move_t structure ? It's hard to answer otherwise

[ZirconiumX]

Code: Select all

typedef struct {
	int	From:7,
		Dest:7,
		Piece:4,
		Colour:2,
		CapturedPiece:4,
		CapturedColour:2,
		Flags:4;
} move;

^^ Has the extra bit - 29bits

Code: Select all

typedef struct {
	int	From:6,
		Dest:6,
		Piece:3,
		Colour:1,
		CapturedPiece:3,
		CapturedColour:1,
		Flags:3;
} move;

^^ doesn't - 22bits

Matthew:out

[lucasart]

Code: Select all

typedef struct {
	int	From:7,
		Dest:7,
		Piece:4,
		Colour:2,
		CapturedPiece:4,
		CapturedColour:2,
		Flags:4;
} move;

^^ Has the extra bit - 29bits

Code: Select all

typedef struct {
	int	From:6,
		Dest:6,
		Piece:3,
		Colour:1,
		CapturedPiece:3,
		CapturedColour:1,
		Flags:3;
} move;

^^ doesn't - 22bits

Matthew:out

I'd say that "Piece" and "Colour" are not necessary. I have a dynamically updated array in by Board struct (or class if you prefer) piece_on[64] and color_on[64].
Also, how do you plan to encode promotions, en passant captures, and castling moves?

I use the following, but I'm sure it can be done more efficiently:

Code: Select all

typedef struct {
	unsigned fsq:6, tsq:6;
	unsigned piece:3, capture:3, promotion:3;
	unsigned ep:1, check:2;
} move_t;

The check flag is used by the search (it has two bits to distinguish normal check and discovered checks for which the SEE should not be trusted)

[ZirconiumX]

in the Flags variable: 0x1 = Capture En Passant, 0x2 = Castling, 0x4 = Promotion (I guess you could have 0x8 for Check)

Matthew:out

[lucasart]

oh one *major* mistake in your code. use unsigned, not int ! problem is that 63 as an int on 6 bits is a negative number, and this might even be compiler dependant!

[ZirconiumX]

Oh, and you forgot to mention a in check function!

Matthew:out

[Sven]

Code: Select all

typedef struct {
	int	From:7,
		Dest:7,
		Piece:4,
		Colour:2,
		CapturedPiece:4,
		CapturedColour:2,
		Flags:4;
} move;

^^ Has the extra bit - 29bits

Code: Select all

typedef struct {
	int	From:6,
		Dest:6,
		Piece:3,
		Colour:1,
		CapturedPiece:3,
		CapturedColour:1,
		Flags:3;
} move;

^^ doesn't - 22bits

Matthew:out

I'd say that "Piece" and "Colour" are not necessary. I have a dynamically updated array in by Board struct (or class if you prefer) piece_on[64] and color_on[64].
Also, how do you plan to encode promotions, en passant captures, and castling moves?

I use the following, but I'm sure it can be done more efficiently:

Code: Select all

typedef struct {
	unsigned fsq:6, tsq:6;
	unsigned piece:3, capture:3, promotion:3;
	unsigned ep:1, check:2;
} move_t;

The check flag is used by the search (it has two bits to distinguish normal check and discovered checks for which the SEE should not be trusted)

@Matthew + Lucas:

Reducing the number of bits in the move data structure is an optimization which is not needed in the beginning. It is also possible to simply use a struct of unsigned 8 bit numbers (i.e., unsigned char) for each part of a move, not caring about the total size.

But if you like that kind of optimization: it is possible to use only 16 bits if you skip the "check" bit. You definitely need 2x6 bits for the "from" and "to" square numbers, leaving 4 bits for the rest. There you can have two bits to indicate something like a "move type", e.g. normal/promotion/castle/ep, and the contents of the other two bits is interpreted depending on the move type, e.g. the exact castle type (four possible values) if move type = "castle", or the promotion piece (four possible values) if move type = "promotion".

Fruit does something similar, I think it does not even distinguish the four possible castles although it could do so.

Sven

[Desperado]

Hi Matthew,

A: init rouinte
=========

Using symbolic constants, even only in an init-routine
seems important to me, it is not only better to read, but
also better to understand. This is a routine snippet i used
back in 2009, and as you can see there is not doubt about
the meaning of constants used, although they can be merged easily
it is also pretty easy to understand what the constants in the sense of the
algorithm are used for.

Code: Select all

for&#40;bb = onebit&#40;sq = a1&#41;; bb ; bb<<=1,sq++)
&#123;
 
 //knight moves
 tmp = (&#40;bb | bR8|bR7|bHF&#41;^&#40;bR8|bR7|bHF&#41;) << 17;
 tmp^= (&#40;bb | bR8|bR7|bAF&#41;^&#40;bR8|bR7|bAF&#41;) << 15;
 tmp^= (&#40;bb | bR1|bR2|bHF&#41;^&#40;bR1|bR2|bHF&#41;) >> 15;
 tmp^= (&#40;bb | bR1|bR2|bAF&#41;^&#40;bR1|bR2|bAF&#41;) >> 17;
 tmp^= (&#40;bb | bAF|bBF|bR8&#41;^&#40;bAF|bBF|bR8&#41;) <<  6;
 tmp^= (&#40;bb | bGF|bHF|bR8&#41;^&#40;bGF|bHF|bR8&#41;) << 10;
 tmp^= (&#40;bb | bAF|bBF|bR1&#41;^&#40;bAF|bBF|bR1&#41;) >> 10;
 tmp^= (&#40;bb | bGF|bHF|bR1&#41;^&#40;bGF|bHF|bR1&#41;) >>  6;
 
 ...

&#125;

B: Just another word on the move encoding
=============================

Like Sven already mentioned it may depend on the development stage of your engine.
In an early stage it is more important to have a "working" solution than an "optimized"
solution. Here are some points you might consider for your demands.

* only pack the move information if you are able to get the same (or faster) speed
when unpacking the move data. It is really possible to have a 16 bit data structure,
while unpacking it only requires one bitoperation. 32 bit packed information can trivially
used that way, 16 bit is a little bit harder.

* another clear advantage _can_ be for the transposition table usage. Depending
on your slot size, 16 bit are preferable of course instead of 32 bit. That
can make the difference if you can manage to use 16 Bytes slot-size instead of 32 (or 16+) Bytes.

* nearly the same argument can be used for the movestack.
Think of a struct like that, or an equivalent with 32 bit size...
struct movestack_t
{
ui16_t move[256];
...
};

Only time will tell you, and after rewritten your engine many times, you will recognize
this doesnt work, and that doesnt work... so you finally end up with something which
will fulfill all your needs.

C: Attackgetter
===========

magics:
----------

Well, i dont know your experiences with bitboards. Someday you will certainly decide for magic bitboards,
because they are simply the fastest and very handy and flexible _in usage_.

rotated:
-----------

rotated, definitely belong to the fastest approaches, but they require an "own" board representation, while
other approaches are more flexible at this point. Another drawback is, that some "tricks" cannot be done
with rotated which are offered by other attack getter approaches like magics. For my personal taste they arent very handy.

Kindergarten
----------------

That looks like a good starting point to me, if you dont want to reinvent for yourself some wheels.

Obstruction Difference
---------------------------

of course this is my favourite, and is certainly a good starting point too, like "Kindergarten".
Pretty simple to understand, transparent, and performance is inbetween "Rotated" and "Magics".

Re - Invention
------------------

Of course if you are not very familiar with bitboards, it makes absolutely sense to play around here
with own ideas. After a while you will know how "you" like to handle bitboards, and maybe at this point, it
seems to make sense to decide for an existing solution, which
you can understand then much more easier.

Good luck, and enjoy ...

Michael

[ZirconiumX]

I am in the process of adding a FEN parser.

Here is what I have so far:

Code: Select all

void board::FromFEN(char FENstring[])
{
	assert(FENstring[0] != 0);
	
	int strnum = 0;
	
	for &#40;int i = 0; i < 64; i++) &#123;
		switch &#40;FENstring&#91;i&#93;) &#123;
		case '/'&#58;
			break;
		case 8&#58;
			i += 7;
			break;
		case 7&#58;
			i += 6;
			break;
		case 6&#58;
			i += 5;
			break;
		case 5&#58;
			i += 4;
			break;
		case 4&#58;
			i += 3;
			break;
		case 3&#58;
			i += 2;
			break;
		case 2&#58;
			i++;
			break;
		case 1&#58;
			break;
		case 'k'&#58;
			Pieces&#91;11&#93; += 1;
			break;
		case 'K'&#58;
			Pieces&#91;5&#93; += 1;
			break;
		case 'q'&#58;
			Pieces&#91;10&#93; += 1;
			break;
		case 'Q'&#58;
			Pieces&#91;4&#93; += 1;
			break;
		case 'r'&#58;
			Pieces&#91;9&#93; += 1;
			break;
		case 'R'&#58;
			Pieces&#91;3&#93; += 1;
			break;
		case 'b'&#58;
			Pieces&#91;8&#93; += 1;
			break;
		case 'B'&#58;
			Pieces&#91;2&#93; += 1;
			break;
		case 'n'&#58;
			Pieces&#91;7&#93; += 1;
			break;
		case 'N'&#58;
			Pieces&#91;1&#93; += 1;
			break;
		case 'p'&#58;
			Pieces&#91;6&#93; += 1;
			break;
		case 'P'&#58;
			Pieces&#91;0&#93; += 1;
			break;
		default&#58;
			assert&#40;false&#41;;
		&#125;
		for &#40;int j = 0; j < 12 && Pieces&#91;j&#93; <<= 1; j++)
			;
		strnum = i;
	&#125;
	
	strnum += 2;
	
	switch &#40;FENstring&#91;strnum&#93;) &#123;
	case 'w'&#58;
		SideToMove = 0;
		break;
	case 'b'&#58;
		SideToMove = 1;
		break;
	default&#58;
		assert&#40;false&#41;;
	&#125;
	
	strnum += 2;
	
	for &#40;int i = 0 && d = 0; i < 4 && d == 0; i++) &#123;
		switch &#40;FENstring&#91;strnum + i&#93;) &#123;
		case '-'&#58;
			CastlingRights = 0;
			d++;
			break;
		case 'K'&#58;
			CastlingRights ^= 1;
			break;
		case 'Q'&#58;
			CastlingRights ^= 2;
			break;
		case 'k'&#58;
			CastlingRights ^= 4;
			break;
		case 'q'&#58;
			CastlingRights ^= 8;
			break;
		default&#58;
			assert&#40;false&#41;;
		&#125;
		strnum++;
	&#125;
	
	
&#125;

How do I detect a space - as the compiler will warn about ' ' as being empty.

Matthew:out