Популярно об ИИ/Lua для игр и не только

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

Формируем первое задание

Перед тем как приступить к написанию генератора кроссвордов, мы захватим менее сложный пример и в этом материале начнем создавать алгоритм преобразования слова «МУХА» в слово «СЛОН». Это стандартная детская головоломка, в рамках которой предлагается составить список промежуточных слов, в каждом из которых в отличие от предыдущего меняется только одна буква. Таким образом, создается некая взаимосвязанная цепочка. В данном случае мы рассмотрим основные методы, покажем наиболее оптимальный, параллельно захватим те области языка Lua, о которых еще не писалось.
Предварительная подготовка

Работать мы будем в программе Scite (бесплатно скачивается с http://scite.ruteam.ru), в ней уже имеется встроенный интерпретатор языка Lua версии 5.1. Дополнительно нам понадобится объемный словарь, включающий четырехбуквенные слова, который можно довольно быстро найти в Интернете, пройдясь по сайтам кроссвордистов. Я нашел один такой вариант на ресурсе http://chyjik.narod.ru, там он получился на чуть меньше чем 4000 слов. Перенес я его в обычный текстовый файл (XML мы делать не будем). Итак, поехали.

Чтение из файла

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

В текстовом файле, так получилось при копировании (Ctrl+C/Ctrl+V), что все четырехбуквенные слова стоят в начале строк, а через несколько пробелов идут их описания. Описания, в общем-то, нам тоже понадобятся, поэтому стоит задача построчного чтения с последующим разбиением строк. То есть структурно это подразумевает написание двух простых функций (если не объединять их в одну), одна из которых производит построчное чтение, вторая — разбивает данные и заносит в массив.

Итак, даю следующий фрагмент кода:

--создаем пустую
--таблицу

dtable = {}

--счетчик для нее
kdt=1

--функция заполнения
--массива словаря
function split_dict(str)
dtable[kdt]={}
local cap = str:sub(1, 4)
table.insert(dtable[kdt],cap)
cap = str:sub(6, -1)
table.insert(dtable[kdt], cap)
kdt=kdt+1
end

--читаем текстовый файл
for line in io.lines("E:\\dictionary.txt") do
split_dict(line)
end

Проверять все можно через команду print(), например, выведя весь словарь:
for i=1,kdt-1 do
print (dtable[i][1], dtable[i][2])
end

Вывод будет производиться с некоторой задержкой, но при этом стоит отметить, что она связана только с выводом, сама операция преобразования файлов в массив занимает очень мало времени (что опять же можно проверить строкой print(os.clock())).

Теперь небольшие пояснения к коду. Операция for line in io.lines(путь к файлу) do что-то там end является оптимальным вариантом автоматизации, в рамках которого открывается файл в режиме чтения, запускается цикл построчечного чтения, пока не встречается значение nil, после этого сам файл автоматически закрывается.

Функция split_dict получает на входе строку из текстового файла, автоматически создавая «второе измерение» для массива/таблицы dtable (строка dtable[kdt]={}), и заполняет две, если говорить образно, колонки, в одну вносит первые четыре символа строки, выделенные функцией str:sub(1, 4), во вторую (поскольку там несколько пробелов) с 6 символа до конца, что делается за счет функции str:sub(6, -1). Следует отметить, что если в качестве последнего символа указывается «-1», это обозначает конец строки.

Таким образом, мы быстро и оперативно заполнили наш массив. Двигаемся дальше.

Отображение уже загруженной таблицы с данными

Разбиение слов на буквы

Я рассматривал листинги некоторых программ (на Java, C++ и т.п.), и там нередко можно встретиться с тем, что сами слова не только разбиваются на символы, но и символы преобразуются в их кодовые значения ASCII. Целесообразность такового в плане Lua не совсем понятна, потому как слово «МУХА» всегда будет равно слову «МУХА», но не равно «МУЗА». Вопросы строчных/заглавных тоже можно решить быстрым конвертированием одних в другие и наоборот. То есть, единственное, что нам в данном случае нужно, — это просто разбиение слов на буквы.

Делаем мы его с помощью той же функции sub, но при этом создав двумерный массив/таблицу под названием result, и сделав для него отдельный счетчик. Все будет выглядеть так:

--таблица, содержащая
--результаты разбиения
--по буквам
result = {}

--ее счетчик
kr=-1

--функция разбиения
function split_word(str)
local bv
result[kr]={}
for i=1,4 do
bv=str:sub(i,i)
table.insert(result[kr], bv)
end
kr=kr+1
end

Теперь поясним. На входе функция split_word() получает слово, после чего открывает второе «измерение» таблицы/массива результатов и заносит в нее четыре новых элемента — буквы, из которых состоит входное слово. Коэффициент kr мы приняли равным единице неспроста, поскольку -1-м и 0-м элементами у нас будут исходное и заключительное слова головоломки.

Мы можем их и сразу внести, дописав снизу строки:

split_word(«МУХА»)
split_word(«СЛОН»)

Этап завершен, двигаемся дальше.

Результаты совпадения со словарем

Начало перебора

Итак, по правилам игры в слове при каждой итерации мы сможем изменять только одну букву. Соответственно, нам понадобятся отдельный массив из букв, а также функция сопоставления получившейся комбинации с теми, что есть в словаре. Иначе говоря, нам нужно вычленить только имеющие смысл слова. Делаем это так:

--задаем массив букв
--по алфавиту
alpha={"А","Б","В","Г","Д","Е","Е","Ж","З","И","Й","К","Л","М","Н","О","П","Р","С","Т","У","Ф","Х","Ц","Ч","Ш","Щ","Ы","Ь","Ъ","Э","Ю","Я"}
--массив уместных
--слов
slova = {}
--его счетчик
ksl=1

--функция сверки
--со словарем
function sootv_dict(str, str_ish)
for i=1,kdt-1 do
if dtable[i][1] == str and dtable[i][1]~=str_ish then
slova[ksl]= dtable[i][1]
ksl=ksl+1
print(dtable[i][1],dtable[i][2])
end
end
end

--функция добавления
--одного символа
function perebor()
for i=1,33 do
str_ish=result[-1][1]..result[-1][2]..result[-1][3]..result[-1][4]
str4 = alpha[i]..result[-1][2]..result[-1][3]..result[-1][4]
sootv_dict(str4,str_ish)
str4 = result[-1][1]..alpha[i]..result[-1][3]..result[-1][4]
sootv_dict(str4,str_ish)
str4 = result[-1][1]..result[-1][2]..alpha[i]..result[-1][4]
sootv_dict(str4,str_ish)
str4 = result[-1][1]..result[-1][2]..result[-1][3]..alpha[i]
sootv_dict(str4,str_ish)
end
end

perebor()
print(ksl-1)

Итак, в рамках функции perebor() мы, во-первых, сохраняем исходное слово, для того чтобы потом его исключить из вариантов, во-вторых, перебираем все варианты с изменением одного символа (буквы), совмещая символы с помощью операции конкатенации «..», после чего вызываем функцию сравнения со словарем. В ее рамках пока находится print(), распечатывающая все найденные варианты, также они заносятся в массив/таблицу slova.

Из слова МУХА у нас получилось 11:

. АУХА — Рыба семейства окуневых.
. МАХА — Один из видов полбы.
. МУЗА — Стихотворение А. Ахматовой.
. МУКА — 1) Пищевой продукт, полученный размолом зерна различных культур; основное сырье для хлебопекарного, макаронного и кондитерского производств. 2) Стихотворение русского поэта XIX века Кольцова.
. НУХА — Название города Шеки в Азербайджане до 1968 года.
. МУНА — Река в Якутии, левый приток Лены.
. МОХА — Город в Йемене, порт на Красном море.
. МУРА — Приток Ангары.
. МУСА — Исламский пророк.
. МУТА — Древнеримская нимфа, рассказавшая Юноне о любви Юпитера к Ютурне; за что Юпитер лишил ее дара речи.
. МУХУ — Остров в Балтийском море.

Дальше предлагаю подумать

Итак, мы сейчас создали весь необходимый базис для дальнейших действий. Предлагаю на данном этапе остановиться и подумать, каким образом мы будем искать ветку преобразования от «МУХА» к «СЛОН». Большинство начинающих студентов склонится к варианту полного перебора. Поэтому предлагаю вам попробовать реализовать все самостоятельным образом, а в продолжении материала опишу некоторые варианты решений. Естественно, блок перебора, отображенный сегодня, — это просто затравка.

Полный листинг предварительной программы

dtable = {}
kdt=1
result = {}
kr=-1
alpha={"А","Б","В","Г","Д","Е","Е","Ж","З","И","Й","К","Л","М","Н","О","П","Р","С","Т","У","Ф","Х","Ц","Ч","Ш","Щ","Ы","Ь","Ъ","Э","Ю","Я"} slova = {}
ksl=1

function split_dict(str)
--создаем второе измерение
dtable[kdt]={}
--вносим добавления
local cap = str:sub(1, 4)
table.insert(dtable[kdt],cap)
cap = str:sub(6, -1)
table.insert(dtable[kdt], cap)
kdt=kdt+1
end

--читаем текстовый файл
for line in io.lines("E:\\dictionary.txt") do
split_dict(line)
end

---------------------------------------------------------------

function split_word(str)
local bv
result[kr]={}
for i=1,4 do
bv=str:sub(i,i)
table.insert(result[kr], bv)
end
kr=kr+1
end

split_word("МУХА")
split_word("СЛОН")

--------------------------------------------------------------

function sootv_dict(str, str_ish)
for i=1,kdt-1 do
if dtable[i][1] == str and dtable[i][1]~=str_ish then
slova[ksl]= dtable[i][1]
ksl=ksl+1
print(dtable[i][1],dtable[i][2])
end
end
end

function perebor()
for i=1,33 do
str_ish=result[-1][1]..result[-1][2]..result[-1][3]..result[-1][4]
str4 = alpha[i]..result[-1][2]..result[-1][3]..result[-1][4]
sootv_dict(str4,str_ish)
str4 = result[-1][1]..alpha[i]..result[-1][3]..result[-1][4]
sootv_dict(str4,str_ish)
str4 = result[-1][1]..result[-1][2]..alpha[i]..result[-1][4]
sootv_dict(str4,str_ish)
str4 = result[-1][1]..result[-1][2]..result[-1][3]..alpha[i]
sootv_dict(str4,str_ish)
end
end

perebor()
print(ksl-1)

Кристофер http://itcs.3dn.ru