Что значит «решить» шахматы — и почему это пока невозможно

Все нейросети в одном месте qiper.ru - Искусственный Интеллект/Нейросети/AI/ИИ 00:00:00 Введение В декабре 2017 года программа «Спасибо» играла в шахматы сама с собой За 4 часа она показала результаты лучше, чем «математический движок в мире» Вопрос о победе в шахматах остаётся открытым 00:00:44 Крестики-нолики и шашки В крестики-нолики при идеальной игре обоих игроков всегда ничья Шашки решались 18 лет командой профессора Джонатана Шеффера Количество позиций в шашках оценивается как 5 на 10 в 20 степени 00:02:23 Теорема Цермело Немецкий математик Эрнст Цермело доказал, что в конечной игре двух игроков без случайности одна из сторон имеет лучшую стратегию Либо белые побеждают при любой защите, либо чёрные, либо обе стороны могут гарантировать себе ничью 00:03:14 Сложность шахматных партий Клод Шеннон оценил количество возможных шахматных партий в 10 в 120 степени Повторение позиций делает перебор всех вариантов невозможным Программист Джон Тромп оценил количество легальных позиций в 4 на 10 в 44 степени 00:04:54 Методы компьютерных шахмат Компьютеры используют Minimax и альфа-бета-отсечение для оптимизации поиска ходов Альфа-бета-отсечение позволяет игнорировать варианты, которые не меняют результат Эффект горизонта помогает компьютерам игнорировать будущие неприятности 00:07:14 Deep Blue и Гарри Каспаров Deep Blue выиграл матч у Гарри Каспарова в 1997 году Оценка позиций Deep Blue настраивалась вручную программистами и гроссмейстерами Каспаров заподозрил вмешательство людей и потребовал реванш, но IBM отказалась 00:08:51 Alpha Zero В декабре 2017 года компания DeepMind запустила программу Alpha Zero Alpha Zero играла сама с собой и адаптировалась после каждой партии В матче из 1000 партий Alpha Zero выиграла 155, проиграла 6, а остальные 839 закончились в ничью 00:10:59 Таблицы матов Для позиций с малым количеством фигур разработаны таблицы матов Компьютер начинает с позиций, где мат уже стоит, и шаг за шагом идёт назад В 2012 году на суперкомпьютере «Ломоносов» в Московском университете посчитали все позиции с семью фигурами Найдена позиция, в которой одна сторона ставит мат при любой защите, но только через 549 ходов 00:12:15 Таблицы Эншпиля и правило 50 ходов Правило 50 ходов иногда отнимает у одной из сторон честно выигранную позицию Играть 500 ходов в одной партии не готов ни один турнир Таблицы на 7 фигур занимают десятки терабайт, а с 8 фигурами всё ещё сложнее Самый длинный известный выигрыш — 584 хода, и это всего 8 фигур из 32 00:12:44 Будущее лилиаматов Для полного решения лилиаматов нужно пройти путь от 8 фигур до 32 Каждая новая фигура увеличивает объём работы в сотни раз Большинство шахматистов и программистов уверены, что ответ — ничья, но это не доказательство Шашки тоже, скорее всего, были ничьей, пока не прошло 18 лет расчёта 00:13:14 Шахматы и шашки Даже если шахматы решат, играть в них вряд ли перестанут Шашки решены почти 20 лет назад, а турниры по шашкам проводятся до сих пор Знать, что идеальная игра ведёт к ничьей, и уметь играть идеально — разные вещи Машина, которая обыгрывает любого чемпиона мира, всё равно не знает, как правильно играть в шахматы Гроссмейстер смотрит на доску несколько секунд и уже видит, что происходит, без перебора миллионов вариантов