Author: Dann Corbit
Date: 21:11:05 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?
If you search this way for every item in the list, then the operation is O(N*N)
Knuth has proved (and it is self apparent) that any algorithm to find the
maximum of N elements must make at least N-1 comparisions.
Hence, to find a single maximum or minimum object, you won't do any better.
If you need to find a cluster of them (suppose the top 5) then you would use the
quickselect algorithm. Here is a sample:
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
/*
**
** In the following code, every reference to CLR means:
**
** "Introduction to Algorithms"
** By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
** ISBN 0-07-013143-0
*/
/*
** CLR, page 187
*/
template < class Etype >
Etype
RandomSelect(Etype A[], size_t p, size_t r, size_t i)
{
size_t q,
k;
if (p == r)
return A[p];
q = RandomPartition(A, p, r);
k = q - p + 1;
if (i <= k)
return RandomSelect(A, p, q, i);
else
return RandomSelect(A, q + 1, r, i - k);
}
size_t RandRange(size_t a, size_t b)
{
size_t c = (size_t) ((double) rand() / ((double) RAND_MAX + 1) * (b
- a));
return c + a;
}
/*
** CLR, page 162
*/
template < class Etype >
size_t
RandomPartition(Etype A[], size_t p, size_t r)
{
size_t i = RandRange(p, r);
Etype Temp;
Temp = A[p];
A[p] = A[i];
A[i] = Temp;
return Partition(A, p, r);
}
/*
** CLR, page 154
*/
template < class Etype >
size_t
Partition(Etype A[], size_t p, size_t r)
{
Etype x,
temp;
size_t i,
j;
x = A[p];
i = p - 1;
j = r + 1;
for (;;) {
do {
j--;
} while (!(A[j] <= x));
do {
i++;
} while (!(A[i] >= x));
if (i < j) {
temp = A[i];
A[i] = A[j];
A[j] = temp;
} else
return j;
}
}
double data[30];
int main(void)
{
size_t i;
size_t size = sizeof(data) / sizeof(data[0]);
for (i = 0; i < size; i++) {
data[i] = rand();
}
for (i = 0; i < size; i++) {
cout << data[i] << endl;
}
cout << "1st item is " << RandomSelect(data, 0, size - 1, 0) << endl;
cout << "2nd item is " << RandomSelect(data, 0, size - 1, 1) << endl;
cout << "3rd item is " << RandomSelect(data, 0, size - 1, 2) << endl;
for (i = 4; i < size; i++)
cout << i << "th item is " << RandomSelect(data, 0, size - 1, i) <<
endl;
return 0;
}
If you explain more clearly to me how often the search is performed, perhaps I
can give a better answer.
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.