Author: Sean Empey
Date: 19:41:53 09/19/04
Go up one level in this thread
On September 19, 2004 at 19:20:31, Uri Blass wrote:
>On September 19, 2004 at 18:35:49, Sean Empey wrote:
>
>>On September 19, 2004 at 11:38:10, Uri Blass wrote:
>>
>>>On September 19, 2004 at 10:36:20, Robert Hyatt wrote:
>>>
>>>>On September 18, 2004 at 14:16:03, Stuart Cracraft wrote:
>>>>
>>>>>On September 17, 2004 at 20:52:19, Robert Hyatt wrote:
>>>>>
>>>>>>On September 16, 2004 at 21:20:50, Uri Blass wrote:
>>>>>>
>>>>>>>What is faster doing a loop on the 1's of a bitboard or doing a loop on array of
>>>>>>>integers
>>>>>>>
>>>>>>>I simply consider to change my knight move generator to bitboards
>>>>>>>
>>>>>>>Today I have array
>>>>>>>int knightmove[64][8] and the question is if getting
>>>>>>>knightmove[c3][0],...knightmove[c3][7] is faster or slower than getting the same
>>>>>>>squares by calculating the 1's of knightoption[c3] in order to get the squares
>>>>>>>that the knight can go.
>>>>>>>
>>>>>>>I also consider to have bitboard knightcapturewhite[64] knightcaptureblack[64]
>>>>>>>and knightquietmoves[64] that are going to be updated incrementally after every
>>>>>>>move and the question is what is the price of this in speed.
>>>>>>>
>>>>>>>Do people who use bitboards have experience with it?
>>>>>>>
>>>>>>>Uri
>>>>>>
>>>>>>
>>>>>>You are asking the wrong question. Bitboards are simply a way of doing
>>>>>>_everything_ differently from array-based board representations. There are
>>>>>>gains and losses (of course you should ignore the naysayers like you-know-who as
>>>>>>bitboards can and do work fine). But when you start to mix things, the only way
>>>>>>to see if it is faster is to simply implement and test. That's what I did with
>>>>>>rotated bitboards when I first thought of the idea. It seemed like a good idea,
>>>>>>but there were issues to overcome... It takes time and testing...
>>>>>
>>>>>If one doesn't want to go full bitboard for everything,
>>>>>then partial bitboard for evaluation...
>>>>>
>>>>>Speed of evaluation without the hassle of rotation...
>>>>>
>>>>>Stuart
>>>>
>>>>Then you have to convert mailbox to bitboard at _every_ q-search position. That
>>>>won't be fast...
>>>
>>>In my case I have no mailbox and my board is simply 0-63
>>>
>>>I know that bitboard do not beat mailbox in generating moves but I hoped that it
>>>may beat my method of generating moves.
>>>
>>>Here is my function for generating knight moves(assuming the knight is not
>>>pinned and I check if the knight is pinned first by my pin array that is updated
>>>after every move so there is no illegal move)
>>>
>>>color(target) is defined to be info[target]>>3;
>>>
>>>static void generatesimpleknights(int square)
>>>{
>>> int i,target;
>>> for (i=0;i<knightnumber[square];i++)
>>> {
>>> target=knightmove[square][i];
>>> if (info[target]==EMPTA)
>>> gen_quietnopawns(square,target);
>>> else
>>> if (color(target)!=side)
>>> gen_push(square,target);
>>> }
>>>}
>>>
>>>for generating moves in bishop direction I have today functions like the
>>>following function
>>>leftup[x]=x-9 when x-9 is in bishop direction relative to x.
>>>rightdown[x]=x+9 or -1 and is defined in the same way
>>>
>>>
>>>static void generate7(int square)
>>>{
>>> int target;
>>> target=leftup[square];
>>> while ((target!=-1)&&(info[target]==EMPTA))
>>> {
>>> gen_quietnopawns(square,target);
>>> target=leftup[target];
>>> }
>>> if ((target!=-1)&& (color(target)!=side))
>>> gen_push(square,target);
>>> target=rightdown[square];
>>> while ((target!=-1)&&(info[target]==EMPTA))
>>> {
>>> gen_quietnopawns(square,target);
>>> target=rightdown[target];
>>> }
>>> if ((target!=-1)&& (color(target)!=side))
>>> gen_push(square,target);
>>>
>>>}
>>>
>>>I wonder if I can have things faster
>>
>>
>>pre-compute your moves and generating knight moves would be extremely fast.
>>something like this for generating them.
>>
>>/*
>> * Function: GenWNM
>> * Purpose: Generates suedo legal moves for white knights
>> * Usage: N/A
>> * Version: See ExtVerInfo
>> */
>>
>>int GenWNM( BoardInfo* cBoard, int sq ) {
>> int *v, u, i = 0;
>> v = KNPreGen[1][sq];
>> u = *v++;
>> do {
>> if( cBoard->Color[u] != WHITE ) {
>> AddMove( cBoard, sq, u, 0 ), i++;
>> }
>> } while( (u=*v++) != STOP );
>> return i;
>>}
>>
>>Hope it helps you so if at all
>>
>>-Sean
>
>Thanks
>
>I already use array with precpomputed moves
>knightmove[64][8]
>
>The only difference is that I do not use pointers
>If I understand correctly you claim that changing the array to
>knightmove[8][64] and using pointers can do it faster.
>
>I do not understand why do you start with
>v = KNPreGen[1][sq];
>
>I think that it is more logical to have v=KNPreGen[0][sq];
>
>Do I miss something?
>
>Uri
Actually my KNPreGen is KNPreGen[2][128][10];
below is my pre-compute code for KNIGHT and KING
for ( i = 0; i < 2; i++ ) { //0 = KING, 1 = KNIGHT
for ( n = 0; n < 128; n++ ) {
for ( j = 0; j < 10; j++ ) {
KNPreGen[i][n][j] = STOP;
if ( j > 7 || ( n & 0x88 )) continue;
sq = n;
if (i == 0 ) sq += KingOffset[j];
else sq += KnightOffset[j];
if ( sq & 0x88 ) continue;
else KNPreGen[i][n][j] = sq;
//printf("From: %d To: %d\n",n,sq);
}
z = -1;
for ( p = 0; p < 10; p++) {
if ( KNPreGen[i][n][p] == STOP && ( p <= z || z == -1 ) ) {
z = p;
}
if ( KNPreGen[i][n][p] != STOP && z != -1 ) {
if ( p > z ) {
KNPreGen[i][n][z] = KNPreGen[i][n][p];
KNPreGen[i][n][p] = STOP;
p = z;
z = -1;
}
}
}
}
}
creating the pointer ( v = KNPreGen[1][sq]) makes the move generation code a
lot faster. I have the board pointer because the program is multi threading.
Below are my move generation numbers. I hope I have not confused you more. I
have a tendancy of explaining things badly. Please feel free to ask any
questions you may have. I hope I have helped.
Bench Test 1 - Move Generation...
***Results for Bench Test 1 - Move Generation***
Time to Complete test:............................... 0:12.97
Number of times the move generators were called:..... 20000000
Total number of moves generated:..................... 760000000
Total number of GMPS:................................ 58596761
Thanks
-Sean
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.