SEX Algorithm

From Chessprogramming wiki
Jump to: navigation, search

Home * Search * Selectivity * SEX Algorithm

Life cycle of sexually reproducing organisms [1]

The SEX Algorithm was a proposal by David Levy, David Broughton and Mark Taylor to apply fractional extensions and reductions. It was introduced in 1989 in the ICGA Journal paper The SEX Algorithm in Computer Chess (Search EXtension), applied in programs and dedicated computers developed by Intelligent Software in the 80s. Since "uninteresting moves" were decremented by up to 21 (forward moves) or 24 (backward moves), and the depth increment of the ID framework was 7 or 8, SEX implemented fractional reductions and even a kind of LMR in Cyrus 68K, considering early non-tactical moves from a evaluated sorted move list by a moderate SX decrement, and to determine the SXDEC values for its non-tactical siblings on the basis of their score differences. Forced tactical moves such as checks and captures were decremented by 3 to 7, and therefor extended by fractions of a ply, while late non-tactical moves were reduced by up to two and some fractional plies.

Beside static move properties and SEE, various other considerations were tried over the years from 1981 until 1988 to improve the algorithm and to distinguish between interesting and uninteresting moves, including game phase (eight phases 0..7), depth, Killer heuristic, Parity Pruning, two separate SEX-values for both sides, Mate threats and Mate at a Glance.

Excerpts

from The SEX Algorithm in Computer Chess 1989 [2] :

The Foundation of the Search Algorithm

If a path in the search tree consists of the moves Mi, Mij, Mijk, with the resulting position being a terminal node, then

P(Mi) * P(Mij) * P(Mijk)

is the probability that a terminal node in that path is the terminal node in the principal continuation. Therefor

log[P(Mi)] + log[P(Mij)] + log[P(Mijk)]

is an appropriate additive measure for the "interestingness" of the terminal node on this path.

The Measurement of "Interestingness"

Our first attempts to formalize this idea were in 1981 when one of us (David Broughton) replaced the usual integer depth (which simply controlled the maximum ply depth) with an integer SX. The SX parameter started out at the root node with some positive value, in a similar way to maximum depth, but instead of being decremented by one at each ply it would be decremented by a number determined by the type (or category) of move just made in the tree. When SX was decremented below zero this signaled the end of the search, except for the usual terminal node evaluations. ... Later we designed a 68000 program called Cyrus 68K, written by one of us (Mark Taylor), which evaluated and sorted all the moves from a node being expanded: we used these evaluations to determine the SXDEC for moves that were non-tactical. An obvious way to accomplish this is to assign the "best" (i.e., highest-scoring) non-tactical move a low SXDEC and to determine the SXDEC values for its non-tactical siblings on the basis of the difference in score among them. ...

Refinements

An important development of the idea was to add further categories of a move that depended on the non-swap-off [3] value of a move in relation to the alpha-beta window. The basic idea was that moves which produced non-swap-off scores that were above the window were considered to be interesting, and it was left to deeper analysis to determine whether of not the move was easily refuted. Although some improvements could be made here, the idea led to control and decision problems at the root, for it violated one of the major principles of the alpha-beta pruning method, namely that the value of a move is independent of the window used for its analysis. ... The early work on SX was designed for a Z80 based system that was later translated into 6502 assembler and used in the Chess Champion MK V, a dedicated chess-computer which won the Commercial World Championship for microcomputers at Travemünde, West Germany, in 1981. Most of the refinements discussed above were first "published" with the launch, by Parker Brothers, of a program for the IBM PC. [4] ...

The Second Generation of the SEX Algorithm

A second generation of the search extension algorithm was developed during the period 1985-1988. Many of the original ideas were used but we tried to eliminate certain obvious deficiencies and to make the intelligence in the program more sophisticated. We came up with a number of new ideas and tested them in a 68000-based program called Cyrus 68K. In general the results were rather encouraging, and we now feel that there is no longer a need to be shy about our work, hence the revised acronym for the algorithm and the renaming of the key variables to SEX and SEXDEC. ...

The SEX Horizon Effect

When looking for a deep combination the program would sometimes terminate the true principal variation prematurely as a result of examining uninteresting moves for the defending side. These uninteresting moves would cause big values of SXDEC which would often wipe out all the remaining SX needed by the program to prove the soundness of the combination.

We overcome this problem in the SEX algorithm by using two separate values of SEX, one for each side. If the value of SEX for either side (or for both sides) remains positive then the search continues. This means that a combination will be found even of the defending side makes uninteresting moves, because the attacking side will score a series of low values for SEXDEC. This change produced a clear improvement in the performance of the program.

Chipography

Since the authors are claiming some originality in the ideas represented in this paper, the following "chipography" is provided. This makes reference to various commercially available chess programs. Anyone doubting our claims as to the date of origination of these ideas should feel free to disassemble the object code in the products and confirm the authors' claims by examining the resulting source code. [5]

See also

Publications

Algorithm

Sex

External Links

References

  1. The sexual cycle, image by Stannered, March 30, 2007, Sex from Wikipedia
  2. David Levy, David Broughton, Mark Taylor (1989). The SEX Algorithm in Computer Chess. ICCA Journal, Vol. 12, No. 1
  3. The swap-off value of a move is defined by its SEE value. The non-swap-off value of a move is the value of the position arising after that move with no exchanging sequences evaluated
  4. Parker Chess developed by David Broughton
  5. ICCA1989 12 1 part.jpg from Schachcomputer.info Wiki

Up one level