Author: Ed Schröder
Date: 01:06:46 02/22/03
Go up one level in this thread
On February 21, 2003 at 00:33:33, Eugene Nalimov wrote: >I believe you can slightly speedup the loop without unrolling the loop or >changing the algorithm -- actually code size would be exactly the same: Thanks Eugene and all those who responded. Your idea was also pointed out by someone else, I tried it but noticed no speed improvement, but also no speed loss. I liked Tony's idea most, that is that every time a move is found you shrink the table by putting the move at the end of the table (defined by 0xff) and mark it as the new end of the table (store 0xff). I haven't tried it yet but it surely will give me a (ahem) nice speed improvement of 0.1 or 0.2% :-) I actually hoped for a mathematical technique I wasn't aware off. The radix-sort approach looks appealing, I must try that. What I have tried in the past is to search the good moves first (hash table move, good captures, killers) and when they do not produce a cutt-off, sort the table using quicksort and then get the moves sequential. That was in the old 6502 days and it gave no improvement, perhaps with nowadays hardware it will. Again, thanks to all who responded. My best, Ed > mov BL,1 // work variable > mov EDX,... // pointer to move list table > mov ESI,-1 // pointer to highest value > jmp loop > >better: > mov BL,CL // value=move_value[x] > mov ESI,EDX // y=x > >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) > jne better > >Thanks, >Eugene > >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
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.