Winboard Forum

Hello everybody,

since this is my first post here I would like to introduce myself before asking my first question. I'm Oliver, 25 year old CS student from Frankfurt, and recently I started working on my 2 year old crappy engine again. After coming to the conclusion that it's code was too messy and it took ages to calculate perft(6) I decided to start over completely.

Now my question is the following:

Because I don't have a lot of experience I would like to be able to replace the core (move generation, board representation etc.) without too much effort so I would be able to experiment. I thought of encapsulating this stuff into C abstract data types, which would then imply that I would have to pass pointers on a lot of function calls.

Do you think that's worth the effort or would this slow me down too much?

Viele Gr??e,
Oliver[/code]

To build an OO chess program does not mean to make a class of everything. My SMIRF makes the attempt to be object oriented that way and nevertheless has very fast perft results (even if that is not that relevant for a well performing engine). If you start a new built, please think it over to also include Chess960 and 10x8 variants (like SMIRF does).

http://www.chessbox.de/Compu/schachsmirf_e.html (SMIRF Donationware Download Page)

Regards, Reinhard.

Reinhard Scharnagl wrote:To build an OO chess program does not mean to make a class of everything. My SMIRF makes the attempt to be object oriented that way and nevertheless has very fast perft results (even if that is not that relevant for a well performing engine). If you start a new built, please think it over to also include Chess960 and 10x8 variants (like SMIRF does).

http://www.chessbox.de/Compu/schachsmirf_e.html (SMIRF Donationware Download Page)

Regards, Reinhard.

Well, it wouldn't be proper OO... no polymorphism or function pointers etc.
Just, for example, like that:

Code: Select all

/* movegen.h */
typedef struct MoveGenContext
{
   /* some stuff here, e.g move stack, checks, pins */
}MoveGenContext;

void GenMoves(int ply, MoveGenContext *context);
...


This way I could experiment with whatever I want to within the functions in movegen.c and would not have to touch the other modules.

I don't think it would be too bad to always pass the pointer, but since I read the discussions here about speed I thought it would be better to think twice...

Chess960 will be seen to, and I'm almost forced to do that, because Hans-Walter Schmitt would rip my head off if I didn't - SC Frankfurt-West are our neighbours in Frankfurt

I have read quite a lot of the threads here and I like the linked list approach. When I started my work two years ago I tried to have something like that as well but I just didn't get good ideas - all the structures I have thought of seemed being too hard to update... well, perhaps I think about it again if I'm eventually familiar again with chess programming...

Viele Gr??e,
Oliver

I expected a lot of the linked-list approach as well, but when experimenting I could never get it to run as fast as a simple array, even if the captured pieces cause holes in the array that have to be skipped over. The problem might be that a linked list causes a very long dependency chain, fetching addresses from memory which even for the L1 cache has appreciable latency. Generating the addresses from a loop counter is much less demanding, since the increment operation that forms the backbone of the dependency chain there has almost no latency. Most CPUs I know really hate dependency chains...

I do not recommend to use link pointers. SMIRF linked those pieces logically.

Reinhard.

I never heard of a 'logically linked' list. Could you explain what you mean by that?

Reinhard Scharnagl wrote:I do not recommend to use link pointers. SMIRF linked those pieces logically.

Yes, that appears to be far more sensible. I contemplated logical relations of squares resp. rays because I wanted to represent the board as a graph with vertices representing the squares and the edges representing the slider directions in order to somehow being able to have information at hand where attacks, pins or discovered attacks are possible at all, given the present of state of the vertices.

I dreamt of an algorithm like:

Code: Select all

   The from-square vertex fires "I'm empty now" and therefore I have or
   have not a discovered attack

   The to-square vertex fires "I'm occupied now" and therefore a former
   attack is now obstructed or not.

   The king attempts to go to a square whose vertex fires "I'm under
   attack"


Probably I lacked imagination then, who knows... I'll go for a bitboard engine for now, but as I said I'm trying to keep everything modular so that a different implementation might be plugged in easily. Bitboards isn't suitable for other board geometries, I know, but I anyway do not want to develop a GUI and neither Arena nor CB support other geometries than 8x8...

Viele Gr??e,
Oliver

Hmm, I do not intend to make SMIRF open source yet. But - as a hint - the complete piece code fits into a 32 Bit integer. Thus the move generator has become very fast.

Reinhard.

H.G.Muller wrote:Most CPUs I know really hate dependency chains...

I wish I'd understand more about these kind of things. I was really taken aback when I read about all the clever stuff the bitboard fraction was discussing here... my current engine has a size of about 1,6 MB because it's packed with lookup tables. Somehow I talked myself into the belief that it's no good to calculate too much stuff on the fly.

Vele Groete,
Oliver

my current engine has a size of about 1,6 MB

my SMIRF engine has about 60K and covers 8x8, 10x8, Chess960 ... so it seems I still have a lot to do.

Reinhard.

My engine is at the other end of the spectrum. Less than 2000 characters...
I think I am really close now to beating the 1 ELO point per character limit!

But I am working on a bigger one as well.

Oliver Uwira wrote:

Reinhard Scharnagl wrote:I do not recommend to use link pointers. SMIRF linked those pieces logically.

Yes, that appears to be far more sensible. I contemplated logical relations of squares resp. rays because I wanted to represent the board as a graph with vertices representing the squares and the edges representing the slider directions in order to somehow being able to have information at hand where attacks, pins or discovered attacks are possible at all, given the present of state of the vertices.

I dreamt of an algorithm like:

Code: Select all

   The from-square vertex fires "I'm empty now" and therefore I have or
   have not a discovered attack

   The to-square vertex fires "I'm occupied now" and therefore a former
   attack is now obstructed or not.

   The king attempts to go to a square whose vertex fires "I'm under
   attack"


Probably I lacked imagination then, who knows... I'll go for a bitboard engine for now, but as I said I'm trying to keep everything modular so that a different implementation might be plugged in easily. Bitboards isn't suitable for other board geometries, I know, but I anyway do not want to develop a GUI and neither Arena nor CB support other geometries than 8x8...

Viele Gr??e,
Oliver

If you want to be creative, by all means use bitboards. If you want to be efficient use something else (well.... ,most of the time)

In XiniX, I use 0x88 combined with bitboards. The bitboards stuff give me more room to experiment, the 0x88 I use for checking my bitboard stuff.

Most stupid mistakes, you only make once, so my double implementation will give me warnings if they give different results.

Beside that, I can check wich one is fastest. A while ago, 0x88 was fastest most of the time, but with the help of recent discussions ( Specially Gerd ) bitboards are taking over.

Tony

Tony van Roon-Werten wrote:If you want to be creative, by all means use bitboards. If you want to be efficient use something else (well.... ,most of the time)

...

Beside that, I can check wich one is fastest. A while ago, 0x88 was fastest most of the time, but with the help of recent discussions ( Specially Gerd ) bitboards are taking over.

Those bit fiddling tricks explained by him made an impression on me, too!

H.G.Muller wrote:I think I am really close now to beating the 1 ELO point per character limit!

Since I will do bitboards until I have a sudden inspiration for the linked list approach I'll never be able to compete...

The first goal for me is to have a reasonably fast core because I'd like to create an engine with very good chess knowledge. When I added a king safety evaluation to my old engine and it didn't see anything anymore as a consequence I thought I should rewrite the thing completely.

It is also going to be exciting how much performance I'll be able to squeeze out of my lousy Celeron...

Unfortunately I haven't done low level programming since the computer architecture lecture a couple of years ago...

Viele Gr??e,
Oliver