Author: Andrew Dados
Date: 11:25:19 02/20/03
Go up one level in this thread
On February 20, 2003 at 03:16:58, Ed Schröder wrote:
>Taken from my web-page:
>
>Contrary to most chess programs, when going one ply deeper in the chess tree
>REBEL generates all moves for the given (and new) ply. During move generation
>REBEL quickly evaluates each move generated by using the piece-square technique,
>this evaluation is only used for move ordering later, it is certainly not for
>evaluating the position.
>
>The advantage of this time consuming process is that it pays off later when move
>ordering becomes an issue, this provided you have created 12 reasonable
>organized piece-square tables for the move generator. REBEL's data structure for
>move generation looks as follows:
>
>static char move_from [5000];
>static char move_to [5000];
>static char move_value [5000];
>
>So when adding a new generated move to "move_from" and "move_to" REBEL also will
>fill "move_value" via the corresponding piece-square table using the formula:
>
>move_value = table[move_to] - table[move_from];
>
>
>http://members.home.nl/matador/chess840.htm
>
>==============
>
>Data structure of "move_value" :
>
>255 : end of move list.
>1-254 : move_value = table[move_to] - table[move_from];
>0 : move already searched.
>
>Now whenever the Search needs a (new) move a routine is called that gets the
>(next) highest move from the move list and then this move is marked (zeroed) as
>being searched.
>
>This is a costly operation, during the years this is the best (fastest) code I
>was able to produce. The question is if there are better (faster) methods to get
>the highest value from an unsorted table.
>
>The main loop:
>
> value=1; // work variable
> x=.... // pointer to move list table
> y=-1; // pointer to highest value
>
>loop: x++; if (move_value[x] <= value) goto loop;
> if (move_value[x] == 255) return y;
> value=move_value[x];
> y=x;
> goto loop;
>
>-> "y" is the highest move from the table.
>
>===================
>
>in ASM I have this:
>
> mov BL,1 // work variable
> mov EDX,... // pointer to move list table
> mov ESI,-1 // pointer to highest value
>
>loop: mov CL,move_value[EDX] // CL = move_value[x]
> inc EDX // x++
>
> cmp CL,BL // if (move_value[x] <= value)
> jbe loop
>
> cmp CL,0FFh // if (move_value[x]==255)
> je done
>
> mov BL,CL // value=move_value[x]
> mov ESI,EDX // y=x
>
> jmp loop
>
>
>==============
>
>Any faster methods?
>
>Ed
Remember the trick to sort values in small range WITHOUT actually sorting
anything?
First consider how could you do it IF your 'preeval' returned all unique values
( means all V=table[move_to] - table[move_from] were unique):
For this we define move_number to be array [0..255] of move NUMBERS, not values
(that is pointers to actual move array). You need to initialize it to some
unique value if your array of moves is zero-based, so make it 255
Then all you do for each move is:
(N means move number in move list)
move_number[table[move_to] - table[move_from]]=N;
now to get them all in sorted order:
for (i=254;i>0;i--)
if (move_number[i] !=255) search(moves[i]);
Now if values are not unique then move_number table is not enough.
We need to keep array of all move values and another array of unique flags.
Hopefully those arrays don't need to be initialized:
unsorted_values,notunique: array [0..255] of char;
now loop generating move values will look:
temp v,moveno: char;
initialize_move_number_to_255;
moveno=0;
for each moveno :
{
v = table[move_to] - table[move_from];
if (move_number[v]==255)
{ //first move of value v:
move_number[v]=moveno;
notunique[v]=0;
} else
{ //move with value c was previously generated;
notunique[v]++;
}
unsorted_values[moveno]=v;
moveno++;
}
----
Now to get it all in sorted order:
for (i=254;i>0;i--)
if (move_number[i] != 255)
{
search_move(move_number[i]);
if (notunique[i])
//here need to loop through unsorted_values array starting from
move_number[i]+1
for (k=move_number[i]+1;k<255;k++)
if (unsorted_values[k] == i) search_move(k);
}
of course you may want to optimize that pseudocode :)
====================================================
obvious note: in this pseudocode value of move can't be 0; it is easy to change
that.
-Andrew-
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.