Size of the smallest number of positions proving a win for black in Queen-odds chess
2
36
155
2061
90%
<=10^50
66%
<=10^30
15%
<=10^10

Resolves to all answers indicating the size, in number of nodes, of the smallest DAG (directed acyclic graph) node-labeled with chess positions that proves a win for black, in a game of chess where white starts without its queen.

A chess position here includes data on whose turn it is, location of all pieces, castling rights, and en passant squares, but not data on 50-move rule timeouts. A DAG of positions proves a win for black if:

  • The collection includes the initial position

  • In every position with white to move, all possible subsequent positions after a move by white are also included, with an edge from the former to the latter.

  • In every position with black to move, either there is a mate-in-one, or there is a unique edge from the position to another position, indicating the state after a legal move from black.

  • There are no cycles (as the definition of DAG requires)

Answers resolve either when the exact number is known, or when the intended resolution is provable to be more/less than the value in the answer. If the game is not a win for Black, resolves to infinity.

Get Ṁ200 play money