25,161
edits
Changes
Created page with "'''Home * Search * Selectivity * SEX Algorithm''' FILE:Sexual cycle.svg|border|right|thumb|Life cycle of sexually reproducing organisms <ref>[https://..."
'''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * SEX Algorithm'''
[[FILE:Sexual cycle.svg|border|right|thumb|Life cycle of sexually reproducing organisms <ref>[https://commons.wikimedia.org/wiki/File:Sexual_cycle.svg The sexual cycle], image by [http://commons.wikimedia.org/wiki/User:Stannered Stannered], March 30, 2007, [https://en.wikipedia.org/wiki/Sex Sex from Wikipedia]</ref> ]]
The '''SEX Algorithm''' was a proposal by [[David Levy]], [[David Broughton]] and [[Mark Taylor]] to apply [[Extensions#FractionalExtensions|fractional extensions]] and [[Reductions|reductions]]. It was introduced in 1989 in the [[ICGA Journal]] paper ''The SEX Algorithm in Computer Chess'' ('''S'''earch '''EX'''tension), applied in programs and [[Dedicated Chess Computers|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 [[Iterative Deepening|ID framework]] was 7 or 8, SEX implemented fractional [[Reductions|reductions]] and even a kind of [[Late Move Reductions|LMR]] in [[Cyrus 68K]], considering early [[Quiet Moves|non-tactical moves]] from a evaluated sorted [[Move List|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|tactical moves]] such as [[Check|checks]] and [[Captures|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 [[Static Exchange Evaluation|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 Phases|game phase]] (eight phases 0..7), [[Depth|depth]], [[Killer Heuristic|Killer heuristic]], [[Parity Pruning]], two separate SEX-values for both sides, [[Checkmate|Mate threats]] and [[Mate at a Glance]].
=Excerpts=
from ''The SEX Algorithm in Computer Chess'' 1989 <ref>[[David Levy]], [[David Broughton]], [[Mark Taylor]] ('''1989'''). ''The SEX Algorithm in Computer Chess''. [[ICGA Journal#12_1|ICCA Journal, Vol. 12, No. 1]]</ref> :
==The Foundation of the Search Algorithm==
If a path in the [[Search Tree|search tree]] consists of the [[Moves|moves]] M<span style="vertical-align: sub;">i</span>, M<span style="vertical-align: sub;">ij</span>, M<span style="vertical-align: sub;">ijk</span>, with the resulting [[Chess Position|position]] being a [[Terminal Node|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 <ref>The '''swap-off value''' of a [[Moves|move]] is defined by its [[Static Exchange Evaluation|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</ref> 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|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 Mark V|Chess Champion MK V]], a dedicated chess-computer which won the Commercial World Championship for microcomputers at [[WMCCC 1981|Travemünde, West Germany, in 1981]]. Most of the refinements discussed above were first "published" with the launch, by [https://en.wikipedia.org/wiki/Parker_Brothers Parker Brothers], of a program for the [[IBM PC]]. <ref>[[Parker Chess]] developed by [[David Broughton]]</ref>
...
==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|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. <ref>[http://www.schach-computer.info/wiki/images/5/56/ICCA1989_12_1_part.jpg ICCA1989 12 1 part.jpg] from [http://www.schach-computer.info/wiki/index.php/Hauptseite_En Schachcomputer.info Wiki]</ref>
* [[Chess Champion Mark V]] - (1981): Dedicated, commercially available chess computer. Manufactured by [[Saitek|Scisys-W Ltd.]], Hong Kong. [[Z80]] [[Philidor|development version]] programmed by [[David Broughton|Broughton, D.C.]] Program translated to [[6502]] [[Assembly]] for production version by [[Mark Taylor|Taylor M.]]
* [[Cyrus 68K]] - (1986): [[68000]] based chess program. Briefly available commercially as the [[CXG Sphinx|Sphinx]] manufactured by [[Newcrest Technology|Newcrest Technology Ltd.]], Hong Kong. Programmed in 68000 assembler by [[Mark Taylor|Taylor M.]]
* [[Parker Chess]] - (1983): Commercially available chess program on disk for [[IBM PC]]. Manufactured by [https://en.wikipedia.org/wiki/Parker_Brothers Parker Brothers Inc., USA]. Programmed in [[8086]] assembler by [[David Broughton|Broughton, D.C.]]
=See also=
* [[Extensions#FractionalExtensions|Fractional Extensions]]
* [[Late Move Reductions]]
=Publications=
==Algorithm==
* [[David Levy]], [[David Broughton]], [[Mark Taylor]] ('''1989'''). ''The SEX Algorithm in Computer Chess''. [[ICGA Journal#12_1|ICCA Journal, Vol. 12, No. 1]]
* [[Yoshimasa Tsuruoka]], [[Daisaku Yokoyama]], [[Takashi Chikayama]] ('''2002'''). ''[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.9258 Game-Tree Search Algorithm based on Realization Probability]''. [[ICGA Journal#25_3|ICGA Journal, Vol. 25, No. 3]]
* [[David Levy]] ('''2002'''). ''[http://ilk.uvt.nl/icga/journal/contents/content25-3.htm#SOME%20COMMENTS%20ON%20REALIZATION%20PROBABILITIES SOME COMMENTS ON REALIZATION PROBABILITIES AND THE SEX ALGORITHM]''. [[ICGA Journal#25_3|ICGA Journal, Vol. 25, No. 3]]
==Sex==
* [[David Levy]] ('''2007'''). ''[https://en.wikipedia.org/wiki/Love_and_Sex_with_Robots Love and Sex With Robots]: The Evolution of Human-Robot Relationships''. [https://en.wikipedia.org/wiki/HarperCollins HarperCollins]
=External Links=
* [https://en.wikipedia.org/wiki/Sex Sex from Wikipedia]
* [https://en.wikipedia.org/wiki/Sexual_reproduction Sexual reproduction from Wikipedia]
* [https://en.wikipedia.org/wiki/Evolution_of_sexual_reproduction Evolution of sexual reproduction from Wikipedia]
* [https://en.wikipedia.org/wiki/Fertilisation Fertilisation from Wikipedia]
* [https://en.wikipedia.org/wiki/Meiosis Meiosis from Wikipedia]
* [https://en.wikipedia.org/wiki/Ploidy Ploidy from Wikipedia]
* [https://en.wikipedia.org/wiki/Sex_%28book%29 Sex (book) from Wikipedia]
* [https://en.wikipedia.org/wiki/Everything_You_Always_Wanted_to_Know_About_Sex*_%28*But_Were_Afraid_to_Ask%29 Everything You Always Wanted to Know About Sex* (*But Were Afraid to Ask) - Wikipedia]
* [https://en.wikipedia.org/wiki/James_Brown James Brown] - [https://en.wikipedia.org/wiki/Get_Up_%28I_Feel_Like_Being_a%29_Sex_Machine Sex Machine], 1971, [https://en.wikipedia.org/wiki/Rai_Storia Rai Storia], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=AVZwejaNmbw|alignment=left|valignment=top}}
=References=
<references />
'''[[Selectivity|Up one level]]'''
[[FILE:Sexual cycle.svg|border|right|thumb|Life cycle of sexually reproducing organisms <ref>[https://commons.wikimedia.org/wiki/File:Sexual_cycle.svg The sexual cycle], image by [http://commons.wikimedia.org/wiki/User:Stannered Stannered], March 30, 2007, [https://en.wikipedia.org/wiki/Sex Sex from Wikipedia]</ref> ]]
The '''SEX Algorithm''' was a proposal by [[David Levy]], [[David Broughton]] and [[Mark Taylor]] to apply [[Extensions#FractionalExtensions|fractional extensions]] and [[Reductions|reductions]]. It was introduced in 1989 in the [[ICGA Journal]] paper ''The SEX Algorithm in Computer Chess'' ('''S'''earch '''EX'''tension), applied in programs and [[Dedicated Chess Computers|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 [[Iterative Deepening|ID framework]] was 7 or 8, SEX implemented fractional [[Reductions|reductions]] and even a kind of [[Late Move Reductions|LMR]] in [[Cyrus 68K]], considering early [[Quiet Moves|non-tactical moves]] from a evaluated sorted [[Move List|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|tactical moves]] such as [[Check|checks]] and [[Captures|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 [[Static Exchange Evaluation|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 Phases|game phase]] (eight phases 0..7), [[Depth|depth]], [[Killer Heuristic|Killer heuristic]], [[Parity Pruning]], two separate SEX-values for both sides, [[Checkmate|Mate threats]] and [[Mate at a Glance]].
=Excerpts=
from ''The SEX Algorithm in Computer Chess'' 1989 <ref>[[David Levy]], [[David Broughton]], [[Mark Taylor]] ('''1989'''). ''The SEX Algorithm in Computer Chess''. [[ICGA Journal#12_1|ICCA Journal, Vol. 12, No. 1]]</ref> :
==The Foundation of the Search Algorithm==
If a path in the [[Search Tree|search tree]] consists of the [[Moves|moves]] M<span style="vertical-align: sub;">i</span>, M<span style="vertical-align: sub;">ij</span>, M<span style="vertical-align: sub;">ijk</span>, with the resulting [[Chess Position|position]] being a [[Terminal Node|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 <ref>The '''swap-off value''' of a [[Moves|move]] is defined by its [[Static Exchange Evaluation|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</ref> 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|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 Mark V|Chess Champion MK V]], a dedicated chess-computer which won the Commercial World Championship for microcomputers at [[WMCCC 1981|Travemünde, West Germany, in 1981]]. Most of the refinements discussed above were first "published" with the launch, by [https://en.wikipedia.org/wiki/Parker_Brothers Parker Brothers], of a program for the [[IBM PC]]. <ref>[[Parker Chess]] developed by [[David Broughton]]</ref>
...
==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|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. <ref>[http://www.schach-computer.info/wiki/images/5/56/ICCA1989_12_1_part.jpg ICCA1989 12 1 part.jpg] from [http://www.schach-computer.info/wiki/index.php/Hauptseite_En Schachcomputer.info Wiki]</ref>
* [[Chess Champion Mark V]] - (1981): Dedicated, commercially available chess computer. Manufactured by [[Saitek|Scisys-W Ltd.]], Hong Kong. [[Z80]] [[Philidor|development version]] programmed by [[David Broughton|Broughton, D.C.]] Program translated to [[6502]] [[Assembly]] for production version by [[Mark Taylor|Taylor M.]]
* [[Cyrus 68K]] - (1986): [[68000]] based chess program. Briefly available commercially as the [[CXG Sphinx|Sphinx]] manufactured by [[Newcrest Technology|Newcrest Technology Ltd.]], Hong Kong. Programmed in 68000 assembler by [[Mark Taylor|Taylor M.]]
* [[Parker Chess]] - (1983): Commercially available chess program on disk for [[IBM PC]]. Manufactured by [https://en.wikipedia.org/wiki/Parker_Brothers Parker Brothers Inc., USA]. Programmed in [[8086]] assembler by [[David Broughton|Broughton, D.C.]]
=See also=
* [[Extensions#FractionalExtensions|Fractional Extensions]]
* [[Late Move Reductions]]
=Publications=
==Algorithm==
* [[David Levy]], [[David Broughton]], [[Mark Taylor]] ('''1989'''). ''The SEX Algorithm in Computer Chess''. [[ICGA Journal#12_1|ICCA Journal, Vol. 12, No. 1]]
* [[Yoshimasa Tsuruoka]], [[Daisaku Yokoyama]], [[Takashi Chikayama]] ('''2002'''). ''[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.9258 Game-Tree Search Algorithm based on Realization Probability]''. [[ICGA Journal#25_3|ICGA Journal, Vol. 25, No. 3]]
* [[David Levy]] ('''2002'''). ''[http://ilk.uvt.nl/icga/journal/contents/content25-3.htm#SOME%20COMMENTS%20ON%20REALIZATION%20PROBABILITIES SOME COMMENTS ON REALIZATION PROBABILITIES AND THE SEX ALGORITHM]''. [[ICGA Journal#25_3|ICGA Journal, Vol. 25, No. 3]]
==Sex==
* [[David Levy]] ('''2007'''). ''[https://en.wikipedia.org/wiki/Love_and_Sex_with_Robots Love and Sex With Robots]: The Evolution of Human-Robot Relationships''. [https://en.wikipedia.org/wiki/HarperCollins HarperCollins]
=External Links=
* [https://en.wikipedia.org/wiki/Sex Sex from Wikipedia]
* [https://en.wikipedia.org/wiki/Sexual_reproduction Sexual reproduction from Wikipedia]
* [https://en.wikipedia.org/wiki/Evolution_of_sexual_reproduction Evolution of sexual reproduction from Wikipedia]
* [https://en.wikipedia.org/wiki/Fertilisation Fertilisation from Wikipedia]
* [https://en.wikipedia.org/wiki/Meiosis Meiosis from Wikipedia]
* [https://en.wikipedia.org/wiki/Ploidy Ploidy from Wikipedia]
* [https://en.wikipedia.org/wiki/Sex_%28book%29 Sex (book) from Wikipedia]
* [https://en.wikipedia.org/wiki/Everything_You_Always_Wanted_to_Know_About_Sex*_%28*But_Were_Afraid_to_Ask%29 Everything You Always Wanted to Know About Sex* (*But Were Afraid to Ask) - Wikipedia]
* [https://en.wikipedia.org/wiki/James_Brown James Brown] - [https://en.wikipedia.org/wiki/Get_Up_%28I_Feel_Like_Being_a%29_Sex_Machine Sex Machine], 1971, [https://en.wikipedia.org/wiki/Rai_Storia Rai Storia], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=AVZwejaNmbw|alignment=left|valignment=top}}
=References=
<references />
'''[[Selectivity|Up one level]]'''
