A new extensive chess programming tutorial

[Eli Bendersky Eli Benders]

Geschrieben von: / Posted by: Eli Bendersky Eli Bendersky at 10 February 2004 19:07:07:

Hello all,
I began publishing a new chess programming tutorial. It
follows my pet project of developing a chess playing agent
from scratch. The tutorial is released in stages, as soon
as I complete parts of the program. Each release includes
a new chapter of the tutorial (in PDF form) and all the
code for that release. The whole thing is free, of course,
including the code which is licensed with the GPL.
I hope it will be of interest to people in this group.
You're welcome to check it out at:
http://www.geocities.com/spur4444/prog/jamca/jamca.html
Kind regards,
Eli



Jamca website

[Tom Likens]

Geschrieben von: / Posted by: Tom Likens at 10 February 2004 20:52:58:
Als Antwort auf: / In reply to: A new extensive chess programming tutorial geschrieben von: / posted by: Eli Bendersky Eli Bendersky at 10 February 2004 19:07:07:

Hello all,
I began publishing a new chess programming tutorial. It
follows my pet project of developing a chess playing agent
from scratch. The tutorial is released in stages, as soon
as I complete parts of the program. Each release includes
a new chapter of the tutorial (in PDF form) and all the
code for that release. The whole thing is free, of course,
including the code which is licensed with the GPL.
I hope it will be of interest to people in this group.
You're welcome to check it out at:
http://www.geocities.com/spur4444/prog/jamca/jamca.html
Kind regards,
Eli

Eli,
This looks interesting and the style of writing is conversational and easy to read (which is
a nice way to go with it). A couple of questions though, why did you select a mailbox
representation for your chess board rather than 0x88 data architecture? I think long term
you will reap more benefit from the 0x88 data structure since it has a lot of nice
features that come releatively cheap (e.g. in-check detection can be made fairly fast
with this data structure and you will do a *lot* of in-check detection one way or another).
Moreland's program Gerbil is a good place to look for a basic implementation of the
technique.
Also another question you will want to answer quickly, besides the type of piece and its
color, is if it is a sliding piece (i.e. Queen, Rook or Bishop). Other items you'll want to
extract quickly are things like the rank and file of a square etc.
Anyway, just a few random thoughts. Good luck with your project.
regards,
--tom

[Thomas Mayer]

Geschrieben von: / Posted by: Thomas Mayer at 11 February 2004 03:50:15:
Als Antwort auf: / In reply to: Re: A new extensive chess programming tutorial geschrieben von: / posted by: Tom Likens at 10 February 2004 20:52:58:

Hi Tom,

This looks interesting and the style of writing is conversational and easy
to read (which is a nice way to go with it).
A couple of questions though, why did you select a mailbox
representation for your chess board rather than 0x88 data architecture?
(e.g. in-check detection can be made fairly fast
with this data structure and you will do a *lot* of in-check detection one
way or another).

That was exactly what I was thinking looking the first time on that page...
you know, each board representation has it's payback... and mailbox is maybe the easiest to understand... Besides, my board-representation is int board[64]; that allows also some nice tricks, like sq & 7 gives the file and sq >> 3 gives the row...
In Quark I have changed that completely... nearly no InCheck is used anymore anywhere -> instead I have attacktables and even before a move is made I know if it checks or not... gaves me a nice speedup...
Greets, Thomas

[Uri Blass]

Geschrieben von: / Posted by: Uri Blass at 11 February 2004 08:01:50:
Als Antwort auf: / In reply to: Re: A new extensive chess programming tutorial geschrieben von: / posted by: Thomas Mayer at 11 February 2004 03:50:15:

Hi Tom,

This looks interesting and the style of writing is conversational and easy
to read (which is a nice way to go with it).
A couple of questions though, why did you select a mailbox
representation for your chess board rather than 0x88 data architecture?
(e.g. in-check detection can be made fairly fast
with this data structure and you will do a *lot* of in-check detection one
way or another).

That was exactly what I was thinking looking the first time on that page...
you know, each board representation has it's payback... and mailbox is maybe the easiest to understand... Besides, my board-representation is int board[64]; that allows also some nice tricks, like sq & 7 gives the file and sq >> 3 gives the row...
In Quark I have changed that completely... nearly no InCheck is used anymore anywhere -> instead I have attacktables and even before a move is made I know if it checks or not... gaves me a nice speedup...
Greets, Thomas

I use the same board representation.
I was told that it is probably not the best but I was too lazy to change.
I do not see how can you know before you make a move if it is check by attack tables.
You can use them to calculate it faster and I do it when I do not need to make all moves(in the qsearch) but my attack tables give me only information about attack squares and not about squares that may be attacked in the future.

It is possible to have a big attack table when a move is check only if
attack[from][to][kingsquare]==1 or maybe attack[from][to]&(1

[Uri Blass]

Geschrieben von: / Posted by: Uri Blass at 11 February 2004 08:04:52:
Als Antwort auf: / In reply to: Re: A new extensive chess programming tutorial geschrieben von: / posted by: Uri Blass at 11 February 2004 08:01:50:

Hi Tom,

This looks interesting and the style of writing is conversational and easy
to read (which is a nice way to go with it).
A couple of questions though, why did you select a mailbox
representation for your chess board rather than 0x88 data architecture?
(e.g. in-check detection can be made fairly fast
with this data structure and you will do a *lot* of in-check detection one
way or another).

That was exactly what I was thinking looking the first time on that page...
you know, each board representation has it's payback... and mailbox is maybe the easiest to understand... Besides, my board-representation is int board[64]; that allows also some nice tricks, like sq & 7 gives the file and sq >> 3 gives the row...
In Quark I have changed that completely... nearly no InCheck is used anymore anywhere -> instead I have attacktables and even before a move is made I know if it checks or not... gaves me a nice speedup...
Greets, Thomas

I use the same board representation.
I was told that it is probably not the best but I was too lazy to change.
I do not see how can you know before you make a move if it is check by attack tables.
You can use them to calculate it faster and I do it when I do not need to make all moves(in the qsearch) but my attack tables give me only information about attack squares and not about squares that may be attacked in the future.

It is possible to have a big attack table when a move is check only if
attack[from][to][kingsquare]==1 or maybe attack[from][to]&(1

[Volker Pittlik]

Geschrieben von: / Posted by: Volker Pittlik at 11 February 2004 09:41:11:
Als Antwort auf: / In reply to: Re: A new extensive chess programming tutorial geschrieben von: / posted by: Uri Blass at 11 February 2004 08:04:52:

...

attack[from][to][kingsquare]==1 or maybe attack[from][to]&(1Uri

I see that you need to click reply in order to read this post like I posted it.

attack[from][to][kingsquare]==1 or maybe attack[from][to]&(1<<kingsquare]

Look here: http://www.pittlik.de/wbforum/formatted.html#form how to do the trick. It can't be explained here.
Volker

[Tord Romstad]

Geschrieben von: / Posted by: Tord Romstad at 11 February 2004 10:46:31:
Als Antwort auf: / In reply to: A new extensive chess programming tutorial geschrieben von: / posted by: Eli Bendersky Eli Bendersky at 10 February 2004 19:07:07:

As others have pointed out, a 10x12 board isn't the best choice if you want
to use a mailbox board representation. I started out with a 10x12 board myself,
but quickly found that a 16x16 board was much more efficient. The "real" board
occupies the left half of the middle eight ranks, all other squares on the board
contain the value OUTSIDE.
A 16x16 board enables you to combine the advantages of 0x88 and mailbox. You
can define your board array as follows:
int Board_[256];
int *Board=Board+0x40;
In the rest of your program, you can forget about the Board_[] array and use
the Board pointer instead. You now have two ways to check whether a given
square is outside the real board: A square is outside the board
if (square&0x88)!=0, or if Board[square]==OUTSIDE. Which condition is most
useful can vary between different parts of your code.
Having 16 files rather than 10 (or 8) gives you the advantage that you can
make many of your lookup tables become much smaller. The point is that
you know the geometrical relationship between two squares just by subtracting
the indices of the squares. For stuff like distance, king relative to passed
pawn bonus, and determining whether a piece on square A can possibly attack
square B, you can use Table[A-B+128] rather than Table[A][B].
Thomas Mayer mentioned that a 64-element board array has the advantage that
it is easy to find the rank and the file of a square. A board with 16 files
has the same advantage. square&15 gives you the file, and square>>4 the rank.
Good luck with your project!
Tord

[Eli Bendersky]

Geschrieben von: / Posted by: Eli Bendersky at 11 February 2004 12:11:50:
Als Antwort auf: / In reply to: Re: A new extensive chess programming tutorial geschrieben von: / posted by: Tom Likens at 10 February 2004 20:52:58:

Eli,
This looks interesting and the style of writing is conversational and easy to read (which is
a nice way to go with it). A couple of questions though, why did you select a mailbox
representation for your chess board rather than 0x88 data architecture? I think long term
you will reap more benefit from the 0x88 data structure since it has a lot of nice
features that come releatively cheap (e.g. in-check detection can be made fairly fast
with this data structure and you will do a *lot* of in-check detection one way or another).
Moreland's program Gerbil is a good place to look for a basic implementation of the
technique.
Also another question you will want to answer quickly, besides the type of piece and its
color, is if it is a sliding piece (i.e. Queen, Rook or Bishop). Other items you'll want to
extract quickly are things like the rank and file of a square etc.
Anyway, just a few random thoughts. Good luck with your project.
regards,
--tom

Thanks for all the replies, guys. I'm happy that you like the writing
style (I had some concerns about it
Regarding representations. As I said a few times in the tutorial, my first
goal is to create a very simple agent, even if it's slow and stupid. It will
give me a good base to move on, introducing improvements.
I'm aware of 0x88, other array tricks, bitboards, etc. For now, I'm beginning
with something very simple, and later I'll definitely improve it. The important
thing is that all those steps will be documented in the tutorial, so it will
take readers through many implementations (all profiled and compared for performance, of course).
Eli