Amundsen

Edit 0 23 …
Older Version Newer Version

GerdIsenberg GerdIsenberg Sep 3, 2013 

**[[Home]] * [[Engines]] * Amundsen**
|| [[image:298px-Roald_Amundsen2.jpg width="238" height="384" link="http://en.wikipedia.org/wiki/File:Roald_Amundsen2.jpg"]] ||~   || **Amundsen**, (Jonte)
a [[Chess Engine Communication Protocol]] compliant [[Open Source Engines|open source chess engine]] under the [[Free Software Foundation#GPL|GNU General Public License]], written in [[C]] by [[John Bergbom]]. Started as college course project at the Department of Numerical Analysis and Computing Science, [[http://en.wikipedia.org/wiki/Royal_Institute_of_Technology|Royal Institute of Technology]], [[http://en.wikipedia.org/wiki/Stockholm|Stockholm]] <ref>[[http://www.nada.kth.se/kurser/master/index-eng.html|Master of Science - Nada, KTH]]</ref>, a name change from Jonte to Amundsen took place between version 0.25 and 0.3, since the initial name was already used at [[Free Internet Chess Server|FICS]] <ref>[[http://www.bergbomconsulting.se/chess/|Amundsen chess program]]</ref>. Amundsen was first released in May 2004, as announced by [[Dann Corbit]] in [[Computer Chess Forums|Winboard Forum]] <ref>[[http://www.open-aurec.com/wbforum/viewtopic.php?f=18&t=47652|A new chess program]] by [[Dann Corbit]], [[Computer Chess Forums|Winboard Forum]], May 22, 2004</ref>.



<span style="text-align: center;
display: block;
font-family: 'Comic Sans MS', cursive;">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.
</span>
>> //Roald Amundsen// <ref>[[http://www.frammuseum.no/polar-expedition.aspx|Fram Museum - Polar Expeditions]]</ref>
 ||
|| Amundsen at wheel of the [[http://en.wikipedia.org/wiki/Maud_%28ship%29|Maud]] <ref>Captain Roald Amundsen at wheel leaving [[http://en.wikipedia.org/wiki/Nome,_Alaska|Nome]] for [[http://en.wikipedia.org/wiki/North_Pole|North Pole]], 1920, Source:[[http://en.wikipedia.org/wiki/Roald_Amundsen|Roald Amundsen from Wikipedia]], [[http://www.loc.gov/pictures/resource/cph.3c21515/|Library of Congress | digital ID cph 3c21515]], Lomen Bros</ref> ||~   ||^   ||
[[toc]]
=Description=
==Bitboard Infrastructure==
===Rotated Bitboards===
Amundsen uses [[Rotated Bitboards|rotated bitboards]] with 1/2 MiB lookup tables, indexed by [[Occupancy of any Line|8-bit line occupancy]], to determine [[Sliding Piece Attacks|sliding piece attacks]], ignoring the possible fourfold reduction excluding the redundant [[First Rank Attacks#TheOuterSquares|outer squares]].
[[#BitScan]]
===BitScan & PopCount===
The [[Memory|memory]] bacchanal is attended by [[Population Count|population count]], [[BitScan#Bitscanforward|bitscan forward]] and [[BitScan#Bitscanreverse|reverse]] with three 16-bit indexed, 64K lookup tables of [[Double Word|double word]] integers, which is another 3/4 MiB <ref>[[http://www.bergbomconsulting.se/chess/|amundsen-0.80.tar.gz]], bitboards.c</ref>. 
[[code format="cpp"]]
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;
}
[[code]]

==Search==
The [[Search|search]] is [[Principal Variation Search|PVS]] [[Alpha-Beta|alpha-beta]] with [[Transposition Table|transposition]] and [[Refutation Table|refutation table]] inside an [[Iterative Deepening|iterative deepening]] framework with [[Aspiration Windows|aspiration windows]], further using [[AEL-Pruning|AEL-pruning]] à la [[Ernst A. Heinz|Heinz]], as well as [[Late Move Reductions|LMR]] and [[Internal Iterative Deepening|IID]] in case of a missing [[Hash Move|hash move]] at [[Node Types#PV|PV-nodes]]. [[Check Extensions|Checks]], [[Passed Pawn Extensions|pawn moves to the 7th rank]], and [[Mate Threat Extensions|mate threatening moves]] are [[Extensions|extended]], [[Killer Heuristic|killer-]] and [[History Heuristic|history heuristic]] help to [[Move Ordering|order moves]], and a [[SEE - The Swap Algorithm|SEE swap routine]] is used to determine winning [[Captures|captures]]. 

==Evaluation==
Amundsen's [[Evaluation|evaluation]] with a [[Pawn Hash Table|pawn structure cache]] features [[Piece-Square Tables|piece-square tables]], and further considers [[Mobility|mobility]], [[Passed Pawn|passed pawns]] and [[Hidden Passed Pawn|hidden passed pawns]], [[King Safety|king safety]] through [[King Safety#KingTropism|king piece tropism]], and various features and defects such as [[Outposts|outposts]], [[Rook on open file|rook on open file]], [[Rook on seventh|seventh rank]] and [[Tarrasch Rule|behind passers]], and [[Bad Bishop|bad bishop]] to name a few, and knows to trade pieces when ahead, but pawns when behind.

=See also=
* [[Various Classifications#Explorer|Explorer]]
* [[PolarChess]]
* [[Siberian Chess]]

=Publications=
* [[John Bergbom]] (**2004**). //Schackprogrammet Amundsen//. (2D1464 Större avancerad individuell kurs i datalogi) [[http://www.nada.kth.se/kurser/kth/2D1464/amundsen/rapport.pdf|pdf]] (Swedish) <ref>[[http://www.nada.kth.se/kurser/kth/2D1464/amundsen/index.html|Amundsen chess program]] (old page)</ref>

=Forum Posts= 
* [[http://www.open-aurec.com/wbforum/viewtopic.php?f=18&t=47652|A new chess program]] by [[Dann Corbit]], [[Computer Chess Forums|Winboard Forum]], May 22, 2004
* [[http://www.open-aurec.com/wbforum/viewtopic.php?f=18&t=47667|Amundsen 0.3 and his book : problem ?]] by Claude Dubois, [[Computer Chess Forums|Winboard Forum]], May 24, 2004
* [[http://www.open-aurec.com/wbforum/viewtopic.php?f=18&t=48692|Amundsen 0.35 exe]] by [[Jim Ablett]], [[Computer Chess Forums|Winboard Forum]], August 25, 2004
* [[http://www.open-aurec.com/wbforum/viewtopic.php?f=2&t=3481&p=17419#p17419|Amundsen 05 Windows binaries]] by [[Jim Ablett]], [[Computer Chess Forums|Winboard Forum]], September 14, 2005
* [[http://www.open-aurec.com/wbforum/viewtopic.php?f=2&t=7065#p32462|Amundsen 0.65 (released on January 11th 2008)]] by [[Denis Mendoza|Denis P. Mendoza]], [[Computer Chess Forums|Winboard Forum]], January 15, 2008
* [[http://www.open-aurec.com/wbforum/viewtopic.php?f=2&t=7158|Amundsen 0.65.1 Windows builds available]] by [[Jim Ablett]], [[Computer Chess Forums|Winboard Forum]], February 23, 2008
* [[http://www.open-aurec.com/wbforum/viewtopic.php?f=2&t=49886|Amundsen_075JA with illegal moves]] by [[Günther Simon]], [[Computer Chess Forums|Winboard Forum]], January 18, 2009 

=External Links= 
==Chess Engine== 
* [[http://www.bergbomconsulting.se/chess/|Amundsen chess program]]
> [[http://www.bergbomconsulting.se/chess/testsuites.html|Amundsen chess program | Testsuites]] » [[Test-Positions]]
* [[http://wbec-ridderkerk.nl/html/details1/Amundsen.html|Amundsen]] from [[WBEC|WBEC Ridderkerk]]
* [[http://computerchess.org.uk/ccrl/4040/cgi/engine_details.cgi?print=Details+%28text%29&eng=Amundsen%200.80%2032-bit|Amundsen 0.80 32-bit]] in [[CCRL|CCRL 40/40]]
==Misc== 
* [[http://en.wikipedia.org/wiki/Roald_Amundsen|Roald Amundsen from Wikipedia]]
* [[http://en.wikipedia.org/wiki/Amundsen_%28disambiguation%29|Amundsen (disambiguation) from Wikipedia]]

=References= 
<references />
=What links here?= 
[[include page="Amundsen" component="backlinks" limit="40" ]]
**[[Engines|Up one level]]**