Datasets for Studying Generalization from Easy to Hard Examples

For each choice of the sample length $n,$ we produce 10,000 unique random strings, each containing $n$ binary numbers that represent a fair coin flip. We then compute their cumulative sums modulo two and save the input-output pairs.

Examples from the sets with 16 bit and 28 bit inputs are shown below.

We generate the mazes as abstract graphs, and then render them as images. We initialize a square grid graph, then use depth first search to find a subset of the edges that form a spanning tree. We randomly assign two nodes in the graph to be the end points of the maze. To render an image from this representation, we represent each node and each edge in the spanning tree with a white cell and each edge from the grid graph that is not in the spanning tree as a black cell. See Figure 2 for a depiction of each stage in the maze generation process. The code used was adapted from another maze generation repository [1]. Finally, the solutions are generated with breadth-first search, using the image as input. By construction, the generated mazes admit a unique solution, in other words, there is exactly one path connecting the “start” and “end” positions.

A note on the size of mazes: After creating an $n\times n$ maze, we represent the graph using $2\times 2=4$ pixels per cell, and add a 3 pixel wide black border on each side. For this reason, a dataset of $n\times n$ mazes is represented using images of dimension $(2n+6)\times(2n+6)$. For example, the $9\times 9$ Mazes dataset contains images of size $24\times 24$ pixels.

Figure 3 shows examples of mazes and their solutions from datasets of three different difficulties.

By combing through 200,000,000 user games using the Stockfish 12/13 chess engines, Lichess creates puzzles consisting of sequences of unique best next moves. Once available for play on Lichess’s website, a puzzle’s initial Elo rating is then refined by having users with known ratings attempt to defeat the puzzle.³³3Elo is a system for rating players; one increases their Elo by besting other players with high Elo, and decreases their Elo by failing against lower rated players. Chess puzzles are rated similarly by presenting them to players with known skill rating. Interactions with hundreds/thousands of users eventually leave the puzzle with an equilibrated final rating, which quantifies difficulty. Each puzzle is tagged with the Forsyth-Edwards Notaion (FEN) representation of the board and an automatically generated short descriptor using code made available on the Lichess website. In other words, we can download a string that describes the current board, the best next move, and the difficulty rating for each of these puzzles.

We use FEN information to create a Pytorch tensor that encodes the board state as a multi-channel “image.” This representation consists of twelve $8\times 8$ channels, one for each class of white piece and one for each class of black piece. In particular, each channel has ones at the locations of the relevant pieces (e.g., pawns for one channel, rooks for another, etc..) and zeros elsewhere. The first six channels correspond to the player who is to move next. For this reason, a machine learning system that accepts this representation should not need to be explicitly told which player acts next, however a boolean flag for this purpose can be requested by the user when the dataset is constructed. Note, that our formulation of this dataset leaves out information about castling rights and En passant – a simplification of the game we make for convenience.

Each board state is labeled with a single-channel $8\times 8$ tensor representing the solution to the problem. In these tensors there are zeros everywhere except on the origin and destination squares for the piece that should be moved. Again, note that the target itself does not possess the explicit information about what type of piece or which color is to move, but that information can be determined with the input and the identification of which color’s turn it is.