Sample code: Moves and variations

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Move flags

Post by sje » Sat Dec 03, 2011 5:07 am

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
Posts: 2141
Joined: Sun Sep 28, 2008 11:50 pm

Re: Sample code: Moves and variations

Post by Michel » Sat Dec 03, 2011 6:05 am

Don wrote: 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 :D

User avatar
lucasart
Posts: 3184
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Sample code: Moves and variations

Post by lucasart » Sat Dec 03, 2011 10:28 am

Evert wrote:
lucasart wrote: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 :)
Evert wrote:
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).

User avatar
lucasart
Posts: 3184
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Sample code: Moves and variations

Post by lucasart » Sat Dec 03, 2011 10:38 am

Zach Wegner wrote:
Don wrote: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).

User avatar
lucasart
Posts: 3184
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Sample code: Moves and variations

Post by lucasart » Sat Dec 03, 2011 10:39 am

Michel wrote:
Don wrote: 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 :D
LOL

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Sample code: Moves and variations

Post by sje » Sat Dec 03, 2011 11:28 am

Don wrote: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.

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: Sample code: Moves and variations

Post by Don » Sat Dec 03, 2011 12:32 pm

lucasart wrote:
Zach Wegner wrote:
Don wrote: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.

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

Re: Sample code: Moves and variations

Post by hgm » Sat Dec 03, 2011 1:06 pm

lucasart wrote:

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.

User avatar
lucasart
Posts: 3184
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Sample code: Moves and variations

Post by lucasart » Sat Dec 03, 2011 1:34 pm

hgm wrote:
lucasart wrote:

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"
Last edited by lucasart on Sat Dec 03, 2011 1:38 pm, edited 1 time in total.

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

Re: Sample code: Moves and variations

Post by Evert » Sat Dec 03, 2011 1:37 pm

lucasart wrote: 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).

Post Reply