182:
the computer to answer some questions about game state with one bitwise operation. For example, if a chess program wants to know if the white player has any pawns in the center of the board (center four squares) it can just compare a bitboard for the player's pawns with one for the center of the board using a bitwise AND operation. If there are no center pawns then the result will be all zero bits (i.e. equal to zero). Multiple bitboards may represent different properties of spaces over the board, and special or temporary bitboards (like temporary variables) may represent local properties or hold intermediate collated results.
467:
in the corresponding hash function). As with other schemes which require a perfect hashing function, an exhaustive process of enumeration, partly algorithmic and partly trial and error, is necessary to generate the hash function. But the intractable issue remains: these are very active tables, and their size (fewer than a million entries in most cases) is huge relative to the lower level cache sizes of modern chip architectures, resulting in cache flooding. So magic bitboards in many applications provide no performance gain over more modest hashing schemes or rotated bitboards.
433:
occupied positions in the rank (because rook attacks stop at the first occupied square). By rotating the bitboard 90 degrees, rook attacks up and down a file can be examined the same way. Adding bitboards rotated 45 degrees and 315 degrees (-45 degrees) produces bitboards in which the diagonals are easy to examine. The queen can be examined by combining rook and bishop attacks. Actually rotating a bitboard is an inelegant transformation that can take dozens of instructions.
382:
universal: one bitboard per square for all pieces attacking the square, and the inverse bitboard for all squares attacked by a piece for each square containing a piece. Bitboards can also be constants like one representing the first rank, which would have one bits in positions 0 - 7. Other local or transitional bitboards like "all spaces adjacent to the king attacked by opposing pieces" may be collated as necessary or convenient.
368:
22:
355:. Separate lists are maintained for white and black pieces, and often for white and black pawns. The maps are updated each move, which requires a linear search (or two if a piece was captured) through the piece list. The advantage of mailbox is simple code; the disadvantage is linear lookups are slow. Faster, but more elaborate data structures that map pieces to locations are called
333:
requires intricate and precise code. This is much faster to execute, because only bitmaps associated with changed spaces, not all bitmaps over the board, need to change. Without incremental update, bitmapped representation may not be more efficient than the older mailbox representation where update is intrinsically local and incremental.
466:
or first and eighth ranks together with the 'a' and 'h' files are irrelevant to the occupancy of the attack vector: the piece attacks those squares or not (depending on other blocking pieces) regardless of occupancy, so these can be eliminated from consideration, leaving just 6x6 or 36 squares (~bits
441:
The rank and file attack vectors of rooks and the diagonal and anti-diagonal attack vectors of bishops can be separately masked and used as indices into a hash table of precomputed attack vectors depending on occupancy, 8-bits each for rooks and 2-8 bits each for bishops. The full attack vector of a
428:
Rotated bitboards are complementary bitboard data structures that enable tabularizing of sliding piece attack vectors, one for file attack vectors of rooks, and one each for the diagonal and anti-diagonal attack vectors of bishops (rank attacks of rooks can be indexed from standard bitboards). With
181:
A bitboard, a specialized bit field, is a format that packs multiple related boolean variables into the same machine word, typically representing a position on a board game, or state of a game. Each bit represents a space; when the bit is positive, a property of that space is true. Bitboards allow
139:
Bits in the same bitboard relate to each other by the rules of the game, often forming a game position when taken together. Other bitboards are commonly used as masks to transform or answer queries about positions. Bitboards are applicable to any game whose progress is represented by the state of,
419:
In acknowledgement of the code size and computing complexity of generating bitboards for the attack vectors of sliding pieces, alternate bitboard data structures have been devised to collate them. The bitboard representations of knights, kings, pawns and other board configurations is unaffected by
323:
For some games, writing a bitboard engine requires a fair amount of source code including data tables that will be longer than the compact mailbox/enumeration implementation. For mobile devices (such as cell phones) with a limited number of registers or processor instruction cache, this can cause a
257:
Bitboard representations have much longer code, both source and object code. Long bit-twiddling sequences are technically tricky to write and debug. The bitboards themselves are sparse, sometimes containing only a single one bit in 64, so bitboard implementations are memory-intensive. Both these
198:
As a result of necessary compression and encoding of the contents of massive tables and the probability of transcription or encoding errors, bitboard programs are tedious for software developers to either write or debug. Auxiliary generative methods not part of the application are usually required
189:
Bitfield implementations take advantage of the presence of fullword (32-bit or 64-bit) bitwise logical operations like AND, OR, NOT and others on modern CPU architectures in order to be efficient. Bitboards may not be effective on earlier 8- and 16-bit minicomputer and microprocessor architectures.
240:
that queue instructions for execution. A processor with multiple execution units can perform more than one instruction per cycle if more than one instruction is available in the pipeline. Normal instruction sequences with branches may cause the pipeline to empty if a branch is mispredicted. Many
442:
piece is obtained as the union of each of the two unidirectional vectors indexed from the hash table. The number of entries in the hash table is modest, on the order of 8*2^8 or 2K bytes, but two hash function computations and two lookups per piece are required., see the hashing scheme employed.
377:
In bitboard representations, each bit of a 64 bit word (or double word on 32-bit architectures) is associated with a square of the chessboard. Any mapping of bits to squares can be used, but by broad convention, bits are associated with squares from left to right and bottom to top, so that bit 0
341:
Some kinds of bitmaps that don't depend on board configurations can be precomputed and retrieved by table lookup rather than collated after a move or state change of the board, such as spaces attacked by a knight or king located on each of 64 spaces of a chessboard that would otherwise require an
381:
Many different configurations of the board are usually represented by their own bitboards including the locations of the kings, all white pawns, all black pawns, as well as bitboards for each of the other piece types or combinations of pieces like all white pieces. Two attack bitboards are also
350:
The obvious, and simplest representation of the configuration of pieces on a chessboard, is as a list (array) of pieces in a conveniently searchable order (such as smallest to largest in value) that maps each piece to its location on the board. Analogously, collating the spaces attacked by each
244:
CPUs have a bit width which they are designed toward and can carry out bitwise operations in one cycle in this width. So, on a 64-bit or more CPU, 64-bit operations can occur in one instruction. There may be support for higher or lower width instructions. Many 32-bit CPUs may have some 64-bit
185:
The efficacy of bitboards is augmented by two other properties of the implementation. First, bitboards are fast to incrementally update, such as flipping the bits at the source and destination positions in a bitboard for piece location when a piece is moved. Second, bitmaps representing static
495:
A decade later, direct lookup methods using masked ranks, files and diagonals to index a table of attack vectors depending on occupancy states of bits under the mask, were introduced. One such scheme utilizing a perfect hash function to eliminate hash collisions, was termed "magic bitboards".
410:
One of the drawbacks of standard bitboards is collating the attack vectors of the sliding pieces (rook, bishop, queen), because they have an indefinite number of attack spaces depending on other occupied spaces. This requires several lengthy sequences of masks, shifts and complements per piece.
491:
Rotated bitboards for collating the moves of sliding pieces were invented by
Professor Robert Hyatt, author of Cray Blitz and Crafty chess engines, sometime in the mid-1990s and shared with the Dark Thought programming team. They were later implemented in Crafty and Dark Thought, but the first
432:
These bitboards rotate the board occupancy configuration by 90 degrees, 45 degrees, and/or 315 degrees. A standard bitboard will have one byte per rank of the chess board. With this bitboard it's easy to determine rook attacks across a rank, using a table indexed by the occupied square and the
332:
Some kinds of bitboards are derived from others by an elaborate process of cross-correlation, such as the attack maps in chess. Reforming all these maps at each change of game state (such as a move) can be prohibitively expensive, so derived bitmaps are incrementally updated, a process which
496:
Nonetheless, the large size and high access rates of such tables caused memory occupancy and cache contention issues, and weren't necessarily more efficacious than the rotated bitboard approach. Today, game programs remain divided, with the best scheme being application dependent.
186:
properties like all spaces attacked by each piece type for every position on a chessboard can be pre-collated and stored in a table, so that answering a question like "what are the legal moves of a knight on space e4?" can be answered by a single memory fetch.
475:
The bitboard method for representing a board game appears to have been invented in the mid-1950s, by Arthur Samuel and was used in his checkers program. For the more complicated game of chess, it appears the method was independently rediscovered later by the
282:
Bitboards require more memory than piece-list board data structures, but are more execution efficient because many loop-and-compare operations are reduced to a single (or small number of) bitwise operation(s). For example, in mailbox, determining whether
147:
Bitboards are especially effective when the associated bits of various related states on the board fit into a single word or double word of the CPU architecture, so that single bitwise operators like AND and OR can be used to build or query game states.
248:
If the bitboard is larger than the width of the instruction set, multiple instructions will be required to perform a full-width operation on it. So a program using 64-bit bitboards would run faster on a 64-bit processor than on a 32-bit processor.
324:
problem. For full-sized computers, it may cause cache misses between level-one and level-two cache. This is only a potential problem, not a major drawback, as most machines will have enough instruction cache for this not to be an issue.
488:" in the early 1970s. The 64-bit word length of 1970s super computers like Amdahl and Cray machines, facilitated the development of bitboard representations which conveniently mapped the 64-squares of the chessboard to bits of a word.
140:
or presence of pieces on, discrete spaces of a gameboard, by mapping of the space states to bits in the data structure. Bitboards are a more efficient alternative board representation to the traditional
450:
Magic bitboards are an extrapolation of the time-space tradeoff of direct hashing lookup of attack vectors. These use a transmutation of the full attack vector as an index into the hash table.
167:. The scheme was first employed in checkers programs in the 1950s, and since the mid-1970s has been the de facto standard for game board representation in computer automatons.
136:, where each bit corresponds to a game board space or piece. This allows parallel bitwise operations to set or query the game state, or determine moves or plays in the game.
913:- (Example of bitboards in the Java Language and a discussion of why this optimization works with the Java Virtual Machine (www.OnJava.com publisher: O'Reilly 2005))
555:
Use of a perfect hash function is not required for implementation of this method, and provides only a vanishingly small benefit over standard hashing methods.
269:' (or 'count zeros'), the implementation will be significantly handicapped, as these operations are extremely inefficient to code as assembly language loops.
887:
775:
241:
bitboard operations require fewer conditionals and therefore increase pipelining and make effective use of multiple execution units on many CPUs.
1060:
790:
Adel'Son-Vel'Skii, G. M.; Arlazarov, V. L.; Bitman, A. R.; Zhivotovskii, A. A.; Uskov, A. V. (1970). "Programming a computer to play chess".
458:
in conjunction with tricks to reduce the potential size of the hash table that would have to be stored in memory, which is 8*2^64 or 144
897:
644:
599:
105:
892:
1065:
715:
485:
43:
928:
576:
Atkin, Larry R.; Slate, David J. (1983) . "Chess 4.5: the
Northwestern University Chess Program". In Frey, Peter W. (ed.).
1075:
792:
536:
245:
instructions and those may take more than one cycle or otherwise be handicapped compared to their 32-bit instructions.
86:
512:, they allow for very efficient testing for four consecutive discs, by just two shift + AND operations per direction.
58:
371:
32:
959:
See the Crafty article. Written in straight C. Rotated bitboards in the old versions, now uses magic bitboards.
39:
65:
516:
1070:
683:
585:
72:
455:
916:
801:
237:
54:
847:
688:
590:
262:
225:
221:
754:
732:
673:
968:
595:
387:
213:
907:
1028:
809:
693:
581:
989:
C. Bitboard, by Carlos del Cacho. Windows and Linux binaries as well as source available.
648:
484:
in the late 1960s, and again by the authors of the U.S. Northwestern
University program "
429:
these bitboards, a single table lookup replaces lengthy sequences of bitwise operations.
220:
that complete in one cycle and are fully pipelined and cached etc. Nearly all CPUs have
805:
378:
represents square a1, bit 7 is square h1, bit 56 is square a8 and bit 63 is square h8.
367:
351:
piece requires a serial enumeration of such spaces for a piece. This scheme is called
126:
79:
1054:
903:
Frayn, Colin. How to implement bitboards in a chess engine (chess programming theory)
902:
813:
616:
859:
711:
664:
640:
621:
509:
481:
233:
830:
399:" would allow matching the pieces to readily determine whether a target piece on
1025:) engines with some source code including an Othello bitboard in C and assembly.
229:
21:
385:
An example of the use of the bitboards would be determining whether a piece is
133:
1045:
877:
662:
Tannous, Sam (2007-07-23) . "Avoiding
Rotated Bitboards with Direct Lookup".
980:
962:
176:
164:
144:
representation, where each piece or space on the board is an array element.
123:
933:
882:
697:
1006:
950:
714:(1973). "Section 6.4. Algorithm D (Open addressing with double hashing)".
261:
If the processor does not have hardware instructions for 'first one' (or '
974:
156:
1032:
1022:
523:
459:
160:
130:
992:
888:
Laramee, Francois-Dominic. Chess
Programming Part 2: Data Structures.
956:
935:
A 155 line java
Connect-4 program demonstrating the use of bitboards.
477:
678:
986:
1018:
917:
Magic Move-Bitboard
Generation in Computer Chess. Pradyumna Kannan
366:
303:
are stored in a bitmap, and that map is ANDed with the bitmap for
152:
930:
The author of the
Frenzee engine had posted some source examples.
454:
is a misnomer, and simply refers to the generation and use of a
266:
773:"Some Studies in Machine Learning Using the Game of Checkers".
151:
Among the computer game implementations that use bitboards are
217:
15:
258:
issues may increase cache misses or cause cache thrashing.
504:
Many other games besides chess benefit from bitboards.
420:
the use of auxiliary bitboards for the sliding pieces.
291:
requires generating and looping through legal moves of
672:(2) (2 ed.). Durham, North Carolina, USA: 85–91.
46:. Unsourced material may be challenged and removed.
898:Hyatt, Robert. Chess program board representations
971:UCI chess engine ranking second in Elo as of 2010
831:http://people.csail.mit.edu/heinz/dt/node2.html
731:Sherwin, Michael; Isenberg, Gerd (2006-12-04).
391:: bitboards for "all friendly pieces guarding
645:"Rotated Bitboards: New Twist on an Old Idea"
8:
1035:) engine with source code based on bitboard.
519:, they are a possible alternative to arrays.
893:Verhelst, Paul. Chess Board Representations
1046:Overview of bit board usage in word games.
953:Unix, Linux, Windows. Rotated bitboards.
687:
677:
589:
492:published description wasn't until 1997.
106:Learn how and when to remove this message
883:Programming area of the Beowulf project
848:64 bits representation and manipulation
776:IBM Journal of Research and Development
568:
548:
299:. With bitboards, the legal moves of
212:Bitboard representations use parallel
462:. The first observation is that the
395:" and "all opposing pieces attacking
7:
337:Precomputed bitmaps and table lookup
44:adding citations to reliable sources
295:and comparing the final space with
216:operations available on nearly all
1031:See the Edax article. An Othello (
755:"Fast(er) bitboard move generator"
615:Heinz, Ernst A. (September 1997).
415:Auxiliary bitboard representations
236:. Furthermore, modern CPUs have
14:
878:Bitboards - Chessprogramming wiki
910:Bitfields, Bitboards, and Beyond
307:. A non-zero result means that
20:
814:10.1070/RM1970v025n02ABEH003792
717:The Art of Computer Programming
31:needs additional citations for
741:Call it Kindergarten Bitboards
617:"How Dark Thought Plays Chess"
578:Chess Skill in Man and Machine
1:
1061:Game artificial intelligence
793:Russian Mathematical Surveys
753:Hansen, Lasse (2006-06-14).
733:"Magic Bitboards Explained!"
537:Board representation (chess)
1092:
965:See the GNU Chess Article.
860:Checkers Bitboard Tutorial
174:
131:computer systems that play
522:Othello/Reversi (see the
977:C++, rotated bitboards.
1066:Digital tabletop games
698:10.3233/ICG-2007-30204
374:
1019:A complete discussion
517:Conway's Game of Life
456:perfect hash function
370:
238:instruction pipelines
199:to build the tables.
194:Implementation issues
175:Further information:
273:Cache and memory use
40:improve this article
1076:Bit data structures
862:by Jonathan Kreuzer
806:1970RuMaS..25..221A
584:. pp. 82–118.
263:count leading zeros
995:Rotated bitboards.
983:GPL. ELO of 2300.
424:Rotated bitboards
375:
372:Algebraic notation
353:mailbox addressing
328:Incremental update
908:Pepicelli, Glen.
129:commonly used in
122:is a specialized
116:
115:
108:
90:
1083:
1029:Edax (computing)
818:
817:
787:
781:
780:
770:
764:
762:
750:
744:
743:
728:
722:
721:
708:
702:
701:
691:
681:
659:
653:
652:
647:. Archived from
637:
631:
630:
612:
606:
605:
593:
573:
556:
553:
111:
104:
100:
97:
91:
89:
48:
24:
16:
1091:
1090:
1086:
1085:
1084:
1082:
1081:
1080:
1051:
1050:
1042:
1015:
1002:
947:
942:
940:Implementations
925:
874:
869:
856:
844:
839:
827:
825:Further reading
822:
821:
789:
788:
784:
772:
771:
767:
752:
751:
747:
730:
729:
725:
710:
709:
705:
689:10.1.1.561.3461
661:
660:
656:
639:
638:
634:
614:
613:
609:
602:
582:Springer Verlag
575:
574:
570:
565:
560:
559:
554:
550:
545:
533:
502:
473:
448:
446:Magic bitboards
439:
426:
417:
365:
348:
346:Chess bitboards
339:
330:
321:
280:
275:
255:
210:
205:
196:
179:
173:
112:
101:
95:
92:
49:
47:
37:
25:
12:
11:
5:
1089:
1087:
1079:
1078:
1073:
1071:Computer chess
1068:
1063:
1053:
1052:
1049:
1048:
1041:
1038:
1037:
1036:
1026:
1014:
1011:
1010:
1009:
1001:
998:
997:
996:
990:
984:
978:
972:
966:
960:
954:
946:
943:
941:
938:
937:
936:
931:
924:
921:
920:
919:
914:
905:
900:
895:
890:
885:
880:
873:
870:
868:
865:
864:
863:
855:
852:
851:
850:
843:
840:
838:
837:External links
835:
834:
833:
826:
823:
820:
819:
782:
765:
759:Winboard Forum
745:
737:Winboard Forum
723:
720:. Vol. 3.
703:
654:
651:on 2005-04-28.
632:
607:
600:
591:10.1.1.111.926
580:(2 ed.).
567:
566:
564:
561:
558:
557:
547:
546:
544:
541:
540:
539:
532:
529:
528:
527:
520:
513:
501:
498:
472:
469:
447:
444:
438:
437:Direct hashing
435:
425:
422:
416:
413:
364:
361:
347:
344:
338:
335:
329:
326:
320:
317:
279:
276:
274:
271:
254:
251:
209:
206:
204:
201:
195:
192:
172:
169:
127:data structure
114:
113:
96:September 2019
28:
26:
19:
13:
10:
9:
6:
4:
3:
2:
1088:
1077:
1074:
1072:
1069:
1067:
1064:
1062:
1059:
1058:
1056:
1047:
1044:
1043:
1039:
1034:
1030:
1027:
1024:
1020:
1017:
1016:
1012:
1008:
1004:
1003:
1000:Closed source
999:
994:
991:
988:
985:
982:
979:
976:
973:
970:
967:
964:
961:
958:
955:
952:
949:
948:
944:
939:
934:
932:
929:
927:
926:
923:Code examples
922:
918:
915:
912:
911:
906:
904:
901:
899:
896:
894:
891:
889:
886:
884:
881:
879:
876:
875:
871:
866:
861:
858:
857:
853:
849:
846:
845:
841:
836:
832:
829:
828:
824:
815:
811:
807:
803:
799:
795:
794:
786:
783:
778:
777:
769:
766:
760:
756:
749:
746:
742:
738:
734:
727:
724:
719:
718:
713:
712:Knuth, Donald
707:
704:
699:
695:
690:
685:
680:
675:
671:
667:
666:
658:
655:
650:
646:
642:
641:Hyatt, Robert
636:
633:
629:(3): 166–176.
628:
624:
623:
618:
611:
608:
603:
601:0-387-90790-4
597:
592:
587:
583:
579:
572:
569:
562:
552:
549:
542:
538:
535:
534:
530:
525:
521:
518:
514:
511:
507:
506:
505:
499:
497:
493:
489:
487:
483:
479:
470:
468:
465:
464:outer squares
461:
457:
453:
445:
443:
436:
434:
430:
423:
421:
414:
412:
408:
406:
402:
398:
394:
390:
389:
383:
379:
373:
369:
362:
360:
358:
354:
345:
343:
342:enumeration.
336:
334:
327:
325:
318:
316:
314:
310:
306:
302:
298:
294:
290:
286:
277:
272:
270:
268:
264:
259:
252:
250:
246:
242:
239:
235:
231:
227:
223:
219:
215:
207:
203:Processor use
202:
200:
193:
191:
187:
183:
178:
170:
168:
166:
162:
158:
154:
149:
145:
143:
137:
135:
132:
128:
125:
121:
110:
107:
99:
88:
85:
81:
78:
74:
71:
67:
64:
60:
57: –
56:
52:
51:Find sources:
45:
41:
35:
34:
29:This article
27:
23:
18:
17:
1021:of Othello (
1005:DarkThought
909:
797:
791:
785:
774:
768:
758:
748:
740:
736:
726:
716:
706:
669:
665:ICGA Journal
663:
657:
649:the original
635:
626:
622:ICCA Journal
620:
610:
577:
571:
551:
510:Connect Four
503:
494:
490:
482:Soviet Union
480:team in the
474:
463:
451:
449:
440:
431:
427:
418:
409:
404:
400:
396:
392:
386:
384:
380:
376:
356:
352:
349:
340:
331:
322:
312:
308:
304:
300:
296:
292:
288:
284:
281:
260:
256:
247:
243:
211:
197:
188:
184:
180:
150:
146:
141:
138:
119:
117:
102:
93:
83:
76:
69:
62:
50:
38:Please help
33:verification
30:
975:Gray Matter
945:Open source
842:Calculators
679:0704.3773v2
500:Other games
171:Description
134:board games
1055:Categories
1040:Word games
993:Simontacci
800:(2): 221.
563:References
267:count ones
165:word games
66:newspapers
55:"Bitboard"
1007:Home Page
981:KnightCap
969:Stockfish
963:GNU Chess
684:CiteSeerX
586:CiteSeerX
526:article).
357:bitboards
177:Bit field
124:bit array
872:Articles
854:Checkers
643:(1999).
531:See also
460:exabytes
405:en prise
388:en prise
363:Standard
311:attacks
287:attacks
265:') and '
157:checkers
120:bitboard
1033:Reversi
1023:Reversi
1013:Othello
951:Beowulf
802:Bibcode
779:. 1959.
524:Reversi
515:In the
471:History
214:bitwise
161:othello
142:mailbox
80:scholar
987:Pepito
957:Crafty
686:
598:
588:
478:Kaissa
232:, and
82:
75:
68:
61:
53:
867:Chess
674:arXiv
543:Notes
486:Chess
452:Magic
401:space
397:space
393:space
313:space
309:piece
305:space
301:piece
297:space
293:piece
289:space
285:piece
153:chess
87:JSTOR
73:books
596:ISBN
319:Cons
278:Pros
253:Cons
218:CPUs
208:Pros
163:and
59:news
810:doi
694:doi
508:In
403:is
234:XOR
230:NOR
222:AND
42:by
1057::
808:.
798:25
796:.
757:.
739:.
735:.
692:.
682:.
670:30
668:.
627:20
625:.
619:.
594:.
407:.
359:.
315:.
228:,
226:OR
224:,
159:,
155:,
118:A
816:.
812::
804::
763:.
761:.
700:.
696::
676::
604:.
109:)
103:(
98:)
94:(
84:·
77:·
70:·
63:·
36:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
