Monday, November 24, 2014

[uvmjqhcm] Automatically deriving the rules of chess

Given a collection of chess games, how difficult would it be to automatically derive the rules of chess?

Consider a relatively difficult input format: a game is presented as a sequence of [0..7]^4 tuples (i.e., 12 bits per half-move), representing start and end squares in the standard way, including castling represented by extended king moves.  Not even the result of the game, e.g., 1-0, is provided, but we assume the games have been played out until the result can be determined mechanistically from the state of the board (no resignations, forfeits, losses on time, draws by agreement).

The computer must derive not only the rules but the objective of the game.  The example games must have been played by agents seeking to win, perhaps loosely defined as never missing mate in N for some small N.

Perhaps this is not enough, and the computer is also provided afterwards with an interactive phase in which it can ask questions about positions not seen in games: "is the following move sequence legal?"

It is hard to imagine that a computer will ever be able to figure out on its own the prohibition against castling through check solely by looking at games, but it could be possible: permitting castling through check would have provided a mate in N or a way to escape mate.

One motivation was laziness: specifying the legal moves and the objective of the game are probably the most error prone and tedious parts of any game programming. Doing it automatically, even semi-automatically, would be great.

The other motivation was considering playing correspondence chess with distant aliens. How can one communicate the rules of a game to the alien culture with which one shares no language?

No comments :