(Heidi Walley/Unsplash) Na jednej úrovni sa šach javí ako jednoduchá hra: 64 jednotlivých čiernych alebo bielych políčok, 16 figúrok na každej strane a dvaja konkurenti usilujúci sa o dobytie.
Ponorte sa však trochu hlbšie a hra ponúka neuveriteľne komplexné možnosti, ktoré predstavujú výzvy pre šachových teoretikov a matematikov, ktoré môžu zostať nevyriešené desaťročia alebo dokonca storočia.
V júli 2021 bola jedna takáto výzva konečne vyriešená – aspoň do určitej miery. Matematik Michael Simkin z Harvardskej univerzity v Massachusetts si to myslel problém n-queens ktorý bol pre odborníkov záhadný už od jeho prvého predstavenia v 40. rokoch 19. storočia.
Ak poznáte svoj šach, viete, že dáma je najmocnejšou figúrkou na šachovnici, ktorá sa môže pohybovať o ľubovoľný počet polí v ľubovoľnom smere. Problém s n-queens sa pýta takto: Pri určitom počte dám (n), koľko usporiadaní je možných, keď sú kráľovné dostatočne ďaleko od seba, takže žiadna z nich nemôže vziať žiadnu z ostatných?
Pre osem dám na štandardnej doske 8 x 8 je odpoveď 92, hoci väčšina z nich sú otočené alebo odrazené varianty len 12 základných riešení.
Ale čo 1 000 dám na šachovnici, ktorá má 1 000 x 1 000 polí? A čo milión kráľovien? Simkinovo približné riešenie problému je (0,143n)n– počet dám vynásobený 0,143, umocnený na n.
To, čo vám zostalo, nie je presná odpoveď, ale je tak blízko, ako je to možné práve teraz. S miliónom kráľovien vychádza číslo ako číslo s piatimi miliónmi číslic za ním – takže ho tu pre vás nebudeme reprodukovať.
Simkinovi trvalo takmer päť rokov, kým prišiel s rovnicou, s množstvom použitých prístupov a techník a s niekoľkými prekážkami na ceste k riešeniu. Nakoniec bol matematik schopný vypočítať spodné a horné hranice možných riešení pomocou rôznych metód, pričom zistil, že sa takmer zhodujú.
„Ak by ste mi povedali, že chcem, aby ste svoje dámy umiestnili na hraciu plochu takým a takým spôsobom, potom by som bol schopný analyzovať algoritmus a povedať vám, koľko existuje riešení, ktoré zodpovedajú tomuto obmedzeniu,“ hovorí Simkin .
'Formálne povedané, redukuje problém na problém optimalizácie.'
Na začiatku, Simkin a kolega Zur Luria na Švajčiarskom federálnom technologickom inštitúte v Zürichu spolupracovali na variácii problému n-queens známeho ako torodiálny alebo modulárny problém. V tomto prípade sa uhlopriečky obopínajú okolo dosky, takže dáma sa môže posunúť diagonálne od pravého okraja dosky a znova sa objaviť napríklad na ľavej strane.
To dáva každej dáme symetriu útoku, ale nie je to tak, ako funguje normálna šachovnica: dáma v rohu šachovnice nemá toľko uhlov útoku ako jedna v strede.
Koniec koncov, pár práca na probléme s toroidom sa zastavila (hoci publikovali nejaké výsledky), ale Simkin nakoniec upravil niektoré plody tejto práce do svojho konečného riešenia.
Ako sa dosky zväčšujú a počet dám sa zvyšuje, výskum ukazuje, že vo väčšine povolených konfigurácií majú dámy tendenciu zhromažďovať sa po stranách dosky, pričom v strede je menej dám, kde sú vystavené útoku. Tieto poznatky umožňujú váženejší prístup.
Teoreticky by mala byť možná presnejšia odpoveď na hádanku n-kráľovná – ale Simkin nás dostal bližšie ako kedykoľvek predtým a je rád, že túto výzvu postúpi niekomu inému, aby študoval ďalej.
„Myslím si, že ja osobne možno na chvíľu skončím s problémom n-queens nie preto, že by sa s tým už nedalo nič robiť, ale len preto, že som sníval o šachu a som pripravený ísť ďalej. môj život,' hovorí Simkin .
Simkinov papier o riešení je dostupný na predtlačovom serveri arXiv .