Тупиковая игра С помощью компьютеров найдено окончательное решение шашечного вопроса: выиграть невозможноМеждународный день шахмат 20 июля 2007 г. можно считать днем официального закрытия шашек. Игра исчерпана. Группа ученых из канадского Университета Альберты в Эдмонтоне математически доказала то, о чем давно догадывались профессионалы. В 64-клеточных шашках, правила которых в Америке немного отличаются от русских, безошибочно играющие соперники неизбежно придут к ничьей*.
В конце 1980-х 30-летний математик Джонатан Шеффер задался целью не просто написать программу, которая хорошо играла бы в шашки (подобно тому, как сегодня делают шахматные компьютеры, включая Deep Blue), а найти полное решение для всех вариантов, которые могут сложиться на доске с 12 белыми и 12 черными фишками. Расчеты начались в 1989 г., а в 1992 г. шашки уже “ломались” на 200 процессорах одновременно. С тех пор Шеффер поседел, его сын вырос из клетчатых слюнявчиков, а самый долгий компьютерный расчет в мире наконец завершился. Вначале Шеффер и коллеги создали базу данных из 39 трлн комбинаций, которые могут сложиться на доске, когда шашек 10 и меньше. А после расчета дебютов выяснилось, что, если оба игрока будут делать правильные ходы, они неизбежно придут к такой 10-шашечной комбинации, которая затем приведет к ничьей.
По ходу работы Шеффер и его коллеги вынуждены были придумывать новые алгоритмы сжатия данных, способы параллельных вычислений и еще много полезных вещей для обработки больших числовых массивов — сейчас их разработками интересуются компании биотехнологического сектора.
К 1994 г., когда расчет был еще на начальных этапах, программа Шеффера Chinook уже выигрывала у лучших шашистов мира. По легенде недоброжелателей, именно она несколькими ничьими подряд вызвала у чемпиона мира Мариона Тинсли стресс, который и свел его в могилу. Сегодня ни Тинсли, ни какой-либо другой шашист принципиально не смог бы выиграть у Chinook. А в серии турниров, скорее всего, победила бы машина. Просто потому, что любой человек рано или поздно ошибается.