Решение игры в шашки
@JoyFromXДжонатан Шеффер (р. 1957)
В 2007 г. математик-программист Джонатан Шеффер с коллегами с помощью компьютеров доказали, что шашки, в том случае если в них играют абсолютно правильно, являются безвыигрышной игрой. Это означает, что шашки напоминают «крестики-нолики» — игру, в которую невозможно выиграть, если оба игрока не делают неверных ходов. Обе игры заканчиваются вничью.
Чтобы доказать это, Шефферу потребовалась работа сотен компьютеров в течение 18 лет, что сделало шашки самой сложной игрой, которая когда-либо была решена. Это также означает, что теоретически возможно построить такую машину, которая никогда не будет проигрывать человеку.
Шашки, для которых используется клеточная доска 8x8, получили колоссальную популярность в Европе в XVI в., а наиболее ранние версии данной игры были обнаружены в руинах античного города Ур (ок. 3000 лет до н. э.) на территории современного Ирака. Фигурки шашек часто имеют форму черных и красных дисков, которые передвигают по диагонали. Игроки поочередно делают ходы и «съедают» шашки противника, «перепрыгивая» через них своими шашками.
Конечно, при том, что в шашках имеется примерно 5 × 10^20 возможных комбинаций, доказать то, что в этой игре гарантируется ничья, гораздо сложнее, чем доказать, что в крестики-нолики выиграть невозможно.
Группа ученых, изучающих шашки, рассмотрела 39 000 миллиардов комбинаций с 10 или меньшим числом шашек на доске и затем определила, могут ли красные или черные выиграть партию. Также эта исследовательская группа использовала специальный поисковый алгоритм для изучения дебюта данной игры и наблюдения за тем, как в результате дебютных ходов образуются 10-шашечные комбинации. Решение проблемы шашек стало важнейшей ступенью в области искусственного интеллекта, где зачастую разрабатываются стратегии решения сложных компьютерных задач.
В 1994 г. программа Шеффера Chinook сыграла несколько партий вничью с чемпионом мира по шашкам Марионом Тинсли. Через восемь месяцев Тинсли умер от рака, и некоторые стали упрекать Шеффера, что он ускорил кончину Тинсли стрессом, который тот пережил, сыграв вничью с программой Chinook.