Розмір шрифта:
Обчислювальна складність гри в шахи: Від числа Шеннона до алгоритмів оцінки позиції
Остання редакція: 2025-12-30
Анотація
Анотація:У доповіді проводиться аналіз математичних викликів, пов'язаних з астрономічною обчислювальною складністю гри в шахи, та методів їх подолання за допомогою комбінаторного аналізу і теорії ймовірностей. Досліджується роль масштабу ігрового простору, визначеного Клодом Шенноном, у формуванні стратегії як для людини, так і для штучного інтелекту. Детально розглядається застосування комбінаторики для розрахунку форсованих варіантів та використання імовірнісної евристики у функціях оцінки позиції шахових рушіїв. Computational complexity of the game of chess: From Shannon's number to position evaluation algorithms
AbstractThe report analyzes the mathematical challenges associated with the astronomical computational complexity of chess and the methods for overcoming them using combinatorial analysis and probability theory. The role of the scale of the game space, defined by Claude Shannon, in the formation of strategy for both humans and artificial intelligence is investigated. The application of combinatorics for calculating forced variations and the use of probabilistic heuristics in chess engine position evaluation functions are considered in detail.
AbstractThe report analyzes the mathematical challenges associated with the astronomical computational complexity of chess and the methods for overcoming them using combinatorial analysis and probability theory. The role of the scale of the game space, defined by Claude Shannon, in the formation of strategy for both humans and artificial intelligence is investigated. The application of combinatorics for calculating forced variations and the use of probabilistic heuristics in chess engine position evaluation functions are considered in detail.
Ключові слова
Шахи; число Шеннона; комбінаторний аналіз; функції оцінки; імовірнісна евристика; шахові рушії. Chess; Shannon number; combinatorial analysis; evaluation functions; probabilistic heuristics; chess engines.
Посилання
Shannon C. E. XXII. Programming a computer for playing chess. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science. 1950. Т. 41, № 314. С. 256–275. URL: https://vision.unipv.it/IA1/ProgrammingaComputerforPlayingChess.pdf (дата звернення: 23.05.2025). Which is greater? The number of atoms in the universe or the number of chess moves? National Museums Liverpool. URL: https://www.liverpoolmuseums.org.uk/stories/which-greater-number-of-atoms-universe-or-number-of-chess-moves (дата звернення: 23.05.2025). L. T. B. R. S. N. P. J. G. K. (2020). Computer Science & AI: Alpha-Beta Pruning. Georgia Tech's Online Master of Science in Computer Science. URL: https://omscs.gatech.edu/sites/default/files/images/omscs_2020_05_05_alpha-beta_pruning_and_evaluation.pdf (дата звернення: 23.05.2025). Елементи теорії ймовірностей та математичної статистики Частина 1 : навчальний посібник / Хом’юк І. В. , Сачанюк-Кавецька Н. В., Ковальчук М. Б., Хом’юк В. В. – Вінниця : ВНТУ, 2017. –145 с. Теорія ймовірностей та математична статистика : навчальний посібник / Хом’юк І. В. , Хом’юк В. В., Краєвський В. О. – Вінниця : ВНТУ, 2009. –189 с. Елементи теорії ймовірностей та математичної статистики Частина 1 : навчальний посібник / Хом’юк І. В. , Сачанюк-Кавецька Н. В., Ковальчук М. Б., Хом’юк В. В. – Вінниця : ВНТУ, 2017. –162 с.
Повний текст:
PDF