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

15

Мы все знаем, что самый короткий мат состоит из 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 о вероятности того, что два игрока сделают случайные ходы в результате одной и той же шахматной игры. Я подозреваю, что короткие игры в значительной степени преобладают над этой вероятностью, что должно упростить приблизительную вероятность, но было бы неплохо иметь реальные цифры для работы.

eyeballfrog
источник
1
Смежный (но не идентичный) вопрос, который может вас заинтересовать: chess.stackexchange.com/questions/24359/…
itub
2
Исходя из контекста вашего вопроса, вам также может быть интересно узнать, что игра может закончиться ничьей из-за повторения примерно в 8 слоев.
DM
1
Я не думаю, что запрашиваемых здесь данных достаточно для точного определения вероятностей в вопросе Math.SE. Вам нужно больше информации о структуре дерева игры. (Для иллюстративного контрпримера рассмотрим игру, в которой есть два возможных варианта для первого хода: A и B. Если первый ход - A, существует 1 миллион различных возможных вариантов для второго хода, тогда как, если это B, единственный второй возможный ход - C. Теперь в игре 1 000 001 возможных двух последовательностей ходов, но вероятность того, что случайный игрок в конечном итоге сыграет последовательность B, C, составляет 50%.)
Илмари
@IlmariKaronen Это правда, и я думал об этом, так как я разместил вопрос. Тем не менее, я не думаю, что разброс по коэффициенту ветвления дерева игры так быстро увеличивается, за исключением строк, содержащих проверку. Если общий вклад в вероятность быстро уменьшается с помощью ply, аппроксимация все равно должна работать достаточно хорошо.
eyeballfrog

Ответы:

26

Нет матов из 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.

konsolas
источник
13

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

orlp
источник
REFERENCES Homer Simpson, Chess Review, Jan-Feb 1982. Хорошо, я сделал часть этого, но это было бы смешно ...
Майкл
У OEIS действительно есть все, не так ли?
eyeballfrog
8

Вот простая программа на 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')
itub
источник
Для дальнейшего использования вы можете добавить такие вещи на pastebin.com; выбор никогда не истекает.
Джейсон С
Комментарии выше предполагают, что исследование фактического дерева игры может быть необходимо для этого расчета, поэтому эта программа может оказаться весьма полезной. Благодарю.
eyeballfrog
7

Главным человеком, которого я знаю по этому виду анализа, является Франсуа Лабель, который вычислил много чисел, связанных с шахматами (включая оценку максимальной скорости роста числа шахматных игр в зависимости от сгиба), и, в частности, вычислил число матов до слоя 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%, что намного слабее, чем указанная здесь схема.

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

Ласка
источник