** COMPUTER CHESS ** swap down evaluators vs capture search

[Jon Dart]

In article <384l4d...@life.ai.mit.edu> de...@great-grain.ai.mit.edu (Deniz Yuret) writes:
>a simple swap down evaluator is blind to indirect attacks like pins and
>discoveries. However capture search is not perfect either. It is blind to
>simple forks for example. Obviously the frequency with which these special
>positions (pins, forks etc) occur would largely effect the performance of these
>two approaches. Does any one have any data, statistics, experience on the
>relative performance of these approaches? Can the speed gain offset accuracy
>loss?
>

My chess program (Arasan) first does some simple tests to determine if a
capture may be profitable (e.g. pawn takes knight generally is. It
doesn't matter if the knight is defended or not. Similarly, attacks
on undefended pieces pass this test). If this test does not succeed
in identifying the move as profitable, it calls a more elaborate swap-
down evaluator, which, however, is still not smart enough to handle pins.

This is reasonably time-efficient, but clearly not very accurate. I
have tried smarter swap-down algorithms, but it can get pretty complex.
The main problem is that you need to determine indirect attacks on
a square, which I have found expensive to compute either statically or
incrementally. If anyone has a killer algorithm for this, let me know!
Also, sdding knowledge about pins and discoveries still leaves holes and
may wind up costing more than the search you would need to find these
things.

The biggest tactical problem I have found is vulnerability to checks.
It is easy to tell when the side to move is in check. It is harder to
compute when a move would cause check (without actually making it). But
these moves are important and should ideally be included in a forward
pruning algorithm.

--Jon
--
--
-- Jon Dart, Rational Software Corp., jd...@rational.com
-- 2800 San Tomas Expy., Santa Clara CA 95051 tel: (408)-496-3656

[Deniz Yuret]

Swap down evaluators are one simple way to approximate capture search. The
program only looks at the current position and attack table, and tries to
simulate the available exchanges to see if one side has an advantage. This is
obviously much faster than capture search, however it is less accurate. For
example unless you include so much hair that it is esentially a capture search,

a simple swap down evaluator is blind to indirect attacks like pins and
discoveries. However capture search is not perfect either. It is blind to
simple forks for example. Obviously the frequency with which these special
positions (pins, forks etc) occur would largely effect the performance of these
two approaches. Does any one have any data, statistics, experience on the
relative performance of these approaches? Can the speed gain offset accuracy
loss?

best,
deniz

--

Deniz Yuret
MIT Artificial Intelligence Laboratory tel: (617) 253-6247
545 Technology Square, Room: NE43-815 fax: (617) 253-5060
Cambridge, MA 02139, USA e-mail: de...@ai.mit.edu
Deniz Yuret
MIT Artificial Intelligence Laboratory tel: (617) 253-6247
545 Technology Square, Room: NE43-815 fax: (617) 253-5060
Cambridge, MA 02139, USA e-mail: de...@ai.mit.edu