Вирішення шахів

Вирішення шахів означає знаходження оптимальної стратегії гри в шахи, за якої один з гравців (чорні або білі) завжди може форсувати виграш, або ж коли обидва можуть форсувати нічию (див. вирішена гра^[en]). Згідно з теоремою Цермело^[en], для шахів існує оптимальна стратегія, яку гіпотетично можна віднайти.

У менш строгому розумінні вирішення шахів може означати доказ, який із трьох можливих результатів (білі виграють; чорні виграють; нічия) є наслідком досконалої гри обох гравців. Цей доказ не обов'язково означає знаходження сам́ої оптимальної стратегії^[1].

Станом на 2015 рік не існує вирішення шахів ні в строгому, ні в менш строгому розумінні, і його також не очікують у близькому майбутньому. Серед дослідників немає консенсусу щодо того, чи теперішнє експоненціальне зростання комп'ютерних потужностей продовжить достатньо довго, щоб у майбутньому дозволити вирішити цю задачу "грубою силою", наприклад, перебором всіх можливих варіантів.

Часткові результати

Бази даних ендшпілю вирішили шахи до певної міри, визначивши досконалу гру для певної кількості Ендшпілів, включаючи всі нетривіальні ендшпілі з не більш як сімома фігурами і пішаками (включаючи обох (королів) на шахівниці^[2]. Повне вирішення задачі в цьому сенсі означає побудову такої бази даних для всіх 32-х фігур і пішаків.

Передбачення чи гру в шахи буде вирішено

На думку гросмейстера Джонатана Роусона^[en] "в принципі комп'ютери повинні бути здатні ... побудувати 32-фігурну базу даних. Це може зайняти десятиліття або століття, але, якщо цьому не перешкодить глобальне потепління або ядерна війна, рано чи пізно станеться"^[3]. Однак, спеціаліст у галузі теорії інформації Клод Шеннон, стверджував, що цю задачу не може вирішити жоден комп'ютер, оскільки це б вимагало від нього або здатності порівнювати близько 10¹²⁰ можливих варіантів розвитку гри, або ж мати "словник", у якому записані оптимальні ходи для кожної з близько 10⁴³ можливих позицій на шахівниці^[4]. Таким чином вирішити шахи теоретично можливо, але відрізок часу, який для цього необхідний (згідно з Шенноном, 10⁹⁰ років на процесорі частотою 1 MHz), виводить цю задачу за межі можливості будь-якої "доступної" (станом на 1950 рік) технології.

Ганс-Йоахім Бремерманн^[en], професор математики і біофізики в Університеті Каліфорнії, у своїй праці 1965 року розмірковував, що "швидкість, пам'ять і обчислювальна здатність будь-якого майбутнього комп'ютерного обладнання обмежена певними фізичними бар'єрами: світловим, квантовим і термодинамічним. Наявність цих бар'єрів дозволяє стверджувати, наприклад, що жоден комп'ютер, як би він не був побудований, ніколи не зможе прослідкувати все дерево можливих послідовностей ходів гри в шахи". Водночас, Бремерманн не відкидав можливості, що комп'ютер одного дня вирішить шахи. Він писав: "Для того, щоб комп'ютер досконало, або майже досконало, грав у шахи, йому потрібно або проаналізувати гру повністю ... або проаналізувати її приблизно і скомбінувати це з обмеженим дослідженням за допомогою дерева послідовностей. ... Однак нам іще далеко до теоретичного розуміння такого евристичного програмування"^[5].

Нещодавні наукові досягнення не сильно змінили цю оцінку. Гру в шашки вирішено (нестрого) у 2007 році^[6], але вона має за грубими оцінками квадратний корінь від кількості можливих позицій у шахах. Джонатан Шеффер, який здійснив цей нестрогий доказ, сказав, що спочатку необхідний такий прорив як побудова квантового комп'ютера, а вже потім можна братись за спробу вирішення шахів. Але він не відкинув такої можливості, додавши, що під час своєї 16-річної праці над вирішенням шашок вивчив одне правило "ніколи не можна недооцінювати розвитку технологій"^[7].

Див. також

Перевага першого ходу в шахах^[en] (міркування шахістів щодо того, чи досконала гра обох шахістів призводить до нічиєї)

Примітки

↑ Allis, V. (1994). PhD thesis: Searching for Solutions in Games and Artificial Intelligence (PDF). Department of Computer Science. University of Limburg. Архів оригіналу (pdf) за 20 серпня 2018. Процитовано 14 липня 2012.
↑ Lomonosov Tablebases. Архів оригіналу за 1 травня 2013. Процитовано 24 квітня 2013.
↑ Rowson 2005, pp. 205–06.^{[прояснити: ком.]}
↑ Shannon, C. (March 1950). Programming a Computer for Playing Chess (PDF). Philosophical Magazine. 7. 41 (314). Архів оригіналу (pdf) за 15 березня 2010. Процитовано 27 червня 2008.
"With chess it is possible, in principle, to play a perfect game or construct a machine to do so as follows: One considers in a given position all possible moves, then all moves for the opponent, etc., to the end of the game (in each variation). The end must occur, by the rules of the games after a finite number of moves (remembering the 50 move drawing rule). Each of these variations ends in win, loss or draw. By working backward from the end one can determine whether there is a forced win, the position is a draw or is lost. It is easy to show, however, even with the high computing speed available in electronic calculators this computation is impractical. In typical chess positions there will be of the order of 30 legal moves. The number holds fairly constant until the game is nearly finished as shown ... by De Groot, who averaged the number of legal moves in a large number of master games. Thus a move for White and then one for Black gives about 10³ possibilities. A typical game lasts about 40 moves to resignation of one party. This is conservative for our calculation since the machine would calculate out to checkmate, not resignation. However, even at this figure there will be 10¹²⁰ variations to be calculated from the initial position. A machine operating at the rate of one variation per micro-second would require over 10⁹⁰ years to calculate the first move!"
↑ Bremermann, H.J. (1965). Quantum Noise and Information. Proc. 5th Berkeley Symp. Math. Statistics and Probability. Архів оригіналу за 27 травня 2001. Процитовано 1 лютого 2016.
↑ Schaeffer, Jonathan; Burch, Neil; Björnsson, Yngvi та ін. (14 вересня 2007). Checkers Is Solved. Science. 317 (5844): 1518—1522. doi:10.1126/science.1144079. PMID 17641166. Архів оригіналу за 26 березня 2009. Процитовано 21 березня 2009. (необхідна підписка)
↑ Sreedhar, Suhas. Checkers, Solved!. Spectrum.ieee.org. Архів оригіналу за 25 березня 2009. Процитовано 21 березня 2009.