Tournaments between computer programs: chess, draughts, checkers, Go, backgammon, and more
Description given in 1995:
Ulysses was the legendary conqueror of Troy and on his adventurous journey home to Athens he made many wanderings. The program 'UlyssesCCN' is written in C and uses a new searching technique called 'Controlled Conspiracy Number Search' (CCNS). The CCNS algorithm has been developed by Lorenz and Rottmann in their master thesis. CCNS takes up the Conspiracy Number scheme which was published by McAllester in 1988. This scheme makes it possible to achieve selectivity in the plain search algorithm without any domain dependent (i.e. chess specific) knowledge. The search tree has to be kept in memory (at least implicitly). Conspiracy Numbers were further investigated by Schaeffer in 1989. He has implemented a Conspiracy Number Search (CNS) in his program 'Conspire', which showed good tactical performance but unfortunately not good positional play. In developing the CCNS we explicitly used, for the first time, the observed locality of other CNS algorithms. In the evaluation of leaf- nodes a CCNS algorithm is able to use quiescence searches with initial windows. Positional play becomes possible. UlyssesCNN also uses a hash table which recognizes transpositions. Last, but not least, only a best move is computed and no resources are wasted for computing an upper bound for the value of this move. All chess specific knowledge used is encoded in the evaluation function. This consists of a static evaluator and a small quiescence search. Using a Sparc10 60MHz, UlyssesCCN searches about 8000 nodes per second, about 350 of them are Conspiracy Number nodes. The opening book consists of 11,000 positions. After 300 seconds at each position, Ulysses solves 281 positions of WinAtChess test set, consisting of 300 positions. To our knowledge, UlyssesCCN is the first chess program based on Conspiracy Numbers which achieved an acceptable result in a computer chess tournament.