Проблема, стоящая перед любой машиной для состязания в шахматы – невероятная сложность игры, связанная с выработкой стратегии и многообразием возможных ходов. Существует в общей сложности около 1046 возможных позиций, а уникальных партий – не меньше 10120 (это число Шеннона, названное в честь американского математика Клода Шеннона, который описал его вычисление в опубликованной в 1950 году статье “Программирование компьютера для игры в шахматы”). В начале партии все довольно просто: у белых есть только двадцать возможных ходов – шестнадцать пешками (самых популярных всего три) и четыре конями (из них распространен всего один). Но по ходу игры, когда вовлеченными оказываются и другие фигуры – слоны, ладьи, ферзь и король, – количество возможных ходов очень быстро растет. После того как каждый из игроков сделал по одному ходу, на доске может возникнуть 400 различных позиций, после двух ходов – 72 084 позиции, после трех – более 9 миллионов, а после четвертого хода – более 288 миллиардов. Это примерно по одной игровой позиции на каждую из звезд нашей галактики. А общее количество возможных партий во много раз превышает число элементарных частиц во Вселенной.
На заре компьютерных шахмат созданию эффективных программ мешала относительно низкая производительность вычислительных машин. Но основной принцип программирования сильного компьютерного шахматиста был выработан уже в 1950-х годах венгерско-американским математиком Джоном фон Нейманом. Алгоритм “минимакс” был назван так потому, что его цель – свести к минимуму счет противника, максимизируя при этом свой собственный. К концу десятилетия этот алгоритм удалось усовершенствовать с помощью метода, получившего название “альфа-бета-отсечение”. Используя эвристические правила, выведенные на основе игровой стратегии лучших шахматистов мира, он при поиске оптимального хода заранее отсекает возможные неудачные ходы, чтобы компьютер не тратил зря время на проверку заведомо бесплодных ветвей своего дерева поиска. Это не то же самое, что компьютер, который учится на собственных ошибках, – такие появились позже, – а лишь попытка учесть в программе приемы и комбинации ходов, использовавшиеся гроссмейстерами в реальных играх.
С появлением в 1970-х и 1980-х годах более мощных компьютеров поиск оптимального хода стал более глубоким и рациональным. В 1978 году компьютер выиграл партию у международного мастера по шахматам. В том же десятилетии прошел первый чемпионат мира по шахматам среди компьютерных программ. Когда один из авторов этой книги (Дэвид) работал менеджером по прикладному программному обеспечению в компании
С того времени компьютерные шахматы сделали огромный шаг вперед. В 1997 году чемпион мира по шахматам Гарри Каспаров в матче из шести партий проиграл компьютеру
Шахматная доска дома у Агниджо. На доске – позиция, возникшая в ходе игры между компьютером
