| This article is part of the series on |
| Chess programming |
|---|
 |
The 0x88 chess board representation is a square-centric method of representing the chess board in computer chess programs. The number 0x88 is a hexadecimal integer (136 10 , 210 8 , 10001000 2 ). The rank and file positions are each represented by a nibble (hexadecimal digit), and the bit gaps simplify a number of computations to bitwise operations.
In the 0x88 board representation, the layout is spread out to cover an 8-by-16 board, equal to the size of two adjacent chessboards. Each square of the 8-by-16 matrix is assigned a number as can be seen in the board layout table. In this scheme each nibble represents a rank or a file, so that the 8-bit integer 0x42 represents the square at (4,2) in zero-based numbering, i.e. c5 in standard algebraic notation. [1]
Adding 16 to a number for a square results in the number for the square one row above, and subtracting 16 results in the number for the square one row below. To move from one column to another the number is increased or decreased by one. [2] In hexadecimal notation, legal chess positions (A1-H8) are always below 0x88. This layout simplifies many computations that chess programs need to perform by allowing bitwise operations instead of comparisons. [3]
| 0x00 (a) | 0x01 (b) | 0x02 (c) | 0x03 (d) | 0x04 (e) | 0x05 (f) | 0x06 (g) | 0x07 (h) | 0x08 | 0x09 | 0x0A | 0x0B | 0x0C | 0x0D | 0x0E | 0x0F | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0x70 (8) | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 7A | 7B | 7C | 7D | 7E | 7F |
| 0x60 (7) | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 6A | 6B | 6C | 6D | 6E | 6F |
| 0x50 (6) | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 5A | 5B | 5C | 5D | 5E | 5F |
| 0x40 (5) | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 4A | 4B | 4C | 4D | 4E | 4F |
| 0x30 (4) | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 3A | 3B | 3C | 3D | 3E | 3F |
| 0x20 (3) | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 2A | 2B | 2C | 2D | 2E | 2F |
| 0x10 (2) | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 1A | 1B | 1C | 1D | 1E | 1F |
| 0x00 (1) | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 0A | 0B | 0C | 0D | 0E | 0F |
The modern standard to identify the squares on a chessboard and moves in a game is algebraic notation, whereby each square of the board is identified by a unique coordinate pair — a letter between a and h for the horizontal coordinate, known as the file, and a number between 1 and 8 for the vertical coordinate, known as the rank.
In computer chess, file-rank coordinates are internally represented as integers ranging from 0 to 7, with file a mapping to 0 through to file h mapping to 7, while the rank coordinate is shifted down by one to the range 0 to 7.
An advantage of the 0x88 coding scheme is that values can be easily converted between 0x88 representation and file-rank coordinates using only bitwise operations, which are simple and efficient for computer processors to work with. To convert a zero-based file-rank coordinate to 0x88 value:
Thus, a1 corresponds to , with all 8 of the bits set to , b2 corresponds to , and h8 corresponds to . [1]
To convert an 0x88 value to a file-rank coordinate pair:
Note: In the above formulas, << and >> represent left and right logical bit shift operations respectively while & represents bitwise and.
Off-the-board detection is a feature of chess programs which determines whether a piece is on or off the legal chess board. In 0x88, the highest bit of each nibble represents whether a piece is on the board or not. Specifically, out of the 8 bits to represent a square, the fourth and the eighth must both be 0 for a piece to be located within the board. [4] This allows off-the-board detection by bitwise and operations. If $square AND 0x88 (or, in binary, 0b10001000) is non-zero, then the square is not on the board. [5] This bitwise operation requires fewer computer resources than integer comparisons. This makes calculations such as illegal move detection faster. [5]
The difference of valid 0x88 coordinates A and B is unique with respect to distance and direction, which is not true for classical packed three-bit rank and file coordinates. That makes lookups for Manhattan distance, possible piece attacks, and legal piece moves more resource-friendly. While classical square coordinates in the 0–63 range require 4K-sized tables (64×64), the 0x88 difference takes 1/16 that or 256-sized tables—or even 16 less. [6]
An offset of 119 (0x77 as the maximum valid square index) is added, to make ±119 a 0–238 range (a size of 240 for alignment reasons). [6]
0x88Diff = 0x77 + A − B
Though the 0x88 representation was initially popular, it has been mostly replaced by the system of bitboards. [7]
In computing, floating-point arithmetic (FP) is arithmetic using formulaic representation of real numbers as an approximation to support a trade-off between range and precision. For this reason, floating-point computation is often used in systems with very small and very large real numbers that require fast processing times. In general, a floating-point number is represented approximately with a fixed number of significant digits and scaled using an exponent in some fixed base; the base for the scaling is normally two, ten, or sixteen. A number that can be represented exactly is of the following form:
In mathematics and computing, the hexadecimal numeral system is a positional numeral system that represents numbers using a radix (base) of 16. Unlike the decimal system representing numbers using 10 symbols, hexadecimal uses 16 distinct symbols, most often the symbols "0"–"9" to represent values 0 to 9, and "A"–"F" to represent values from 10 to 15.
A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes. The values are usually used to index a fixed-size table called a hash table. Use of a hash function to index a hash table is called hashing or scatter storage addressing.
In computer science, an integer is a datum of integral data type, a data type that represents some range of mathematical integers. Integral data types may be of different sizes and may or may not be allowed to contain negative values. Integers are commonly represented in a computer as a group of binary digits (bits). The size of the grouping varies so the set of integer sizes available varies between different types of computers. Computer hardware nearly always provides a way to represent a processor register or memory address as an integer.
In computing, a nibble (occasionally nybble, nyble, or nybl to match the spelling of byte) is a four-bit aggregation, or half an octet. It is also known as half-byte or tetrade. In a networking or telecommunication context, the nibble is often called a semi-octet, quadbit, or quartet. A nibble has sixteen (24) possible values. A nibble can be represented by a single hexadecimal digit (0–F) and called a hex digit.
A computer number format is the internal representation of numeric values in digital device hardware and software, such as in programmable computers and calculators. Numerical values are stored as groupings of bits, such as bytes and words. The encoding between numerical values and bit patterns is chosen for convenience of the operation of the computer; the encoding used by the computer's instruction set generally requires conversion for external use, such as for printing and display. Different types of processors may have different internal representations of numerical values and different conventions are used for integer and real numbers. Most calculations are carried out with number formats that fit into a processor register, but some software systems allow representation of arbitrarily large numbers using multiple words of memory.
Double-precision floating-point format is a computer number format, usually occupying 64 bits in computer memory; it represents a wide dynamic range of numeric values by using a floating radix point.
A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" (zero) and "1" (one).
A bitboard is a specialized bit array data structure commonly used in computer systems that play board games, 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.
Dot-decimal notation is a presentation format for numerical data. It consists of a string of decimal numbers, using the full stop (dot) as a separation character.
In computer science, a mask or bitmask is data that is used for bitwise operations, particularly in a bit field. Using a mask, multiple bits in a byte, nibble, word, etc. can be set either on or off, or inverted from on to off in a single bitwise operation. An additional use of masking involves predication in vector processing, where the bitmask is used to select which element operations in the vector are to be executed and which are not.
In computing, signed number representations are required to encode negative numbers in binary number systems.
Bit manipulation is the act of algorithmically manipulating bits or other pieces of data shorter than a word. Computer programming tasks that require bit manipulation include low-level device control, error detection and correction algorithms, data compression, encryption algorithms, and optimization. For most other tasks, modern programming languages allow the programmer to work directly with abstractions instead of bits that represent those abstractions. Source code that does bit manipulation makes use of the bitwise operations: AND, OR, XOR, NOT, and possibly other operations analogous to the boolean operators; there are also bit shifts and operations to count ones and zeros, find high and low one or zero, set, reset and test bits, extract and insert fields, mask and zero fields, gather and scatter bits to and from specified bit positions or fields. Integer arithmetic operators can also effect bit-operations in conjunction with the other operators.
Signed zero is zero with an associated sign. In ordinary arithmetic, the number 0 does not have a sign, so that −0, +0 and 0 are identical. However, in computing, some number representations allow for the existence of two zeros, often denoted by −0 and +0, regarded as equal by the numerical comparison operations but with possible different behaviors in particular operations. This occurs in the sign and magnitude and ones' complement signed number representations for integers, and in most floating-point number representations. The number 0 is usually encoded as +0, but can be represented by either +0 or −0.
Board representation in computer chess is a data structure in a chess program representing the position on the chessboard 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 as well as maintaining the state of the game during play. Several different board representations exist. Chess programs often utilize more than one board representation at different times, for efficiency. Execution efficiency and memory footprint are the primary factors in choosing a board representation; secondary considerations are effort required to code, test and debug the application.
The cyclic redundancy check (CRC) is based on division in the ring of polynomials over the finite field GF(2), that is, the set of polynomials where each coefficient is either zero or one, and arithmetic operations wrap around.
In computing, bit numbering is the convention used to identify the bit positions in a binary number.
Single-precision floating-point format is a computer number format, usually occupying 32 bits in computer memory; it represents a wide dynamic range of numeric values by using a floating radix point.
Sequence Alignment Map (SAM) is a text-based format originally for storing biological sequences aligned to a reference sequence developed by Heng Li and Bob Handsaker et al. It was developed when the 1000 Genomes Project wanted to move away from the MAQ mapper format and decided to design a new format. The overall TAB-delimited flavour of the format came from an earlier format inspired by BLAT’s PSL. The name of SAM came from Gabor Marth from University of Utah, who originally had a format under the same name but with a different syntax more similar to a BLAST output. It is widely used for storing data, such as nucleotide sequences, generated by next generation sequencing technologies, and the standard has been broadened to include unmapped sequences. The format supports short and long reads produced by different sequencing platforms and is used to hold mapped data within the Genome Analysis Toolkit (GATK) and across the Broad Institute, the Wellcome Sanger Institute, and throughout the 1000 Genomes Project.
In number theory, the Moser–de Bruijn sequence is an integer sequence named after Leo Moser and Nicolaas Govert de Bruijn, consisting of the sums of distinct powers of 4, or equivalently the numbers whose binary representations are nonzero only in even positions.
