Abyss

From Chessprogramming wiki
Jump to: navigation, search

Home * Engines * Abyss

At the Edge of the Abyss [1]

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.

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

Zobrist Hashing

Move Ordering

Selectivity

Check Evasion Extensions
Recapture Extensions
King Threats
One Reply Extensions
Singular Extensions
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

[10]

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

External Links

Engine

Misc

References

  1. 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
  2. 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.
  3. Chun Ye (1992). Experiments in Selective Search Extensions. M.Sc. thesis, Department of Computing Science, University of Alberta, pdf
  4. Description is based on Chun Ye (1992). Experiments in Selective Search Extensions. M.Sc. thesis, Department of Computing Science, University of Alberta, pdf
  5. Fred Popowich, Tony Marsland. (1983) Parabelle: Experience with a Parallel Chess Program. Technical Report 83-7. Computing Science Department, University of Alberta, pdf
  6. Chun Ye, Tony Marsland (1992). Experiments in Forward Pruning with Limited Extensions. ICCA Journal, Vol. 15, No. 2, pdf
  7. Chun Ye, Tony Marsland (1992). Selective Extensions in Game-Tree Search. Heuristic Programming in AI 3, pdf
  8. Gordon Goetsch, Murray Campbell (1990). Experiments with the Null-Move Heuristic. Computers, Chess, and Cognition, pp. 159-168
  9. 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.
  10. Abyss' ICGA Tournaments

Up one Level