Author: blass uri
Date: 21:12:22 06/21/98
Go up one level in this thread
On June 21, 1998 at 21:23:22, Don Dailey wrote: >On June 21, 1998 at 18:42:50, Amir Ban wrote: > >>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 > > >Hi Amir, > >One of us did not understand the heuristic. I think he should >explain it a little better because I am unclear about the details. >(FRANK, if you are listening ...) > >But, by what I (thought) I understood then: > >1. e4 e5 >2. Nf3 (attacks the square black just moved to) >2. ... Nc6 (defends the square the last move attacked) >3. Bb5 (attacked the last piece that moved) >4. ... a6 (attacks the last piece moved) >5. Ba4 (moves piece just attacked) >5. ... Nf6 (-- NO DIRECT RELATION but attacks d6 which the > bishop attacks through the knight) should be attack d7 >... etc. I understand you mean 6.0-0 (no direct relation but attacks d1 which the bishop in a4 attacks through the pawn c2). > > >You mentioned that the real goal was to get the most reliable >evaluation which I agree with. I believe (in the spirit of >what Frank is trying to do) this is quite consistant with that >goal. Whether it works or can be made to work is an open >question (at least to me) but it may be that your intuition >on this is stronger. I cannot dismiss it yet without taking >a closer look. > >This stuff is VERY similar to some stuff one of our team members >is experimenting with. We get a nice node reduction for free, >but the implementation reduces our nodes per second drastically. >Our experiences with this gives me reason to believe something >like what Frank is experimenting with has a chance to pay off. > >I definitely agree with you on the test suites. My experience >has been that they have no value at all for evaluating how good >the chess program is, but I use them quite extensively >because they have a lot of value for evaluating the behavior >of various algorithms. When it comes time to really find out >if some change really improves the program, other methods must >be used. I have this idea that a few of the programmers use >problem sets to evaluate their programs since it is by far the >simplest thing to do and I believe this may be a serious mistake. > >- Don
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.