Author: Filip Tvrzsky
Date: 15:44:08 02/20/03
Go up one level in this thread
On February 20, 2003 at 12:43:08, Filip Tvrzsky wrote:
>On February 20, 2003 at 11:19:45, Axel Grüttner wrote:
>
>>On February 20, 2003 at 08:45:06, Filip Tvrzsky wrote:
>>
>>>On February 20, 2003 at 08:10:47, Axel Grüttner wrote:
>>>
>>>>I´m programming my first Move Generator using a 10x12 Board.
>>>>
>>>>1)The main structure is somthing like this:
>>>>
>>>>for(i=A1;i<=H8; i++){
>>>> switch(BOARD[i]){
>>>> case KNIGHT: ...(make moves)
>>>> case PAWN : ...
>>>> ...}
>>>>}
>>>>is this construct ok? or are there any better models which are simply to
>>>>implement?
>>>>
>>>
>>>Major improvement here is to use the list of pieces containing their placing on
>>>the board. Than you don't have to search whole board (64 arrays) but only this
>
>correction: "64 squares", sorry
>
>>>list (16 pieces at most).
>>
>>You mean an array[16] for each color with the positions of the pieces?
>>something like: pos_white[16]={A1, B1, ..., A2, B2, ..., H2} for the starting
>>position?
>
>Yes, it is one possibility how to implement such list.
>
>>Isn´t it possible/faster to use instead of an array two global 64-Bit-Bitboards
>>to mark the pieces of each color?
>>
>
>Of course, that's also possible, but I think it is a different story ... (I mean
>bitboards. I'm not an expert in bitboards, I use them not solely but only in a
>combination with 8x8 board.) I doubt if it would be faster because you had to
>use some bitscan function to detect piece positions (there was an interesting
>thread about bitscan few days ago!) and than test which piece is on the square.
>In my engine I use for this purposes certain improved (I think so!) kind of
>piece list, not bitboards ...
>
>>
>>>
>>>>2)First I used for KNIGHT moves a offset-array Koffset={-21,-19,..., 21}
>>>> and implemented it :
>>>>case KNIGHT: {
>>>> for(j=0; j<8; j++){
>>>> if(BOARD[i+Koffset[j]]==EMPTY)
>>>> _make move_
>>>>}
>>>>
>>>>But testing with 8 seperate IF´s
>>>> case KNIGHT: {
>>>> if(BOARD[i-21]==EMPTY){_make move_}
>>>> if(BOARD[i-12]==EMPTY){_make move_}
>>>> ...
>>>> if(BOARD[i+21]==EMPTY){_make move_} }
>>>>and without such an Offset-array was much faster. is this because of the LOOP,
>>>>or because of everlasting dereferencing the offset
>>>>
>>>
>>>You need to have the lookup table Knight_moves[square][12] containing directly
>>>the list of all possible moves for each square. The last element of all lists is
>>>some arbitrary value which is different from all your legal square indexes,
>>>let's name it END. Your code is going to be like this:
>>> for (unsigned char* pTo = &Knight_moves[From].To[0]; *pTo != END; pTo++)
>>> { make_move(From, *pTo); }
>>>Mote that pTo is a pointer!
>>
>>Why the "12" (km[square][12]) in you lookup table? the maximum moves a knight
>>can made is eight. i think i didn´t understand the functionality of this
>>construct. can you describe it a bit more precisly?
>>
>
>You need to allocate an array of size at least 9 for each square because 8 is
>maximum number of moves and you need also one element more which marks the end
>of the array! It looks like this:
> Knight_moves[e4]: c3, c5, d2, d6, f2, f6, g3, g5, END
>or
> Knight_moves[a1]: b3, c2, END, x, x, x, x, x, x
>Access to this array will be faster if it is alined on an boundary which is an
>power of 2. So it should be 16 here, not 12, sorry.
>Now we have an array Knight_moves[NUMBER_OF_SQUARES][16] which look like this
>(assuming that a1 == 0 and b1 == 1):
>b3, c2, END, x, x, x, x, x, x, x, x, x, x, x, x, x, a3, c3, d2, END, x, x, ...
>etc.
>Variable pTo is a pointer to this array. At the start you assign to it the value
>&Knight_moves[From].To[0] which is a beginn of an subarray[16] containing the
Sorry, I talk about an array
unsigned char Knight_moves[NUMBER_OF_SQUARES][16]
and actually use in my example an array of structures
struct { unsigned char To[16]; } Knight_moves[NUMBER_OF_SQUARES].
This is some relict of previous points in my engine's development which I
haven't cleaned yet but the effect is the same. I guess this fact confused you
...
It should be:
for (unsigned char* pTo = &Knight_moves[From][0]; *pTo != END; pTo++)
{ make_move(From, *pTo); }
Filip
>moves from the square From. *pTo is the requested square To. Than you simply
>increment the pointer pTo until *pTo equals END.
>This is definitely faster then computing moves using offsets in move generator -
>this work should be done only once during the engine initialization, not in
>every node of search tree ...
>Using pointer arithmetic is also faster then accessing array through indexes.
>I wonder if there is any better solution than that one I have explained ? ...
>
>>axel
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.