Популярно об ИИ

Продолжаем рассматривать три ключевых пункта разработчика ИИ, которые описывают основные подходы к его созданию. Напомним, что это решения:

1. С помощью поиска наиболее выгодного хода (alpha-beta-перебор) с расчетом на определенную глубину и выделением наиболее выгодных ветвей поиска с продлением расчетов.
2. C активным использованием логики, опираясь на специфику задачи.
3. С помощью графа (использование хеш-таблиц, шаблонов).
Первые два пункта мы рассмотрели в прошлой части, сегодня нам предстоит самое веселое — третий. Причем мы уже договорились, что наиболее оптимальное решение найдено, для крестиков-ноликов — это применение логики. Но на базе крестиков-ноликов очень удобно показывать особенности той или иной технологии. Приступим…

Intro…

Суперкубок по крестикам-ноликам! Смотрим на развитие игры (-1 — крестик, 1 — нолик, 0 — пустая клетка):
(-1, 0, 0, 0, 0, 0, 0, 0, 0)
(-1, 0, 0, 0, 0, 0, 0, 0, 1)
(-1, -1, 0, 0, 0, 0, 0, 0, 1)
…

Использование графов

Давайте внимательно присмотримся к строке с третьим полуходом нашего примера, а именно (-1,-1,0,0,0,0,0,0,1). Из такой записи можно понять, куда первыми походили «крестики»? Нет. Можем ли попробовать графы? Теоретически, конечно! Ведь комбинацию (-1,-1,0,0,0,0,0,0,1) можно представить и как позицию, и как описание состояния. Изначально мы получаем 19683 всех возможных комбинаций, что соответствует 3-м в девятой степени (сравнимо с девятью разрядами троичной системы). У нас, по существу, есть девять элементов массива, каждый из которых может принимать только одно из трех значений (0, -1 или 1). 19683 — гораздо меньше 362880 (цифра, с которой мы сталкивались, описывая полный перебор, см. прошлый материал). Это количество можно еще уменьшить, исключив варианты, в которых количество «-1» больше пяти, а «1» — больше четырех, а также число «-1» больше или меньше «1» на два и более (крестики или нолики не могут ходить несколько раз подряд). На самом деле выгоднее поставить условие, что количество «1» должно быть равно количеству «-1» или быть меньше на один. Делается это просто, достаточно суммировать все элементы массива, и сумма должна быть равна либо 0, либо -1, все другие варианты — отметаем. Этим удобен вариант указания в -1, 0, 1.

В общем, при желании вы можете сократить таблицу весьма существенно.

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

Пример с нахождением всех возможных вариантов

Итак, у нас есть массив, который содержит 19683 комбинации из девяти чисел со значениями: -1, 0 или 1. Каким образом можно найти все комбинации?
Пример одного из методов мы покажем на С-подобном Lua, алгоритмическая начинка легко переводится в любой другой язык. Хотя… три значения на девяти позициях… можно сделать проще, но далеко не все высокоуровневые языки позволяют эффективно работать с троичной системой счисления, к тому же она несколько неудобна. Поэтому возьмем что-нибудь из стандартных методов. Для работы с языком рекомендуется скачать SciTE ( http://scite.ruteam.ru , бесплатна, 1,4 Мб).

Также отметим специфику Lua, а именно: комментарии обозначаются «--», в конце операторов (в том числе if) должно быть слово end, операторы «;» не используются, вместо них достаточно пробела или перехода на следующую строку, вместо «&&» используется слово «and». Также в Lua нет такого конкретного типа данных, как массив, а вместо него используются структуры типа таблиц (table). Отсчет начинается не с нуля, как в большинстве языков программирования, а с 1. Переменным присваиваются данные динамически, то есть автоматизированное приведение типов. О Lua мы подробно писали в серии материалов «Lua для игр, и не только».

Для простоты понимания сначала напишем код для случая, когда у нас всего три клетки, а не девять. Таким образом, общее количество комбинаций равно 3 в третьей степени, то есть 27. По существу, у нас будет двумерный массив 27х3.

Программа:
--текущая позиция
n=1
-- создаем двумерный
-- массив 27х3
a={}
for i=1,27,1 do
a[i]={}
end
--специфика Lua--
--размер второго измерения
--можно не указывать
-------
--вводим диапазон
-- используемых значений
z={}
z[1]=-1
z[2]=0
z[3]=1
-----------
-----------
--основной цикл
while (n<28) do
--переменная-флаг
pp=false
-- промежуточный массив
-- подбираем случайную
-- комбинацию
b={z[math.random(3)],z[math.random(3)],z[math.random(3)]}
-- сравнение с имеющимися
for i=1,n-1,1 do
if a[i][1]==b[1]
and a[i][2]==b[2]
and a[i][3]==b[3]
then pp=true
end --end if
end --end for
--если совпадение
--не найдено, то...
if pp==false then
a[n]={b[1],b[2],b[3]}
--вывод результатов
print (n, "-я позиция ", a[n][1],a[n][2],a[n][3])
n=n+1
end --end if
--конец основного цикла
end

Разобраться в представленном коде не сложно, причем он намеренно показан в неоптимизированном виде, чтобы его могли понять даже школьники. Только, опять же, специфика Lua: элементы массива могут задаваться в фигурных скобках, что видно в строках b={z[math.random(3)],z[math.random(3)],z[math.random(3)]} и a[n]={b[1],b[2],b[3]}. Индексы могут задаваться как явно, так и нет, то есть если они не указаны, то присваивание идет по порядку, начиная от первого элемента.

Как работает код? n — это текущая позиция в нашем массиве, и изначально мы будем стартовать с первого элемента. Сам массив (таблица) формируется весьма просто, если бы он был одномерный, то мы бы обошлись строкой a={}, но в двумерном варианте такое поведение будет действенным для второго измерения, а первое мы указываем явно, то есть, сколько должно быть элементов.

В массиве z хранятся наши три значения -1, 1 и 0.

При первом прохождении цикла в случайном режиме формируется первая тройка значений, которая сохраняется во временном массиве b. После этого идет сравнение с наполнением уже сохраненных комбинаций, коих пока нет (обратите внимание на то, что цикл сравнения работает от 1 до n-1). Если совпадение не найдено, то элементу a[n] присваивается тройка значений b. Далее, n=n+1, после чего идет следующий виток цикла. Функция print отображает все полученные комбинации — элементы. Причем мы априори знаем, что будет всего 27 вариантов, это число и указываем. При желании можете проверить правильность, заменив while (n<28) на while (n<29) — появится сообщение об ошибке.

***

В нашем примере представлен вариант с циклом, использование рекурсии в данном случае ничем себя не оправдывает, а по мере роста количества обрабатываемых данных только ухудшит положение (если вы не будете делать оптимизацию рекурсии, о чем говорилось в одном из недавнишних материалов серии «Популярно об ИИ»).
На самом деле, создавая массив 19683х9, вы столкнетесь с громоздкостью и в рамках использования цикла. Почему и какие самые слабые стороны алгоритма? На самом деле они себя проявят. В первую очередь — это частое использование random и система сравнения. Чуть менее ресурсоемкой окажется функция print, она оказывает влияние в силу того, что использует автоматическое приведение типов.

Разделяй и властвуй

В итоге, воспользовавшись данным кодом как руководством к действию и применив его к более объемным вычислениям, вы получите громоздкую модель. Считаться для комбинаций из 9 чисел все будет очень медленно. Но напомню, что мы создаем базу шаблонов, это делается единожды, а потом при внесении определенных дополнительных данных к этой таблице мы будем работать уже только с нею. И пока нам нужно найти все возможные варианты комбинаций, коих 19683.
При запуске программы, созданной по нашему шаблону, но постоянно приращивая количество элементов в комбинациях, вы можете заметить, что все варианты для комбинаций из 5 или 6 чисел считаются довольно легко. На семи, восьми и девяти компьютер начинает подтормаживать. ОК. Все решается просто. Мы можем разделить все на две отдельные части. И лучше это сделать даже вручную. Как? Показано на листинге во врезке.
То есть, цикл считает только 729 комбинаций для 6 последних элементов, а 27 для трех первых мы указываем вручную. После этого с помощью функции add сочленяем эти части. Скорость расчетов значительно повысится.

Зерна от плевел…

Как мы уже упомянули, далеко не все комбинации являются игровыми, поэтому мы отделяем то, что нам понадобится, по двум условиям:
. По горизонталям, вертикалям и диагоналям не должно быть одинаковых элементов, если это не нули. Тут понятно — победы не считаются игровыми ситуациями.
. Сумма всех элементов должна быть равна 0 или -1.
В результате отчленения мы получили 4277 игровых ситуаций.

Последующая обработка

После можно к таблице добавить еще одно поле, в котором будет указываться рекомендуемый ход, что можно сделать как автоматизировано, так и вручную для отдельных ситуаций. Причем ход либо указывается явно, либо дается индексный номер следующей позиции из таблицы.
Игровой процесс по такой схеме будет происходить следующим образом: игрок сделал полуход, текущая позиция ищется в таблице, после чего компьютер ходит, пользуясь соответствующим руководством. То есть он практически не думает. Это сравнимо с образно-ассоциативным мышлением человека:))). В смысле того, что у нас очень многое построено на ассоциациях и многое в поведении предсказуемо.

Код программы (Lua), находящей все играбельные комбинации в крестики-нолики

--текущая позиция
n=1
-- задаем основной
-- массив
a={}
-- создаем двумерный
-- массив
a={}
for i=1,19683,1 do
a[i]={}
end
--вводим диапазон
-- используемых значений
z={}
z[1]=-1
z[2]=0
z[3]=1
-----------
-----------
--основной цикл
--который рассчитывает
--последние шесть элементов
-- т.е. 729 комбинаций
while (n<730) do
--переменная-флаг
pp=false
--промежуточный массив
-- подбираем случайную
-- комбинацию
b2={z[math.random(3)],z[math.random(3)], z[math.random(3)], z[math.random(3)], z[math.random(3)], z[math.random(3)]}
-- сравнение с имеющимися
for i=1,n-1,1 do
if a[i][4]==b2[1]
and a[i][5]==b2[2]
and a[i][6]==b2[3]
and a[i][7]==b2[4]
and a[i][8]==b2[5]
and a[i][9]==b2[6]
then pp=true end --end if
end --end for
--если совпадение
--не найдено, то...
if pp==false then
a[n]={0, 0, 0, b2[1],b2[2],b2[3],b2[4],b2[5],b2[6]}
n=n+1
end --end if
--конец основного цикла
end

--функция сочленения двух
--частей массива

function add(a1,a2,a3,u)
for n=1,729,1 do
a[n+729*u]={a1,a2,a3, a[n][4],a[n][5],a[n][6],a[n][7],a[n][8],a[n][9]}
end
end

---мы указываем только три первых
---значения и коэффициент умножения
---для индексов
add(0, 0, -1, 1)
add(0, -1, 0, 2)
add(-1, 0, 0, 3)
add( 0, -1, -1, 4)
add(-1, -1, 0, 5)
add(-1, 0, -1, 6)
add(-1, -1, -1, 7)
add(0, 0, 1, 8)
add(0, 1, 0, 9)
add(1, 0, 0, 10)
add(0, 1, 1, 11)
add(1, 1, 0, 12)
add(1, 0, 1, 13)
add(1, 1, 1, 14)
add(-1, -1, 1, 15)
add(-1, 1, -1, 16)
add(1, -1, -1, 17)
add(-1, 1, 1, 18)
add(1, 1, -1, 19)
add(1, -1, 1, 20)
add(0, 1, -1, 21)
add(0, -1, 1, 22)
add(1, 0, -1, 23)
add(1, -1, 0, 24)
add(-1, 1, 0, 25)
add(-1, 0, 1, 26)

---все! массив a[19683][9] заполнен
------------
---отделяем игровые ситуации
ss=0
sum=0
---окончательный массив
--включающий все играбельные
--комбинации
supa_array={}
for i=1,19683,1 do
if a[i][1]==a[i][2] and a[i][1]==a[i][3] then sum=10
elseif a[i][4]==a[i][5] and a[i][4]==a[i][6] and a[i][4]~=0 then sum=10
elseif a[i][7]==a[i][8] and a[i][7]==a[i][9] and a[i][7]~=0 then sum=10
elseif a[i][1]==a[i][4] and a[i][1]==a[i][7] and a[i][1]~=0 then sum=10
elseif a[i][2]==a[i][5] and a[i][2]==a[i][8] and a[i][2]~=0 then sum=10
elseif a[i][3]==a[i][6] and a[i][3]==a[i][9] and a[i][3]~=0 then sum=10
elseif a[i][1]==a[i][5] and a[i][1]==a[i][9] and a[i][1]~=0 then sum=10
elseif a[i][3]==a[i][5] and a[i][3]==a[i][7] and a[i][3]~=0 then sum=10
else sum=a[i][1]+a[i][2]+a[i][3]+a[i][4]+a[i][5]+a[i][6]+a[i][7]+a[i][8]+a[i][9] end
if sum==0 or sum==-1 then
ss=ss+1
supa_array[ss]={a[i][1],a[i][2],a[i][3],a[i][4],a[i][5],a[i][6],a[i][7],a[i][8],a[i][9]}
print(ss, "-й найденный", a[i][1],a[i][2],a[i][3],a[i][4],a[i][5],a[i][6],a[i][7],a[i][8],a[i][9])
end
sum=0
end
---результат -- 4277 комбинаций

Кристофер christopher@tut.by