Changes

Jump to: navigation, search

Abyss

11,032 bytes added, 16:32, 7 June 2018
Created page with "'''Home * Engines * Abyss''' '''Home * Games * Chinese Chess Engines * Abyss''' FILE:Lysefjorden - Man standin..."
'''[[Main Page|Home]] * [[Engines]] * Abyss'''
'''[[Main Page|Home]] * [[Games]] * [[Chinese Chess#Engines|Chinese Chess Engines]] * Abyss'''

[[FILE:Lysefjorden - Man standing on Preikestolen.JPG|border|right|thumb|At the Edge of the Abyss <ref>[https://en.wikipedia.org/wiki/Lysefjord Lysefjord], [https://en.wikipedia.org/wiki/Norway Norway]- a man standing on [https://en.wikipedia.org/wiki/Preikestolen Preikestolen] at the edge of the Abyss, [https://commons.wikimedia.org/wiki/File:Lysefjorden_-_Man_standing_on_Preikestolen.JPG Image] by [https://commons.wikimedia.org/wiki/User:Mercy Mercy], August 2008, [https://creativecommons.org/licenses/by-sa/3.0/deed.en CC BY-SA 3.0], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]

'''Abyss''',<br/>
a [[Chinese Chess]] program by [[Chun Ye]] and [[Tony Marsland]], written in [[C]] under [[Unix]] aka [https://en.wikipedia.org/wiki/SunOS SunOS]. A [https://en.wikipedia.org/wiki/X_Window_System X Window] [[GUI]] was written in [[Cpp|C++]] by [[Haiying Wang]] <ref>[[Haiying Wang]] ('''1994'''). ''[https://era.library.ualberta.ca/files/2227mr67d An application-oriented user interface model and development system]''. Ph.D. thesis, [[University of Alberta]], [https://era.library.ualberta.ca/files/2227mr67d/NN11407.pdf pdf], see 6.2 Chinese Chess Program pp. 101.</ref>. The program was subject of Chun Ye's 1992 master thesis at [[University of Alberta]] <ref>[[Chun Ye]] ('''1992'''). ''Experiments in Selective Search Extensions''. M.Sc. thesis, Department of Computing Science, [[University of Alberta]], [https://era.library.ualberta.ca/public/datastream/get/uuid:e4fbf48d-7603-490f-85cc-5497bbecf5a8/DS1 pdf]</ref> on the topic of [[Selectivity|selectivity]] and [[Extensions|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 Pruning#NMQS|null move quiescence search]].

Abyss participated at all three [[Computer Olympiad|Computer Olympiads]] which took place in [https://en.wikipedia.org/wiki/Maastricht Maastricht], winning the gold medal (shared) at the [[3rd Computer Olympiad#ChineseChess|3rd Computer Olympiad, 1991]], while the 1999 version played in [[6th Computer Olympiad#ChineseChess|2001]] and [[7th Computer Olympiad#ChineseChess|2002]], respectively.

=Description=
The framework of Abyss <ref>Description is based on [[Chun Ye]] ('''1992'''). ''Experiments in Selective Search Extensions''. M.Sc. thesis, Department of Computing Science, [[University of Alberta]], [https://era.library.ualberta.ca/public/datastream/get/uuid:e4fbf48d-7603-490f-85cc-5497bbecf5a8/DS1 pdf]</ref> was based on the Western experimental Chess program [[Parabelle]] by [[Fred Popowich]] and Tony Marsland <ref>[[Fred Popowich]], [[Tony Marsland]]. ('''1983''') ''Parabelle: Experience with a Parallel Chess Program.'' Technical Report 83-7. Computing Science Department, [[University of Alberta]], [https://webdocs.cs.ualberta.ca/~tony/TechnicalReports/TR83-7.pdf pdf]</ref>.

==[[Move Generation]]==
Abyss' board is [[Chinese Chess Board Representation|represented]] as [[Mailbox]] - a one-dimensional [[Array|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 [[Chinese Chess#Palace|palace]] during move generation, board arrays of pre-computed 12-bit [[Direction|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|target square]] indicates target on board or inside palace, followed by piece specific tests to generate [[Pseudo-Legal Move|pseudo legal moves]] or to continue a direction loop for rook or [[Chinese Chess#Cannon|cannon]]. Detection of strictly [[Legal Move|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|selectivity]], in particular [[Extensions|extensions]] which are combined in various experiments, and further elaborated in two additional papers along with Tony Marsland <ref>[[Chun Ye]], [[Tony Marsland]] ('''1992'''). ''Experiments in Forward Pruning with Limited Extensions.'' [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]], [http://webdocs.cs.ualberta.ca/~tony/RecentPapers/Experiments-FP-YeMars-1992.pdf pdf]</ref> <ref>[[Chun Ye]], [[Tony Marsland]] ('''1992'''). ''Selective Extensions in Game-Tree Search.'' [[3rd Computer Olympiad#Workshop|Heuristic Programming in AI 3]], [https://webdocs.cs.ualberta.ca/~tony/RecentPapers/SelectiveExten-YeMars.pdf pdf]</ref>. Abyss already featured [[Null Move Pruning|recursive null move pruning]] with [[Depth Reduction R|depth reduction]] of 1 <ref>[[Gordon Goetsch]], [[Murray Campbell]] ('''1990'''). ''[https://link.springer.com/chapter/10.1007/978-1-4613-9080-0_9 Experiments with the Null-Move Heuristic]''. [[Computers, Chess, and Cognition]], pp. 159-168</ref>, and further [[Don Beal|Don Beal's]] [[Null Move Pruning#NMQS|null move quiescence search]] <ref>[[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''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 43, No. 1, pp. 85-98. ISSN 0004-3702.</ref>. A piece evading move extension was motivated by threat detection concerning the complicated [[Repetitions|repetition]] rules of Chinese Chess.

===Basics===
* [[Iterative Deepening]]
* [[Aspiration Windows]]
* [[Principal Variation Search]]
* [[Transposition Table]]
: [[Zobrist Hashing]]
* [[Refutation Table]]
===[[Move Ordering]]===
* [[Hash Move]]
* [[Refutation Move]]
* [[MVV-LVA|MVV/LVA]]
* [[History Heuristic]]
===[[Selectivity]]===
* [[Extensions]]
: [[Check Extensions|Check Evasion Extensions]]
: [[Recapture Extensions]]
: [[Mate Threat Extensions|King Threats]]
: [[One Reply Extensions]]
: [[Singular Extensions]]
* [[Pruning]]
: [[Null Move Pruning|Recursive Null Move Pruning]] with [[Depth Reduction R|R]] = 1
: [[Null Move Pruning#NMQS|Don Beal's Null Move Quiescence Search]]
: [[Futility Pruning]]
: [[Quiescence Search]]

==[[Evaluation]]==
* [[Material|Material Balance]] with [[Point Value|Point Values]]
: {| class="wikitable" style="text-align: center;
|-
! Piece
! Opening
! Endgame
|-
| style="text-align: left; | [[Chinese Chess#King|King]]
| colspan="2" | 7000
|-
| style="text-align: left; | [[Chinese Chess#Rook|Rook]]
| colspan="2" | 1800
|-
| style="text-align: left; | [[Chinese Chess#Cannon|Cannon]]
| style="text-align:right;" | 900
| style="text-align:right;" | 800
|-
| style="text-align: left; | [[Chinese Chess#Horse|Horse]]
| style="text-align:right;" | 800
| style="text-align:right;" | 900
|-
| style="text-align: left; | [[Chinese Chess#Elephant|Elephant]]
| colspan="2"| 300
|-
| style="text-align: left; | [[Chinese Chess#Advisor|Advisor]]
| colspan="2" | 300
|-
| style="text-align: left; | [[Chinese Chess#Pawn|Pawn]]
| colspan="2" | 100
|}
* [[Piece-Square Tables]]
* [[Square Control]]
* [[King Safety]]
: [[King Safety#Attacking|Attacking King Zone]]
: [[King Safety#Patterns|Penalty for King]] on [[Ranks|rank]] or [[Files|file]] of opponent's [[Chinese Chess#Cannon|Cannon]]
==Misc==
* [[Opening Book]]

=Abyss' ICGA Tournaments=
<ref>[https://www.game-ai-forum.org/icga-tournaments/program.php?id=252 Abyss' ICGA Tournaments]</ref>
{| class="wikitable"
|-
! Edition
! Version
! Ranking
! Participants
|-
| [[3rd Computer Olympiad#ChineseChess|3rd Computer Olympiad, Maastricht 1991]]
|
| style="text-align:right;" | 1
| style="text-align:right;" | 2
|-
| [[6th Computer Olympiad#ChineseChess|6th Computer Olympiad, Maastricht 2001]]
| Abyss '99
| style="text-align:right;" | 3
| style="text-align:right;" | 3
|-
| [[7th Computer Olympiad#ChineseChess|7th Computer Olympiad, Maastricht 2002]]
| Abyss '99
| style="text-align:right;" | 4
| style="text-align:right;" | 4
|}

=See also=
* [[Various Classifications#Comics|Comics]]
* [[Various Classifications#Demonology|Demonology]]
* [[Various Classifications#Metaphysics|Metaphysics]]
* [[Various Classifications#Mythology|Mythology]]
* [[Parabelle]]

=Publications=
* [[Chun Ye]] ('''1992'''). ''Experiments in Selective Search Extensions''. M.Sc. thesis, Department of Computing Science, [[University of Alberta]], [https://era.library.ualberta.ca/public/datastream/get/uuid:e4fbf48d-7603-490f-85cc-5497bbecf5a8/DS1 pdf]
* [[Chun Ye]], [[Tony Marsland]] ('''1992'''). ''Experiments in Forward Pruning with Limited Extensions.'' [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]], [http://webdocs.cs.ualberta.ca/~tony/RecentPapers/Experiments-FP-YeMars-1992.pdf pdf]
* [[Chun Ye]], [[Tony Marsland]] ('''1992'''). ''Selective Extensions in Game-Tree Search.'' [[3rd Computer Olympiad#Workshop|Heuristic Programming in AI 3]], [https://webdocs.cs.ualberta.ca/~tony/RecentPapers/SelectiveExten-YeMars.pdf pdf]

=External Links=
==Engine==
* [https://www.game-ai-forum.org/icga-tournaments/program.php?id=252 Abyss' ICGA Tournaments]
==Misc==
* [https://en.wiktionary.org/wiki/abyss abyss - Wiktionary]
* [https://en.wikipedia.org/wiki/Abyss Abyss from Wikipedia]
* [https://en.wikipedia.org/wiki/Abyssal_zone Abyssal zone from Wikipedia]
* [https://en.wikipedia.org/wiki/Abyssal_plain Abyssal plain from Wikipedia]
* [https://en.wikipedia.org/wiki/Abyss_(comics) Abyss (comics) from Wikipedia]
* [https://en.wikipedia.org/wiki/Abyss_(religion) Abyss (religion) from Wikipedia]
* [https://en.wikipedia.org/wiki/Abyss_(roller_coaster) Abyss (roller coaster) from Wikipedia]
* [https://en.wikipedia.org/wiki/Abyss_(Thelema) Abyss (Thelema) from Wikipedia]
* [https://en.wikipedia.org/wiki/Abyssinia Abyssinia from Wikipedia]
* [https://en.wikipedia.org/wiki/In_the_Abyss In the Abyss - Wikipedia]
* [https://en.wikipedia.org/wiki/Abyss_Odyssey Abyss Odyssey - Wikipedia]
* [https://en.wikipedia.org/wiki/Tales_of_the_Abyss Tales of the Abyss - Wikipedia]
* [[Videos#Slayer|Slayer]] - [https://en.wikipedia.org/wiki/Seasons_in_the_Abyss Seasons in the Abyss], [https://en.wikipedia.org/wiki/Wacken_Open_Air Wacken] [https://en.wikipedia.org/wiki/Wacken_Open_Air#2014 2014], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=r_zTerIEYGk|alignment=left|valignment=top}}

=References=
<references />

'''[[Chinese Chess|Up one Level]]'''

Navigation menu