Author: Amir Ban
Date: 15:42:50 06/21/98
Go up one level in this thread
On June 21, 1998 at 09:02:51, Frank Schneider wrote: >Has anybody tried the idea described below? > >Almost all strong chessprograms are based on brute-force alpha-beta search. >It has proven difficult to use chessknowledge to recognize important or >less important variations during search. There are a some extensions that >are known to improve strength (chess-extensions, recapture-extensions,..) >and some heuristics that try to prune away unimportant parts of the >searchtree (nullmove, razoring). These heuristics are usually based on a >very 'basic' kind of chessknowledge. Nullmoves, as an example, exploit >the knowledge that it is usually a privilege to make a move. >I want to present another idea that I experimented with. So far the results >are at least interesting. > >The idea is based on the observation that most lines that a brute-force >program searches are illogical because there is no relationship between >the moves. There are many lines like 1. g2g4 xy 2. a2a4. 1. g2g4 could be >the beginning of a kingside attack, but 2. a2a4 is (usually) not part >of the plan and therefore illogical. >In my experiment I define a move m as 'unrelated' to previous moves m2 >and m3 if the the attacktables of m.to and m.from were not changed by >m2 and m3. I only test for illogic moves if enough material is on >the board, if there were no checks and if m is not a capture (see code >below). When the heuristic thinks that a move is 'illogical' it searches >the move with reduced searchdepth. If the returned score is above alpha >the move is searched again as usual, but if the score is below alpha >the next move is searched and some time was saved. > >The idea has been tested with a pre-alpha version of GromitChess 2.0 >using the WAC-testsuit, a private 100-position-suite and the 24 >Bratko-Kopec positions. >Results for the BK-Test are given below (using a K6/200): > >Ply correct time/s nodes >----------------------------------- >without heuristic: > 7 14 371 7508457 > 8 16 1218 24616834 > 9 16 4548 90870914 > >with heuristic: > 7 15 305 6308228 > 8 15 1008 20736540 > 9 16 2993 62041817 > >There seems to be a 15-30% decrease in nodes searched without affecting >the correct-moves too much. >WAC and the 100-position suite were searched to ply 6 (10% less nodes) >and 7 (20% less nodes) without changing the number of correct moves >found. >The implementation is still 'experimental' and I'm sure it could be >improved. > >Has anybody tried this before? Any comments? > > >Frank Schneider > > How does your rule apply to the Spanish ? e4 e5 Nf3 Nc6 Bb5 a6 Ba4 Nf6 O-O Be7. Seems that both white and black play illogical sequences where no move is related to the other. I think the definition of "logical" is too simple. Possibly, with effort, it can be improved, but may not work anyway because of this: Extensions and forward pruning are not about following "logical" lines but about getting a reliable eval for a line. I don't see an obvious reason why a "logical" line should be searched more deeply while an "illogical" line less deeply. Conceivably, you can stop the search of an excellent move after two plies, because the score is reliable enough, while you would need to search a terrible line to 12 plies to reach the conclusion that it is terrible. You may have discovered that depth reduction is in many cases a useful thing to do, and the justification you found for it is perhaps irrelevant. Evaluating such a heuristic with a test-suite is not a very sensitive or appropriate way. Amir
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.