Amundsen

From Chessprogramming wiki
Jump to: navigation, search

Home * Engines * Amundsen

Victory awaits him, who has everything in order.
Luck we call it.
Defeat is definitely due for him,
who has neglected to take the necessary precautions.
Bad luck we call it.
Roald Amundsen [1] [2]

Amundsen, (Jonte)
a Chess Engine Communication Protocol compliant open source chess engine by John Bergbom, written in C and licensed under the GPL. Started as college course project at the Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm [3], a name change from Jonte to Amundsen took place between version 0.25 and 0.3, since the initial name was already used at FICS [4]. Amundsen was first released in May 2004, as announced by Dann Corbit in Winboard Forum [5].

Description

Board Representation

Amundsen is a bitboard engine and applies rotated bitboards using the classical 1/2 MiB lookup tables, indexed by 8-bit line occupancy to determine sliding piece attacks, ignoring the possible fourfold reduction excluding the redundant outer squares. Population count, bitscan forward and reverse further use three 16-bit indexed, 64K lookup tables of double word integers, which is another 3/4 MiB of memory [6].

int bits_in_16bits[65536];
int first_bit_in_16bits[65536];
int last_bit_in_16bits[65536];

/* This function returns the number of the first set bit in an int64.
   The search is done from LSB to MSB. */
int get_first_bitpos(int64 n) {
  if (first_bit_in_16bits[n & 0xffff] >= 0)
    return first_bit_in_16bits[n & 0xffff];
  if (first_bit_in_16bits[(n >> 16) & 0xffff] >= 0)
    return first_bit_in_16bits[(n >> 16) & 0xffff] + 16;
  if (first_bit_in_16bits[(n >> 32) & 0xffff] >= 0)
    return first_bit_in_16bits[(n >> 32) & 0xffff] + 32;
  if (first_bit_in_16bits[(n >> 48) & 0xffff] >= 0)
    return first_bit_in_16bits[(n >> 48) & 0xffff] + 48;
  return -1;
}

Search

The search is PVS alpha-beta with transposition and refutation table inside an iterative deepening framework with aspiration windows, further using AEL-pruning à la Heinz, as well as LMR and IID in case of a missing hash move at PV-nodes. Checks, pawn moves to the 7th rank, and mate threatening moves are extended, killer- and history heuristic help to order moves, and a SEE swap routine is used to determine winning captures.

Evaluation

Amundsen's evaluation with a pawn structure cache features piece-square tables, and further considers mobility, passed pawns and hidden passed pawns, king safety through king piece tropism, and various features and defects such as outposts, rook on open file, seventh rank and behind passers, and bad bishop to name a few, and knows to trade pieces when ahead, but pawns when behind.

See also

Publications

  • John Bergbom (2004). Schackprogrammet Amundsen. (2D1464 Större avancerad individuell kurs i datalogi) pdf (Swedish) [7]

Forum Posts

External Links

References