25,161
edits
Changes
Created page with "'''Home * Engines * Lachex''' FILE:Lachex.JPG|border|right|thumb|380px|link=http://en.wikipedia.org/wiki/Los_Alamos_National_Laboratory| Los Alamos <ref>[..."
'''[[Main Page|Home]] * [[Engines]] * Lachex'''
[[FILE:Lachex.JPG|border|right|thumb|380px|link=http://en.wikipedia.org/wiki/Los_Alamos_National_Laboratory| Los Alamos <ref>[https://en.wikipedia.org/wiki/Los_Alamos_National_Laboratory Los Alamos National Laboratory from Wikipedia]</ref> Chess Experiment ]]
'''Lachex''', <br/>
an Acronym for [[Los Alamos National Laboratory|Los Alamos]] Chess Experiment, is the chess program developed by [[Burton Wendroff]] and [[Tony Warnock]]. Lachex was a mainframe program, playing on a [[Cray X-MP|Cray X-MP 48]], and was written in [[Fortran]] and [[Assembly]], performing some kind of full width [[Parallel Search|parallel]] [[Principal Variation Search|principal variation search]] inside an [[Iterative Deepening|iterative deepening framework]]. Also, Lachex already implemented presumably none [[Recursion|recursive]] [[Null Move Pruning|null move pruning]], as mentioned in the [[Lachex#Description|description]] from the [[WCCC 1989]] booklet.
=Tournament Play=
Lachex played two [[World Computer Chess Championship|World Computer Chess Championships]] <ref>[https://www.game-ai-forum.org/icga-tournaments/program.php?id=227 Lachex's ICGA Tournaments]</ref>, the [[WCCC 1986]] and [[WCCC 1992]], and four [[ACM North American Computer Chess Championship|ACM North American Computer Chess Championships]], [[ACM 1985]], [[ACM 1986]], [[ACM 1987]] and [[ACM 1991]]. It was runner up in 1986 only losing the eventual winner [[Belle]].
=Selected Games=
[[WCCC 1986]], round 1, [[Ostrich]] - [[Lachex]] <ref>[https://www.game-ai-forum.org/icga-tournaments/round.php?tournament=62&round=1&id=3 Cologne 1986 - Chess - Round 1 - Game 3 (ICGA Tournaments)]</ref>
<pre>
[Event "WCCC 1986"]
[Site "Cologne, Germany"]
[Date "1986.06.11"]
[Round "1"]
[White "Ostrich"]
[Black "Lachex"]
[Result "0-1"]
1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Bxc6 dxc6 5.d4 exd4 6.Qxd4 Qxd4 7.Nxd4 Nf6 8.O-O
Bc5 9.c3 O-O 10.f3 Bd6 11.Bg5 c5 12.Bxf6 gxf6 13.Ne2 Be6 14.Nd2 Rfd8 15.Rfd1 Kh8
16.a4 b5 17.axb5 axb5 18.Rxa8 Rxa8 19.g3 f5 20.Kf2 Ra2 21.Rb1 Bd7 22.Ke3 Ra8
23.Re1 Kg8 24.f4 Re8 25.Kd3 fxe4+ 26.Nxe4 Bf5 27.Nc1 Bf8 28.b3 c4+ 29.bxc4 bxc4+
30.Kxc4 Bxe4 31.Rd1 c6 32.Rd2 Bd5+ 33.Kd3 Bc5 34.Re2 Rb8 35.c4 Be6 36.Kc3 Bb4+
37.Kc2 Bxc4 38.Re5 f6 39.Rf5 Rd8 40.Rxf6 Rd2+ 41.Kb1 Bc3 0-1
</pre>
<span id="Description"></span>
=Description=
from the [[WCCC 1989]] booklet <ref>[http://www.computerhistory.org/chess/full_record.php?iid=doc-434fea055cbb3 Kings Move - Welcome to the 1989 AGT World Computer Chess Championship.] Edmonton, Alberta, Canada, Courtesy of [[Peter Jennings]], from [[The Computer History Museum]], [http://archive.computerhistory.org/projects/chess/related_materials/text/3-1%20and%203-2%20and%203-3%20and%204-3.1989_WCCC/1989%20WCCC.062302028.sm.pdf pdf]</ref>:
Lachex is specifically designed for the architecture of the Cray XMP and YMP series of machines. The highly repetitive parts of the program are written in [[Assembly|assembly language]], the rest in [[Fortran]]. Low level parallelism is achieved by extensive use of vector functional units and [https://en.wikipedia.org/wiki/Pipeline_%28computing%29 pipelining]. High level parallelism is obtained by means of multiple independent processors splitting up the search using a self-scheduling algorithm and communicating with each other through a large common [[Memory|memory]].
The search is basically [[Alpha-Beta|alpha-beta]] with [[Iterative Deepening|iterative deepening]]. In the initial depth one search each [[Root|root]] move is actually [[Score|scored]] and the list of moves ordered accordantly. [[Best Move|Best moves]] at subsequent iterations are moved to the top of the list. [[Scout|Scouting]] is used at [[Ply|ply]] one only - the first move in the list is scored and the remaining moves are tested with [[Null Window|minimal window]]. [[Pruning|Forward pruning]] is done with a positional estimator at nodes below the horizon and with the [[Null Move Pruning|null move algorithm]] above. Moves out of [[Check|check]] above the horizon [[Check Extensions|extend]] the [[Depth|search depth]] for that path by one, but by two if the check is [[Discovered Check|discovered]] or [[Double Check|double]]. [[Quiescence Search|Selective searches]] below the horizon include [[Captures|captures]], [[Promotions|promotions]], [[Castling|castling]], and some checking moves.
Lachex spends 1/3 of its time [[Move Generation|generating moves]], 1/3 doing bookkeeping, and 1/3 [[Evaluation|evaluating]] [[Leaf Node|leaf nodes]]. The evaluation function is symmetric wherever possible. [[Mobility]], [[Pawn Structure|pawn structure]], [[King Safety|king safety]], [[Piece-Square tables|piece placement]] and other features make up the evaluation function. Some strategy is incorporated at the root by shifting the minimal window to bias certain types of moves. There is a [[Transposition Table|transposition table]] which can be a big as 32 million positions, on a 64 million word machine.
==Board Representation==
Lachex used following [[Pieces#PieceCoding|piece enumeration scheme]] from the [[Initial Position|initial position]], which does not change during the cause of the game: the a1-rook was labeled with 1, b1-knight with 2, a2-pawn with 9, the a8-rook with 17 and the h7-pawn with 32. Beside a [[Bitboard Board-Definition|bitboard board-definition]] using 12 piece [[Bitboards|bitboards]] and [[Occupancy|occupancy]] as union set, Lachex used a redundant [[8x8 Board|8x8 board array]], containing those 1..32 piece-codes, but zero for empty squares, and [[Piece-Lists|piece-arrays]] containing [[Squares|squares]] and associated [[Pieces#PieceTypeCoding|piece-types]] or zero if the piece is missing. A so called ''INC-Array'' indexed by [[Origin Square|origin]], [[Target Square|target square]] and [[Pieces#PieceTypeCoding|piece type]] (excluding color, but white and black pawn as distinct types) was used in direct [[Move Generation|move generation]], similar as described in ''[[Square Attacked By#InBetween|In Between]] and [[Square Attacked By#AttackedByPieceOnSquare|Attacked by Piece on Square]]''.
Further, something which reminds on [[Fill Algorithms|fill algorithms]] like [[Dumb7Fill]] was used as described by Wendroff <ref>[[Burton Wendroff]] ('''1985'''). ''Attack Detection and Move Generation on the X-MP/48.'' [[ICGA Journal#8_2|ICCA Journal, Vol. 8, No. 2]]</ref> :
There are several methods for generating the moves of the long range pieces. The method we have had the most success with on Cray machines preceding the X-MP/48 finds the to-squares closest to the home square, and then by a complicated sequence of shifts and boolean operations simultaneously continues these moves in the appropriate directions.
==BCH Hashing==
To index and lock [[Hash Table#SearchTables|search tables]], especially the [[Transposition Table|transposition table]], Lachex utilized signatures of chess positions by [[BCH Hashing]] based on [https://en.wikipedia.org/wiki/BCH_code BCH-Code] as used in [https://en.wikipedia.org/wiki/Error_detection_and_correction Error detection and correction], otherwise [[Incremental Updates|incrementally updated]] similar than signatures from [[Zobrist Hashing]]. Lachex used a BCH signature length of 81 (or more) bits to protect 16 bits from the full position string of 749 (64*12 - 2*2*8 + 4 + 8 + 1) bits, which is sufficient to avoid [[Transposition Table#KeyCollisions|collisions]] within an 8 ply search. In their paper on ''Search Tables'' <ref>[[Tony Warnock]], [[Burton Wendroff]] ('''1988'''). ''Search Tables in Computer Chess''. [[ICGA Journal#11_1|ICCA Journal, Vol. 11, No. 1]]</ref> , Warnock and Wendroff further elaborate on [[Alpha-Beta|alpha-beta]] [[Search Instability|inconsistencies]], and that with the introduction of search tables, depending on the implementation, alpha-beta may not be order-independent. They refer implementations given by [[Tony Marsland]] <ref>[[Tony Marsland]] ('''1986'''). ''A Review of Game-Tree Pruning.'' [[ICGA Journal#9_1|ICCA Journal, Vol. 9, No. 1]]</ref> and [[Harry Nelson]] <ref>[[Harry Nelson]] ('''1985'''). ''Hash Tables in [[Cray Blitz]]''. [[ICGA Journal#8_1|ICCA Journal, Vol. 8, No. 1]]</ref>.
=See also=
* [[ACM 1991#KnightPromotion|ACM 1991 | Mephisto - Lachex]]
* [[Various Classifications#Acronym|Acronym]]
=Publications=
* [[Burton Wendroff]] ('''1985'''). ''Attack Detection and Move Generation on the X-MP/48.'' [[ICGA Journal#8_2|ICCA Journal, Vol. 8, No. 2]]
* [[Tony Warnock]], [[Burton Wendroff]] ('''1988'''). ''Search Tables in Computer Chess''. [[ICGA Journal#11_1|ICCA Journal, Vol. 11, No. 1]]
=External Links=
* [https://www.game-ai-forum.org/icga-tournaments/program.php?id=227 Lachex's ICGA Tournaments]
* [http://www.365chess.com/players/Lachex Lachex chess games] from [http://www.365chess.com/ 365Chess.com]
=References=
<references />
'''[[Engines|Up one level]]'''
[[FILE:Lachex.JPG|border|right|thumb|380px|link=http://en.wikipedia.org/wiki/Los_Alamos_National_Laboratory| Los Alamos <ref>[https://en.wikipedia.org/wiki/Los_Alamos_National_Laboratory Los Alamos National Laboratory from Wikipedia]</ref> Chess Experiment ]]
'''Lachex''', <br/>
an Acronym for [[Los Alamos National Laboratory|Los Alamos]] Chess Experiment, is the chess program developed by [[Burton Wendroff]] and [[Tony Warnock]]. Lachex was a mainframe program, playing on a [[Cray X-MP|Cray X-MP 48]], and was written in [[Fortran]] and [[Assembly]], performing some kind of full width [[Parallel Search|parallel]] [[Principal Variation Search|principal variation search]] inside an [[Iterative Deepening|iterative deepening framework]]. Also, Lachex already implemented presumably none [[Recursion|recursive]] [[Null Move Pruning|null move pruning]], as mentioned in the [[Lachex#Description|description]] from the [[WCCC 1989]] booklet.
=Tournament Play=
Lachex played two [[World Computer Chess Championship|World Computer Chess Championships]] <ref>[https://www.game-ai-forum.org/icga-tournaments/program.php?id=227 Lachex's ICGA Tournaments]</ref>, the [[WCCC 1986]] and [[WCCC 1992]], and four [[ACM North American Computer Chess Championship|ACM North American Computer Chess Championships]], [[ACM 1985]], [[ACM 1986]], [[ACM 1987]] and [[ACM 1991]]. It was runner up in 1986 only losing the eventual winner [[Belle]].
=Selected Games=
[[WCCC 1986]], round 1, [[Ostrich]] - [[Lachex]] <ref>[https://www.game-ai-forum.org/icga-tournaments/round.php?tournament=62&round=1&id=3 Cologne 1986 - Chess - Round 1 - Game 3 (ICGA Tournaments)]</ref>
<pre>
[Event "WCCC 1986"]
[Site "Cologne, Germany"]
[Date "1986.06.11"]
[Round "1"]
[White "Ostrich"]
[Black "Lachex"]
[Result "0-1"]
1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Bxc6 dxc6 5.d4 exd4 6.Qxd4 Qxd4 7.Nxd4 Nf6 8.O-O
Bc5 9.c3 O-O 10.f3 Bd6 11.Bg5 c5 12.Bxf6 gxf6 13.Ne2 Be6 14.Nd2 Rfd8 15.Rfd1 Kh8
16.a4 b5 17.axb5 axb5 18.Rxa8 Rxa8 19.g3 f5 20.Kf2 Ra2 21.Rb1 Bd7 22.Ke3 Ra8
23.Re1 Kg8 24.f4 Re8 25.Kd3 fxe4+ 26.Nxe4 Bf5 27.Nc1 Bf8 28.b3 c4+ 29.bxc4 bxc4+
30.Kxc4 Bxe4 31.Rd1 c6 32.Rd2 Bd5+ 33.Kd3 Bc5 34.Re2 Rb8 35.c4 Be6 36.Kc3 Bb4+
37.Kc2 Bxc4 38.Re5 f6 39.Rf5 Rd8 40.Rxf6 Rd2+ 41.Kb1 Bc3 0-1
</pre>
<span id="Description"></span>
=Description=
from the [[WCCC 1989]] booklet <ref>[http://www.computerhistory.org/chess/full_record.php?iid=doc-434fea055cbb3 Kings Move - Welcome to the 1989 AGT World Computer Chess Championship.] Edmonton, Alberta, Canada, Courtesy of [[Peter Jennings]], from [[The Computer History Museum]], [http://archive.computerhistory.org/projects/chess/related_materials/text/3-1%20and%203-2%20and%203-3%20and%204-3.1989_WCCC/1989%20WCCC.062302028.sm.pdf pdf]</ref>:
Lachex is specifically designed for the architecture of the Cray XMP and YMP series of machines. The highly repetitive parts of the program are written in [[Assembly|assembly language]], the rest in [[Fortran]]. Low level parallelism is achieved by extensive use of vector functional units and [https://en.wikipedia.org/wiki/Pipeline_%28computing%29 pipelining]. High level parallelism is obtained by means of multiple independent processors splitting up the search using a self-scheduling algorithm and communicating with each other through a large common [[Memory|memory]].
The search is basically [[Alpha-Beta|alpha-beta]] with [[Iterative Deepening|iterative deepening]]. In the initial depth one search each [[Root|root]] move is actually [[Score|scored]] and the list of moves ordered accordantly. [[Best Move|Best moves]] at subsequent iterations are moved to the top of the list. [[Scout|Scouting]] is used at [[Ply|ply]] one only - the first move in the list is scored and the remaining moves are tested with [[Null Window|minimal window]]. [[Pruning|Forward pruning]] is done with a positional estimator at nodes below the horizon and with the [[Null Move Pruning|null move algorithm]] above. Moves out of [[Check|check]] above the horizon [[Check Extensions|extend]] the [[Depth|search depth]] for that path by one, but by two if the check is [[Discovered Check|discovered]] or [[Double Check|double]]. [[Quiescence Search|Selective searches]] below the horizon include [[Captures|captures]], [[Promotions|promotions]], [[Castling|castling]], and some checking moves.
Lachex spends 1/3 of its time [[Move Generation|generating moves]], 1/3 doing bookkeeping, and 1/3 [[Evaluation|evaluating]] [[Leaf Node|leaf nodes]]. The evaluation function is symmetric wherever possible. [[Mobility]], [[Pawn Structure|pawn structure]], [[King Safety|king safety]], [[Piece-Square tables|piece placement]] and other features make up the evaluation function. Some strategy is incorporated at the root by shifting the minimal window to bias certain types of moves. There is a [[Transposition Table|transposition table]] which can be a big as 32 million positions, on a 64 million word machine.
==Board Representation==
Lachex used following [[Pieces#PieceCoding|piece enumeration scheme]] from the [[Initial Position|initial position]], which does not change during the cause of the game: the a1-rook was labeled with 1, b1-knight with 2, a2-pawn with 9, the a8-rook with 17 and the h7-pawn with 32. Beside a [[Bitboard Board-Definition|bitboard board-definition]] using 12 piece [[Bitboards|bitboards]] and [[Occupancy|occupancy]] as union set, Lachex used a redundant [[8x8 Board|8x8 board array]], containing those 1..32 piece-codes, but zero for empty squares, and [[Piece-Lists|piece-arrays]] containing [[Squares|squares]] and associated [[Pieces#PieceTypeCoding|piece-types]] or zero if the piece is missing. A so called ''INC-Array'' indexed by [[Origin Square|origin]], [[Target Square|target square]] and [[Pieces#PieceTypeCoding|piece type]] (excluding color, but white and black pawn as distinct types) was used in direct [[Move Generation|move generation]], similar as described in ''[[Square Attacked By#InBetween|In Between]] and [[Square Attacked By#AttackedByPieceOnSquare|Attacked by Piece on Square]]''.
Further, something which reminds on [[Fill Algorithms|fill algorithms]] like [[Dumb7Fill]] was used as described by Wendroff <ref>[[Burton Wendroff]] ('''1985'''). ''Attack Detection and Move Generation on the X-MP/48.'' [[ICGA Journal#8_2|ICCA Journal, Vol. 8, No. 2]]</ref> :
There are several methods for generating the moves of the long range pieces. The method we have had the most success with on Cray machines preceding the X-MP/48 finds the to-squares closest to the home square, and then by a complicated sequence of shifts and boolean operations simultaneously continues these moves in the appropriate directions.
==BCH Hashing==
To index and lock [[Hash Table#SearchTables|search tables]], especially the [[Transposition Table|transposition table]], Lachex utilized signatures of chess positions by [[BCH Hashing]] based on [https://en.wikipedia.org/wiki/BCH_code BCH-Code] as used in [https://en.wikipedia.org/wiki/Error_detection_and_correction Error detection and correction], otherwise [[Incremental Updates|incrementally updated]] similar than signatures from [[Zobrist Hashing]]. Lachex used a BCH signature length of 81 (or more) bits to protect 16 bits from the full position string of 749 (64*12 - 2*2*8 + 4 + 8 + 1) bits, which is sufficient to avoid [[Transposition Table#KeyCollisions|collisions]] within an 8 ply search. In their paper on ''Search Tables'' <ref>[[Tony Warnock]], [[Burton Wendroff]] ('''1988'''). ''Search Tables in Computer Chess''. [[ICGA Journal#11_1|ICCA Journal, Vol. 11, No. 1]]</ref> , Warnock and Wendroff further elaborate on [[Alpha-Beta|alpha-beta]] [[Search Instability|inconsistencies]], and that with the introduction of search tables, depending on the implementation, alpha-beta may not be order-independent. They refer implementations given by [[Tony Marsland]] <ref>[[Tony Marsland]] ('''1986'''). ''A Review of Game-Tree Pruning.'' [[ICGA Journal#9_1|ICCA Journal, Vol. 9, No. 1]]</ref> and [[Harry Nelson]] <ref>[[Harry Nelson]] ('''1985'''). ''Hash Tables in [[Cray Blitz]]''. [[ICGA Journal#8_1|ICCA Journal, Vol. 8, No. 1]]</ref>.
=See also=
* [[ACM 1991#KnightPromotion|ACM 1991 | Mephisto - Lachex]]
* [[Various Classifications#Acronym|Acronym]]
=Publications=
* [[Burton Wendroff]] ('''1985'''). ''Attack Detection and Move Generation on the X-MP/48.'' [[ICGA Journal#8_2|ICCA Journal, Vol. 8, No. 2]]
* [[Tony Warnock]], [[Burton Wendroff]] ('''1988'''). ''Search Tables in Computer Chess''. [[ICGA Journal#11_1|ICCA Journal, Vol. 11, No. 1]]
=External Links=
* [https://www.game-ai-forum.org/icga-tournaments/program.php?id=227 Lachex's ICGA Tournaments]
* [http://www.365chess.com/players/Lachex Lachex chess games] from [http://www.365chess.com/ 365Chess.com]
=References=
<references />
'''[[Engines|Up one level]]'''
