Author: Filip Tvrzsky
Date: 09:43:08 02/20/03
Go up one level in this thread
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
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.