Kriegspiel Checkmate Problem Database

I. Introduction:

This page provides a downloadable database of checkmate problems for Kriegspiel, and describes the format of this database.

    Our current Kriegspiel problem database (v1.2) is available here as a single archive, which contains 500 3-ply, 5-ply, and 7-ply mate and near-miss instances, and 200 9-ply mate and near-miss instances. A csv file with aggregated statistics is also available here.

    krieg-db-v1.2.tgz     Berkeley Kriegspiel problem database v1.2.

    Please be aware that the database contains a small number of repeated problem instances. For more information about the the database formatting, read on.

III. Problem Details:

    This section assumes a familiarity with our rules and Kriegspiel PGN notation.

    In chess, a checkmate problem can be stated as follows: given a board position with <player> to move, is there a conditional move plan that guarantees checkmate for <player> within <d> ply (half-moves)? Kriegspiel checkmate problems are similar; however, Kriegspiel game states are specified by filtered move histories, not board positions. Thus, a Kriegspiel checkmate problem can be stated as follows: given a move history filtered from <player>'s perspective with <player> to move, is there a conditional move plan that guarantees checkmate within <d> ply?
    The above 3-ply database contains 1000 files in filtered Kriegspiel PGN format, each of which states a Kriegspiel checkmate problem that arose in a real game; 500 of the files describe Kriegspiel game states from which guaranteed checkmates exist ("mate" instances), and the other 500 describe Kriegspiel game states from which guaranteed checkmates almost exist ("near miss" instances). The higher-ply instances were created by analyzing a large set of 3-ply near-miss instances, and re-categorizing them into mate and near-miss instances based on whether they admit a guaranteed checkmate at the corresponding greater depth.

A. Problem Specifications

This section defines the terms "mate instance" and "near-miss instance" in more detail. It also describes some fixed characteristics of the problems in the databases, and the process of constructing the 5-ply database from the 3-ply one.

1. Checkmate Instances:

A <d>-ply checkmate instance is defined as a filtered Kriegspiel move history, with <player> to move, that has a guaranteed checkmate for <player> within at most <d> ply (half-moves). For a guaranteed checkmate to exist, <player> must be able to force each possible board position to a checkmate position, without being given any more information than the filtered move history and future referee responses. In thsi version of the database, <player> is always White (for no particular reason); future databases may include problems with <player> as Black. For a very simple example of a checkmate instance, check out the Kriegspiel PGN page.

In Kriegspiel, as in chess, many combinations of material admit an algorithmic win for the player with the advantage (i.e. KQvK). For most of these material combinations, mate can be achieved with probability 1; however, in some, it can only be secured with probability 1-epsilon. For more information about such situations, see the Rules. For the purposes of this problem database, we consider such material win positions to be immediate wins. Thus, a position is won for <player> when <player>'s opponent is checkmated, or when the position meets the following conditions:

The opponent of the <player> has a lone king
<player> has one of the following combinations of pieces directly protected by his king (plus any other pieces).
- a Queen*
- a Rook*
- a non-edge Pawn*
- two Bishops**
- a Knight and a Bishop**

*These combinations are allowed whenever the <forced> parameter is "T"; in this version of the database, <forced> is always "T"
**These combinations are allowed whenever the <forced> and <epsilon> parameters are both "T"; in this version of the database, <forced> and <epsilon> are always "T"

All problem instances are constrained to have between 1 and 8 Black pieces

2. "Near-miss" Instances:

A near-miss instance of a Kriegspiel checkmate problem is like a mate instance, except that it "almost but not quite" admits a guaranteed win. The exact specifications of a near miss rely on the notion of a belief state, the set of possible positions that are consistent with the move and observation history. In a checkmate instance, there exists a conditional move plan that guarantees a win regardless of what state the opponent is actually in, and how she moves subsequently. In a near-miss instance, if the belief state contains <n> positions, there will exist a subset of the belief state with at least <n>/2 positions (but less than <n>) for which a guaranteed checkmate exists. Note that even if each position in a belief state independently admits a Kriegspiel checkmate, the belief state as a whole may not.

B. Problem Parameters

The database contains a variety of checkmate and near-miss instances. Each problem instance is annotated with a required set of parameters, followed by an optional set of variables describing it. These parameters and variables are, respectively:

filtered: The move history must always be filtered; the <filtered> player is also the player-to-mate. In the current problem database, always "white".
depth: The depth (number of moves for <filtered> player) to force checkmate. Depth is 2 in the 3-ply portion of the database, and 3 in the 5-ply portion.
forced: Are material checkmate situations (i.e. KQvK), within the constraints described above, considered immediate wins? In the current problem database, always "T" (yes).
epsilon: Are epsilon material checkmate situations (i.e. KBBvK), within the constraints described above, considered immediate wins? Implies <forced>. In the current problem database, always "T" (yes).

computed-states: The sum of the sizes of the belief states held by the player-to-mate throughout the game. That is, the minimum number of states that could be computed by a forward belief state tracking algorithm to ensure an accurate solution to the problem
final-states: The size of the belief state of the player-to-mate at the point immediately after the last move in the problem's move history. That is, the size of the belief state that the player must find a checkmate for.
mate-states: The number of final states that individually have Kriegspiel forced mates (apart from other states in the belief state). For checkmate instances, mate-states = final-states
largest-mate-subset: A lower bound on the largest subset of the belief state that has a Kriegspiel forced mate. For checkmate instances, largest-mate-subset = final-states. Near-miss instances are defined as instances for which final-states/2 <= largest-mate-subset < final-states. Note that computing the largest mate subset is computationally hard, and so in some near miss instances there may exist a subset with a mate that is larger than largest-mate-subset (but still smaller than final-states).
white-pcs: Number of white pieces at the point immediately after the last move in the problem's move history
black-pcs: Number of black pieces at the point immediately after the last move in the problem's move history.

These variables vary widely between problems in the database, ranging from:

100s to 100,000s of computed-states
1 to 100 final-states
2 to 15 White pieces
1 to 8 Black pieces

The checkmate and near-miss problems have roughly similar distributions with respect to these parameters. In the downloads section above, there is a CSV (comma separated value) file that provides these statistics for all of the problem instances. The statistics are also stored in the instance files themselves; read on for more information.

IV. Problem Format:

The problem files are just Kriegspiel PGN files, with <filtered> (the player-to-mate), as the player-to-move. They contain additional tag-pairs, which provide extra information about the problem's rules and solution.
The header part of a problem PGN looks like:

    [event "...."]
    ... (site, date, round, white, black)
    [result "*"]
    [variant "Kriegspiel (Berkeley)"]
    [filtered "white"]
    [depth "2"]
    [forced "T"]
    [epsilon "T"]
    [computed-states "6837"]
    [final-states "24"]
    [mate-states "24"]
    [largest-mate-subset "24"]
    [white-pcs "10"]
    [black-pcs "8"]

    In every checkmate problem instance, result is "*" and variant is "Kriegspiel (Berkeley)". In this particular set of problems, filtered is always "white", depth is always "2" or "3", and forced and epsilon are always "T" (corresponding to the above specifications). These tag pairs will always be present, in this order. The other six tag pairs describe the characteristics of the instance, as explained above. These six are all-or-none; that is, either they are all present in the above order, or none of them are present. In all of the instances in this problem set, this extra information is included; however, in test instances, it would not be.
    The movetext in a Kriegspiel PGN problem instance is formatted according to the Kriegspiel PGN format; for sample movetext, see here. The only added stipulation on the movetext is that the last move must have been made by player-to-mate's (<filtered>'s) opponent.