North American Computer Chess Championship

North American Computer Chess Championship (NACCC) — серия ежегодных соревнований по компьютерным шахматам, проводившихся в Северной Америке с 1970 по 1994 год. Являлся одним из первых и наиболее престижных турниров, в котором участвовали шахматные программы, разработанные университетскими исследовательскими группами, корпорациями и независимыми программистами. NACCC сыграл ключевую роль в развитии алгоритмов искусственного интеллекта, методов перебора и оценки позиций, а также в популяризации компьютерных шахмат.

История

Предпосылки и основание

Первые шахматные программы появились в 1950-х годах, но их возможности были крайне ограничены из-за низкой вычислительной мощности. К концу 1960-х годов, с развитием мейнфреймов и мини-ЭВМ, стало возможным проводить соревнования между программами. Идея создания регулярного чемпионата принадлежала группе исследователей из Массачусетского технологического института (MIT) и Стэнфордского университета. Первый турнир состоялся в 1970 году в Нью-Йорке, его организатором выступила Ассоциация вычислительной техники (ACM). В соревновании участвовали 6 программ, включая Mac Hack (разработчик — Ричард Гринблатт, MIT) и Chess 3.0 (Стэнфорд).

Развитие в 1970-е годы

В 1970-х годах NACCC проводился ежегодно, обычно в рамках конференций ACM. Программы быстро совершенствовались: к 1973 году Chess 4.0 (Северо-Западный университет) стала первой программой, победившей человека в турнирной партии (с рейтингом 2200). В 1977 году Chess 4.6 выиграла чемпионат, продемонстрировав глубину перебора до 8 полуходов. К концу десятилетия программы достигли уровня мастера ФИДЕ.

Эпоха доминирования Cray Blitz и Hitech

В 1980-х годах NACCC стал ареной борьбы между программами, работавшими на суперкомпьютерах. Cray Blitz (разработчик — Роберт Хайатт, Университет Алабамы) выиграл чемпионат в 1983, 1984, 1985 и 1986 годах, используя векторный процессор Cray-1. В 1985 году Hitech (Карнеги-Меллон) стал первой программой, достигшей рейтинга 2500, и победил в NACCC в 1988 году. В 1989 году Deep Thought (IBM) одержал победу, став первой программой, обыгравшей гроссмейстера в официальной партии (Бент Ларсен, 1988).

Закат и завершение

К началу 1990-х годов NACCC утратил монопольное положение из-за появления коммерческих программ (например, Fritz, Chessmaster) и специализированных турниров, таких как Чемпионат мира по компьютерным шахматам (WCCC). Последний NACCC состоялся в 1994 году в Кейп-Код, Массачусетс. Победителем стала программа Deep Blue 2 (IBM). После этого ACM прекратила проведение турнира, сосредоточившись на других направлениях. Всего было проведено 25 чемпионатов.

Правила и формат

Регламент

• Участники: программы, работающие на любом аппаратном обеспечении, включая суперкомпьютеры, кластеры и персональные ЭВМ. Допускались как академические, так и коммерческие разработки.
• Контроль времени: варьировался от 40 ходов за 2 часа до 40 ходов за 1,5 часа (в разные годы). В 1980-х годах использовался контроль 40 ходов за 2 часа, затем 20 ходов за 1 час.
• Формат: круговой турнир (все против всех) или швейцарская система (при большом числе участников). Количество туров — от 5 до 7.
• Определение победителя: по сумме набранных очков. При равенстве очков проводились дополнительные партии с укороченным контролем времени.

Особенности

• Программы не имели доступа к шахматным базам данных или эндшпильным таблицам (кроме поздних лет, когда разрешались таблицы для 5-6 фигур).
• Партии игрались на стандартных шахматных досках, ходы вводились оператором программы (человеком). В 1990-х годах некоторые программы подключались напрямую к компьютеру-серверу.
• Запрещалось использование подсказок от человека во время партии.

Классификация участников

По типу аппаратного обеспечения

• Мейнфреймы и суперкомпьютеры: Cray Blitz (Cray-1), Deep Thought (IBM), Hitech (специализированная ЭВМ с 64 процессорами).
• Мини-ЭВМ: Chess 4.0 (CDC 6400), Mac Hack (PDP-10).
• Персональные компьютеры: программы для IBM PC и Apple Macintosh, например, MChess (1980-е).

По происхождению

• Академические: разрабатывались в университетах (MIT, Стэнфорд, Карнеги-Меллон, Северо-Западный университет).
• Корпоративные: IBM (Deep Thought, Deep Blue), Bell Labs (Belle), Cray Research (Cray Blitz).
• Независимые: энтузиасты-одиночки (например, Chess 3.0 от Дэвида Слэйта).

Значимые программы и их достижения

Mac Hack (1970)

• Победитель первого NACCC (1970). Первая программа, сыгравшая в турнире с людьми (1971, рейтинг 1500).
• Использовала алгоритм минимакс с альфа-бета-отсечением и эвристическую оценку позиции.

Chess 4.0–4.6 (1973–1977)

• Разработчик: Дэвид Слэйт, Ларри Аткинс (Северо-Западный университет).
• Chess 4.0 (1973): первая программа, победившая человека в турнирной партии (рейтинг 2200).
• Chess 4.6 (1977): выиграла NACCC и Чемпионат мира по компьютерным шахматам (1977). Достигла глубины перебора 8 полуходов.

Belle (1978–1982)

• Разработчик: Кен Томпсон, Джо Кондон (Bell Labs).
• Первая программа, получившая звание мастера по шахматам (1978, рейтинг 2200). Победитель NACCC 1978, 1979, 1980, 1982.
• Использовала специализированное аппаратное обеспечение (плата с 16 процессорами).

Cray Blitz (1983–1986)

• Разработчик: Роберт Хайатт, Гарри Нельсон (Университет Алабамы).
• Работала на суперкомпьютере Cray-1. Победитель NACCC 1983–1986. Достигла рейтинга 2550.
• Первая программа, использовавшая векторный процессор для параллельного перебора.

Hitech (1985–1988)

• Разработчик: Ханс Берлинер, Мюррей Кэмпбелл (Карнеги-Меллон).
• Победитель NACCC 1988. Первая программа с рейтингом 2500 (1985). Использовала 64 специализированных процессора для оценки позиций.

Deep Thought (1988–1990)

• Разработчик: IBM (Томас Эннесли, Мюррей Кэмпбелл, Фэн-сюн Сюй).
• Победитель NACCC 1989, 1990. Первая программа, обыгравшая гроссмейстера в официальной партии (Бент Ларсен, 1988, рейтинг 2600).
• Использовала 6 процессоров IBM RS/6000. Достигла глубины перебора до 20 полуходов.

Deep Blue 2 (1994)

• Разработчик: IBM.
• Победитель последнего NACCC (1994). Преемник Deep Thought. В 1996 году сыграла матч с Гарри Каспаровым (поражение 2-4), а в 1997 году победила его (3,5-2,5).

Влияние на развитие компьютерных шахмат и ИИ

Технические инновации

• Альфа-бета-отсечение: оптимизация перебора, позволившая значительно сократить количество рассматриваемых ходов.
• Эвристические оценки: разработка функций оценки позиции (материал, пешечная структура, безопасность короля).
• Параллельные вычисления: использование нескольких процессоров (Hitech, Deep Thought) и векторных процессоров (Cray Blitz).
• Аппаратные ускорители: специализированные платы для шахмат (Belle, Hitech).

Научное значение

• NACCC стимулировал исследования в области искусственного интеллекта, теории игр и алгоритмов поиска.
• Многие участники (Ханс Берлинер, Кен Томпсон, Роберт Хайатт) стали пионерами в области машинного обучения и компьютерного зрения.
• Соревнования показали, что комбинация грубой силы перебора и эвристик может превзойти человеческое мастерство в ограниченной области.

Популяризация

• NACCC привлёк внимание СМИ и широкой публики к компьютерным шахматам. Матчи Deep Thought и Deep Blue транслировались по телевидению.
• Способствовал развитию коммерческих шахматных программ (Fritz, Chessmaster, Shredder), которые стали доступны на персональных компьютерах.

Критика и ограничения

Зависимость от аппаратного обеспечения

• Критики отмечали, что победы в NACCC часто определялись не столько качеством алгоритмов, сколько вычислительной мощностью. Например, Cray Blitz (стоимостью $10 млн) имел огромное преимущество перед программами на ПК.

Отсутствие стандартизации

• В разные годы правила допускали разное аппаратное обеспечение, что затрудняло сравнение программ. Некоторые участники использовали суперкомпьютеры, другие — персональные ЭВМ.

Узкая специализация

• Программы были оптимизированы исключительно для шахмат и не демонстрировали общих интеллектуальных способностей. Это вызывало критику со стороны исследователей общего ИИ.

Итоги

NACCC завершился в 1994 году, когда компьютерные шахматы достигли уровня гроссмейстеров. Чемпионат уступил место более специализированным турнирам (WCCC, CCT) и коммерческим соревнованиям. Однако его историческое значение велико: NACCC стал первым регулярным турниром, объединившим исследователей, программистов и шахматистов, и заложил основы для современных алгоритмов поиска и оценки в играх.

Источники

• Newborn, M. (1997). Kasparov vs. Deep Blue: Computer Chess Comes of Age. Springer-Verlag.
• Levy, D. (1988). Computer Chess: A History from the 1950s to the 1980s. Batsford.
• Berliner, H. (1989). Hitech: A Computer Chess Program. Communications of the ACM.
• Hyatt, R. (1990). Cray Blitz: A Computer Chess Program. Journal of the International Computer Chess Association.
• Campbell, M., Hoane, A. J., & Hsu, F. (2002). Deep Blue. Artificial Intelligence, 134(1-2), 57-83.
• ACM SIGART (1970–1994). Annual Reports on the North American Computer Chess Championship.