First published - around 2011
Last update - April 2017 (added comments)
Scope
This document describes Chess Storage Algorithms / Systems / Algorithmic Code created by Anup K Parikh. No distinction will be made between an algorithm, a system or algorithmic code in this document.
The following systems are described in this document:
1) Chess Storage System (Positions)
2) Chess Storage System (Games)
Notation and Assumptions
The chess board consists of ranks (rows 1 to 8) and files (columns a to h) where the square a1 = 00, b1 = 01, h1 = 07, a2 = 10, h2 = 17, h8 = 77 (in octal or radix 8). In other words, the square a1 = 0, b1 = 1, h1 = 7, a2 = 8, h2 = 15, h3 = 23, and so on to, h8 = 63 (in decimal 0 to 63). The bottom left square is the square 00 (a1) which is a black square and the said bottom comprises the white side.
The information to be stored for a chess position (standard chess) consists of:
1) The position of each piece on the chess board
2) Castling rights
3) En pass information
4) Color to move
The 'Color to move' information can be discarded as the storage system can be designed to store all positions with reference to white (it is always white to move) or black (it is always black to move). The positions with other color to move can be inverted first and then a search be performed. For example, a position with just one white rook (kings are in by default) and black to move is similar to an equivalent (inverted board) position with just one black rook and white to move.
However, if a system is being used for saving games (partially played games which may be restored later) then the 'Color to move' information will be needed. This system will not store the 'Color to move' information. If needed 'Color to move' information can be appended at the end. The 'Color to move' information is a single bit and when used with this system this bit may indicate whether the board is an inverted board or not or it may indicate directly the color to move (Implementation defined).
Some other contextual information that may be associated with standard chess is:
1) 3 Repetition Rule
2) 50 Move Rule
For the '3 Repetition Rule', complete game history is needed, but since this system is concerned only with storage of positions without context of history, the '3 Repetition Rule' can be discarded. As such, from any position, the '3 Repetition Rule' can be activated if the players opt in to moves that may lead to three repetitions. So, this is useless unless games are being stored rather than positions.
If from some board position, suppose a forced checkmate (all possibilities leading to a checkmate) can be achieved (probably without movement of any pawn or without any capture), then that position is a position of interest and it may be marked as a winning position. Sometimes the number of moves required may be more than 50 (with perfect play, in case of imperfect play the moves may be less), and suppose that none of those 50+ moves is a pawn move or a capture, still that position is a winning position and hence a position of interest. Hence, the '50 Move Rule' will be ignored. However, if required (for sake of completeness or when games are being stored) this information can be appended at the end (Implementation defined).
The primary and intended use for these systems is long term storage (for standard chess). These systems are designed to be fairly fast (not compute intensive). In other words, the implementation of these systems will be fairly fast, regardless of the complexity of implementation.
The 'Chess Storage System (Positions)' does not use any compression or ordered permutations of any kind, but the 'Chess Storage System (Games)' uses ordered permutations.
These systems will be described by an algorithm / code like notation.
'#' will be used as a mathematical symbol to define numerical range.
'//' will be used to write comments within the algorithmic description.
'///' will be used to delimit comment blocks within the algorithmic description.
'new' will be used to allocate memory.
'Bit' is a data type that can store a single bit of information.
The declaration of any Bit will cause it to contain zero (0).
The declaration of any Bit array will cause its elements to contain zero (0).
'[]' declares an array.
The declaration of an array with zero (0) as count will result in array of size zero.
The don't care bit(s) will be referred to as useless bit(s) in this document, since whenever these bits assume the don't care status, they become useless for that particular instance. Apparently, such useless bits may not be saved, resulting in space being saved, but since it does not alter the generic upper bound for the system(s) (only particular instance(s) will use less number of bits than the upper bound), the decision whether to save them or not is left to implementation.
Also, there are multiple optimization points in the system(s) where bits can be saved (and savings can be huge), but these savings can be realized for particular instances only, and hence have no effect on the upper bound for the system(s). So, whether to optimize or not is left to implementation.
For any Bit array, a method called CountOnes() returns the number of ones in that Bit array. For an array with zero elements, it will return zero.
For any Bit array, a method called CountZeros() returns the number of zeros in that Bit array. For an array with zero elements, it will return zero.
For any Bit or a Bit array, a method called Save() will save the corresponding bit(s) to a file or a stream. For an array with zero elements, Save() executes successfully, but will not save any bit. Any parameters mentioned for Save(Integer) are only for informational purposes and it means that Integer number of bits are saved.
For any array (Bit or other), a method called Count() returns the number of elements in that array.
For any Integer (Int where Int can be 0 or more), a method called Save() will save that integer in k bits, for an integer p, p = 0 obviously implies k = 1, and p > 0 implies k = truncate(log2p) + 1.
A method called Read(Integer) will return Integer number of bits from a file or a stream.
Any available information or information computable from available information will be marked by the angular brackets (< and >).
The following information is assumed to be available (either directly or can be computed).
Enumeration PieceType {
None
WKing
WQueen
WBishop
WKnight
WRook
WPawn
BKing
BQueen
BBishop
BKnight
BRook
BPawn
}
PieceType[64]
The array that stores the PieceType at the corresponding square on board.
PieceCount
The number of pieces on the board #[2, 32] (2 kings are always there).
PromotedPieceCount
The number of promoted pieces on the board. Please note that this count includes only the number of pieces in excess of the default (2 queens, 4 rooks, 4 bishops and 4 knights = 14 pieces) as, even though 16 promotions are possible it would require capture of existing pieces.
EnpassablePawnCount
The number of black pawns on the rank 4 that are en passable (having white pawn beside it and not having anything exactly below it (rank 5)) (assuming a "white to move" notation - change the color and rank for a "black to move" notation).
Chess Storage System (Positions)
This system describes how to write / save the complete chess position information into some storage. The retrieval process can be inferred from the write process and hence the retrieval process will not be described here.
This system is described as follows:
Bit[] nonEmpty = new Bit[64];
For index = 0; index < 64; index++
If PieceType[index] != PieceType.None
nonEmpty[index] = 1;
Endif
Endfor
///
Since a maximum of 32 nonEmpty[] elements can be 1, 5 bits will be needed to access any of these elements (25 = 32)
///
Bit format = new Bit;
If Not PromotedPieceCount #[0, 3]
format = 1;
Endif
Bit[] whiteKingPosition = new Bit[5];
Bit[] blackKingPosition = new Bit[5];
Bit whiteKingOriginal = new Bit;
Bit blackKingOriginal = new Bit;
Int castling = 0;
Bit[] whiteCastling;
Bit[] blackCastling;
If format == 0
whiteKingPosition = <position of white king>
blackKingPosition = <position of black king>
Else
If <white king is at its original square [e1]>
whiteKingOriginal = 1;
castling = <number of white rooks on their original positions>
//castling #[0, 2]
whiteCastling = new Bit[castling];
whiteCastling = <castling rights for white>
Else
whiteKingPosition = <position of white king>
Endif
If <black king is at its original square [e8]>
blackKingOriginal = 1;
castling = <number of black rooks on their original positions>
//castling #[0, 2]
blackCastling = new Bit[castling];
blackCastling = <castling rights for black>
Else
blackKingPosition = <position of black king>
Endif
Endif
///
for format 0 – 64 + 10 + 1 = [75, 75] bits are used
for format 1 – 64 + [2, 12] + 1 = [67, 77] bits are used
empty squares are encoded
kings are encoded
castling information is encoded for format 1 only
///
Int nonKingPieceCount = nonEmpty.CountOnes() - 2;
//as kings are already encoded
//nonKingPieceCount #[0, 30]
Bit[] color = new Bit[nonKingPieceCount];
color = <white or black for corresponding entries in the array nonEmpty>
//white is zero (0) and black is one (1)
///
for format 0 – [75, 75] + [0, 30] = [75, 105] bits are used
for format 1 – [67, 77] + [0, 28] = [67, 105] bits are used
empty squares are encoded
kings are encoded
colors of all other (non King) pieces are encoded
castling information is encoded for format 1 only
///
//nonKingPieceCount #[0, 28] for format 1 will be explained later in this document
Bit[] pawn;
Bit[] piece;
Int pieceCount;
If format == 0
pawn = new Bit[nonKingPieceCount];
pawn = <pawn or piece for corresponding entries in the array nonEmpty>
//here piece is one of Queen / Bishop / Knight / Rook
//pawn is one (1) and piece is zero (0)
///
Suppose that the number of pieces in the first and last ranks (nonEmpty #[0, 7] and nonEmpty #[56, 63]) are extremeRankPieceCount #[0, 16], then extremeRankPieceCount number of corresponding elements in this Bit array (pawn) will be useless bits as the corresponding elements in the Bit array nonEmpty can be determined as nonPawnPieces (Queen / Bishop / Knight / Rook), since Kings are already known.
Now, if any of the four (4) possibilities for castling are available (call it nCastling #[0, 4]), then nCastling number of rooks will be in their own positions, hence at least nCastling number of elements (bits of pawn array) will be useless bits.
These corresponding bits (four corners as they will always be available whenever corresponding castling is available) will be used to store the castling rights when needed and the rest of the elements (extremeRankPieceCount - nCastling) will be treated as useless bits.
///
<encode castling rights if needed within pawn array>
///
Example of an optimization point
Consider all positions with the initial piece set (no promotions and all 32 pieces present) (this is a collection of specific instances (all instances with the initial piece set)).
Here for all those positions with the major pieces (King and other non pawn pieces) being in the extreme ranks and only pawns occupying nonEmpty [8, 55], this array (pawn array) can be entirely omitted, as the total number of pieces can be determined by nonEmpty.CountOnes() which will be 32 and number of ones in the extreme ranks (also determinable from nonEmpty) will be 16 - which inherently determines that all entries for extreme ranks are non pawns and all other entries ([8, 55]) are pawns resulting in a saving of 30 bits (of course these 30 bits are saved when there are only two kings present, but here these 30 bits are being saved even when all pieces are present) (30 bits can be saved under other instances as well).
But, out of these 30 saved bits, 4 will be used to encode castling rights, so actual saving will be 26 bits for this example. This is mentioned as an example only, as this uses the contextual information that is particular to certain positions only. Whether or not to make use of such information (for further optimization) is left to implementation.
///
///
for format 0 – [75, 105] + [0, 30] = [75, 135] bits are used
for format 1 – [67, 105] = [67, 105] bits are used
empty squares are encoded
kings are encoded
colors of other (non King) pieces are encoded
pawns are encoded for format 0 only
castling information is encoded for both formats
///
pieceCount = pawn.CountZeros();
//pieceCount #[0, 17] since a maximum of 14 pieces (excluding kings) are possible without promotions
piece = new Bit[pieceCount * 2];
///
piece [index*2, index*2 + 1] where index #[0, pieceCount - 1] and index is the loop index, will encode the piece (Queen 00 / Bishop 01 / Knight 10 / Rook 11) note that pieceCount has to be > 0 to loop through the piece array
///
piece = <piece information (Queen 00 / Bishop 01 / Knight 10 / Rook 11)>
///
For promotions #[0, 0] the piece array will contain maximum of 14 * 2 = 28 bits
For promotions #[1, 3] at least one pawn/piece would have been captured (otherwise promotion is legally not possible - plus a promoted pawn itself essentially leaves the board), this saves at least one bit in both arrays (color and pawn) (saving of 2 bits).
Also for p promotions p*2 extra bits will be needed (extra over 28 bits as needed for positions without promotions), so extra bits needed will be #[2, 6] but due to saving of 2 bits (if there is a promotion) the total addition will be 4 bits (max) for worst case (three promotions - and three promotions are legally possible with just one capture)
So, whenever the piece array will contain more than 28 bits – there would have been a saving of at least 2 bits in previous arrays (color and pawn)
Consider that saving as being passed on to this array and so the true range can be considered as #[0, 32] instead of #[0, 34] for the piece array (even with 17 pieces)
///
///
for format 0 – [75, 135] + [0, 32] = [75, 167] bits are used
for format 1 – [67, 105] = [67, 105] bits are used
empty squares are encoded
kings are encoded
colors of other (non King) pieces are encoded
pawns are encoded for format 0 only
all other pieces are encoded for format 0 only
castling information is encoded for both formats
///
Else
///
Since format 1 is being used, it means there are at least four promotions and hence at least two pawn(s) or piece(s) would have been captured which implies that the total number of pieces will be 28 or less excluding kings.
In other words, the range of the nonKingPieceCount here is #[0, 28] instead of #[0, 30]
So, there is a saving in the color array (saving of 2 bits) and hence the range #[67, 105]
These [0, 28] pieces (Queen / Bishop / Knight / Rook / Pawn) are encoded as: Queen = 0, Bishop = 1, Knight = 2, Rook = 3, Pawn = 4 (piece encoding #[0, 4])
So, 3 of such radix 5 values can be encoded in 7 bits (as 53 < 27) and to encode 27 such radix 5 values 9 * 7 = 63 bits are required and the last value (28th value) can be encoded using 3 bits giving an upper bound of 66 bits.
The implementation is not provided here (mathematically trivial)
///
Int bitsForPieces, quotient, remainder;
(quotient, remainder) = nonKingPieceCount / 3;
//quotient #[0, 9] and remainder #[0, 2] as nonKingPieceCount #[0, 28]
bitsForPieces = quotient * 7;
If remainder == 1
bitsForPieces += 3;
Endif
If remainder == 2
bitsForPieces += 5;
Endif
piece = new Bit[bitsForPieces];
piece = <piece information>
///
for format 0 – [75, 167] = [75, 167] bits are used
for format 1 – [67, 105] + [0, 66] = [67, 171] bits are used
empty squares are encoded
kings are encoded
colors of other (non King) pieces are encoded
pawns are encoded
all other pieces are encoded
castling information is encoded for both formats
///
Endif
///
Since there can be a maximum of 5 en passable pawns for any position #[0, 5]
en pass information can be encoded in maximum 3 bits
///
Bit[] enpass = new Bit[EnpassablePawnCount];
enpass = <en pass column>
///
for format 0 – [75, 167] + [0, 3] = [75, 170] bits are used
for format 1 – [67, 171] + [0, 3] = [67, 174] bits are used
empty squares are encoded
kings are encoded
colors of other (non King) pieces are encoded
pawns are encoded
all other pieces are encoded
castling information is encoded for both formats
en pass information in encoded for both formats
///
Hence the range for 'Chess Storage System (Positions)' as a whole is [67, 174] bits.
However one minor optimization can be made for the lower bound of this system. Immediately after setting up the Bit array nonEmpty – if the PieceCount is 2, only one more bit is required to determine which of the two set bits is the whiteKing. Set this bit to 1 if the first king (piece that appears first in the array nonEmpty #[0, 63]) is white otherwise this bit is 0.
Bit whiteKingDetermination = new Bit;
If PieceCount == 2
whiteKingDetermination = <1 if first king is white else 0>
Else
<The rest of the above code goes here>
Endif
With this minor optimization the range for 'Chess Storage System (Positions)' as a whole is [65, 174] bits.
The following process outlines the write / save process and hence describes the actual format for storage. In the implementation the save process may be integrated with the main algorithm if desired.
nonEmpty.Save(64)
If nonEmpty.CountOnes() == 2
whiteKingDetermination.Save(1)
Else
format.Save(1)
If format == 0
whiteKingPosition.Save(5)
blackKingPosition.Save(5)
Else
whiteKingOriginal.Save(1)
blackKingOriginal.Save(1)
If whiteKingOriginal == 0
whiteKingPosition.Save(5)
Endif
If blackKingOriginal == 0
blackKingPosition.Save(5)
Endif
Endif
color.Save(nonKingPieceCount);
If format == 0
pawn.Save(nonKingPieceCount);
piece.Save(pieceCount * 2);
Else
piece.Save(bitsForPieces);
If whiteKingOriginal == 1
whiteCastling.Save(<number of white rooks on their position>);
Endif
If blackKingOriginal == 1
blackCastling.Save(<number of black rooks on their position>);
Endif
Endif
enpass.Save(<number of en passable pawns>);
Endif
Chess Storage System (Games)
Assumptions
A method called GenerateMoves(position) returns an array of moves (all possible legal moves) from a given board position (this position must include castling / enpass / turn information – turn information is needed here as it is a for a game).
It (GenerateMoves) generates the moves in ascending order.
The pieces of the color to move (empty squares and pieces of other color are ignored) are processed in the order they appear on the board (position) [0] being the first to be processed and [63] being the last. All moves for a piece are processed before moving to the next piece.
Also, the moves for a particular piece are in ascending order (first move for a piece is a move to lowest numbered square and so on). In other words, the moves a piece can legally make are arranged according to the target square. For example, if a white king is on e1 – it can move to d1 f1 d2 e2 f2 g1(0-0) or c1(0-0-0) (only legal ones from these are actually processed) – the arrangement / generation of the moves is of the following order – c1(0-0-0) d1 f1 g1(0-0) d2 e2 f2 (ascending order)).
Castling is a King's move.
Promotions are processed as follows:
For each pawn move that leads to promotion, all possible promotions are processed before processing the next possible move of that pawn. The order for promotions will be Queen / Bishop / Knight / Rook. This will be considered as an ascending order for promotions.
Also, assume that GenerateMoves detects and / or processes the 3 Repetition Rule, 50 Move Rule, board draw conditions (including stalemate) and checkmate. GenerateMoves also detects partial games (implementation defined, for example move count in a header).
GenerateMoves returns zero (0) for any of the following being detected: board draw, checkmate, 3 Repetition Rule, 50 Move Rule and end of a partial game.
Chess Storage System (Games1)
This algorithm / code describes how to write / save the game moves and is described as follows:
Bit isInitial = new Bit;
Position position;
///
Consider the Position as some format that represents a chess game state completely and position as an instance where position is assumed to be a valid reachable position (reachable from the initial state)
///
If <the game is from initial position (initial setup + white to move + all four castling rights active)>
isInitial = 1;
position = <initial position>
Else
position = <load position>
///
If the above system 'Chess Storage System (Positions)' is used then the number of bits in position will be [65, 174] + 1 (turn bit) = [66, 175]. Here, consider position to be a Bit array.
///
Endif
isInitial.Save(1)
If isInitial == 0
position.Save([66, 175])
Endif
///
Here, 1 + [0, 175] = [1, 176] bits are used OR Zero. The 'isInitial' logic is provided so that games from particular positions can also be stored. If only games from the initial position are to be stored, the bits used so far will be 0 as the entire 'isInitial' logic can be skipped and the position at the start of this algorithm / system will always be the <initial position>
///
While TRUE
Move[] moves = GenerateMoves(position);
//A single Move can be any format to represent a move (implementation defined)
Int m = moves.Count();
///
KingMoves #[0, 8]
QueenMoves #[0, 28]
BishopMoves #[0, 14]
KnightMoves #[0, 8]
RookMoves #[0, 14]
PawnMoves #[0, 12]
Considering the worst case (King, 9 Queens, 2 Bishops, 2 Knights, 2 Rooks) and including even invalid moves, m #[0, 332] (this is a very impractical range, in practice the number of moves possible at any instant is very low as compared to 332)
///
Int index;
If m == 0
///
GenerateMoves must have detected one of the following: board draw, checkmate, end of a partial game, 3 Repetition Rule and 50 Move Rule
///
<appropriate action (also terminates the 'While TRUE')>
Endif
If m == 1
<forced move, so make the move and update position>
Endif
If m > 1
///
Suppose the move to be played be moves[index] in the moves array index #[0, m – 1] implying index can be stored in k bits, where k is chosen such that 2k-1 < m <= 2k. This can be optimally implemented by a single instruction lookup in a table (which may be precomputed) since the range of m is known (or a log (base 2) based logic can be used (slow as compared to lookup on some processor architectures)) (I.E. k = Ceiling(log2m))
Since m > 1, k #[1, 9]
In this document the Integer.Save() will 'know' the range of Integer and handle saving the Integer in appropriate number of bits transparently
///
<make the move at index (moves[index]) and update position>
index.Save(k)
Endif
Endwhile
The reading process is described as follows:
Bit isInitial = Read(1);
Position position;
If isInitial == 1
position = <initial position>
Else
position = <load position from file or stream (Read([66, 175]))>
Endif
While <not end of file or stream>
Move[] moves = GenerateMoves(position);
Int m = moves.Count();
Int k, index;
If m == 0
<appropriate action (including game over action) (as described above)>
Endif
If m == 1
<forced move, so make the move and update position>
Endif
If m > 1
k = <choose k such that 2k-1 < m <= 2k>
//for example, k = Ceiling(log2 m)
index = Read(k);
<make the move at index (moves[index]) and update position>
Endif
Endwhile
Chess Storage System (Games2)
This is a system similar to the one described above, but it mostly uses more bits per game move than the above system while being faster than the above system.
Since the maximum number of pieces of either color are 16, maximum of 4 bits are required to select the piece to be moved #[1, 4].
piecesWhite #[1, 16] and piecesBlack #[1, 16] (where pieces #[2, 32])
If no piece can be moved, the game has already concluded.
If only one piece can be moved, piece selection bits are not required.
For 2 to 16 movable pieces (mp) select k such that 2k-1 < mp <= 2k.
Since mp #[2, 16], k #[1, 4]
Now, once the piece is known, its bounds are known (upper bound = max moves possible) and this upper bound is highest for the queen ([0, 28]) (here [2, 28] as, if 0 moves can be made then that piece will not be selected and if 1 move can be made, it is an implied move), hence if the number of moves returned by GenerateMoves is m, then m #[2, 28]. (Here consider a method GenerateMoves(position, piece) instead of GenerateMoves(position)). Apparently index #[0, m – 1] and index can be stored in k bits where k = Ceiling(log2m). Since m #[2, 28], k #[1, 5]. In other words, the index for a piece will use only that many bits as required by its upper bound. For example, once the king has been selected the index can be stored in 3 bits max, for a queen it is 5 bits max, also if there is only one move possible for a piece the index bits are not required.
Chess Storage System (Games3)
Chess Storage System (Games1) has yet another advantage of a non deterministic channel for storage or transfer. The channel is non deterministic (or rather probabilistic) as the channel is available only when a move from a specific subset of all possible moves is made.
The channel can be used (write / save) as follows:
Bit isInitial = new Bit;
Position position;
If <the game is from initial position (initial setup + white to move + all four castling rights active)>
isInitial = 1;
position = <initial position>
Else
position = <load position>
Endif
isInitial.Save(1)
If isInitial == 0
position.Save([66, 175])
Endif
While TRUE
Move[] moves = GenerateMoves(position);
Int m = moves.Count();
Int k, z, index;
Bit lucky;
If m == 0
<appropriate action (also terminates the 'While TRUE')>
Endif
If m == 1
<forced move, so make the move and update position>
Endif
If m > 1
k = Ceiling(log2m);
//since m > 1, k #[1, 9]
z = 2k – m;
///
z and m are inversely proportional
(as m increases z decreases and vice versa)
z #[2k - (2k), 2k - (2k-1 + 1)] = [0, 2k-1 - 1]
z will always be m - (some) p, where p #[2, m] (z will be at least 2 less than m)
///
///
Suppose the move to be played be moves[index] in the moves array
index #[0, m - 1], implying index can be stored in k bits
also when index < z, index < 2k - m, index + m < 2k, implying <index + m> can be stored in k bits (for index < z)
///
<make the move at index (moves[index]) and update position>
If index < z
lucky = <store one bit of information in the lucky bit>
If lucky == 0
index.Save(k)
Else
(index + m).Save(k)
Endif
Else
index.Save(k)
Endif
///
In other words, whenever index < z, the probabilistic / non deterministic channel becomes available and 1 bit of information can be stored in it
///
Endif
Endwhile
The reading process is described as follows:
Bit isInitial = Read(1);
Position position;
If isInitial == 1
position = <initial position>
Else
position = <load position from file or stream (Read([66, 175]))>
Endif
While <not end of file or stream>
Move[] moves = GenerateMoves(position);
Int m = moves.Count();
Int k, z, index;
Bit lucky;
If m == 0
<appropriate action (including game over action) (as described above)>
Endif
If m == 1
<forced move, so make the move and update position>
Endif
If m > 1
k = Ceiling(log2m);
//since m > 1, k #[1, 9]
z = 2k - m;
index = Read(k);
//index #[0, 2k), index #[0, m - 1]
If index < z
lucky = 0;
<process 1 bit of information from the lucky bit>
Else
If index >= m
index –= m;
lucky = 1;
<process 1 bit of information from the lucky bit>
Endif
Endif
<make the move at index (moves[index]) and update position>
Endif
Endwhile
Chess Storage System (Games4)
This system is provided to make use of the probabilistic channel described above (Games3) for the purpose of bit usage reduction (more saving).
The system (write / save) is described as follows:
Bit isInitial = new Bit;
Position position;
If <the game is from initial position (initial setup + white to move + all four castling rights active)>
isInitial = 1;
position = <initial position>
Else
position = <load position>
Endif
isInitial.Save(1)
If isInitial == 0
position.Save([66, 175])
Endif
Stack stack = new Stack;
While TRUE
Move[] moves = GenerateMoves(position);
Int m = moves.Count();
Int k, z, index;
Bit lucky;
If m == 0
stack.Save();
//save any unsaved elements
<appropriate action (also terminates the 'While TRUE')>
Endif
If m == 1
<forced move, so make the move and update position>
Endif
If m > 1
k = Ceiling(log2m);
z = 2k – m;
<make the move at index (moves[index]) and update position>
//consider the pair (index, m) as a single stack element
stack.Push(index, m);
If index >= z
stack.Save();
Endif
Endif
Endwhile
The method Stack.Save() is defined on an instance of Stack and is described as follows:
This is a method specific only to the code for 'Chess Storage System (Games4)'.
The stack element at the bottom (first in) will always be stack element [0] and the stack element at the top (last in) will always be stack element [stackCount – 1] where stackCount is the number of elements in the Stack instance. Note that the elements are pushed onto the stack only when m > 1 (code for Games4).
If the stack has only one element it cannot have the probabilistic channel or it is ignored, and for multiple elements in the stack all elements except the top element will have the probabilistic channel (because, except the top element, all elements will be having index < z).
Also, consider a method called RemoveLeftBit(Integer) that removes the leftmost bit (most significant bit) from the Integer and returns that bit (the Integer itself is modified – and if the Integer had 'k' bits before the call it will have 'k – 1' bits after the call). Since, this will be used only when m > 1, k will be at least 1 and the Integer with its single bit removed will contain zero bits and saving it will save zero bits.
Also, consider a method called Integer.AppendLeftBit(Bit) that appends (actually prefixes or prepends) the Bit to the left side (msb position) of the Integer.
The word 'this' is used to refer to information for a particular instance for which the method is being executed.
Stack.Save() Begins
Int index, m, lucky;
If this.stackCount == 0
Return
Endif
If this.stackCount == 1
(index, m) = this.[0];
index.Save();
Return
Endif
//now, this instance of Stack has at least two elements
Stack tempStack = new Stack;
(index, m) = this.Pop();
lucky = RemoveLeftBit(index);
tempStack.Push(index, m);
While <this instance of Stack is not empty>
(index, m) = this.Pop();
If lucky == 1
index += m;
Endif
If <this instance of Stack is not empty>
lucky = RemoveLeftBit(index);
Endif
tempStack.Push(index, m);
Endwhile
While <tempStack is not empty>
(index, m) = tempStack.Pop();
index.Save();
Endwhile
Stack.Save() Ends
The reading process is described as follows:
Bit isInitial = Read(1);
Position position;
If isInitial == 1
position = <initial position>
Else
position = <load position from file or stream (Read([66, 175]))>
Endif
Bit lucky, luckyBit;
While <not end of file or stream>
Move[] moves = GenerateMoves(position);
Int m = moves.Count();
Int k, z, index;
If m == 0
<appropriate action (including game over action) (as described above)>
Endif
If m == 1
<forced move, so make the move and update position>
Endif
If m > 1
k = Ceiling(log2m);
//since m > 1, k #[1, 9]
z = 2k - m;
If luckyBit == 1
index = Read(k - 1);
index.AppendLeftBit(lucky);
Else
index = Read(k);
Endif
//index #[0, 2k), index #[0, m - 1]
luckyBit = 0;
If index < z
luckyBit = 1;
lucky = 0;
Else
If index >= m
index –= m;
luckyBit = 1;
lucky = 1;
Endif
Endif
<make the move at index (moves[index]) and update position>
Endif
Endwhile