Sample code: Moves and variations

[sje]

I converted the move flag group into a set. Why? Because I would rather avoid a conversation like this with a neophyte programmer:

Junior Person: "Mr. Wizard, why didn't you use a Pascal set type for these values?"

Me: "Uh, well, it's like this, uh, explicit shifts and masks are okay, uh, sometimes, maybe."

Junior Person: "But Mr. Wizard, in this case a Pascal set type would be no less efficient in any reasonable implementation."

Me: "Uh, well, perhaps you are not yet sufficiently experienced in the mysteries of the programming arts."

Junior Person: "Mr. Wizard, why are you trying to feed me bullshit?"

Me: "Silence! Do not meddle in my affairs, for I am subtle and quick to anger."

[Michel]

I like the Python way of indenting.

I do to. But it's not so good for copy paste as things usually get pasted in the wrong indentation level, messing everything up.

So not a good chess programming language

[lucasart]

what's the "sizeof" of your move structure ? trust me you need to stuff it in 32-bit for hash tables later on.

Jazz used to have 64-bit move structs, I didn't notice much of a gain by compating it to 32 bits (but I did it anyway).

I didn't mean to say it would be faster, but rather than it would allow smaller hash entries and therefore make better use of the memory that is given. For example if a tournament is played with 64 MB hash for everyone, and your program takes twice more memory per entry than others, it's as if other were using 32 MB. Probably not a big deal, but anyway since it's a simple fix why not do it

Another beauty of the C language is that all the bitwise operations to extract and put info into such a structure are done by the compiler. In practice it's better to trust the compiler to optimize this than to write it yourself: it's just as fast (sometimes more), much less error prone and much easier to write and to read.

Here I found exactly the opposite: writing the bit-shifts and extracting the data myself was faster than relying on the compiler to optimise bit-fields.
I agree that the compiler should be doing as good a job, if not better, than you can do yourself, but in practice it doesn't seem to...

Strange, because I started doing it alll "manually", and then let the compiler do it all, measured the relevant parts of code and found the compiler optimization to be as good as my manual bit twiddling. I use GCC 4.6 on GNU/Linux with full optimizations (-O3 -flto).

[lucasart]

I have always viewed pascal code as ugly, and verbose and this doesn't change my mind C is perhaps even worse except that it's not as verbose. There has GOT to be a better way .....

Yes, Python!

Well I'm a C fan, so I'm biaised. I agree that Pascal is ugly and verbose. And I agree that Python is great for almost everything, but *certainly not* for writing a chess engine using these kind of memory packing techniques, bit-twidling everywhere (starting from the generation of magic bitboards).

[lucasart]

I like the Python way of indenting.

I do to. But it's not so good for copy paste as things usually get pasted in the wrong indentation level, messing everything up.

So not a good chess programming language

LOL

[sje]

I have always viewed pascal code as ugly, and verbose and this doesn't change my mind C is perhaps even worse except that it's not as verbose.

If you dislike verbosity that much, perhaps you might try coding a chess program in APL, or its ASCII cousin, J.

As for ugly vs sexy, many a man would have benefited greatly from listening to the old song:

Code: Select all

If you wanna be happy for the rest of your life,
Never make a pretty woman your wife.
So from my personal point of view,
Get an ugly girl to marry you.

A pretty woman makes her husband look small
And very often causes his downfall.
As soon as he marries her
Then she starts to do the things
That will break his heart in two.

But if you make an ugly woman your wife,
You'll be happy for the rest of your life,
An ugly woman cooks her meals on time,
She'll always give you peace of mind.

If you wanna be happy for the rest of your life,
Never make a pretty woman your wife.
So from my personal point of view,
Get an ugly girl to marry you.

Don't let your friends say
You have no taste,
Go ahead and marry anyway,
Though her face is ugly,
Her eyes don't match,
Take it from me she's a better catch.

[Don]

I have always viewed pascal code as ugly, and verbose and this doesn't change my mind C is perhaps even worse except that it's not as verbose. There has GOT to be a better way .....

Yes, Python!

Well I'm a C fan, so I'm biaised. I agree that Pascal is ugly and verbose. And I agree that Python is great for almost everything, but *certainly not* for writing a chess engine using these kind of memory packing techniques, bit-twidling everywhere (starting from the generation of magic bitboards).

Agreed,

I don't think there is yet a better language for chess than C or C++.

C could be modified to have Python style intending of course. I'm not advocating that but it's possible.

As someone already implied, one of the problems with Python style indenting is confusion and agreement about how much to intend, whether to use tabs, spaces, etc.

And there IS something a little fishy about invisible characters as part of the language, but still I like it.

[hgm]

Code: Select all

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

I eventually converged on a system where there is no need for a separate field to indicate the promotion piece, but in addition to from and to-square there only a single bit is needed to indicate the move is special (i.e. castling, promotion, e.p. capture or double push). If that bit is set, the to-square contains a table index used to retrieve true to-square, capture square, Rook from- and to-square, squares to test for enemy Pawns to set e.p. rights and promotion pieces. That way I can have as many special moves as there are board squares.

For convenience, I use a larger-than-necessary to-square field, which absorbs the flag in it. This because my board is 0x88 like, so that the square numbers are not contiguous, and thus run up to a higher maximum. Spartacus has a (half used) 24x11 board, so square numbers can run up to 251. The square numbers in the unused 12x10 half are then available as 'signaling squares', to indicate 120 different special moves.

Unfortunately this was not enough for variants with a deep promotion zone and large board; Grand Chess (10x10 board) has a promotion zone of 3 ranks, and 6 eligible piece types, so for one color alone there can be 180 combinations of to-square and promo-piece. So I decided to indicate all square numbers (true to-square, capture square, squares to test) relative to the from square. As promoting Pawns have only 3 different possible move steps, the number of (move-step, promo-piece) combinations is only 18 per color even in Grand Chess. As a side effect the number of e.p. captures is reduced to 2 per color (left or right) and the number of double pushes to only 1 per color (but I use 3 double pushes and 4 e.p. captures per color, to support variants that reverse capture and non-capture of the Pawn).

I still have not found an elegant way to express S-Chess gatings in this system, though.

[lucasart]

Code: Select all

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

I eventually converged on a system where there is no need for a separate field to indicate the promotion piece, but in addition to from and to-square there only a single bit is needed to indicate the move is special (i.e. castling, promotion, e.p. capture or double push). If that bit is set, the to-square contains a table index used to retrieve true to-square, capture square, Rook from- and to-square, squares to test for enemy Pawns to set e.p. rights and promotion pieces. That way I can have as many special moves as there are board squares.

For convenience, I use a larger-than-necessary to-square field, which absorbs the flag in it. This because my board is 0x88 like, so that the square numbers are not contiguous, and thus run up to a higher maximum. Spartacus has a (half used) 24x11 board, so square numbers can run up to 251. The square numbers in the unused 12x10 half are then available as 'signaling squares', to indicate 120 different special moves.

Unfortunately this was not enough for variants with a deep promotion zone and large board; Grand Chess (10x10 board) has a promotion zone of 3 ranks, and 6 eligible piece types, so for one color alone there can be 180 combinations of to-square and promo-piece. So I decided to indicate all square numbers (true to-square, capture square, squares to test) relative to the from square. As promoting Pawns have only 3 different possible move steps, the number of (move-step, promo-piece) combinations is only 18 per color even in Grand Chess. As a side effect the number of e.p. captures is reduced to 2 per color (left or right) and the number of double pushes to only 1 per color (but I use 3 double pushes and 4 e.p. captures per color, to support variants that reverse capture and non-capture of the Pawn).

I still have not found an elegant way to express S-Chess gatings in this system, though.

To be honest, building from scratch all the board representation and move generation code was so painful. I'm happy it's behind me, and I don't want to go in there again, unless I really have a good reason to.
I would like to implement Chess960 for the next version. I haven't really thought about it though. Currently my castling moves are encoded as "e1g1" (if you see what I mean), so I was thinking of just coding castling moves as KxR whether in Chess960 or normal chess. I guess it would not be too hard to implement like this ? Is it how everyone else does this ? Are there nasty traps to watch out for ?
As for other chess variants, I'm not that much interested and will probably never to do anything else than normal chess and chess 960.

PS: I like your idea about the special move flag and the tsq field to be used to define the "true to square"

[Evert]

I didn't mean to say it would be faster, but rather than it would allow smaller hash entries and therefore make better use of the memory that is given. For example if a tournament is played with 64 MB hash for everyone, and your program takes twice more memory per entry than others, it's as if other were using 32 MB. Probably not a big deal, but anyway since it's a simple fix why not do it

In the case of Jazz, it was an easy change (so I did it). Sjaak also uses 64 bit words for moves, but there it's not so easy to change...

Strange, because I started doing it alll "manually", and then let the compiler do it all, measured the relevant parts of code and found the compiler optimization to be as good as my manual bit twiddling. I use GCC 4.6 on GNU/Linux with full optimizations (-O3 -flto).

That could make a difference, think I used GCC 4.2 on a Mac (and I would have been using -O2 rather than -O3).