Author: Tom Kerrigan
Date: 14:21:02 05/31/00
Go up one level in this thread
On May 31, 2000 at 16:29:48, Roberto Waldteufel wrote: >On May 31, 2000 at 13:00:07, Tom Kerrigan wrote: > >>On May 31, 2000 at 12:24:20, Roberto Waldteufel wrote: >> >>>On May 31, 2000 at 12:01:22, Ed Schröder wrote: >>> >>>>On May 31, 2000 at 04:16:44, Roberto Waldteufel wrote: >>>> >>>>>I am experimenting with some move ordering heuristics and I would like to know >>>>>for comparison what percentage of moves proposed and searched by the killer >>>>>and/or history heuristic lead to cut-offs in other programs. Many thanks in >>>>>advance for any info >>>>> >>>>>Roberto >>>> >>>>It depends. It will strongly depend on what you already have in your >>>>program. If you (for instance) don't have "the best move from the hash >>>>table" in your program the "killer heuristic" will give you a lot more >>>>than if you already have the "best move from the hash table". >>>> >>>>But implement a 2-slot "killer heuristic" by all means. It should give >>>>you a clear speed-up. Maybe just 5-10%, maybe a lot more. As already >>>>said, it depends. >>>> >>>>Ed >>> >>>Hi Ed, >>> >>>Thank you for my response. Perhaps I should have made myself more clear - what I >>>am doing is experimenting with a new heuristic that suggests a move to try for a >>>quick cut-off. I wanted to know how effective it was compared to the commonly >>>used methods for doing this. I do try the hash table move first, then the move >>>proposed by my test heuristic if the hash move did not produce a cut-off. My >>>heuristic generates a cut-off about 65%-75% of all the times it is invoked. It >>>is meant to be an alternative to history/killer heuristic for closing move >>>prediction, but I am not sure how well this figure compares to the well tried >>>methods. >> >>Make sure you're also searching captures before anything else. >> >>-Tom > > >My currant move order is:- > >1)Null Move > >2)Hash move > >3)My heuristic move (if legal and different from (2)) > >4)Captures in MVV/LVA order > >5)Non-capturing pawn promotions > >6)En Passant captures > >7)Castling > >8)Non-capture Moves with all pieces except the king and pawns > >9)Non-capture king moves > >10)Non-capture/Non-Promoting Pawn moves > >The heuristic move is not available in the immediate successor to a null move, >but is available at all other nodes except for the quiescence search and nodes >where the side to move is in check. It is sometimes the same as the hash move >anyway (so not tried a second time), since the move will be tried first if no >hash move exists, and will then be the hash move (assuming a cutoff generated) >in subsequent iterations, so that it is most useful when either there is no hash >move in the table or the hash move fails to generate a cut-off. I should add >that my program uses MTDF, so it revisits nodes and has a correspondingly high >hit rate for hash moves. Also the heuristic move can be (and often is) a capture >or promotion. I don't have killer tables, and I wondered how good my heuristic >was compared to killer tables. Would ordinary killers produce cutoffs in more >than 65%-75% of nodes where the hash move has not already done so? This is sort of a loaded question because killer moves should not be searched before captures. Killer moves are pretty trivial to implement, BTW. There's no reason not to use them. You probably also want to be using the history heuristic. To measure search efficiency, what I like to do is run all of the BK positions to a fixed depth. You can compare node counts between versions of your program to get a good approximation of your speedup. -Tom
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.