ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Speedup with bitboards on 64-bit CPUs
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Vincent Diepeveen



Joined: 09 Mar 2006
Posts: 1738
Location: The Netherlands
PostPost subject: Re: Speedup with bitboards on 64-bit CPUs    Posted: Sat May 19, 2007 5:20 pm Reply to topic Reply with quote
CRoberson wrote:
Telepath (bitboard) is slower than NoonianChess in NPS by about 2x using a 32 bit complier (g++) for both on a Core2Duo and an AMD 4400+.
Both machines using a 32 bit version of windows.

When I went to the newer version of MSVC, Telepath gained a 33% speedup and it still was a 32 bit compile running on a 32 bit OS.

When I recompiled Telepath with g++ (64 bit version) and ran on the AMD with a 64 bit version of Linux, Telepath was 20% faster than NoonianChess was.

Telepath is bitboard (nonrotated) and NoonianChess uses a 64 element array and two piecelists.


Try using THIS datastructure & move generator for noonianchess and you kick the hell out of your bitboard program with a MORE generic approach:

Code:

/*
Gnu public license here.
See copy of it at FSF (free software foundation)
*/

const int
 nunmap[144] = {
  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  -1, -1,  0,  1,  2,  3,  4,  5,  6,  7, -1, -1,
  -1, -1,  8,  9, 10, 11, 12, 13, 14, 15, -1, -1,
  -1, -1, 16, 17, 18, 19, 20, 21, 22, 23, -1, -1,
  -1, -1, 24, 25, 26, 27, 28, 29, 30, 31, -1, -1,
  -1, -1, 32, 33, 34, 35, 36, 37, 38, 39, -1, -1,
  -1, -1, 40, 41, 42, 43, 44, 45, 46, 47, -1, -1,
  -1, -1, 48, 49, 50, 51, 52, 53, 54, 55, -1, -1,
  -1, -1, 56, 57, 58, 59, 60, 61, 62, 63, -1, -1,
  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
 };


int
  color[64], // having 0 = white, 1 = black, 2 = neutral
  board[64], // having 0 = empty, pawn=1,knight=2,bishop=3,rook=4,queen=5,king=6
  snelbord[64], // for white same as board[64], for black same as white but with a +8 for each piece
                // like whitepawn = 1, blackpawn = 9


  gentable[3][64][128], //* 24k loper, toren, dame *
  iskippos[64][64],     /*      l t d */
  ipiecepos[7][64][32], /* 0 = witte pion, 1 = zwarte pion, 2 = knight ... 6 = koning */
  ipawndir[2][64][4];   /* slagzetten */


void QuickFullMoveList(int side,struct Move *EP) {
/* Generate semi-legal moves in fast manner
*/
  int to,xside,*psq,sq,*t;

  xside = side^1;
  to    = EP->zet&63;
  if( board[to] == pawn ) { /* for enpassant */
    int from = (EP->zet>>6)&63;
    if( to-from == 16 || from-to == 16 ) {
      int f,*w,u;
      f = (to+from)>>1;
      w = ipawndir[xside][f];
      u = *w++;
      if( color[u] == side && board[u] == pawn ) {
        genindex->score = 1000;
        QuickLink((u<<6)|f|move_captures|move_enpassant);
      }

      if( (u=*w) != 128 && color[u] == side && board[u] == pawn ) {
        genindex->score = 1000;
        QuickLink((u<<6)|f|move_captures|move_enpassant);
      }
    }
  }

  if( !castld[side] ) {
    int u = PieceList[side][0];
    if( quickcastle(side,u,u+2) ) {
      genindex->score = 0;
      QuickLink((u<<6)|(u+2)|move_castles);
    }
    if( quickcastle(side,u,u-2) ) {
      genindex->score = 0;
      QuickLink((u<<6)|(u-2)|move_castles);
    }
  }

  t    = cancapside[side];
  psq  = &quickpiecelist[side][12]; /* Q R B */
  while( (sq=*psq++) != 128 ) {
    int SRsq  = (sq<<6);
    int piece = board[sq];
    int *s,*v,*w,u;

    s = andscan[0];
    v = ipiecepos[piece][sq];
    w = iskippos[sq];
    u = *v++;
    do {
      int p1=snelbord[u],sh=w[u];
      v += (s[p1]&sh);
      if( ((p1-1)>>3) != side ) {
        genindex->score = pvals[p1];
        QuickLink(SRsq|u|t[p1]);
      }
    } while( (u=*v++) != 128 );
  }

  psq  = &quickpiecelist[side][26]; /* pawns */
  while( (sq=*psq++) != 128 ) {
    int SRsq  = (sq<<6);
    int u,*v,*w;
    v = ipiecepos[side][sq];
    w = ipawndir[side][sq];
    u = *v++;
    if( row(u) != 0 && row(u) != 7 ) {
      if( color[u] == neutral) {
        genindex->score = 0;
        QuickLink(SRsq|u);
        if( (u=*v) != 128 && color[u] == neutral ) { /* indien u == sq dan false */
          genindex->score = 0;
          QuickLink(SRsq|u);
        }
      }

      u = *w++;
      if( color[u] == xside ) { /* ppos bevat geen 100, maar sq. */
        genindex->score = pvals[snelbord[u]];
        QuickLink(SRsq|u|move_captures);
      }
      if( (u=*w) != 128 && color[u] == xside ) { /* zelf ben je per definitie side */
        genindex->score = pvals[snelbord[u]];
        QuickLink(SRsq|u|move_captures);
      }
    }
    else {
      if( color[u] == neutral) {
        genindex->score = pvals[queen];
        QuickLink(SRsq|u|move_pqueen);
        genindex->score = 0;
        QuickLink(SRsq|u|move_pknight);
        genindex->score = 0;
        QuickLink(SRsq|u|move_prook);
        genindex->score = 0;
        QuickLink(SRsq|u|move_pbishop);
      }
      u = *w++;
      if( color[u] == xside) {/* captures */
        genindex->score = pvals[queen];
        QuickLink(SRsq|u|move_captures|move_pqueen);
        genindex->score = 0;
        QuickLink(SRsq|u|move_captures|move_pknight);
        genindex->score = 0;
        QuickLink(SRsq|u|move_captures|move_prook);
        genindex->score = 0;
        QuickLink(SRsq|u|move_captures|move_pbishop);
      }

      if( (u=*w) != 128 && color[u] == xside) {
        genindex->score = pvals[queen];
        QuickLink(SRsq|u|move_captures|move_pqueen);
        genindex->score = 0;
        QuickLink(SRsq|u|move_captures|move_pknight);
        genindex->score = 0;
        QuickLink(SRsq|u|move_captures|move_prook);
        genindex->score = 0;
        QuickLink(SRsq|u|move_captures|move_pbishop);
      }
    }
  }

  psq = quickpiecelist[side]; /* K N */
  while( (sq=*psq++) != 128 ) {
    int SRsq  = (sq<<6);
    int piece = board[sq];

    int u,*v;
    v = ipiecepos[piece][sq];
    u = *v++;
    do {
      int p1 = snelbord[u];
      if( ((p1-1)>>3) != side ) {
        genindex->score = pvals[p1];
        QuickLink(SRsq|u|t[p1]);
      }
    } while( (u=*v++) != 128 );
  }

} /* End QuickFullMoveList() */

void InitGens(void) {
  /* vul tabellen voor een 8x8 bord */
  int
    paardspring[8]  = {15,-15,17,-17,6,-6,10,-10},
    koningvlucht[8] = {7,-7,9,-9,8,-8,1,-1},
    alldirec[3][8]  = { /* delta richtingen op een 8x8 bord */
      {7,-7,9,-9,0,0,0,0},
      {8,-8,1,-1,0,0,0,0},
      {7,-7,9,-9,8,-8,1,-1}
    },
    nsq,sq,flag,i,j,next_sq,rij,piece,np,lijn,m,ms,c,t,old_sq,
    skipm[16],
    rij8[2]      = {7,0},
    rij2[2]      = {1,6},
    slalinks[2]  = {7,-9},
    slarechts[2] = {9,-7},
    veuren[2]    = {8,-8},

    /* 12x12 bord delta-coordinaten */
    numberpiece[3] = {bishop,rook,queen},
    numberfields[3] = {4,4,8},
    direc[3][10] = { /* richtingen op een 12x12 bord */
     {11,-11,13,-13,0,0,0,0,0,0}, /* loper */
     {12,-12,1 ,-1 ,0,0,0,0,0,0}, /* toren */
     {11,-11,13,-13,12,-12,1 ,-1,0,0}  /* dame */
    },
    vlucht[8] = {11,-11,13,-13,12,-12,1 ,-1}, /* koning */
    spring[8] = {23,-23,25,-25,10,-10,14,-14};/* paard */

  for( sq = 0 ; sq < 64 ; sq++ )
    for( m = 0 ; m < 64 ; m++ )
      iskippos[sq][m] = 0;

  for( i = 0 ; i < 7 ; i++ ) /* default value */
    for( sq = 0 ; sq < 64 ; sq++ )
      for( m = 0 ; m < 32 ; m++ )
        ipiecepos[i][sq][m] = 128;

  /* pionnen */
  for( sq = 0 ; sq < 64 ; sq++ ) {
    lijn = sq&7;
    rij  = sq/8;
    nsq  = 26 + rij*12 + lijn;

    for( c = white ; c <= black ; c++ ) { /* pion: wit en zwart */
      if( rij == rij8[c] )
        ipawndir[c][sq][0] = 128;
      else {
        m = 0;
        if( lijn != 7 ) {
          ipawndir[c][sq][m] = (sq+slarechts[c]);
          m++;
        }
        if( lijn != 0 ) {
          ipawndir[c][sq][m] = (sq+slalinks[c]);
          m++;
        }
        ipawndir[c][sq][m] = 128;

        m = 0;
        ipiecepos[c][sq][m] = (sq+veuren[c]);
        m++;
        if( rij == rij2[c] )
          ipiecepos[c][sq][m] = (sq+2*veuren[c]);
      }
    }

    m = 0;
    old_sq = sq;
    for( i = 0; i < 8; i++ ) {/* paard */
      t = nsq+spring[i];
      if( nunmap[t] >=  0 ) {
        ipiecepos[knight][sq][m] = nunmap[t];
        m++;
        old_sq = nunmap[t];
      }
    }
    ipiecepos[knight][sq][m] = 128;

    m = 0;
    old_sq = sq;
    for( i = 0; i < 8; i++ ) { /* koning */
      t = nsq+vlucht[i];
      if( nunmap[t] >=  0 ) {
        ipiecepos[king][sq][m] = nunmap[t];
        m++;
        old_sq = nunmap[t];
      }
    }
    ipiecepos[king][sq][m] = 128;

    for( np = 0 ; np < 3 ; np++ ) { /* loper,toren,dame */
      piece = numberpiece[np];
      m = 0;
      ms = 0;
      flag = 0;

      j = 0;
      while( nunmap[nsq+direc[np][j]] == -1 )
        j++;

      for( i = 0; i < numberfields[np]; i++ ) { /* voor alle richtingen */
        int sqdone=0;

        t = nsq;
        t = t+direc[np][i];

        j = i+1;
        while( nunmap[nsq+direc[np][j]] == -1 )
          j++;
        next_sq = nunmap[nsq+direc[np][j]];

        while( nunmap[t] != -1 ) {
          sqdone++;
          ipiecepos[piece][sq][m] = nunmap[t];

          m++;
          t = t+direc[np][i];
          flag = 1;
        }

        if( sqdone >= 2 && np <= 1 ) {
          /* alleen als er bij from-to daarna nog velden af
           * te gaan zijn dan is het interessant. Anders 0.
           * Dame hoeft niet want toren,loper al gedaan */
          int my12sq/*,yesdeze=false*/;
          /* begonnen met  nsq (12x12) + delta (direc[np][i])
           * */

          my12sq = nsq+direc[np][i];
          do {
            /* 8x8 bord opslaan */
            sqdone--;
            my12sq += direc[np][i];
          } while( sqdone >= 2 );
        }

        if( flag ) {
          flag = 0;
          skipm[ms] = m;
          ms++;
        }
      }
      ipiecepos[piece][sq][m] = 128;

      m  = 0;
      ms = 0;
      t  = ipiecepos[piece][sq][m];
      if( np == 2 ) { /* skippos alleen voor de dame vullen dat is genoeg */
        do {
          iskippos[sq][t] = (skipm[ms]-m)-1;
          m++;
          t = ipiecepos[piece][sq][m];
          if( m == skipm[ms] )
            ms++;
        } while( t != 128 );
      }
    }
  }
}

This is far faster at a K7 than crafty at a 64 bits chip.

Of course you no longer lose time to 'optimizing' the datastructure when using this and you can use all your time to improve your program algorithmically. Most bitboarders are IMHO 99% of their time busy improving small tiny subroutines of their engine in order to get bitboards faster or fixing bugs as a result of the complex overview you have at bitboards.

Keep a generic datastructure like the above one and kick butt!

Vincent
Back to top
View user's profile Send private message Send e-mail Visit poster's website MSN Messenger
Display posts from previous:   
Subject Author Date/Time
Speedup with bitboards on 64-bit CPUs Tord Romstad Fri Apr 27, 2007 8:39 am
      Re: Speedup with bitboards on 64-bit CPUs Mark Lefler Fri Apr 27, 2007 9:34 am
            Re: Speedup with bitboards on 64-bit CPUs Tord Romstad Fri Apr 27, 2007 11:04 am
                  Re: Speedup with bitboards on 64-bit CPUs Pradu Kannan Fri Apr 27, 2007 11:15 am
                  Re: Speedup with bitboards on 64-bit CPUs jswaff Sat Apr 28, 2007 12:21 am
      Re: Speedup with bitboards on 64-bit CPUs H.G.Muller Fri Apr 27, 2007 10:20 am
            Re: Speedup with bitboards on 64-bit CPUs Tord Romstad Fri Apr 27, 2007 11:13 am
                  Re: Speedup with bitboards on 64-bit CPUs Pradu Kannan Fri Apr 27, 2007 11:18 am
                        Re: Speedup with bitboards on 64-bit CPUs Tord Romstad Mon Apr 30, 2007 3:01 pm
                  Re: Speedup with bitboards on 64-bit CPUs Robert Hyatt Sun Apr 29, 2007 12:34 am
                        Re: Speedup with bitboards on 64-bit CPUs Tord Romstad Mon Apr 30, 2007 3:14 pm
                              Re: Speedup with bitboards on 64-bit CPUs Robert Hyatt Mon Apr 30, 2007 5:08 pm
                                    post gone?? Guetti Tue May 01, 2007 8:26 pm
                                          Re: post gone?? Gerd Isenberg Wed May 02, 2007 6:36 am
                                                Re: post gone?? Guetti Wed May 02, 2007 7:54 am
                                                Re: post gone?? H.G.Muller Wed May 02, 2007 3:47 pm
                                                      Re: post gone?? Gerd Isenberg Wed May 02, 2007 6:08 pm
      Re: Speedup with bitboards on 64-bit CPUs Charles Roberson Fri Apr 27, 2007 1:45 pm
            Re: Speedup with bitboards on 64-bit CPUs Vincent Diepeveen Sat May 19, 2007 5:20 pm
                  Re: Speedup with bitboards on 64-bit CPUs Robert Hyatt Mon May 21, 2007 5:34 pm
                  Re: Speedup with bitboards on 64-bit CPUs Tony Thomas Mon May 21, 2007 5:40 pm
                        Re: Speedup with bitboards on 64-bit CPUs Robert Hyatt Mon May 21, 2007 9:47 pm
                              Re: Speedup with bitboards on 64-bit CPUs Vincent Diepeveen Sat May 26, 2007 7:21 pm
                                    Re: Speedup with bitboards on 64-bit CPUs Robert Hyatt Sun May 27, 2007 9:41 pm
                                          Re: Speedup with bitboards on 64-bit CPUs Chan Rasjid Mon May 28, 2007 7:29 am
                                                Re: Speedup with bitboards on 64-bit CPUs Tony Thomas Mon May 28, 2007 9:04 pm
                                                Re: Speedup with bitboards on 64-bit CPUs Jacob Mon May 28, 2007 9:49 pm
                                                      Re: Speedup with bitboards on 64-bit CPUs Chan Rasjid Tue May 29, 2007 5:58 am
                                                            Re: Speedup with bitboards on 64-bit CPUs Robert Hyatt Tue May 29, 2007 3:18 pm
                                                                  Re: Speedup with bitboards on 64-bit CPUs Chan Rasjid Tue May 29, 2007 4:09 pm
                                                                        Re: Speedup with bitboards on 64-bit CPUs Robert Hyatt Tue May 29, 2007 9:23 pm
                                                                  Quiescence search width Steven Edwards Tue May 29, 2007 10:02 pm
                                                                        Re: Quiescence search width Greg McGlynn Wed May 30, 2007 3:36 pm
                                                                        Re: Quiescence search width Robert Hyatt Thu May 31, 2007 1:45 am
                                                                              Re: Quiescence search width Steven Edwards Thu May 31, 2007 2:16 am
                                                Re: Speedup with bitboards on 64-bit CPUs Robert Hyatt Tue May 29, 2007 3:15 pm
      Re: Speedup with bitboards on 64-bit CPUs Jon Dart Fri Apr 27, 2007 6:25 pm
            Re: Speedup with bitboards on 64-bit CPUs Michael Sherwin Fri Apr 27, 2007 11:32 pm
                  Re: Speedup with bitboards on 64-bit CPUs Robert Hyatt Sun Apr 29, 2007 12:38 am
                        Re: Speedup with bitboards on 64-bit CPUs Michael Sherwin Sun Apr 29, 2007 2:01 am
                              Re: Speedup with bitboards on 64-bit CPUs Robert Hyatt Mon Apr 30, 2007 12:41 am
      Re: Speedup with bitboards on 64-bit CPUs frank phillips Sat Apr 28, 2007 10:38 am
            Re: Speedup with bitboards on 64-bit CPUs Tord Romstad Mon Apr 30, 2007 3:22 pm
                  Re: Speedup with bitboards on 64-bit CPUs Robert Hyatt Mon Apr 30, 2007 8:59 pm
                        Re: Speedup with bitboards on 64-bit CPUs Michael Sherwin Tue May 01, 2007 9:55 am
                              Re: Speedup with bitboards on 64-bit CPUs Robert Hyatt Tue May 01, 2007 9:05 pm
                        Re: Speedup with bitboards on 64-bit CPUs H.G.Muller Tue May 01, 2007 11:38 am
                              Re: Speedup with bitboards on 64-bit CPUs Robert Hyatt Tue May 01, 2007 9:07 pm
      Re: Speedup with bitboards on 64-bit CPUs Shaun Brewer Tue May 01, 2007 11:20 pm
      Re: Speedup with bitboards on 64-bit CPUs Tord Romstad Fri May 11, 2007 8:16 am
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads