561:
representing its legal moves. There were several lists, one set for white pieces and another for black pieces. The lists were usually divided into pieces and pawns. This was a compact representation because most squares of the board are unoccupied, but inefficient because acquiring information about the relationship of pieces to the board or to each other was tedious. Piece lists are still used by many of today's programs in conjunction with a separate board representation structure, to give serial access to the pieces without searching the board.
44:
679:
spaces attacked by these pieces. The bitboard is rotated 90° for file indexing and either 45° or -45° for diagonal indexing. Rotating a chessboard is conceptually challenging, and rotating a bitboard is computationally inelegant, but the transformation avoids serially enumerating the piece moves, or a lengthy sequence of shifting and masking a bitboard of the attack map of the piece to take into account the board configuration.
670:
piece resides which, excluding spaces occupied by friendly pieces (one bitwise operation), yields the legal moves of the piece. But the moves of the sliding pieces (rooks, bishops, queens) are indeterminate because the moves of these pieces depend on the configuration of other pieces on the board. So special and complex data structures have been devised to represent their moves.
654:. A bitboard is a 64-bit sequence of bits (0 or 1), which indicates the absence or presence (false or true) of some state of each space on the board. A board position can then be represented using a series of bitboards. For example, a series of bitboards for each piece type, for each side, can represent the board position.
727:
CCR uses 4 bits per square to represent the occupancy of the square, an entire rank can be represented in 32 bits, and the board in 8 registers (with an additional one for remaining position information). The occupancy code for a square can be dialed out of a register and added to the program counter
678:
Rotated bitboards is a move generation technique for the sliding pieces that uses rotated copies of a bitboard to place spaces (bits) in a file or diagonal into adjacent bits analogous to the bits representing a rank. These bits can be extracted and used as an index into a table to obtain the map of
596:
Better memory usage can be achieved with a 10x12 array, which provides the same functionalities as a 12x12 one by overlapping the leftmost and rightmost edge files (which are marked as off-the-board). Some chess engines use 16x16 arrays to improve the speed of the rank and file number conversion and
560:
Some of the very earliest chess programs working with extremely limited amounts of memory maintained serial lists (arrays) of the pieces in a conveniently searchable order, like largest to smallest; associated with each piece was its location on the board as well as other information, such as squares
611:
The 0x88 method takes advantage of the fact that a chessboard's 8x8 dimensions are an even power of two (i.e. 8 squared). The board uses a one-dimensional array of size 16x8 = 128, numbered 0 to 127 rather than an array of size 64. It is basically two boards next to each other, the actual board on
466:
and associated game state. Board representation is fundamental to all aspects of a chess program including move generation, the evaluation function, and making and unmaking moves (i.e. search) as well as maintaining the state of the game during play. Several different board representations exist.
592:
A problem with this approach arises during move generation. Each move has to be checked to ensure it does not wrap around an edge of the board, which significantly slows down the process. One solution is to use a 12x12 array instead, with the outer edges filled with, say, the value 99. During move
541:
The board state is associated with each node of the game tree, representing a position arrived at by a move, whether that move was played over the board, or generated as part of the program's search. It is conceptually local to the node, but may be defined globally, and incrementally updated from
533:
rule. To determine this rule, a complete history of the game from the last irreversible action (capture, pawn movement, or castling) needs to be maintained, and so, is generally tracked in separate data structures. Without this information, models may repeat the position despite having a winning
732:, branching directly to code to generate moves for the type of piece on this square (if any). Although the program is longer than for conventional move generation methods, no checks for the edge of the board are required, and no moves off the board are possible, increasing move generation speed.
669:
A substantive advantage of bitboards is that enables maps for the spaces attacked by each type of piece on each space of the board to be pre-collated and stored in a table, so that possible moves of the piece can be retrieved in a single memory fetch of the attack map for the square on which the
691:
to directly index a table of precomputed attack vectors based on the occupancy bits in the masked portion. One such scheme that uses a perfect hash function along with tricks to minimize the potential size of the table that must be stored in memory, is called "magic bitboards".
500:. The name of this is sometimes a bit confusing, as it is 50 moves by each player, and therefore 100 half-moves, or ply. For example, if the previous 80 half-moves passed without a capture or a pawn move, the fifty-move rule will kick in after another twenty half-moves.
573:(or, equivalently, a 64 element one-dimensional array). Each array element would identify what piece occupied the given square, or alternatively, if the square is empty. A common encoding is to consider 0 as empty, positive as white, and negative as black, e.g., white
636:). A non-zero result indicates that the square is off the main board. In addition, the difference between two squares' coordinates uniquely determines whether those two squares are along the same row, column, or diagonal (a common query used for determining check).
735:
The drawbacks of CCR are: 1) dependency on 32-bit word size; 2) availability of at least 9 free registers to the API; 3) necessity of assembly programming on a CISC architecture to access the registers; 4) non-portability of assembly application.
537:
The board state may also contain secondary derived information like which pieces attack a square; for squares containing pieces, which spaces are attacked or guarded by that piece; which pieces are pinned; and other convenient or temporary state.
665:
entities instead of iteration to manipulate and derive information about the state of the board. This makes maximal use of the hardware available, especially as 64-bit processors have become mainstream.
752:
There are 6 types of pieces: king, queen, rook, bishop, knight, pawn for each of black and white plus unoccupied square, for a total of 13 states, representable in 4 bits or 2=16 possible codes.
474:
Early programs used piece lists and square lists, both array based. Most modern implementations use a more elaborate but more efficient bit array approach called
612:
the left while the board on the right would contain illegal territory. The binary layout for a legal board coordinate's rank and file within the array is
438:
471:
are the primary factors in choosing a board representation; secondary considerations are effort required to code, test and debug the application.
832:
624:). When generating moves from the main board, one can check that a destination square is on the main board before consulting the array simply by
130:
593:
generation, the operation to check for a piece on the destination square will also indicate whether the destination square is off the board.
89:
431:
467:
Chess programs often utilize more than one board representation at different times, for efficiency. Execution efficiency and
863:
100:
105:
784:
424:
712:
generated by a computer game playing program. For fast searching of the table, a hash function may be used, such as
724:
Other methods such as
Compact Chessboard Representation (CCR) have been proposed, but none has gained acceptance.
225:
95:
120:
486:
A full description of a chess position, i.e. the position "state", must contain the following elements:
621:
220:
170:
616:(The r's are the 3 bits used to represent the rank. The f's for the file). For example, 0x71 (binary
240:
880:, Tech. Rep. 88, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, (1969).
17:
896:
180:
650:
A more efficient but more elaborate board representation than the array-based structures is the
355:
330:
290:
115:
21:
200:
135:
570:
527:
400:
8:
705:
701:
380:
125:
85:
78:
165:
110:
826:
395:
175:
875:
625:
468:
345:
305:
569:
One of the simplest ways to represent a board is to create an 8x8 two-dimensional
713:
497:
320:
148:
582:
578:
459:
455:
340:
325:
193:
152:
65:
35:
890:
811:
788:
688:
410:
385:
370:
300:
235:
780:
729:
658:
574:
530:
365:
258:
205:
687:
The masked ranks, files and diagonals of sliding pieces can be used via a
629:
280:
270:
478:
which map bits of a 64-bit word or double word to squares of the board.
519:
463:
350:
285:
215:
709:
512:
405:
390:
335:
310:
295:
265:
43:
651:
645:
508:
504:
210:
849:
Frey, Peter W., ed. (1983) , "An introduction to computer chess",
526:
Board representation typically does not include the status of the
160:
662:
360:
315:
275:
245:
230:
375:
657:
The advantage to this representation is the ability to use
606:
60:
704:
is a cache of previously seen positions, and associated
877:
A New
Hashing Method with Application for Game Playing
534:
advantage, resulting in an excessive amount of draws.
503:
Whether either player is permanently disqualified to
462:
in a chess program representing the position on the
597:allow some special coding tricks for attacks etc.
888:
16:For User interface board representations, see
432:
831:: CS1 maint: numeric names: authors list (
844:
842:
439:
425:
839:
775:
773:
771:
769:
542:node to node as the tree is traversed.
490:The location of each piece on the board
889:
695:
585:+3, and so on. This scheme is called
809:
785:"Chess program board representations"
101:Efficiently updatable neural networks
30:This article is part of the series on
848:
766:
716:, to speed finding matching boards.
673:
620:) would represent the square b8 (in
13:
14:
908:
853:, Springer–Verlag, pp. 55–56
779:
719:
682:
106:Handcrafted evaluation functions
42:
868:
857:
851:Chess Skill In Man and Machine
803:
746:
600:
564:
555:
550:
481:
1:
759:
639:
7:
864:0x88 method. Bruce Moreland
581:+2, black knight −2, white
121:Stochastic gradient descent
10:
913:
643:
604:
171:Principal variation search
15:
577:+1, black pawn −1, white
874:Albert Lindsey Zobrist,
739:
545:
493:Whose turn it is to move
18:Forsyth-Edwards Notation
813:mnj12/chessDeepLearning
628:the square number with
181:Monte Carlo tree search
291:Dragon by Komodo Chess
116:Reinforcement learning
22:Portable Game Notation
136:Unsupervised learning
54:Board representations
810:mnj12 (2021-07-07),
661:operations upon the
528:threefold repetition
522:capture is possible.
452:Board representation
86:Deep neural networks
79:Evaluation functions
791:on 12 February 2013
702:transposition table
696:Transposition table
126:Supervised learning
111:Piece-square tables
622:Algebraic notation
166:Alpha-beta pruning
674:Rotated bitboards
498:50-move draw rule
449:
448:
176:Quiescence search
155:search algorithms
36:Chess programming
904:
881:
872:
866:
861:
855:
854:
846:
837:
836:
830:
822:
821:
820:
807:
801:
800:
798:
796:
787:. Archived from
777:
753:
750:
469:memory footprint
441:
434:
427:
346:Leela Chess Zero
46:
27:
26:
912:
911:
907:
906:
905:
903:
902:
901:
887:
886:
885:
884:
873:
869:
862:
858:
847:
840:
824:
823:
818:
816:
808:
804:
794:
792:
778:
767:
762:
757:
756:
751:
747:
742:
722:
714:Zobrist hashing
698:
685:
676:
648:
642:
635:
619:
615:
609:
603:
567:
558:
553:
548:
484:
445:
416:
415:
261:
251:
250:
196:
194:Chess computers
186:
185:
156:
141:
140:
81:
71:
70:
56:
25:
12:
11:
5:
910:
900:
899:
897:Computer chess
883:
882:
867:
856:
838:
802:
764:
763:
761:
758:
755:
754:
744:
743:
741:
738:
721:
718:
697:
694:
684:
681:
675:
672:
644:Main article:
641:
638:
633:
617:
613:
605:Main article:
602:
599:
566:
563:
557:
554:
552:
549:
547:
544:
524:
523:
516:
501:
496:Status of the
494:
491:
483:
480:
460:data structure
456:computer chess
447:
446:
444:
443:
436:
429:
421:
418:
417:
414:
413:
408:
403:
398:
393:
388:
383:
378:
373:
368:
363:
358:
353:
348:
343:
338:
333:
328:
323:
318:
313:
308:
303:
298:
293:
288:
283:
278:
273:
268:
262:
257:
256:
253:
252:
249:
248:
243:
238:
233:
228:
223:
218:
213:
208:
203:
197:
192:
191:
188:
187:
184:
183:
178:
173:
168:
163:
157:
147:
146:
143:
142:
139:
138:
133:
128:
123:
118:
113:
108:
103:
98:
93:
82:
77:
76:
73:
72:
69:
68:
63:
57:
52:
51:
48:
47:
39:
38:
32:
31:
9:
6:
4:
3:
2:
909:
898:
895:
894:
892:
879:
878:
871:
865:
860:
852:
845:
843:
834:
828:
815:
814:
806:
790:
786:
782:
781:Hyatt, Robert
776:
774:
772:
770:
765:
749:
745:
737:
733:
731:
725:
720:Other methods
717:
715:
711:
707:
703:
693:
690:
689:hash function
683:Direct lookup
680:
671:
667:
664:
660:
655:
653:
647:
637:
632:0x88 (binary
631:
627:
623:
608:
598:
594:
590:
588:
584:
580:
576:
572:
562:
543:
539:
535:
532:
529:
521:
517:
514:
510:
506:
502:
499:
495:
492:
489:
488:
487:
479:
477:
472:
470:
465:
461:
457:
453:
442:
437:
435:
430:
428:
423:
422:
420:
419:
412:
409:
407:
404:
402:
399:
397:
394:
392:
389:
387:
384:
382:
379:
377:
374:
372:
369:
367:
364:
362:
359:
357:
354:
352:
349:
347:
344:
342:
339:
337:
334:
332:
329:
327:
324:
322:
319:
317:
314:
312:
309:
307:
304:
302:
299:
297:
294:
292:
289:
287:
284:
282:
279:
277:
274:
272:
269:
267:
264:
263:
260:
259:Chess engines
255:
254:
247:
244:
242:
239:
237:
234:
232:
229:
227:
224:
222:
219:
217:
214:
212:
209:
207:
204:
202:
199:
198:
195:
190:
189:
182:
179:
177:
174:
172:
169:
167:
164:
162:
159:
158:
154:
150:
145:
144:
137:
134:
132:
129:
127:
124:
122:
119:
117:
114:
112:
109:
107:
104:
102:
99:
97:
94:
91:
87:
84:
83:
80:
75:
74:
67:
64:
62:
59:
58:
55:
50:
49:
45:
41:
40:
37:
34:
33:
29:
28:
23:
19:
876:
870:
859:
850:
817:, retrieved
812:
805:
793:. Retrieved
789:the original
748:
734:
726:
723:
699:
686:
677:
668:
659:bit parallel
656:
649:
610:
595:
591:
589:addressing.
586:
568:
559:
540:
536:
525:
485:
475:
473:
451:
450:
226:Deep Thought
206:ChessMachine
131:Texel tuning
90:Transformers
53:
728:to index a
706:evaluations
630:hexadecimal
601:0x88 method
565:Square list
556:Piece lists
551:Array based
482:Board state
281:CuckooChess
271:Chess Tiger
819:2021-07-07
795:15 January
760:References
730:jump table
520:en passant
464:chessboard
351:MChess Pro
286:Deep Fritz
216:Cray Blitz
710:game tree
640:Bitboards
513:queenside
476:bitboards
406:Turochamp
396:Stockfish
391:SmarThink
336:KnightCap
311:GNU Chess
296:Fairy-Max
266:AlphaZero
221:Deep Blue
96:Attention
66:Bitboards
891:Category
827:citation
652:bitboard
646:Bitboard
634:10001000
618:01110001
614:0rrr0fff
509:kingside
381:Shredder
241:Mephisto
211:ChipTest
708:, in a
587:mailbox
507:, both
356:Mittens
321:Houdini
161:Minimax
663:64-bit
626:ANDing
583:bishop
579:knight
518:If an
505:castle
361:MuZero
341:Komodo
331:Junior
326:Ikarus
316:HIARCS
276:Crafty
246:Saitek
231:HiTech
740:Notes
571:array
546:Types
458:is a
411:Zappa
401:Torch
386:Sjeng
376:Rybka
371:REBEL
306:Fruit
301:Fritz
236:Hydra
201:Belle
149:Graph
833:link
797:2012
607:0x88
575:pawn
531:draw
511:and
366:Naum
153:tree
151:and
61:0x88
20:and
454:in
893::
841:^
829:}}
825:{{
783:.
768:^
700:A
835:)
799:.
515:.
440:e
433:t
426:v
92:)
88:(
24:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
