«Еще пять тысяч ведер, и золотой ключик будет у нас в кармане»
Наиболее интересным всегда является алгоритмический движок, который приводит к правильному решению (или правильным решениям). Сегодня мы поговорим о специфике программирования ИИ, продолжая тему создания шахматных программ, но при этом именно сегодня мы возьмем вариант игры попроще: хочется, чтобы с сущностью технологий могли разобраться и школьники. Некоторые методы могут показаться не оптимальными, это правда, но наша задача — объяснить сам принцип. Приступим…
Давайте ответим на вопрос: почему в шахматных программах часто используются базы дебютов (начал) и эндшпилей (завершений партий)? То есть, они не рассчитываются, а используются готовые решения.
Представьте себе ситуацию, когда на доске у одного из игроков остался король, а у второго — король и ладья. То есть, любой начинающий шахматист, осваивающий навыки постановки мата ладьей и королем, скажет, что тот математически или логически строится на отсечении линий/областей. Вместе с тем, в рамках alpha-beta компьютер будет в первую очередь обсчитывать самые выгодные по его мнению полуходы — шахи и взятия. Например, одна программа даже не могла быстро поставить линейный мат, поскольку все время пыталась атаковать короля, но даже не видела разницы между атаками.
То есть, как многие могли понять, наиболее сильно программный переборный принцип, не зависимо от методик, которые он подразумевает, работает в миттершпиле (середине партии), а когда речь заходит об определенных алгоритмах/моделях поведения (дебюты, эндшпили) чаще всего используются заготовки.
Мы уже говорили о том, что написание шахматного интеллекта — это конкретная, а не абстрактная задача, поэтому давайте остановимся на трех базовых подходах к реализации ИИ. Кстати, это относится ко всем вычислительным системам, использующим ИИ для выработки конкретных решений на базе входящих данных, т.е. не только шахматам.
Три пункта разработчика ИИ
Написать игру (игровой интеллектуальный движок) мы можем тремя различными путями (назовем их ТРЕМЯ ключевыми ПУНКТАМИ), а именно: - С помощью поиска наиболее выгодного хода (alpha-beta-перебор) с расчетом на определенную глубину и выделением наиболее выгодных ветвей поиска с продлением расчетов.
- Активно использовать логику, опираясь на специфику задачи.
- С помощью графа (использование хеш-таблиц, шаблонов).
Причем одним из самых важных моментов, который нужно осознавать — это взаимосвязь между стоимостью продукта (алгоритм — это тоже продукт) и его содержанием. Немного непонятно? ОК, скажем по-другому: цель должна оправдывать средства. Теперь пройдемся по пунктам подробнее.
1…
Был такой старый советский еще черно-белый фильм про Буратино, в котором черепаха Тортила выбросила золотой ключик в пруд, и помощники Карабаса начали вычерпывать водоем для того, чтобы его достать. Один из них произнес веселую фразу, которая, кстати, очень любима среди математиков: «Еще пять тысяч ведер, и золотой ключик будет у нас в кармане». Как вы понимаете, речь идет в определенном смысле о полном переборе (каждое ведро — шаг к конечной цели, оценивается только конечная точка), но цель оправдывает средства.
В своих статьях по программированию шахмат в начале 50-х прошлого столетия Клод Шеннон предположил две стратегии вычислений с оценкой конечной точки, а именно, тип А, где на определенную глубину осуществляется полный перебор, и… тип B, где осуществляется выборочное расширение определенных строк, которые выявляются на базе шахматных знаний. Например, как мы уже говорили, в первую очередь считаются взятия и шахи. Оценочная функция вызывается только для конечной точки перебора.
2…
Что касается активного использования логики и применения чисто алгоритмического мышления, можно также вспомнить известную в мире программирования шахмат фразу: «Ботвинник только думает, что он знает, как он думает». Речь идет о чемпионе мира (1948-57, 1958-60, 1961-63 гг.) Михаиле Моисеевиче Ботвиннике, который активно занимался теорией программирования шахмат, и думал, что можно создать некий универсальный алгоритм игрока. Возможно ли это? На самом деле, даже чемпионы играют по-разному. Например, не было конкретного матча за шахматную корону между Ботвинником и Алехиным. При этом, Фишер, изучивший множество шахматной литературы (для этого он даже выучил русский язык), однажды сказал, что наиболее непонятный принцип игры у Алехина. И, вообще, можно ли создать электронную копию человеческого мозга? По крайней мере, варианты с персептронами (что мы обсуждали весной этого года) не выросли во что-то состоятельное, также как и множество других идей.
Впрочем, персептроны, равно как и некоторые находки Ботвинника нашли применение на практике. Например, если говорить о работах шахматного чемпиона, то достаточно сказать, что они использовались для той же электроэнергетики. Персептронный принцип иногда внедряют для систем решения нетрививальных математических задач и доказательства теорем. То есть, какое бы направление не развили, оно всегда может принести свои полезные плоды.
Вместе с тем, Ботвинник не предложил что-то нереализуемое. Дело в том, что в простейших играх гораздо более удобно применять алгоритмы, эмулирующие мышление человека, а зачастую и простейшую логику. Шахматный интеллект к такому только начинает подходить.
3…
Что касается графов, то тут все достаточно просто по структуре, потому как рассматриваются конкретные позиции таблицы. Ведь не секрет, что к одной и той же позиции можно придти различными путями. Также, могут рассматриваться не только конкретно позиции, а определенные ситуации. Одну из них мы уже описали, когда нужно просто поставить мат ладьей и королем. Здесь может вызываться и алгоритм поведения. Например, существуют варианты безоговорочного мата в несколько ходов. Ставить такие ситуации на расчеты — затратно, а включить в некую таблицу игровых шаблонов — выгодно. Впрочем, мы об этом подробно поговорим позже.
Крестики-нолики, вроде бы просто
Давайте возьмем тривиальную задачу, а именно, игру крестики-нолики. У нас есть девять полей (доска 3х3), каждое из которых может: - Быть пустым.
- Быть заполнено крестиком.
- Быть заполнено ноликом.
Условием выигрыша считается вариант, когда имеются три крестика или три нолика по вертикали, горизонтали или диагонали. Считать мы можем по разному. При этом давайте рассмотрим все ключевые варианты решений, которые используются в более «взрослых» играх.
Считаем полным перебором
Для первого полухода («крестики») мы получаем вариант из 9 возможных позиций, которые, если мы будем руководствоваться шахматными технологиями, нам нужно посчитать до конца. Сколько это будет расчетов? Для первого полухода — факториал 9-ти (обозначается 9!). То есть, для него мы сначала считаем возможность постановки на одну из девяти клеток. Потом считаем ответный полуход ноликов, то есть второй полуход, который ищется уже из 8-ми вариантов. Для третьего полухода — из 7-ми и так далее. Таким образом, для первого полухода мы получаем количество рассматриваемых позиций равное факториалу 9, т.е. 362880. Гхм-м, это для крестиков-ноликов:))).
ПРИМЕЧАНИЕ: Говоря слово «позиций», мы подразумеваем количество рассматриваемых вариантов развития, а сами позиции могут повторяться.
Покажем наглядно для тех, кто не совсем разобрался. Введем обозначения, 0 — пустая клетка, -1 — крестик, 1 — нолик. Первый вариант первого полухода (всего их 9), здесь мы ставим крестик в левом верхнем углу:
(-1,0,0,0,0,0,0,0,0)
Для него рассчитывается восемь вариантов второго полухода для нашего первого, когда крестик был поставлен в левом верхнем углу:
(-1,1,0,0,0,0,0,0,0) (-1,0,1,0,0,0,0,0,0) (-1,0,0,1,0,0,0,0,0) (-1,0,0,0,1,0,0,0,0) (-1,0,0,0,0,1,0,0,0) (-1,0,0,0,0,0,1,0,0) (-1,0,0,0,0,0,0,1,0) (-1,0,0,0,0,0,0,0,1)
Семь вариантов третьего полухода, если нолик был поставлен в правом нижнем углу:
(-1,-1,0,0,0,0,0,0,1) (-1,0,-1,0,0,0,0,0,1) (-1,0,0,-1,0,0,0,0,1) (-1,0,0,0,-1,0,0,0,1) (-1,0,0,0,0,-1,0,0,1) (-1,0,0,0,0,0,-1,0,1) (-1,0,0,0,0,0,0,-1,1)
И так далее, пока не будут рассчитаны все позиции для нашего первого полухода, после мы повторяем расчеты для (0,1,0,0,0,0,0,0,0) и так далее.
Это очень напоминает наше достаточно давнишнее решение задачи с восемью ферзями. Принцип схож, потому как мы сталкиваемся с игровым типом с ограниченным количеством ходов. Есть и своя специфика. То есть, вариант конца игры может возникнуть, начиная с шестого полухода, дальше считать не нужно. К тому же с полным перебором возникнут трудности, выраженные в том: а как же все-таки оценивать наиболее выгодные ходы? То есть, здесь полный перебор не выгоден вообще.
Но при этом вы можете заметить, что как только первый полуход уже сделан, количество расчетов существенно уменьшается. То есть, для: - второго полухода рассчитывается 40320 позиций (8!).
- третьего — 5040 (7!).
- четвертого — 720 (6!).
- пятого — 120 (5!).
- шестого — 24 (4!).
- седьмого — 6 (3!).
- восьмого — 2 (2!).
- девятого — 1 (1!).
Перебор с выборочным расширением
Очевидно, что: - Для начала игры наиболее выгодным ходом будет вариант, когда охватывается как можно большее количество пустующих горизонталей, вертикалей или горизонталей.
- Для середины игры наиболее выгодным ходом будет вариант, когда охватывается как можно большее количество горизонталей, вертикалей или горизонталей, где есть пустоты или уже имеются идентичные элементы (для ноликов — нолики).
Исходя из этого можно строить alpha-beta с выборочным продлением наиболее выгодных ветвей. Построить alpha-beta с учетом только форсированных ходов в крестиках-ноликах не сложно и примеры такого подхода вы можете найти в любом учебнике по программированию шахматных программ.
Логика применительно к задаче
Пункт 2 в нашем случае является самым выгодным решением. Полуход формируется, как говорится «по месту», для чего необходимо сделать несколько строчек if с расчетом двух условий из предыдущего подраздела. Никакого alpha-beta не нужно, достаточно при расчете каждого полухода вставить переменную с оценкой. На С++ у меня такая программа заняла 30-40 строчек кода.
Какие у нас условия в крестиках-ноликах? Для простоты представления в С++, представьте себе игровое поле как:
0,1,2, 3,4,5, 6,7,8.
Перечислим варианты победы, подразумевая массив из 9 элементов (от [0] до [8]).
Горизонтали: 0-1-2, 3-4-5, 6-7-8. Вертикали: 0-3-6, 1-4-7, 2-5-8. Диагонали: 0-4-8, 2-4-6.
Наиболее выгодным ходом, особенно в начале игры, является тот, который подразумевает развитие выигрышных ситуаций по наибольшему количеству направлений (вертикали, горизонтали, диагонали).
Таким образом, в такой простейшей игре как крестики-нолики с доской 3х3 нам вообще нет необходимости в пересмотре всех вариантов позиций, а также в использовании альфа-бета перебора. Мы выберем «активное использования логики» (см. ПУНКТ 2). Итак, рассчитаем лучший, например, второй полуход для «ноликов» в рамках функции BestZeroMove(). В массиве pos[] содержится текущая ситуация на доске.
int pos[9]={0,0,0,0,0,0,0,0,0}; //допустим, «крестики» //ходят так… pos[0]=-1; //находим лучший //полуход «ноликов» void BestZeroMove() { max[8]; int best_move; for (int i=0; i=8; i++) { max[i]=0; //делаем ход на пустую клетку if (pos[i]==0) best_move= i; //горизонтали if (i==0 || i==1|| i==2 && pos[0]>=0 && pos[1]>=0 && pos[2]>=0 ) max[i]++; if (i==3 || i==4|| i==5 && pos[3]>=0 && pos[4]>=0 && pos[5]>=0 ) max[i]++; if (i==6 || i==7|| i==8 && pos[6]>=0 && pos[7]>=0 && pos[8]>=0 ) max[i]++; //вертикали if (i==0 || i==3|| i==6 && pos[0]>=0 && pos[3]>=0 && pos[6]>=0 ) max[i]++; if (i==1 || i==4|| i==7 && pos[1]>=0 && pos[4]>=0 && pos[7]>=0 ) max[i]++; if (i==2 || i==5|| i==8 && pos[2]==0 && pos[5]==0 && pos[8]==0 ) max[i]++; //диагонали if (i==0 || i==4|| i==8 && pos[0]>=0 && pos[4]>=0 && pos[8]>=0 ) max[i]++; if (i==2 || i==4|| i==6 && pos[2]>=0 && pos[4]>=0 && pos[6]>=0 ) max[i]++; } for (int i=0; i=7; i++) { if (max[i+1]>max[i]) best_move= i+1; } pos[best_move]=1; }
Теперь объясним. Если на какой-либо вертикали, горизонтали или диагонали остальные клетки являются пустыми, либо, опережая будущие события, предусмотрим, что там расположены нолики (условие на >=0, именно поэтому мы и использовали 0, -1 и 1 — если вы будете писать такую функцию для крестиков, то идентичным условием станет <=0, 0 — пустота), то это дает прирост в максимальной оценке, которая содержится в массиве max[8].
В конце функции стоит пузырьковая сортировка, которая выделяет ход с максимальным значением из массива max[].
Вам показана «сырая заготовка», которая рассчитывает только второй полуход для ноликов. После этого нам нужно упаковывать алгоритм и распространить его действие для генерации всех полуходов. Это не сложно.
В следующей части материала мы попробуем применить метод графов с выделением всех возможных игровых ситуаций и заполнением таблицы.
Перепечатка материалов или их фрагментов возможна только с согласия автора.
|
