Author: Ricardo Gibert
Date: 16:32:14 02/21/03
Go up one level in this thread
On February 21, 2003 at 00:11:05, Dann Corbit wrote: >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. This can't be what he said. Even if it is assumed the elements are unordered, which you do not state, the elements can be sorted by a sort method that does not make comparisions such as a bin sort, etc. He must have said something like: Any algorithm to find the maximum of N [unordered] elements [based on making comparisions] must make at least N-1 comparisions. [snip]
This page took 0.02 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.