Ile jest sposobów matowania we wczesnej fazie gry?

15

Wszyscy wiemy, że najkrótszy możliwy mat to 4 warstwy:

  1. f3 e5

  2. g4 Qh5 #

To nie jedyny możliwy ruch. W rzeczywistości istnieje 8, w zależności od tego, czy biały najpierw przesuwa pionek f lub g, czy przesuwa pionek f do f3 lub f4 i czy czarny gra w e6 czy e5. Oczywiście stanowi to tylko niewielką część możliwych 4-warstwowych sekwencji ruchów, ale to jedyne, które kończą grę.

To, czego szukam, to dla niewielkiej liczby warstw, ile sekwencji ruchów kończy się na mat, a nie na mat. Idealnie, co chciałbym, to coś w stylu

  • 4 warstwy: X sekwencji bez szachów, 8 4 warstw
  • 5 warstw: Y sekwencje bez szachów, 8 4-warstwowych mat, N 5-warstwowych mat
  • 6 warstw: Z sekwencjami bez szachownicy, 8 mat 4-warstwowych, N 5-warstwowych mat, M 6-warstwowych mat

i tak długo, jak to rozsądne.

Jest to zainspirowane pytaniem Math.SE dotyczącym prawdopodobieństwa wykonania losowych ruchów przez dwóch graczy w wyniku tej samej gry w szachy. Podejrzewam, że krótkie gry mocno zdominowały to prawdopodobieństwo, co powinno ułatwić oszacowanie prawdopodobieństwa, ale fajnie byłoby mieć rzeczywiste liczby do pracy.

gałka oczna
źródło
1
Powiązane (ale nie identyczne) pytanie, które może Cię zainteresować: chess.stackexchange.com/questions/24359/…
itub
2
W zależności od kontekstu pytania możesz również wiedzieć, że gra może zakończyć się remisem z powodu powtórzenia przy około 8 warstwach.
DM
1
Nie sądzę, aby dane, o które tu prosisz, były wystarczające, aby podać dokładne granice prawdopodobieństw w pytaniu Math.SE. Potrzebujesz więcej informacji o strukturze drzewa gry. (Dla przykładowego kontrprzykładu rozważ grę, w której istnieją dwa możliwe opcje pierwszego ruchu: A i B. Jeśli pierwszym ruchem jest A, istnieje 1 milion różnych możliwych wyborów dla drugiego ruchu, natomiast jeśli jest to B, jedyny możliwy drugi ruch to C. Teraz gra ma 1 000,001 możliwych dwóch sekwencji ruchów, ale prawdopodobieństwo, że przypadkowy gracz skończy grać w sekwencji B, C wynosi 50%.)
Ilmari Karonen
@IlmariKaronen To prawda i pomyślałem o tym, odkąd opublikowałem pytanie. Nie sądzę jednak, aby rozpiętość współczynnika rozgałęzienia drzewa gry zwiększała się tak szybko, z wyjątkiem linii zawierających czek. Jeśli całkowity udział w prawdopodobieństwie szybko spada wraz z warstwą, przybliżenie powinno nadal działać dość dobrze.
gałka oczna

Odpowiedzi:

26

Nie ma mat z 0-3 warstw.

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

„mat” oznacza liczbę ruchów matujących wykonanych na ostatniej warstwie. Tak więc dla 5 warstw istnieje 347 sekwencji matematycznych o dokładnie długości 5.

Wartości te pochodzą z: https://www.chessprogramming.org/Perft_Results

Obecnie nie ma danych matematycznych dla 10 warstw i więcej, prawdopodobnie ze względu na potrzebne zasoby obliczeniowe.

Aby uzyskać bardziej szczegółowe dane (np. Same linie), musisz napisać własny program perft, który zapisuje linie kończące się szachem.

konsolas
źródło
13

Ta sekwencja liczb całkowitych jest znana jako A079485 w On-Line Encyclopedia of Integer Sequences (OEIS), a liczby do 13 warstw włącznie włącznie są dostępne z różnymi dostępnymi odnośnikami.

orlp
źródło
REFERENCES Homer Simpson, Chess Review, Jan-Feb 1982. Ok, już to wymyśliłem, ale byłoby zabawnie ...
Michael,
OEIS naprawdę ma wszystko, prawda?
gałka oczna
8

Oto prosty program w języku Python, który odpowiada na pytanie, ale jest powolny, zajmuje 40 minut, aby uruchomić do 5 warstw na moim laptopie (i zwiększa się co najmniej 30-krotnie na każdą dodatkową warstwę). Fajną rzeczą jest to, że drukuje gry, jeśli tego potrzebujesz. Mógłbym opublikować tutaj wynik, ale nie chciałem udzielić długiej odpowiedzi na 347 linii ... :-)

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
źródło
W celu późniejszego wykorzystania możesz wrzucić takie treści na pastebin.com; kilof nigdy nie wygasa.
Jason C,
Powyższe komentarze sugerują, że do obliczeń konieczne może być zbadanie rzeczywistego drzewa gry, więc ten program może okazać się bardzo pomocny. Dzięki.
gałka oczna
7

Najważniejszą osobą, którą znam do tego rodzaju analiz, jest François Labelle, który obliczył wiele liczb związanych z szachami (w tym oszacowanie maksymalnego tempa wzrostu liczby gier szachowych jako funkcji warstwy), a w szczególności obliczył liczba szachów do warstwy 13. Wartości do warstwy 12 znajdują się na rysunku w http://wismuth.com/chess/chess.html .

Następnie na stronie http://wismuth.com/chess/statistics-games.html podaje konkretne liczby do warstwy 13, która zawiera 346 742 245 764 219 gier matowych.

Przy całej liczbie gier przytacza wyniki innych, którzy poszli do stawki 15 (!), Ale myślę, że nie śledzili mat.

Z warstw 5-13 jest około 1 szansa na 10 000, że ruch dostarcza partnera. Wydaje się jednak, że znacznie łatwiej jest skojarzyć jako biały w porównaniu do czarnego:

wykres warstwy w porównaniu z szansą wiązania

Tempo wzrostu liczby gier jest również większe w przypadku białych ruchów w porównaniu z czarnymi, ale jest to tylko około 1%, znacznie mniej niż w podanym tu wzorze.

Lubię losowe gry w szachy. Kiedyś miło byłoby połączyć to z internetowym generatorem liczb losowych, aby mieć program, który gra we wszystkie gry w szachy, jeśli hipoteza wielu światów się utrzymuje.

Laska
źródło