Need some help on speed optimization

[Dann Corbit]

Bob is right. Never mind if your move generator is too slow for now, just focus on improving your engine and implementing all the basic features. Optimization can be done later, maybe with a complete rewrite from scratch.

This is based on my experience with my engine. And you will have a hard time beating Crafty's NPS anyway as it is well optimized and is written in C, whereas your engine is in C#.

I would put it this way:
1. First make it correct and complete
2. Then make it fast.

If you try to do it in the other order, it is a guarantee of problems.

[bob]

Bob is right. Never mind if your move generator is too slow for now, just focus on improving your engine and implementing all the basic features. Optimization can be done later, maybe with a complete rewrite from scratch.

This is based on my experience with my engine. And you will have a hard time beating Crafty's NPS anyway as it is well optimized and is written in C, whereas your engine is in C#.

I would put it this way:
1. First make it correct and complete
2. Then make it fast.

If you try to do it in the other order, it is a guarantee of problems.

I would add one suggestion to save a _lot_ of time later. Start with known good approaches to doing things. Magic bitboards for example. Because you will likely "build around" core decisions, and if your core decisions are bad, all the code built around them have to be rewritten as well when the core code changes...

Bitboards are the obvious future of computer chess. 64 bit architectures make this simple to realize. Next, overall program structure is important to make it easy to understand, modify, and debug...

[Jan Brouwer]

Bitboards are the obvious future of computer chess.

Is this a commonly held opinion?
I am considering rewriting my engine and I can't make up my mind which way to go (at present I use a mailbox representation).

[bob]

Bitboards are the obvious future of computer chess.

Is this a commonly held opinion?
I am considering rewriting my engine and I can't make up my mind which way to go (at present I use a mailbox representation).

Look at the programs that have switched, from Rybka on down. It is not easy to switch without a rewrite, because now you think "sets" (bitmaps) rather than array loops. This takes some getting used to, so the learning curve is pretty slow. But eventually, you "see the light" and it works very well.

[Dann Corbit]

Bitboards are the obvious future of computer chess.

Is this a commonly held opinion?
I am considering rewriting my engine and I can't make up my mind which way to go (at present I use a mailbox representation).

Now that 64 bit operating systems and compilers are available, I don't think there is any doubt.

[hgm]

I did not yet implemented the piece list, because I'm a little bit confusing. I read about an array of 32 elements, one for each piece, indexing the 0x88 square, but... in any case, to discover, for example, where is an opponent slider, I have to loop on that array, just because due to promotion the only standing point about chess man is that there is at most 8 pawns for each color, the other can vary. I would like to try a Dictionary for this...

It should not be necessary to loop through the piece list for making and unmaking moves. You should store the piece number on the board, not the type. Then you will immediately know where to find the piece in the piece list.

You only loop through the list if you want indeed to do something to every piece in the list. For this a directory is indeed useful, to divide the list in sections. So that if you want to do something with sliders (e.g. look for pins), you know the first and last slider in your list, and only loop through those.

[Tord Romstad]

Surprisingly, I find myself to disagree with almost everything in Bob's last two posts, probably because I am a high-level guy while Bob is a low-level guy.

Look at the programs that have switched, from Rybka on down. It is not easy to switch without a rewrite,

In my experience, it is easy to switch without a rewrite, and I have done so several times. I would say that if switching between a mailbox and bitboard board representation without a rewrite is difficult, you either have a poorly written program which lacks a lot of simple abstractions, or a program with a huge amount of magic, low-level optimization tricks. Crafty, of course, is in the latter category, and I greatly admire your skill in writing complex blazingly fast low-level code with hardly any bugs. I could never have done it myself.

For a beginner, setting out to write madly optimized code from the beginning is obviously a bad idea. For this reason, I also disagree with the point you made in another post:

Start with known good approaches to doing things. Magic bitboards for example. Because you will likely "build around" core decisions, and if your core decisions are bad, all the code built around them have to be rewritten as well when the core code changes...

I don't think this is very important. Beginners should be more concerned about flexibility and debugability than with speed, and should therefore make the high-level parts of the programs as agnostic as possible about the board representation. It is far more important that the board representation is easy to replace than that it is extremely efficient. Different board representations have different strengths and weaknesses, and which one is faster in one particular program depends on what sorts of questions that program asks in its search and evaluation function. Beginners don't know what sort of questions they want to ask in their search and eval, it is therefore useful to postpone the decision about board representation, and to facilitate experimentation.

because now you think "sets" (bitmaps) rather than array loops.

I've found that it hasn't had any impact whatsoever on how I think. Regardless of my board representation, I tend to think in terms of chess concepts like mobility, pawn structure, hanging pieces and king safety.

This takes some getting used to, so the learning curve is pretty slow.

I don't recall any learning curve at all. It was just a low-level implementation detail. Perhaps it's because I still haven't learned or understood anything, but I would like to think I am not quite that slow and stupid.

Tord

[Felpo]

I would add one suggestion to save a _lot_ of time later. Start with known good approaches to doing things. Magic bitboards for example. Because you will likely "build around" core decisions, and if your core decisions are bad, all the code built around them have to be rewritten as well when the core code changes...

Bitboards are the obvious future of computer chess. 64 bit architectures make this simple to realize. Next, overall program structure is important to make it easy to understand, modify, and debug...

My first version was bitboard based, and move generation was a port in C# of a magic move generator found over the net. I decided to move ( back ) to 0x88 for some reason: C# does not have inline ( at least not under programmer control ) and macros, writing readable code requires to keep some order, and without that kind of low level control it's not possible to be really efficient. Furthermore, I did not completely got what magic do with its perfect hashing, I'm doing programming ( in this circumstance ) for hobby, and I don't want to copy without knowing the core.
Another thing: first version I create, with magic bitboard, suffer of a lot of architectural error, don't know if this forum is interested to, but I have collected a lot of "worst practices" to avoid in using managed code and looking for performance.

[Felpo]

It should not be necessary to loop through the piece list for making and unmaking moves. You should store the piece number on the board, not the type. Then you will immediately know where to find the piece in the piece list.

You only loop through the list if you want indeed to do something to every piece in the list. For this a directory is indeed useful, to divide the list in sections. So that if you want to do something with sliders (e.g. look for pins), you know the first and last slider in your list, and only loop through those.

I did implement this way in my test past we. Results are good. I need some refinements to keep some order in the piece list, i show you the idea:
I would logically divide the array in two for the two colors. Each array has the first position for the king, 8 position for pawns next comes Knights, and sliders ( in any order ). So I can easilly point the piece king without any if doing generation. The only problem are promotion: just because is a rare evenience, I thought about recreating the piece list in this case.

[bob]

Surprisingly, I find myself to disagree with almost everything in Bob's last two posts, probably because I am a high-level guy while Bob is a low-level guy.

Look at the programs that have switched, from Rybka on down. It is not easy to switch without a rewrite,

In my experience, it is easy to switch without a rewrite, and I have done so several times. I would say that if switching between a mailbox and bitboard board representation without a rewrite is difficult, you either have a poorly written program which lacks a lot of simple abstractions, or a program with a huge amount of magic, low-level optimization tricks. Crafty, of course, is in the latter category, and I greatly admire your skill in writing complex blazingly fast low-level code with hardly any bugs. I could never have done it myself.

I disagree. The way you use bitboards is _completely_ different than the way you use mailbox representation. With bitboards, you think "sets of squares" whereas with mailbox, you think "looping over a group of squares". The way you think about things is totally different. From generating checks (generate all moves and then cull non-checks to finding sets of squares that can give check and see if you can find a correct piece with a set of attack squares that intersects with the set of targets. The list goes on and on. I've done both, and it took me a _long_ while to get into "bitboard" thinking.

For a beginner, setting out to write madly optimized code from the beginning is obviously a bad idea. For this reason, I also disagree with the point you made in another post:

Start with known good approaches to doing things. Magic bitboards for example. Because you will likely "build around" core decisions, and if your core decisions are bad, all the code built around them have to be rewritten as well when the core code changes...

I don't think this is very important. Beginners should be more concerned about flexibility and debugability than with speed, and should therefore make the high-level parts of the programs as agnostic as possible about the board representation. It is far more important that the board representation is easy to replace than that it is extremely efficient. Different board representations have different strengths and weaknesses, and which one is faster in one particular program depends on what sorts of questions that program asks in its search and evaluation function. Beginners don't know what sort of questions they want to ask in their search and eval, it is therefore useful to postpone the decision about board representation, and to facilitate experimentation.

Different philosophies. I don't go for speed "up front". But I try to never design with blinders on so that I make decisions that will make it very difficult to go fast later. That is an easy mistake to make, and you end up rewriting things that could have been designed differently up front.

because now you think "sets" (bitmaps) rather than array loops.

I've found that it hasn't had any impact whatsoever on how I think. Regardless of my board representation, I tend to think in terms of chess concepts like mobility, pawn structure, hanging pieces and king safety.

For chess-related stuff, yes. But for things like evaluating mobility, or generating just checks, or generating just legal check evasions, it is a different thing. Ditto for evaluation. You can ask multiple questions with a single AND if you know how to do it and plan on doing that from the beginning.

This takes some getting used to, so the learning curve is pretty slow.

I don't recall any learning curve at all. It was just a low-level implementation detail. Perhaps it's because I still haven't learned or understood anything, but I would like to think I am not quite that slow and stupid.

Tord

Every programmer I have talked to that "made the switch" found it a very different way of thinking. Whether it is because of how long we did mailboxes before converting, or whatever else, I don't know. It took me a _lot_ of time to reach the point where now bitboard solutions are an obvious thing for any question I want to ask or any algorithm I want to design...