Author: Don Dailey
Date: 09:00:18 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
>
>
>Code snippet from the current (experimental) implementation:
>------------------------------------------------------------
>next_move:
> m = nextMove();
> if ((stp>2) && (depth>1) &&
> ((sdptr->material[COMPUTER]+sdptr->material[OPPONENT])>3600) &&
> (((m & (CAPTURE | PROMOTION | ENPASSANT))==0)
> )
> )
> {
> searchmove m2=stack[stp-1].lastmove;
> searchmove m3=stack[stp-2].lastmove;
> if ((m2.tosquare!=ILLEGAL) &&
> (m3.tosquare!=ILLEGAL) && // not after nullmove
> (m.from!=m3.to) && (m2.to!=m3.to) &&
> !sdptr->incheck && // not after check
> !stack[stp-1].sdptr->incheck && !stack[stp-2].sdptr->incheck
> )
> {
> // a move m is illogical if the attacktables of the from- and
> // to-squares of the move are unchanged by m2 and m3.
> // catab[square] contains a bit for every computerpiece
> // attacking square (oatab for every opponentpiece).
> if (!((catab[m.to]==stack[stp-1].scatab[m.to]) &&
> (stack[stp-1].scatab[m.to]==stack[stp-2].scatab[m.to])
> ) ) goto normal_search;
> if (!((catab[m.from]==stack[stp-1].scatab[m.from]) &&
> (stack[stp-1].scatab[m.from]==stack[stp-2].scatab[m.from])
> ) ) goto normal_search;
> if (!((oatab[m.to]==stack[stp-1].soatab[m.to]) &&
> (stack[stp-1].soatab[m.to]==stack[stp-2].soatab[m.to])
> ) ) goto normal_search;
> if (!((oatab[m.from]==stack[stp-1].soatab[m.from]) &&
> (stack[stp-1].soatab[m.from]==stack[stp-2].soatab[m.from])
> ) ) goto normal_search;
> // reduce searchdepth
> short r;
> if (depth>2) r=2; else r=1;
> doMove(m);
> value = -pvs( -alpha-1, -alpha, TRUE, partply, depth-r-1 );
> undoMove();
> // if the move fails low believe the result
> if (value<=alpha) goto next_move;
> }
> }
>normal_search: // search the move as usual
Frank,
I only have a minute but I wanted to thank you for the idea.
Your algorithm sounds useful. I can see some problems with it but
that means nothing, any selective algorithm is subject to problems.
It makes some sense and time (and more experimentation) will tell if
in fact it can be made to pay off. I hope to get some time to take a
look at it in more detail. Please keep us posted on your results, no
matter how it turns out.
For those of you reluctant to contribute ideas like this please don't
be. I think some may be afraid an idea may be proved to be silly or
show that you are naive. I think all the programmers will tell you
most of the things we experiment with do not work out. At least I
will tell you this.
- 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.