Home

Welcome to the roece wiki! A chess search space is identified by its initial position, which.

A prime position is an arrangement of pieces and rule states (such as castling and en passant) that can not exist in any other search space.

A prime search space is created whenever any of the following occur: The game begins (the initial position is by definition a prime position) A pawn moves A piece is captured Castling en passant is possible Pawn promotion

By concentrating on completing one search space the number of positions to traverse is greatly reduced. So any prime position is spooled off to a separate queue and only positions in the current search space are retained as belonging to the search space. Once one search space completes, then the next search space is taken from the queue and processed completely.

A terminal position is a position that can not produce any additional unique positions. These are generated when a move results in any of the following conditions: Checkmate Stalemate Repeated position (loop) Draw

A game is a graph of positions and moves: The root of the graph is a prime position Nodes of the graph are the individual unique positions. An edge between nodes is a legal move. old positions -> move -> new position

Size of a search space

A position is composed of: 64-bit (8-bytes) map of occupied squares (pop-map) 32-nibble array (16-bytes) of piece information (indexed to bits in pop-map 16-bits (2-bytes) of game status Hence a position is 26-bytes wide, or 208-bits, which results in an impossible upper bound of 2^208 (4.1137614e+62). This means the total number of possible positions cannot approach and hence the total number of games cannot approach this impossible upper bound.

Not all bits in the position can be set.

We know that at most 32 bits of the pop-map can be set (as there are a maximum of 32 pieces on the board.) So the pop-map has 32 set bits and 32 unset bits. This means that every one of the 32 bits has 32 other positions to occupy. Taking one set bit, there are now 31 bits in their original positions, and 32 positions to move that bit to. So the combination is 3132 for that one bit, and given 32 possible bits, the total number would be 32(3132) possible results from moving one bit, or 31744 possible positions as a lower bound. The pop-map only records which squares are occupied, but each square can be occupied by most any piece.

Most pieces have an occupation space of 64 squares - basically they can occupy any square on the board. White pawns, however, cannot occupy the first rank, and black pawns cannot occupy the eighth rank. So pawns have an occupation space of 56 squares. But even this is restricted.

Pawn occupation space

White pawns cannot occupy the first rank, and black pawns cannot occupy the eight rank. Since pawns only move forward, or diagonal forward on capture/en passant, then the possible paths a pawn can take can be calculated based on its home file.

pawns on file a and f have 12 + 15 + 12 + 9 + 6 + 3 = 57
              b and g have 10 + 18 + 15 + 12 + 9 + 6 + 3 = 73
              c and f have 8 + 15 + 18 + 15 + 12 + 9 + 6 + 2 = 85
              d and e have 6 + 12 + 15 + 18 + 15 + 12 + 9 + 4 = 91

possible positions via move or capture, making a total of 306 possible moves/side or 612 total.

Without capture/en passant, the pawn occupation space is simply 8*7=72 or 144 total.

Bishop occupation space is limited to 32 x 4 = 128 total.

Total occupation space / search space upper bound

The other 16 pieces can theoretically occupy any square on the board, although this is not possible by the Rules. But to calculate an impossible upper range we can make some gross calculations: The first piece can occupy any square (64) and the second piece can occupy any other square (63), so the possible number of combinations is 64x63 (4032). The third piece can occupy any unoccupied square (62) making the number of combinations 64x62x62 (249984). Through all 16 pieces, the total number of combinations is 1.02213E+28, which is less than 2^94 with no pawn on board. With pawns, there are 16 less squares, so this reduces the occupation space to only 48 squares, which is 4.71777E+25 with pawns on board, which is less than 2^86. Factoring in the fixed size of the pawn occupation space (144) this results in a total occupation space of all pieces on board to an impossible upper bound of 6.7935888e+27, which is less than 2^93. Hence all possible combinations can be represented in 92-bits.

This means that all subsequent search spaces are at most < 2^93 positions large, but with any pieces removed reduces the upper bound: 31 pieces 9.82869E+23 < 2^80 30 pieces 2.09121E+22 < 2^75 29 pieces 4.54611E+20 < 2^69

So the size of the search space reduces by several orders of magnitude as material is removed from the board.

The initial position

This is the starting position of the game with all pieces on their home squares. When traversing a position, the engine applies all legal moves to each piece in turn, which generates new positions. If a move generates a new root position, then that position is not further traversed. So, from the initial position (first root position,) not much can happen since any movement of a pawn results in new root positions, so the only moves that exist in this search space will be the movement of knights and rooks (oscillating between a1 and a2, for example), blocked in by pawns fixed at their origins.

The initial position will therefore generate a fair number of prime positions only from initial pawn moves on the white side, and a gyration of knight and rook moves and should terminate relatively early from loops.