Author: blass uri
Date: 10:38:04 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.
It is interesting to see what is the probability a move of a grandmaster
or a move of a program will be illogical by your definition.
a good definition of illogical moves should give a low probabilty.
Uri
>
>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 }
> }
>normal_search: // search the move as usual
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.