Abyss
Abyss,
a Chinese Chess program by Chun Ye and Tony Marsland, written in C under Unix aka SunOS. A X Window GUI was written in C++ by Haiying Wang [2]. The program was subject of Chun Ye's 1992 master thesis at University of Alberta [3] on the topic of selectivity and extension heuristics in the domain of Chinese Chess. Not only Ye's advisor, Tony Marsland, contributed to the development of the program, but also Don Beal - at that time visiting professor at University of Alberta - in particular concerning null move quiescence search.
Abyss participated at all three Computer Olympiads which took place in Maastricht, winning the gold medal (shared) at the 3rd Computer Olympiad, 1991, while the 1999 version played in 2001 and 2002, respectively.
Contents
Description
The framework of Abyss [4] was based on the Western experimental Chess program Parabelle by Fred Popowich and Tony Marsland [5].
Move Generation
Abyss' board is represented as Mailbox - a one-dimensional array of 90 computer words, indexed by 0 .. 89. Pieces are encoded by ±1 for red and black pawns until ±7 for red and black kings, empty squares are represented by zero. To detect the edges of the board and palace during move generation, board arrays of pre-computed 12-bit direction masks consisting of four groups for each orthogonal direction of 3 bits each are utilized. Only the empty intersection of the move direction with the mask of the target square indicates target on board or inside palace, followed by piece specific tests to generate pseudo legal moves or to continue a direction loop for rook or cannon. Detection of strictly legal moves, i.e. it does not expose the own king in check, or does not oppose both kings on the same file with no pieces intervening, is delayed until the move is actually made for efficiency reasons - since not all generated pseudo legal moves are examined.
Search
The search procedure of Abyss was subject of Chun Ye's thesis concerning selectivity, in particular extensions which are combined in various experiments, and further elaborated in two additional papers along with Tony Marsland [6] [7]. Abyss already featured recursive null move pruning with depth reduction of 1 [8], and further Don Beal's null move quiescence search [9]. A piece evading move extension was motivated by threat detection concerning the complicated repetition rules of Chinese Chess.
Basics
Move Ordering
Selectivity
- Recursive Null Move Pruning with R = 1
- Don Beal's Null Move Quiescence Search
- Futility Pruning
- Quiescence Search
Evaluation
Piece Opening Endgame King 7000 Rook 1800 Cannon 900 800 Horse 800 900 Elephant 300 Advisor 300 Pawn 100
- Attacking King Zone
- Penalty for King on rank or file of opponent's Cannon
Misc
Abyss' ICGA Tournaments
| Edition | Version | Ranking | Participants |
|---|---|---|---|
| 3rd Computer Olympiad, Maastricht 1991 | 1 | 2 | |
| 6th Computer Olympiad, Maastricht 2001 | Abyss '99 | 3 | 3 |
| 7th Computer Olympiad, Maastricht 2002 | Abyss '99 | 4 | 4 |
See also
Publications
- Chun Ye (1992). Experiments in Selective Search Extensions. M.Sc. thesis, Department of Computing Science, University of Alberta, pdf
- Chun Ye, Tony Marsland (1992). Experiments in Forward Pruning with Limited Extensions. ICCA Journal, Vol. 15, No. 2, pdf
- Chun Ye, Tony Marsland (1992). Selective Extensions in Game-Tree Search. Heuristic Programming in AI 3, pdf
External Links
Engine
Misc
- abyss - Wiktionary
- Abyss from Wikipedia
- Abyssal zone from Wikipedia
- Abyssal plain from Wikipedia
- Abyss (comics) from Wikipedia
- Abyss (religion) from Wikipedia
- Abyss (roller coaster) from Wikipedia
- Abyss (Thelema) from Wikipedia
- Abyssinia from Wikipedia
- In the Abyss - Wikipedia
- Abyss Odyssey - Wikipedia
- Tales of the Abyss - Wikipedia
- Slayer - Seasons in the Abyss, Wacken 2014, YouTube Video
References
- ↑ Lysefjord, Norway- a man standing on Preikestolen at the edge of the Abyss, Image by Mercy, August 2008, CC BY-SA 3.0, Wikimedia Commons
- ↑ Haiying Wang (1994). An application-oriented user interface model and development system. Ph.D. thesis, University of Alberta, pdf, see 6.2 Chinese Chess Program pp. 101.
- ↑ Chun Ye (1992). Experiments in Selective Search Extensions. M.Sc. thesis, Department of Computing Science, University of Alberta, pdf
- ↑ Description is based on Chun Ye (1992). Experiments in Selective Search Extensions. M.Sc. thesis, Department of Computing Science, University of Alberta, pdf
- ↑ Fred Popowich, Tony Marsland. (1983) Parabelle: Experience with a Parallel Chess Program. Technical Report 83-7. Computing Science Department, University of Alberta, pdf
- ↑ Chun Ye, Tony Marsland (1992). Experiments in Forward Pruning with Limited Extensions. ICCA Journal, Vol. 15, No. 2, pdf
- ↑ Chun Ye, Tony Marsland (1992). Selective Extensions in Game-Tree Search. Heuristic Programming in AI 3, pdf
- ↑ Gordon Goetsch, Murray Campbell (1990). Experiments with the Null-Move Heuristic. Computers, Chess, and Cognition, pp. 159-168
- ↑ Don Beal (1989). Experiments with the Null Move. Advances in Computer Chess 5, A revised version is published (1990) under the title A Generalized Quiescence Search Algorithm. Artificial Intelligence, Vol. 43, No. 1, pp. 85-98. ISSN 0004-3702.
- ↑ Abyss' ICGA Tournaments
