Skip to main content
MANIFOLD
Size of the smallest number of positions proving at least a draw for black in chess
1
Ṁ100Ṁ20
2555
63%
<=10^50
50%
<=10^30
37%
<=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.

A chess position here includes data on whose turn it is, location of all pieces, castling rights, en passant squares, and half-turns since the 50-move rule counter was reset. A DAG of positions proves a win or draw 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 a draw-in-one, or there is an 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 or draw for Black, resolves to infinity.

Get
Ṁ1,000
to start trading!
Sort by:

How do you handle the triple repetition rule? You don't mention it at all. If it is in play, then the position data must include the full game history and position count balloons, while if it isn't, this changes some endgames.

A DAG of positions proves a win for black if:

Should be "proves a win or draw" I think?