Алгоритмы используемые в играх.

В этом разделе мы рассмотрим логические игры типа шахмат. В эту группу входят различные реализации как известных игр - шахматы, шашки, го, бридж, маджонг, так и неизвестных или полностью выдуманных, например, наверняка запомнившейся игры “SPOT” с великолепным анимационным дизайном и отличной идеей игры. Подобные оригинальные игры похожи на другие в плане подбора правил. Как в аркадных играх, например, подчас требуется очень точная регулировка параметров, так и в придумываемых оригинальных логических играх требуется очень аккуратно подбирать правила, чтобы с одной стороны, они не были слишком сложны, а с другой игра не теряла интереса и не обнаруживался достаточно простой алгоритм выигрыша.

В этом отношении игра "SPOT"(“пятнышко”) безусловно выделяется отлично сбалансированными правилами. Ее автор фирма “Virgin Games”, известная такими играми, как "Dune 2", впоследствии переименовалась в “Virgin Interactive Entertainment”. Ее CD-ROM хит “7-й Гость” включает в себя в качестве одной из 23 головоломок, которые вы решаете, путешествуя по мрачному дому, свою игру “пятно”, тоже, можно сказать, превратившуюся из “Game” в “Interactive Entertainment”.

Надо сказать, что хотя логические игры никогда не занимают верхних строчек в любых таблицах популярности компьютерных игр, но тем не менее пользуются устойчивым спросом и способны приносить своим создателям немалый доход. К примеру, всем известный “Chess Master” фирмы “Software Toolworks”, реализованный в семи версиях (CM2000, CM2100, CM3000), в том числе для компьютеров ATARI, AMIGA и MAC, для среды WINDOWS, в конце 1993-го года - еще до выхода очередной суперверсии "ChessMaster 4000 Turbo" имел устойчивый объем ежемесячных продаж четыре тысячи копий. А программа разрабатывается уже более десяти лет! Кроме того, в ряде традиционных игр, таких как шахматы или Го, призы за победу над чемпионом мира достигают миллионов долларов, что намного превышает прибыли от самых лучших компьютерных игр других жанров.

В некоторых странах логические игры возводятся в ранг религии. Так, в Японии древнейшая игра Го приносит своим чемпионам поистине божественное поклонение. Можно с уверенностью сказать, что человек, способный создать сильную программу в Го, на уровне лучших японских мастеров, обессмертит свое имя в Стране Восходящего Солнца и получит миллионные доходы. Уже официально объявлен приз в один миллион долларов для программы, играющей в силу 1-го дана. Но игра Го отличается от других игр подобного плана именно сложностью эффективной реализации на компьютерах, поэтому появление сильнейшей программы в Го предсказывается к 2050-му году (для примера, в шахматы - к 2010-му).

Возможности, предоставляемые программами класса традиционных игр, стандартны. Вы всегда видите перед собой игровую доску в двумерной или трехмерной проекции. Изображения фигур могут быть как соответствующими типовым, так и оригинальными - например, короли и королевы, солдаты, рыцари и т.п. - как в "Battle Chess". Дополнительно на экране отображается много вспомогательной информации - время, список ходов, имена игроков. Вы можете сохранить или восстановить из базы ранее сыгранные партии, ваши или других игроков и профессионалов, просмотреть их по ходам вперед-назад, продолжить текущую партию с любого места, выбрать свой цвет, установить контроль времени и силу игры программы, ее настройку цветов и т.д. Но все эти технические дополнения требуют чисто рутинной работы. А как же программа выбирает лучший ход? Именно этот момент является ключевым в программировании традиционных игр.

Подавляющее большинство программ построено на так называемом методе “грубой силы” - “brute force” (полный перебор). Из текущей позиции определяются все возможные ходы - в шахматах их в среднем бывает около 50, в Го - 100-300, в калах - до 6. Они запоминаются в массиве Moves[][], где первым измерением является глубина перебора (исходно 0), а вторым - список ходов из позиции на i-м уровне. Затем выбирается очередной ход из нерассмотренных на данном уровне, совершается, опять определяются все возможные ходы (уже за другую сторону), снова выбирается очередной ход, и так происходит до достижения некоторой заданной глубины. В конце варианта происходит оценка возникшей позиции с помощью экспертных оценок (например, значения фигур плюс позиционная составляющая - конь в центре-хорошо, король открыт-плохо), и из всех позиций, перебирающихся на заданной глубине, выбирается одна с максимальной оценкой, и первый ход, ведущий по ветке в эту позицию, объявляется лучшим.

Эта методика стандартна, она описана во множестве статей и учебников по игровому программированию. Но посмотрим, а на какую-же реальную глубину сможем мы рассчитать варианты? Ведь количество ходов в дереве вариантов явно подчиняется геометрической прогрессии. В шахматы для игры на мастерском уровне требуется считать не менее чем на четыре-пять ходов (или 8-10 полуходов - ходов одной стороны) плюс форсированные продолжения - взятия, шахи и превращения. Тогда программе за две минуты стандартного контроля времени в официальных партиях потребуется просмотреть минимально 50 в десятой степени ходов, что составляет 10 в пятнадцатой степени позиций (миллион миллиардов). Лучшие программы на 486-м процессоре в секунду анализируют не более тысячи позиций. За две минуты это составит 120000 позиций. Для расчета на глубину 10 полуходов программе потребовалось бы 10 миллиардов секунд или около сорока лет!

Но, к счастью, умные люди придумали специальные эвристики, позволяющие существенно сократить объем перебора. Это, в первую очередь, алгоритм ветвей и границ, затем служба лучших ходов, хэш-таблицы и еще несколько других. Таких эвристик в мире известно немного, около десятка, и за каждую новую математики всех ведущих научных центров мира готовы платить огромные суммы - ведь большое количество прикладных задач решается именно методом перебора. Более подробно интересующиеся методами программирования переборных задач могут почитать статью о программировании игры в калах с исходными текстами алгоритмов на языке Си в одном из номеров PC-Review.

Отсюда становится понятной проблема программирования игры в Го. Если в шахматах коэффициент геометрической прогрессии 50 позволяет лучшим программам быстро рассчитывать варианты на пять-шесть ходов, то в Го количество ходов в начале партии составляет 19*19 = 361 ход, а в середине, когда начинается основная борьба - около двухсот. Понятно, что в лучшем случае программа сможет сделать расчет на четыре, максимум пять полуходов, что совсем недостаточно для сильнейшей игры. Го игра во многом позиционная, но, к сожалению, проблема обучения программ позиционной игре остается пока открытой.

Недавно появившаяся программа "Chess Master 4000 Turbo" помимо нового дизайна содержит очень интересные нововведения. Во-первых, она способна оценить с позиционной точки зрения словесными выражениями любой ваш ход с помощью комментариев типа “этот ход хорош тем, что ладья занимает открытую линию d” или “этот ход плох тем, что конь уходит из центра, ослабляя контроль над полем f5”. Такая, безусловно полезная для подавляющего большинства игроков возможность, достигается сравнением оценок позиции до и после хода и выявлением тех позиционных составляющих, которые дают основную разницу в оценках. Каждой из таких составляющих приписан набор стандартных фраз на английском, и они выводятся на экран.

Вторая уникальная возможность в “CM-4000” - это возможность настройки программы на стиль игры конкретного игрока как по силе, так и по манере игры. Если вы совсем не умеете играть в шахматы, а знаете только правила, то выберите в партнеры “новичка” или “болвана”, который делает заведомо плохие ходы. Вы можете также выбрать из большого списка игроков в партнеры Карпова, Каспарова, Алехина и других великих шахматистов или создать партнера со своим собственным стилем игры.

Это достигается очень гибкой системой позиционных оценок. Все коэффициенты каждой позиционной составляющей регулируются человеком. Вы можете устанавливать такие параметры как “активность в атаке”, “стремление пешек в ферзи”, “подвижность фигур” и т.д. Вы даже можете задавать соотношения между значениями фигур, как своих, так и противника, причем без ограничений. Например, значение пешки вы можете сделать равным ладье, а ферзя - коню. Программируется это тривиально, просто вместо констант, характеризующих позиционные параметры, используются переменные, которые разрешено менять. Это в какой-то степени похоже на работу создателя игровой программы, подбирающего оптимальные параметры оценки.

Отметим также чемпиона мира последних лет среди компьютерных программ для IBM PC - английскую программу “Hiarcs-Master 3.0” Марка Униаке, имеющую рейтинг выше 2500 (гроссмейстер), а в блице около 2600 - сильный международный гроссмейстер. Конечно, на процессоре Р6, когда он появится, рейтинг программы возрастет еще больше, так как скорость расчета напрямую зависит от быстродействия компьютера и объема свободной памяти. Ее автору удалось найти достаточно оптимальное соотношение между необходимостью глубокого расчета и сложностью позиционной оценки.

Ведь для увеличения глубины анализа вариантов, чем отличаются два других конкурента “Хайрекса” на гроссмейстерском уровне - программа “Fritz” немецкой фирмы “ChessBase”, производящей шахматные справочные системы, и “Genius” Ричарда Лэнга, выигравшая недавно у Каспарова матч из двух партий в блиц на компьютере с Pentium-процессором, приходится жертвовать качеством позиционного оценивания. Кстати, после проигрыша Каспарова большинство ведущих гроссмейстеров потребовало запретить с 1995-го года участие компьютеров в турнирах людей.

Последняя программа известна любителям шахмат по шахматным компьютерам “Мефисто” с мощным специализированным процессором, в память которых зашит “Genius”. Интересно, что автор сначала писал программу исключительно для этих автоматов, и лишь затем перенес программу в MSDOS. Ричард Лэнг пишет свои программы исключительно на ассемблере, начиная от дизайна и кончая логической частью. Такое мастерство потрясает, впрочем, по собственному признанию автора, он и не знает других языков программирования, кроме ассемблера.

Благодаря “вылизанному” коду эти две программы способны осуществлять глубокий расчет, не очень заботясь о качестве позиционной оценки. Да это и понятно - ведь более качественный анализ каждой из миллионов позиций существенно тормозит скорость работы и, как следствие, снижает глубину расчета. Но так ли важен грубый расчет? Может быть, достаточно считать на некоторую не очень большую глубину, но более качественно оценивать позицию, используя специализированную шахматную информацию, как это делает человек? Этой проблеме столько же лет, сколько и первой шахматной программе, и пока сильнейшие программы одерживали победу с помощью лишь далекого расчета.

Но вот наконец англичанин Марк Униаке написал свой “Hiarcs” (в свободное от работы время, он даже просит не присылать ему по электронной почте письма о его программе на работу, только домой!), который считает не очень глубоко (относительно, конечно), но интеллектуально подходит к оценке каждой позиции, что дает ему существенное преимущество, особенно при игре с большим контролем времени, когда на первый план выходит не глубина расчета, а чисто шахматное понимание позиции. Московская фирма “ИнформСистемы” (939-10-24), обладающая исключительными правами на распространение данной программы и ряда других сильнейших шахматных спортивных программ в России, предлагала своим постоянным клиентам - пользователям шахматной системы “Chess Assistant”, сильнейшим мастерам и гроссмейстерам СНГ, при тестировании “Хайрекса” сыграть с ним несколько партий. За один месяц несколько международных мастеров и гроссмейстеров сыграли с программой более десяти партий и набрали всего пол-очка (только одна ничья), проиграв все остальные !!!

Некоторые версии шахмат, как например, "Star War Chess" вышеупомянутой фирмы “Software Toolworks”, основной упор делают на графику, повторяющую в данном случае мотивы фильма “Звездные Войны”, когда трехмерные фигуры роботов и космических рейнджеров схватываются в красивых мультяшках, причем игра ведется не чисто по шахматным правилам, а с целью уничтожить главного вражеского предводителя, или "Terminator 2. Chess Wars" фирмы Capstone с фигурами и видеовставками из одноименного фильма. Развивая идею игр с нестандартными правилами, “Software Toolworks” выпустила трехмерную версию игры в нечто, похожее на шахматы, на девятиклеточной доске.

Основная сложность программирования в традицоннных играх ложится на оптимальное построение алгоритма перебора, позволяющего за заданное время анализировать как можно больше позиций. Здесь подчас недостаточно знания программирования, необходимы еще знания математики и теории игр. Сложность программирования - от 5 до 9 баллов из 10 в зависимости от игры, подлежащей программированию. Некоторые игры, например, калах, легко поддаются перебору из-за небольшого числа вариантов, и выигрывают у любого, пусть даже самого сильного, игрока-человека, другие, как Го, позволяют создавать программы пока не сильнее второго разряда.