Author: Frank Schneider
Date: 06:02:51 06/21/98
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
This page took 0.01 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.