board representation

[Anonymous]

I am interested in trying to make a very fast perft engine. I have been making a bitboard engine for a while now, and it is an excellent board representation for analyzing positions, but it seems that if you are just after mindless speed, bitboards aren't the way to go. I know almost nothing about other kinds of board representations, and could use some suggestions if you have any . I would definitely post the code if it gets up to an interesting speed.

[Reinhard Scharnagl]

Have you already focussed some programs which perft values you want to surpass? Are you interested in my perft results from a move generator used in a really playing 8x8 and 10x8 boards program?

I am doubting that bitboard based engines would be optimal if targeting on perft values only.

Reinhard.

[Anonymous]

Reinhard, I'm not trying to surpass anything really, just interested in the challenge of making it as fast as I can. And yes, I would be interested in your perft results .

[Reinhard Scharnagl]

Ok, Ochazuke,

here are some last year results (P4, 2.8 GHz, Win XP, without caching but with building a big statistic):

Code: Select all

FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

  +-*--b--c--d--*--f--g--*-+ MS Vis. Studio C++ Vers. 13.10
8 |[r][n][b][q][k][b][n][r]| (Compilation: Nov  7 2004)
7 |[p][p][p][p][p][p][p][p]|
6 |   :::   :::   :::   :::| Perft Testseries
5 |:::   :::   :::   :::   |
4 |   :::   :::   :::   :::| (without caching)
3 |:::   :::   :::   :::   |
2 |<P><P><P><P><P><P><P><P>| Smirf Test No.: 00
1 |<R><N><B><Q><K><B><N><R>|
=>+-*--b--c--d--*--f--g--*-+ Break Time 250.0 Sec.

Ply     Nodes    all (x)   (e.p.)    all (+) all (++)    Promot.    Castl. Sec.
-------------------------------------------------------------------------------
1          20          0        0          0        0          0         0    0
2         400          0        0          0        0          0         0    0
3        8902         34        0         12        0          0         0    0
4      197281       1576        0        469        0          0         0    0
5     4865609      82719      258      27351        0          0         0  0.2
6   119060324    2812008     5248     809099       46          0         0  4.5
7  3195901860  108329926   319617   33103848     1628          0    883453  116
8 84998978956 3523740106  7187977  968981593   147215          0  23605205 3116
-------------------------------------------------------------------------------


FEN: r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 25

  +-*--b--c--d--*--f--g--*-+ MS Vis. Studio C++ Vers. 13.10
8 |[r]:::   :::[k]:::   [r]| (Compilation: Nov  7 2004)
7 |[p]   [p][p][q][p][b]   |
6 |[b][n]   :::[p][n][p]:::| Perft Testseries
5 |:::   :::<P><N>   :::   |
4 |   [p]   :::<P>:::   :::| (without caching)
3 |:::   <N>   :::<Q>:::[p]|
2 |<P><P><P><B><B><P><P><P>| Smirf Test No.: 01
1 |<R>   :::   <K>   :::<R>|
=>+-*--b--c--d--*--f--g--*-+ Break Time 250.0 Sec.

Ply     Nodes    all (x)   (e.p.)    all (+) all (++)    Promot.    Castl. Sec.
-------------------------------------------------------------------------------
1          48          8        0          0        0          0         2    0
2        2039        351        1          3        0          0        91    0
3       97862      17102       45        993        0          0      3162    0
4     4085603     757163     1929      25523        6      15172    128013  0.2
5   193690690   35043416    73365    3309887     2645       8392   4993637  7.4
6  8031647685 1558445089  3577504   92238050    55014   56627920 184513607  321
-------------------------------------------------------------------------------


Reinhard.

[Anonymous]

How does a 8x8 and 10x8 board work, if you dont mind me asking?

[Reinhard Scharnagl]

Well, it sets its bounds new each time it applies a FEN string.

You could have a view on my restricted Smirf-Beta program downloadable at:

http://www.chessbox.de/beta.html Project Chronicle 2004-Dec-10

Reinhard.

[Mihail Croitor]

at first, excuse me for my pure English, please.
i have a little question - really bitboard representation is more faster then simple table?!:?: as i know, delfi don't have bitboards, but is so strong engine.

[Reinhard Scharnagl]

Hi Mihail,

if you are searching for a bitboard expert I am the wrong man. But a lot members here will be able to explain bitboard properties to you.

I only can assure you, that Smirf is not using bitboards. And as far as I have had contact to bitboards I have had the impression that they are neither simple nor faster (concerning move generation).

Reinhard.

[Rémi Coulom]

I am interested in trying to make a very fast perft engine. I have been making a bitboard engine for a while now, and it is an excellent board representation for analyzing positions, but it seems that if you are just after mindless speed, bitboards aren't the way to go. I know almost nothing about other kinds of board representations, and could use some suggestions if you have any :) . I would definitely post the code if it gets up to an interesting speed.

If you do not know it already, you should take a look at the 0x88 board representation.
http://www.brucemo.com/compchess/programming/0x88.htm

R?mi

[Anonymous]

If you do not know it already, you should take a look at the 0x88 board representation.

Thanks, that may be what I was looking for .

[Dan Honeycutt]

I am interested in trying to make a very fast perft engine.

Vincent will send you diep's "world's fastest" move generator if you write him. Not easy to understand - if he didn't use variable names like "pawn" etc. you'd never guess it had anything to do with chess.

Dan H.

[Anthony Cozzie]

Vincent's move generator is in Dutch

The way it works (for sliders) is that for each square there is just a list of squares that a slider could attack, and a skip to the end of the ray value.

so the loop ends up being:

for(index = 0; square[index] >= 0; index += 1) {
if(occupied) index += skip[index];

if(!friendly) add_move(square[index]);

}

And with a trick you can remove the first branch (mask) so that it ends up being only 1 branch, which is just about optimal.

anthony

[Anonymous]

Anthony:

>so the loop ends up being:

>for(index = 0; square[index] >= 0; index += 1) {
>if(occupied) index += skip[index];
>
>if(!friendly) add_move(square[index]);
>}

Hmmm, what exectly are "occupied" and "friendly". Seems some function/macro/array-access, that needs some additional info.

if (occupied(index)) or if (occupied[index]) or more indirections I might understand. Like given, I am not smart enough, to even understand the pseudo code (which I think it is - yes?).

>And with a trick you can remove the first branch (mask) so that it ends
> up being only 1 branch, which is just about optimal.

So, how would the code look like, with this trick applied?

Dieter

[Tony van Roon-Werten]

Anthony:

>so the loop ends up being:

>for(index = 0; square[index] >= 0; index += 1) {
>if(occupied) index += skip[index];
>
>if(!friendly) add_move(square[index]);
>}

Hmmm, what exectly are "occupied" and "friendly". Seems some function/macro/array-access, that needs some additional info.

if (occupied(index)) or if (occupied[index]) or more indirections I might understand. Like given, I am not smart enough, to even understand the pseudo code (which I think it is - yes?).

>And with a trick you can remove the first branch (mask) so that it ends
> up being only 1 branch, which is just about optimal.

So, how would the code look like, with this trick applied?



Dieter

At the end of each row of squares, add the from square.

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

[Sune Fischer]

Vincent's move generator is in Dutch

The way it works (for sliders) is that for each square there is just a list of squares that a slider could attack, and a skip to the end of the ray value.

so the loop ends up being:

for(index = 0; square[index] >= 0; index += 1) {
if(occupied) index += skip[index];

if(!friendly) add_move(square[index]);

}

And with a trick you can remove the first branch (mask) so that it ends up being only 1 branch, which is just about optimal.

anthony

It is hardly optimal, mostly you only need a good cutoff move

It seems to me bitboards are better suited to find the moves you need in the order you need them.

-S.

[Daniel Shawul]

It seems to me bitboards are better suited to find the moves you need in the order you need them.

It will not be important if you don't order moves during generation.
ordering based on piece square tables may give better result.

And with a trick you can remove the first branch (mask) so that it ends up being only 1 branch, which is just about optimal.

How much is vincen't move generator faster than a 0x88 one?
is !(move & 0x88) too costy?

daniel

[Reinhard Scharnagl]

Hi Sune,

... It seems to me bitboards are better suited to find the moves you need in the order you need them.

I am quite satisfied with a non bitboard based legal move generator.

Moreover I am convinced, that a decision towards bitboards has a more philosophical nature. If you feel well with your data structure, your decision will be ok, whether it will be bitboards or not (as for me).

Reinhard.

[Uri Blass]

Anthony:

>so the loop ends up being:

>for(index = 0; square[index] >= 0; index += 1) {
>if(occupied) index += skip[index];
>
>if(!friendly) add_move(square[index]);
>}

Hmmm, what exectly are "occupied" and "friendly". Seems some function/macro/array-access, that needs some additional info.

if (occupied(index)) or if (occupied[index]) or more indirections I might understand. Like given, I am not smart enough, to even understand the pseudo code (which I think it is - yes?).

>And with a trick you can remove the first branch (mask) so that it ends
> up being only 1 branch, which is just about optimal.

So, how would the code look like, with this trick applied?



Dieter

At the end of each row of squares, add the from square.

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 do not understand and you did not reply Dieter questions.
What exactly are occupied and friendly.

I guess that friendly mean having friendly piece in the from square and occupied means having a friendly piece in the to square but the code that is posted is too abstract to undertand.

You do not need to give all the code.

explaining only the content of the arrays and the definitions will probably be enough to understand the code.

Uri

[Tord Romstad]

Hi Reinhard!

Moreover I am convinced, that a decision towards bitboards has a more philosophical nature. If you feel well with your data structure, your decision will be ok, whether it will be bitboards or not (as for me).

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

[Reinhard Scharnagl]

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. The effect for your engine's peformance ideed is marginal.

But I cannot see any relation between the decision to use bitboards or not and the speed of a move generator. I do not think that a decision for a flat representation (not using bitboards) will slow down the speed of your move generator. The truth might be that you will get earlier a fast generator by "patchworking" foreign bitboard source code instead of writing your own board flat representing code.

Regards, Reinhard.