Первый бой двух программ

Эта история началась в 1965 году, когда Джон Маккарти посетил СССР и познакомился с компьютером М-2 в лаборатории Александра Кронрода (на фото №2) в Московском институте теоретической и экспериментальной физики (ИТЭФ). Визит одного из отцов-основателей искусственного интеллекта, человека, придумавшего этот термин, в советский компьютерный центр был событием невероятным. Это было время, когда мир был разделён «железным занавесом», а наука, особенно кибернетика и вычислительная техника, стала ещё одним полем идеологического и технологического соперничества сверхдержав. И именно шахматы, эталон логики и стратегии, оказались в центре необычного соревнования — первой в истории шахматной партии между компьютерными программами по разные стороны океана.

Александр Кронрод, принимавший Маккарти, был яркой фигурой в советской науке. Математик с широкими интересами, он руководил созданием одной из первых в СССР действующих ЭВМ — М-2. Эта машина была чудом инженерной мысли в условиях дефицита. Кронрод также был страстным шахматистом, и именно он собрал в ИТЭФ талантливую группу молодых математиков, увлечённых задачей научить машину играть. Лидером этой группы стал Георгий Адельсон-Вельский, будущий соавтор знаменитого алгоритма «альфа-бета-отсечения», который на десятилетия определил развитие не только шахматных программ, но и методов поиска в искусственном интеллекте.

Джон Маккарти увёз из Москвы не только впечатления. Он увёз идею. В его багаже была плёнка с кодом шахматной программы, которую писали в ИТЭФ. А в голове — мысль устроить настоящий матч. В Стэнфорде, где он теперь работал, у Маккарти была своя «шахматная карта» — программа, написанная ещё в Массачусетском технологическом институте (MIT) студентом Аланом Котоком и его товарищами под руководством самого Маккарти. Алан Коток (на фото №3), впоследствии один из создателей первых компьютерных игр и соавтор протокола DHCP, в начале 60-х был просто талантливым студентом, взявшимся за амбициозный проект. Их программа, известная как «Коток-Маккарти», уже умела играть, но делала это медленно и довольно примитивно.

Эта программа, детально описанная в дипломной работе Котока 1962 года, была сложным, но во многом наивным созданием. Она использовала переменную глубину поиска, останавливаясь либо на произвольном максимуме, либо в «стабильной позиции». Её оценка позиции складывалась из взвешенной суммы факторов: материального баланса, контроля центра, структуры пешек, темпа и развития. Однако сами авторы признавали, что их оценка несовершенна, поскольку идеально оценить позицию в шахматах можно, лишь просчитав её до конца — до мата, ничьей или поражения.

Тут нужно пояснить терминологию:

Переменная глубина поиска, «произвольный максимум» и «стабильная позиция» — это были попытки программы решить, насколько далеко ей думать. Она не всегда считала одинаково. Иногда она просто останавливалась на заданном пределе, например, обдумав всего четыре хода вперёд («произвольный максимум»). В других случаях она пыталась быть умнее: если на доске заканчивалась немедленная «драка» — не было видно прямых взятий или атак — программа считала позицию «стабильной», прекращала глубокий расчёт и выставляла итоговую оценку, полагая, что главное уже ясно.

Материальный баланс — это простейший подсчёт. Каждая фигура имела свою цену: пешка — 1, конь или слон — 3, ладья — 5, ферзь — 9. Программа постоянно сравнивала сумму своих очков с очками противника. Самым сложным для неё было предсказать итог разменов — она пыталась смоделировать, кто кого переберёт в серии взаимных взятий, и часто в этом ошибалась.

Контроль центра — это стратегическое правило. Клетки в середине доски считались самыми важными, как высота на поле боя. Программа добавляла баллы за каждую свою фигуру, которая могла на них напасть или там стоять, веря, что это даёт преимущество. Позже, к 30-му ходу, это правило вообще отключалось, как будто программа «забывала» о нём, переходя к другой фазе игры.

Структура пешек — оценка здоровья пешечного «строя». Программа негативно оценивала изолированные пешки, две пешки на одной линии и т.д., и положительно – пешку, которая, к примеру, могла стать ферзём. Но влияние этой оценки было небольшим.

Темп — это попытка оценить инициативу и выигрыш во времени. В теории программа должна была ценить ходы, которые заставляют противника терять время на ответы, а самому развивать атаку. Однако на практике этот сложный концепт, судя по всему, так и не был полноценно встроен в её логику.

Развитие — правило про быструю мобилизацию. В начале игры программа более высоко оценивала ходы, которые выводили фигуры с начальных позиций в бой. Но, как и контроль центра, это правило со временем переставало действовать — ведь в середине игры все фигуры уже давно развиты.

Создатели программы консультировались с гроссмейстерами, чтобы выяснить, насколько контроль центра важнее крепкой пешечной структуры, но в литературе не находили точных количественных ответов. Из-за нехватки машинного времени они и вовсе отказались от внедрения в программу механизмов обучения, которые могли бы автоматически подстраивать веса оценочных критериев.

Маккарти улучшил программу, и в 1966 году по телеграфу между Калифорнией и Москвой начался уникальный матч из четырёх партий. Представьте: огромные, занимающие целые залы компьютеры IBM 7090 в США и советская М-20. Они не были связаны сетью. Ходы передавались обычными телеграммами. Каждый ход был результатом многочасовых, а иногда и многодневных вычислений. Машины перебирали варианты, оценивали позиции — и делали выбор.

Американская программа, как явствует из отчёта Котока, даже в 1962 году была далека от совершенства. Она тратила от 5 до 20 минут на ход, просматривая около 1100 позиций в минуту. Её главной проблемой был неэффективный и «шумный» поиск. Программа рассматривала множество заведомо бесполезных позиций. Хотя Маккарти и предложил для борьбы с этим эвристику «альфа-бета», её реализация в программе Котока была, судя по всему, не столь изящной и эффективной, как у советских коллег.

Более того, материальный баланс программа вычисляла громоздким и не всегда точным способом, полностью пересчитывая все атаки и защиты на каждой позиции с помощью подпрограмм. Программа не распознавала связки ферзя и короля, не учитывала вскрытые нападения, что, по признанию автора, часто приводило к «смущающим» ошибкам в оценке. Даже генератор правдоподобных ходов не был реализован в задуманном виде; вместо интеллектуального отбора ходов по целям программа просто сортировала все легальные ходы по результатам поверхностной оценки.

Советская программа, созданная командой Адельсона-Вельского, включавшей таких учёных, как Владимир Арлазаров, Анатолий Усков и Михаил Донской, использовала более совершенный и изящный алгоритм поиска. Они придумали, как отбрасывать заведомо проигрышные ветви расчётов, не тратя на них драгоценное машинное время. Это и было то самое «альфа-бета-отсечение», которое позже станет стандартом для всех шахматных программ. Американская программа перебирала варианты более прямолинейно и грубо, и её оценочная функция была уязвима для типичных тактических ударов — вилок, связок и вскрытых шахов, о чём с сожалением писал Коток.

Сам автор скромно оценивал силу своего творения на уровне любителя с опытом примерно в сто партий, отмечая, что большинство ходов программы не были ни блестящими, ни глупыми, но периодические грубые ошибки случались.

Матч длился девять месяцев и завершился со счётом 3:1 в пользу советской программы из ИТЭФ. Это была не просто победа в шахматах. В разгар холодной войны советские учёные доказали, что в области программирования и алгоритмов они не только не отстают, но и могут опережать своих американских коллег. При этом железо у них было значительно слабее. Американская программа Котока-Маккарти, несмотря на работу на мощном IBM 7090, несла в себе груз архитектурных недостатков и упрощённых решений, в то время как советская команда сделала ставку на математическую элегантность и алгоритмическую эффективность, что в итоге и принесло им историческую победу в первой в мире межконтинентальной шахматной дуэли машин.

В 1967 году программа Mac Hack VI стала первым компьютером, удостоенным звания почётного члена Шахматной федерации США после победы над человеком в турнире. Разработка шахматных программ в СССР (проект ITEP, позже — «Каисса») привела к серьёзным организационным последствиям для её создателей (хотя тут, на самом деле, очень спорный момент, в чём были реальные причины проблем создателей программы), но в 1974 году «Каисса» стала первым чемпионом мира среди компьютерных программ.

На протяжении десятилетий в компьютерных шахматах шла дискуссия между двумя подходами: «грубым перебором» (Тип A), анализирующим множество ходов, и «избирательным поиском» (Тип B), пытающимся имитировать человеческую логику. К 1970-м годам переборная стратегия, как у программы Chess 4.5, доказала своё практическое превосходство в силе игры.

Однако настоящая революция произошла недавно с появлением программ на основе искусственных нейронных сетей (таких как AlphaZero и Leela Chess Zero). Они сочетают в себе «интуитивную» оценку позиции, обученную на основе самой игры, и эффективный алгоритм поиска по методу Монте-Карло, который позволяет глубоко анализировать только самые перспективные ветки, превзойдя все предыдущие методы.

Но это меня уже сильно занесло. Давайте вернёмся к Джону Маккарти, который начинает самый важный этап своей жизни – занимается созданием «собственной» лаборатории.

Источник: vk.com

Комментарии: