board representation

[Tord Romstad]

Hi Tord,

It is surprising how many beginners seem to believe that the speed of the move generator is one of the main factors deciding the strength of the engine.

well, the move generator's speed is of course important to judge, whether your board representation is implemented well or not, thus if your data structure is acceptable designed.

Not necessarily. This depends on what else you want to do in your program, and whether the more expensive computations you want to do later will have much resemblance to move generation. For most beginning chess programmers, this is very hard to guess. Therefore, I think it is better to concentrate on creating a working, strong and reasonably bug-free program first, and only then try to find out what sort of operations tend to be the most expensive in your code, and optimise your data structures to do these operations more quickly. When the program is young and rapidly developing, it is useful to keep the code simple, fluid and flexible. Being able to easily switch to entirely different data structures and board representations without having to rewrite everything is a considerable advantage.

Another fact which cannot be mentioned often enough is that amateurs overestimate the importance of efficient data structures, and spend too much time and energy trying to optimise them. Efficiency on a higher level is more important by an order of magnitude. On the average amateur level, you usually do not win games by searching more nodes per second than the opponent. You win by having fewer bugs and a more efficient search.

Tord

[Reinhard Scharnagl]

Hi Tord,

Another fact which cannot be mentioned often enough is that amateurs overestimate the importance of efficient data structures, and spend too much time and energy trying to optimise them. Efficiency on a higher level is more important by an order of magnitude. On the average amateur level, you usually do not win games by searching more nodes per second than the opponent. You win by having fewer bugs and a more efficient search.

I partially agree. But it seems to me that you are always thinking, that when somebody is working on chess algorithms he always has to be interested in writing a full working chess program. Chess is already highly interesting, when creating and testing data structures. You can learn a lot from that and get more familiar with a may be new programming language. It could be an interesting challenge to write a fast move generator, if that would be your goal.

Beside of optimizing data structures their flexibility is more important. Because if you finally switch to write a playing chess program you will get a lot of experiences, which might lead back in a wish to modify your data structures. A structure like bitboards hardly would be created by a little change of an ad hoc structure when facing some problems in finishing a working engine. Thus a basing data structure has to be somehow adult and stable.

A lot of amateur chess programmers, when starting with foreign sorces, of course would hardly make such experiences, because they rely on worked out structures like bitboards. This might fix the illusion that working on data structures would not be that important. But the reality is that mostly this already had been done by others.

So when starting completely from zero, you have to work out your data structures intensivly until they could be used as a stable and trustworthy base for building an engine upon it. And to write a move generator of acceptable performance e.g. is one way to succeed with that.

Regards, Reinhard.

[Tord Romstad]

Another fact which cannot be mentioned often enough is that amateurs overestimate the importance of efficient data structures, and spend too much time and energy trying to optimise them. Efficiency on a higher level is more important by an order of magnitude. On the average amateur level, you usually do not win games by searching more nodes per second than the opponent. You win by having fewer bugs and a more efficient search.

I partially agree. But it seems to me that you are always thinking, that when somebody is working on chess algorithms he always has to be interested in writing a full working chess program. Chess is already highly interesting, when creating and testing data structures. You can learn a lot from that and get more familiar with a may be new programming language. It could be an interesting challenge to write a fast move generator, if that would be your goal.

Yes, this is of course a perfectly valid goal, but I am fairly sure that the clear majority of chess programmers really are interested in writing a full working chess program. In case it was not clear, I was not really writing only to you, and nothing I write is intended as criticism of anything in your approach to chess programming. You are clearly a more experienced and intelligent programmer than I am (and I have no doubt that your engine will end up being much stronger than mine), and it would be ridiculous for me to try to give you advice. I am writing for the benefit of beginning chess programmers, in the hope that it can help some of them to avoid repeating the mistakes so many of us have made in the past.

Beside of optimizing data structures their flexibility is more important.

Yes, flexibility is important. In fact, this is one of the main points I tried to get across in my previous message.

Because if you finally switch to write a playing chess program you will get a lot of experiences, which might lead back in a wish to modify your data structures.

Exactly.

A structure like bitboards hardly would be created by a little change of an ad hoc structure when facing some problems in finishing a working engine.

This isn't necessarily true, though. As long as you keep the more complicated parts of your program data structure agnostic, ripping out the existing board representation and replacing it with bitboards doesn't have to be a very big task. In fact, I did exactly this a couple of weeks ago in an experimental version of my own program.

Thus a basing data structure has to be somehow adult and stable.

A lot of amateur chess programmers, when starting with foreign sorces, of course would hardly make such experiences, because they rely on worked out structures like bitboards.

I agree, but I think you overestimate how often programmers start from foreign sources. I think almost everyone implements everything from scratch.

Tord

[Anonymous]

idx=0;
while (1)
if (occupied){
if !(sq[idx]==friendly) AddCaptureMove;
else if (sq[idx]==fromsq) break;
ixd+=skip[idx];
} else AddNonCaptureMove;
idx++;
wend;

I actually thought you meant this, but from your first post I was a bit confused. Perhaps the following is slightly clearer:

Code: Select all

int *sqtbl, *skip; /* initialized to specific piece and from table */
to = sqtbl[from]; 
while(1)
{
  while (color[to] == empty) /* Inner loop with one branch/move */
  {
    addmove(from,to);
    to = sqtbl[to]; /* or your idx++ to have denser tables */           
  } 
  if (color[to] == me)
  {
    if (to == from)
      break;
  }
  else /* not empty and not me -> must be opponent */
    addcapture(from,to);
  to = skip[to];
}


1 branch for all slides in one direction until hitting a piece, when not hitting a piece will go on to the next direction still with one branch each move. For each piece hit 2 branches (so 2 branches for each capture move, and for non moves, because own piece hit). And 3 branches once when the "scan" is over.

Regards,
Dieter

[Sune Fischer]

I agree entirely. The speed of move generation and the choice of whether or not to use bitboards or nowhere near as important as many programmers seem to believe. Just write something that works and looks clear and logical. As long as you keep your program simple and bug-free, it is easy to change to a different board representation at a later stage.

It is surprising how many beginners seem to believe that the speed of the move generator is one of the main factors deciding the strength of the engine. The truth is that for more than 90% of the amateur engines, the number of serious bugs is by far the most important factor.

Tord

Hi Tord,

Well I agree too, of course, that move generation speed itself is not very time consuming.

It's astonishing how many that seems to care about it though, and when they do bring it up, they often neglect to consider what the search tree in a real chess program looks like (hint: it's _nothing_ like perft ;).

I believe that bitboards have the speed advantage on fail-high and quiesce nodes, while on PV and fail-low nodes they are possibly slower.

But you can relax Tord, I'm not using bitboard because I believe they are faster at move generation. What concerned me most was creating easy structures to work with in the evaluation.
That's another debate though, just as silly probably :)

-S.

[Reinhard Scharnagl]

Hi Tord,

... and I have no doubt that your engine will end up being much stronger than mine ...

I just have investigated that your Glaurung will be measured around 2400 Elo (please correct me), that is of course already strong. Smirf still is a baby and I would be glad to reach such a rating with Smirf during the next months. I prosume it is actually as strong as Frenzee, but I have not the time to perform a lot of test games to verify that seriously. There still are a lot of weaknesses to be fixed in Smirf, and e.g. the evaluation routine is still the first ad hoc realisation from early November, crying for to be rewritten, from which I hope to get a triple speed.

This thread is on board representation. Therefore I will not close here without remembering that it would be much easier for chess programmers to include Chess960 (FRC) from the very beginning instead of doing that sometimes after finishing an engine. Same is valid for supporting also the 10x8 board with the Capablanca extended piece set, but that would be of interest only for few - it might change in future - as I hope. http://www.chessbox.de/beta.html

Regards, Reinhard.