Канадская команда специалистов по искусственному интеллекту из Университета Альберты под руководством профессора Джонатана Шаффера (Jonathan Schaeffer) создала непобедимую версию компьютерной программы Chinook для игры в английские шашки на доске 8х8. Научная статья, в которой утверждается, что в игре с любым противником программа либо выиграет, либо сведет партию к ничьей, недавно опубликована в журнале Science.
Работа над программой началась еще в 1989 году. Разрабатываемые учеными алгоритмы использовали примерно те же принципы, что и программы для игры в шахматы. В каждой позиции просчитывались возможные варианты развития событий, а бесперспективные пути отбрасывались с использованием эвристических правил. А поскольку шашки значительно проще шахмат, анализировать позиции легче, и можно считать на несколько десятков ходов вперед.
Мощность компьютеров росла, алгоритмы совершенствовались, и к 1994 году программа победила знаменитого чемпиона мира по шашкам Мариона Тинсли, который удерживал этот титул с 1955 года. С тех пор программа Chinook оставалась непобедимой, лишь изредка проигрывая отдельные партии турниров.
Но работа ученых продолжалась, и теперь им удалось полностью убрать из алгоритма эвристические процедуры, исключив тем самым возможность ошибки и всякие шансы противника на выигрыш. Дело в том, что начиная с того далекого 1989 года в научной группе над анализом шашечных позиций постоянно трудилось несколько десятков, а в лучше годы до двух сотен компьютеров. Это позволило проанализировать все 5х1020 шашечных позиций и в каждой найти лучший ход. И теперь, грубо говоря, расчет вариантов следующего хода сведен к поиску по обширной базе данных готовых решений.