25,161
edits
Changes
no edit summary
'''[[Main Page|Home]] * [[Board Representation]] * Bitboards'''
=The Board of Sets=
To [[Board Representation|represent the board]] we typically need one bitboard for each [[Pieces#PieceTypeCoding|piece-type]] and [[Color|color]] - likely encapsulated inside a class or structure, or as an [[Array|array]] of bitboards as part of a position object. A one-bit inside a bitboard implies the existence of a piece of this piece-type on a certain square - one to one associated by the bit-position.
=<span id="BitboardHistory"></span>Bitboard-History=
The general approach of [[Mikhail R. Shura-Bura#Bitsets|bitsets]] was proposed by [[Mikhail R. Shura-Bura]] in 1952 <ref>[https://en.wikipedia.org/wiki/Lazar_Lyusternik Lazar A. Lyusternik]], [[http://www.mathnet.ru/php/person.phtml?personid=30351&option_lang=eng Aleksandr A. Abramov], [https://en.wikipedia.org/wiki/Victor_ShestakovVictor Victor_Shestakov Victor I. Shestakov], [[Mikhail R. Shura-Bura]] ('''1952'''). ''Programming for High-Speed Electronic Computers''. (Программирование для электронных счетных машин)</ref> <ref>[[Mathematician#Ershov|Andrey Ershov]], [[Mikhail R. Shura-Bura]] ('''1980'''). ''[http://ershov.iis.nsk.su/archive/eaindex.asp?lang=2&gid=910 The Early Development of Programming in the USSR]''. in [http://en.wikipedia.org/wiki/Nicholas_C._Metropolis|Nicholas C. Metropolis]] (ed.) ''[[http://dl.acm.org/citation.cfm?id=578384 A History of Computing in the Twentieth Century]''. [https://en.wikipedia.org/wiki/Academic_Press Academic Press], [http://ershov.iis.nsk.su/archive/eaimage.asp?did=28792&fileid=173670 preprint pp. 43]</ref>. The bitboard method for holding a board game appears to have been invented also in 1952 by [[Christopher Strachey]] using White, Black and King bitboards in his checkers program for the [[Ferranti Mark 1]], and in the mid 1950's by [[Arthur Samuel]] in his checkers program as well. In computer chess, bitboards were first described by [[Georgy Adelson-Velsky]] et al. in 1967 <ref>[http://groups.google.com/group/rec.games.chess/browse_frm/thread/0e3a93f45ff07d31# Early Reference on Bit-Boards] by [[Tony Warnock]] from , [[Computer Chess Forums|rec.games.chess]], October 29, 1994</ref>, reprinted 1970 <ref>[[Georgy Adelson-Velsky]], [[Vladimir Arlazarov]], [[Alexander Bitman]], [[Alexander Zhivotovsky]], [[Anatoly Uskov]] ('''1970'''). ''[http://iopscience.iop.org/0036-0279/25/2/R07 Programming a Computer to Play Chess]''. [http://iopscience.iop.org/0036-0279/25/2 Russian Mathematical Surveys, Vol. 25], pp. 221-262.</ref> . Bitboards were used in [[Kaissa]] and in [[Chess (Program)|Chess]]. The invention and publication of [[Rotated Bitboards]] by [[Robert Hyatt]] <ref>[[Robert Hyatt]] ('''1999'''). ''[http://www.craftychess.com/hyatt/bitmaps.html Rotated Bitmaps, a New Twist on an Old Idea]''. [[ICGA Journal#22_4|ICCA Journal, Vol. 22, No. 4]]</ref> and [[Peter Gillgasch]] with [[Ernst A. Heinz]] in the 90s was another milestone in the history of bitboards. [[Steffan Westcott|Steffan Westcott's]] innovations, too expensive on 32-bit [[x86]] processors, should be revisited with [[x86-64]] and [[SIMD and SWAR Techniques|SIMD instructions]] in mind. With the advent of fast 64-bit multiplication along with faster [[Memory|memory]], [[Magic Bitboards]] as proposed by [[Lasse Hansen]] <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?t=5015 Fast(er) bitboard move generator] by [[Lasse Hansen]], [[Computer Chess Forums|Winboard Forum]], June 14, [[Timeline#2006|2006]]</ref> and refined by [[Pradu Kannan]] <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?t=5441 List of magics for bitboard move generation] by [[Pradu Kannan]], [[Computer Chess Forums|Winboard Forum]], August 23, [[Timeline#2006|2006]]</ref> have surpassed Rotated.
=Analysis=
'''[[Board Representation|Up one level]]'''
[[Category:Samuel Bak]]