Chess murder mystery

Question

You know how many and which kinds of chess pieces were murdered. Can you come up with any possibility for who killed whom and how?

Background

During the course of a game of chess, there are between 2 and 32 pieces on the board. Call the collection of all pieces on the board (both white and black), without regard to position, the material content of the board.

The game begins with 16 pieces per side, often represented together as KQRRBBNNPPPPPPPPkqrrbbnnpppppppp. (Capital letters represent white, lowercase letters represent black. The pieces are King, Queen, Rook, Bishop, kNight, and Pawn.)

The challenge

Write a program that receives as input a possible material content of the board, and produces as output a legal sequence of moves that achieves this content at the end of the sequence of moves.

The program need only work for subcollections of the initial 32 pieces (that include the white king K and the black king k). In other words, there is no need to consider crazy situations like multiples queens per side. That also means that promotion is not necessary, but it is still allowed.

Input format

You may take input in a format convenient to you. For example, the following formats are acceptable:

1. A string like KQRRBBNPPPPPPPPkqrrbbnpppppp or QRRBBNPPPPPPPPqrrbbnpppppp (kings implied).

2. A list like ['Q', 'R', 'R', 'B', 'B', 'N', 'P', 'P', 'P', 'P', 'P', 'P', 'P', 'P', 'q', 'r', 'r', 'b', 'b', 'n', 'p', 'p', 'p', 'p', 'p', 'p'].

3. A tuple of piece counts like \$(1,2,2,1,8,1,2,2,1,6)\$ representing \$(Q,R,B,N,P,q,r,b,n,p)\$ or like \$(1,1,2,2,2,2,1,1,8,6)\$ representing \$(Q,q,R,r,B,b,N,n,P,p)\$.

4. A dictionary of piece counts like {'K': 1, 'Q': 1, 'R': 2, 'B': 2, 'N': 1, 'P': 8, 'k': 1, 'q': 1, 'r': 2, 'b': 2, 'n': 1, 'p': 6} (or without the implied kings).

5. A string like Nnpp (or list ['N','n','p','p'], or tuple \$(0,0,0,1,0,0,0,0,1,2)\$, or dictionary) representing which pieces are missing, or in line with the title, have been murdered!

Output format

The output format is also flexible, but it must be parseable by a standard game engine. That means that the following are acceptable formats:

1. Standard algebraic notation, like Nf3 e5 Nxe5 Ne7 Nxd7 Nec6 Nxb8 Nxb8.

2. "UCI" long algebraic notation, like g1f3 e7e5 f3e5 g8e7 e5d7 e7c6 d7b8 c6b8.

(These sample outputs are solutions to the sample inputs before. These games appear to leave the original pieces in their starting squares, but this is not necessary nor in fact the case here.)

The output can be a string or a list, or it can be output to the screen. There is no need to number your moves, but you may if you want. (However, they must of course alternate between white and black, as well as follow other rules of chess!)

Scoring

This is almost a standard code-golf question, meaning that submissions are scored by the length of the program in bytes.

However, in case not all subcollections are solved correctly (whether intentionally or unintentionally), that does not invalidate a submission. Instead, an additional one byte penalty will be assessed per subcollection of pieces that is not solved correctly.

Note that because white could have 0 or 1 queens; 0, 1, or 2 rooks; and so forth, there are \$2\cdot 3\cdot 3\cdot 3\cdot 9 = 486\$ possible material contents per color, and thus \$486^2 = 236196\$ total possible material content inputs. Thus it is strongly advisable to solve the vast majority of inputs correctly! The following program enumerates the possible inputs, and also produces the various example input formats listed above:

count = 0
for Q in range(2):
  for R in range(3):
    for B in range(3):
      for N in range(3):
        for P in range(9):
          for q in range(2):
            for r in range(3):
              for b in range(3):
                for n in range(3):
                  for p in range(9):
                    s1 = ("K" + "Q" * Q + "R" * R + "B" * B + "N" * N + "P" * P +
                          "k" + "q" * q + "r" * r + "b" * b + "n" * n + "p" * p)
                    s2 = ("Q" * Q + "R" * R + "B" * B + "N" * N + "P" * P + 
                          "q" * q + "r" * r + "b" * b + "n" * n + "p" * p)
                    l1 = [piece for piece in s1]
                    l2 = [piece for piece in s2]
                    t1 = (Q, R, B, N, P, q, r, b, n, p)
                    t2 = (Q, q, R, r, B, b, N, n, P, p)
                    d1 = {"K": 1, "Q": Q, "R": R, "B": B, "N": N, "P": P,
                          "k": 1, "q": q, "r": r, "b": b, "n": n, "p": p}
                    d2 = {"Q": Q, "R": R, "B": B, "N": N, "P": P,
                          "q": q, "r": r, "b": b, "n": n, "p": p}
                    murders = ("Q" * (1-Q) + "R" * (2-R) + "B" * (2-B) +
                               "N" * (2-N) + "P" * (8-P) +
                               "q" * (1-q) + "r" * (2-r) + "b" * (2-b) +
                               "n" * (2-n) + "p" * (8-p))
                    murderl = [piece for piece in murders]
                    murdert1 = (1-Q, 2-R, 2-B, 2-N, 8-P,
                                1-q, 2-r, 2-b, 2-n, 8-p)
                    murdert2 = (1-Q, 1-q, 2-R, 2-r, 2-B, 2-b,
                                2-N, 2-n, 8-P, 8-p)
                    murderd = {"Q": 1-Q, "R": 2-R, "B": 2-B, "N": 2-N, "P": 8-P,
                               "q": 1-q, "r": 2-r, "b": 2-b, "n": 2-n, "p": 8-p}
                    count += 1
print(count)

Verifier

The following Python3.7+ sample demonstrates how to check that a game achieves a given collection of pieces:

import chess
import chess.pgn
import io

pieces = "KQRBNPkqrbnp"
def piece_key(x):
  return pieces.find(x)
def sort_pieces(ps):
  return sorted(ps, key=piece_key)
def only_pieces(s):
  return filter(lambda x: piece_key(x) >= 0, s)
def final_pieces(moves):
  board = chess.Board()
  for move in moves:
    board.push(move)
  return "".join(sort_pieces(only_pieces(str(board))))
def moves_from_pgn_string_parser(s):
  pgn = io.StringIO(s)
  game = chess.pgn.read_game(pgn)
  return game.main_line()
def moves_from_uci_list(l):
  return [chess.Move.from_uci(x) for x in l]
def moves_from_uci_string(s):
  return moves_from_uci_list(s.split())

print(final_pieces(moves_from_pgn_string_parser(
    "1. Nf3 e5 2. Nxe5 Ne7 3. Nxd7 Nec6 4. Nxb8 Nxb8")))
# KQRRBBNPPPPPPPPkqrrbbnpppppp
print(final_pieces(moves_from_uci_list(
    ["g1f3", "e7e5", "f3e5", "g8e7", "e5d7", "e7c6", "d7b8", "c6b8"])))
# KQRRBBNPPPPPPPPkqrrbbnpppppp

Potential clarifications

• Pieces with the same name and color, such as the two white rooks, are indistinguishable. That is, you need not ensure that the a1 rook specifically be killed.

• The input format is quite flexible. If you wish to have the black pieces before the white, or the pieces in alphabetical order, you're welcome to.

• The output games need not be the simplest or shortest possible in any sense; they must merely be legal. Intricacies like the fifty-move/seventy-five-move rule, draw by threefold/fivefold repetition, and insufficient material may be ignored. Key rules like check, checkmate, and stalemate may not be ignored.

• The output game need not terminate with mate. It can just end after an arbitrary move.

• You may use chess libraries available in your language or platform.

Answer 1

JavaScript (ES10),  499  450 bytes

Expects [[q,r,b,n,p], [Q,R,B,N,P]], where each variable is the number of missing pieces. Returns an array of strings in standard algebraic notation.

M=>M.map((a,w)=>a.map(h=(v,i)=>v--?[(q=[...'002//2770/222/2772/220/000//27n0/0n02/b77/277b/20/2n22/b7b/b0b'.split`/`[i*2+v]].map(d=>"abcdefgh"[y=(s+=parseInt(d,36)-17)>>3,s%8]+(w?1+y:8-y),s=52),c=q.pop())?[...q,"x"+c,q.reverse(),w?'e7':'e2']:q,h(v,i)]:[]).flat(10).map((s,i)=>o+=w?(i&1?"Ne2N":"Ng1N")+s:"N"+s+(i&1?S:"Ng8")),o=S="Ne7")&&`a3a6c4c5e3e6g4g5h3h6Ne2${o}Ng3Ng6Nf5Nf4${b=M[1][3]>1?'Ne2Kxe2':'',M[0][3]>1?S+b+`Kxe7`:'Ng3'+b}`.split(/(?<=\d)/)

Try it online!

How?

1. We first play 1. a3 a6 2. c4 c5 3. e3 e6 4. g4 g5 5. h3 h6 6. Ne2 Ne7:

   

2. The White king's knight follows some pre-computed paths to capture each Black piece except the Black king's knight, avoiding the squares c7, d6, f6 and g7 that would put the Black king in check. It also avoids c3, because Nc3 would be ambiguous. It goes back to e2 after each capture. Meanwhile, the Black king's knight moves back and forth between e7 and g8 and ends up on e7.

   For instance, to capture the queen: 7. Nd4 Ng8 8. Nc6 Ne7 9. Nxd8 Ng8 10. Nc6 Ne7 11. Nd4 Ng8 12. Ne2 Ne7

3. We do the same thing with the Black king's knight.

4. We play Ng3 Ng6 / Nf5 Nf4:

   

   Note: All pieces are shown in the above diagram, but only the kings and the king's knights are guaranteed to still be on the board at this point.

5. White play Ne7 if the White king's knight has to be captured, or Ng3 otherwise. This is followed by Ne2 Kxe2 if the Black king's knight has to be captured. Finally, Black play ... Kxe7 if the White king's knight has to be captured.

_{Images generated with www.365chess.com.}

Answer 2

Python 3.7+, 299 bytes

Expects a dictionary like {'K': 1, 'Q': 1, 'R': 2, 'B': 2, 'N': 2, 'P': 6, 'k': 1, 'q': 1, 'r': 2, 'b': 2, 'n': 2, 'p': 5} indicating how many of each piece should remain at the end of the game. Outputs a game in standard algebraic notation, complete with move numbering, like 1. d4 a6 2. g4 a5 3. c3 d5 4. Bd2 f6 5. c4 e5 6. b4 Nc6 7. e3 Nge7 8. f4 Bxg4 9. Bd3 b6 10. Qc2 Ng6 11. fxe5 Qe7 12. exf6 dxc4 13. Nc3 Rg8 14. Bxc4.

Obeys the trickier rules of chess, including the 75-move rule, repetition, and insufficient mating material. On average, takes approximately one second per desired material content on my computer; I have checked all possible inputs.

from chess import*
from random import*
S=Board
def f(t):
 seed(0);b=S()
 while 1:
  for m in choices([*b.legal_moves],k=9):
   b.push(m)
   if max(d:=[str(b).count(x)-t[x]for x in t])<1:return S().variation_san(b.move_stack)
   if b.is_game_over()+b.is_check()-min(d)<1:break
   b.pop()
  else:b=S()

How?

Beginning at the starting position , we randomly play moves. A move is not played if it results in too few of a desired piece on the board. (That is, we pick another random move instead, up to nine times before giving up.) A move is also not played if it results in check or any game-ending condition (checkmate, stalemate, draw by 75-move-rule, etc), except on the final move. Promotions are played occasionally, just like any other move, if the pawn is not necessary for the desired material content. There is no backtracking of individual moves beyond this "one move lookahead" mentioned already; in the event of failure, we restart from the beginning with a fresh starting board and fresh random moves.

The function is deterministic because we explicitly set the seed to 0. As a result, most of the games begin exactly the same, differing only when a capture is or is not allowed to be made, or when the entire attempt is a failure and we have to start over.

PS. When I started working on this challenge, I planned on a knight-based approach like Arnauld's. I didn't know whether random would work out, but I'm glad it did!

Example games

• Kk: Reaching King versus king takes 166 moves and features 3 promotions, to two white rooks and a black bishop.
• KBkqrr: Features 6 promotions (to RRnbNQ) in 282 moves ending in check.
• KRNPPPk: Three promotions to black queens. White ends with three pawns on the seventh rank, but doesn't promote any because they're part of the desired material content.
• KQRRBNNPPPPPPPkrbnppppp: Mate in 42.
• KQBNNPPPPkqrbppppppp: Features capture en passant on move 21.
• KQRRBNNPPPPPPPPkrrbnppppppp: Both sides castle, consecutively but in opposite directions.
• KQRRBBNNPPPPPPPkrnnppp: Knight delivers mate.