Author: Nathan Thom
Date: 15:20:31 01/23/03
Go up one level in this thread
On January 23, 2003 at 08:44:55, Peter Fendrich wrote: >On January 22, 2003 at 22:04:17, Nathan Thom wrote: > >>On January 22, 2003 at 21:21:33, Robert Hyatt wrote: >> >>>On January 22, 2003 at 19:41:33, Nathan Thom wrote: >>> >>>>Hi all, I implemented a pretty quick killer move algorithm into LittleThought >>>>last night from memory of what its supposed to do. >>>> >>>>A couple of questions: >>>>1. First, i incremented the killers[from][to] array by the inverse of the >>>>current depth (ie MAX_DEPTH - depth) when a cutoff occurred. In my code depth 0 >>>>is the root and it increases downwards. I figured this would be better than >>>>plain depth because cutoffs closer to the root node would be better. However i >>>>found this to slow it down considerably. To test my theory, i changed it to >>>>plain depth and it perfored much better than normal. So, can someone explain why >>>>incrementing by depth was better than MAX_DEPTH - depth or this just some quirk >>>>with my implementation/test positions? Also if someone has any ideas as to a >>>>better incremental? >>>> >>>>2. What is a history move? why is it different from a killer move? >>>> >>>>Thanks. >>> >>> >>>I'm not sure I follow what you are doing. First, an explanation of how they >>>both work. >>> >>>1. Killers. when you fail high at a ply, or you search all moves and find >>>a new best move at a ply, you add that move to the killer list for that ply. >>>Usually this killer list is a list of two moves. Typically they both have a >>>"counter" and each time you go to add a move to the list and it is already >>>there, you increment the counter for that move instead. If it isn't in the >>>list, you replace the killer with the smallest counter. When you search, you >>>search the killer with the largest count, after captures and hash move. Note >>>that each ply has its own set of two moves + counters. So the idea of >>>incrementing by anything other than 1 makes no real sense since killers apply >>>to a specific ply only. >>> >>>2. History. Here you use a "global" type of list, but there are no real >>>moves in the history list, just counters. There are several ways to index >>>into the history table, and I won't really touch on those. But when a move >>>is best or causes a fail high, you increment the appropriate counter for that >>>move, and you generally want to increment by some constant that varies >>>inversely proportional to the depth. A selection sort is usually used to search >>>the move with the largest history value first, again after the hash and good >>>capture moves. >> >>OK, so what im doing is actually a History algorithm. I have tried two different >>increments: >>1. += MAX_DEPTH - Current Depth >>2. += Current Depth >> >>I expected the first one to be better (isnt this inversly proportional to >>depth?) as the closer to the root, the higher the score and the closer to the >>leaves, the lower the score. Remembering, the root is at depth 0. >> >>But my testing showed that the second increment was better and im not yet sure >>why. > >I suppose that MAX_DEPTH is a constant that is quite high. 100 or so? >You will increment with quite high amounts. Are you sure that you wont get >overflows that destroys your table? > >Another thing is that your increment are still linear. If you add in the range >85, 84 etc doesn't seem to make any differens compared to 5, 4 etc. > >value += MAX_DEPTH - Current_Depth*Current_Depth would change that >Maybe you could try something logaritmic: >value += Tab[Current_Depth] with Tab-values 25, 10 , 5 or something similar. > >/Peter Yes, MAX_DEPTH is 100 but im pretty sure there are no overflows. Could you explain whats wrong with a linear increment? Why would a parabolic or logarithmic increment be better?
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.