Author: Filip Tvrzsky
Date: 04:25:01 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 I have thought a lot about this stuff in the past. At the time I use the same method like you, but my idea is to split the move list into few parts depending on the move evaluation. It means to have one (short!) list for killer moves, one for captures and so on. Every loop would be than much shorter and you have a good chance to avoid browsing "less valuable" lists due the cutoff. But implementig won't be easy, I'm afraid. Filip
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.