Сколько существует различных способов поставить мат в начале игры?

Мы все знаем, что самый короткий мат состоит из 4 слоев:

1. f3 e5

2. g4 Qh5 #

Это не единственный возможный порядок перемещения. На самом деле их 8, в зависимости от того, передаст ли белая пешка f или g первой, переместит ли пешка f на f3 или f4, и сыграет ли чёрная e6 или e5. Конечно, это составляет лишь крошечную долю возможных 4-слойных последовательностей ходов, но это единственные, которые заканчивают игру.

Что я ищу, так это для небольшого количества слоев, сколько последовательностей ходов заканчивается матом, а не матом. В идеале я хотел бы что-то вроде

• 4 слоя: X последовательностей без матов, 8 4-слойных матов
• 5 слоев: Y последовательностей без матов, 8 4-слойных матов, N 5-слойных матов
• 6 слоев: Z последовательностей без матов, 8 4-слойных матов, N 5-слойных матов, M 6-слойных матов

и так далее настолько глубоко, насколько это разумно сделать.

Это основано на вопросе Math.SE о вероятности того, что два игрока сделают случайные ходы в результате одной и той же шахматной игры. Я подозреваю, что короткие игры в значительной степени преобладают над этой вероятностью, что должно упростить приблизительную вероятность, но было бы неплохо иметь реальные цифры для работы.

Нет матов из 0-3 сгиба.

4 ply: 8 checkmates, 197,281 total nodes
5 ply: 347 checkmates, 4,865,609 total nodes
6 ply: 10,828 checkmates, 119,060,324 total nodes
7 ply: 435,767 checkmates, 3,195,901,860 total nodes
8 ply: 9,852,036 checkmates, 84,998,978,956 total nodes
9 ply: 400,191,963 checkmates, 2,439,530,234,167 total nodes

"checkmates" - количество ходов checkmating, сделанных на последнем слое. Таким образом, для 5 слоев существует 347 последовательностей матов ровной длины 5.

Эти значения от: https://www.chessprogramming.org/Perft_Results

В настоящее время нет данных матов для 10 слоев и выше, предположительно из-за необходимых вычислительных ресурсов.

Чтобы получить более конкретные данные (например, сами строки), вам нужно написать собственную программу, которая сохраняет строки, заканчивающиеся на checkmate.

Эта последовательность целых чисел известна как A079485 в онлайновой энциклопедии целочисленных последовательностей (OEIS), и известны числа до 13 слоев, включая различные доступные ссылки.

Вот простая программа на Python, которая отвечает на этот вопрос, но идет медленно, занимая 40 минут до 5 слоев на моем ноутбуке (и увеличивая как минимум в 30 раз на дополнительный слой). Приятно то, что он печатает игры, если вам это нужно. Я мог бы опубликовать вывод здесь, но не хотел делать ответ длиной в 347 строк ... :-)

import chess
from chess import pgn

def dfs(board, depth):
    global n
    result = board.result(claim_draw=True)
    if result != '*':
        game = pgn.Game.from_board(board)
        print(game.mainline())
    elif depth > 0:
        moves = list(board.legal_moves)
        for move in moves:
            n += 1
            board.push(move)
            dfs(board, depth-1)
            board.pop()

n = 0
try:
    board = chess.Board()
    dfs(board, 4)
except KeyboardInterrupt:
    pass
print(n, 'positions checked')

Главным человеком, которого я знаю по этому виду анализа, является Франсуа Лабель, который вычислил много чисел, связанных с шахматами (включая оценку максимальной скорости роста числа шахматных игр в зависимости от сгиба), и, в частности, вычислил число матов до слоя 13. Для значений до слоя 12 см. рисунок в http://wismuth.com/chess/chess.html .

Затем по адресу http://wismuth.com/chess/statistics-games.html он приводит конкретные цифры до уровня 13, что, по-видимому, имеет 346 742 245 764 219 матовых игр.

Для общего количества игр он цитирует результаты других, которые поднялись до 15 (!), Но я думаю, что они не отслеживали матов.

Из слоев 5-13 есть примерно 1 шанс на 10000, что ход доставит мат. Но кажется, что спариваться с белыми значительно легче, чем с черными:

Темпы роста количества игр также выше, если белые ходят за ходы черных, но это примерно на 1%, что намного слабее, чем указанная здесь схема.

Мне нравятся случайные игры в шахматы. Иногда было бы неплохо связать это с онлайн-генератором квантовых случайных чисел, чтобы иметь программу, которая играет во все игры в шахматы, если гипотеза о множественных мирах верна.