Lua для игр и не только. Часть 6
Итак, сегодня у нас практическое занятие, потому как от формальных выкладок пользы на самом деле мало. Мы будем решать задачу с восемью ферзями, которые нужно расположить на шахматной доске таким образом, чтобы ни один из них не оказался под атакой другого. Напомним, что все у нас практически бесплатно, то есть пользуемся программой SciTE ( сайт , 1,2 Мб), язык Lua изучаем пока в автономном виде, то есть без привязки к какому-нибудь внешнему API.
Нужно сказать, что данная задача является классикой в программировании, особенно искусственного интеллекта. Мы о ней писали в серии «Популярно об ИИ», причем дали ее большей частью на самостоятельное освоение. Что интересно, те результаты, которые были тогда присланы, как бы это сказать… Нужно разместить восемь ферзей, не пять, не четыре, а восемь! А большинство ограничилось стандартным ограниченным перебором с не до конца доведенными методами получения правильных результатов. Восемь так никто и не расставил.
Задача с восемью ферзями имеет продолжение в реале. Например, в шахматах нужно определить, находится ли та или иная клетка под боем, в некоторых приложениях с иерархией элементы какого-либо одного типа нужно рассортировать так, чтобы не было явных пересечений и так далее.
Мы можем решить эту задачу несколькими способами, которые выражены, как это часто бывает, в обычном программировании и программировании с помощью рекурсивных функций (функций, которые вызывают сами себя). Последние часто недолюбливают программисты, потому как, во-первых, использование рекурсии требует специального понимания и навыков, а, во-вторых, рекурсия — это непосредственная работа со стеком, который может и переполниться. В некоторых языках на размер стека даже существуют ограничения. Хотя его переполнение часто бывает и при обычном программировании.
Впрочем, напомним основное правило, о котором мы уже писали: «Любая задача, которая решается с помощью рекурсии, может быть решена и без нее обычными методами». Но в ряде случаев рекурсия очень выгодна в силу минимизации кода, иначе он раздувается без всякой ощутимой пользы. То есть в некоторых случаях без рекурсии не обойтись.
Постановка задачи
Итак, шахматная доска имеет размеры 8х8, ферзь может атаковать по вертикали, горизонтали и диагоналям. За основу возьмем координатную систему, то есть X (от 1 до 8) — это горизонталь, Y (от 1 до 8) — вертикаль. Как быть с диагоналями? Достаточно просто. Если смотреть на восходящую (/), то можно отметить, что у нее будет неизменным значением являться разность X-Y, если на нисходящую (\), то будет постоянным значение суммы X+Y. Выводим базовые постулаты.
Ферзь оказывается под атакой другого, если:
. его координата Х соответствует X другого ферзя;
. его координата Y соответствует Y другого ферзя;
. сумма X+Y равна X+Y другого ферзя;
. разность X-Y равна X-Y другого ферзя.
При этом мы понимаем, что ферзи будут находиться каждый на одной из восьми вертикалей и на одной из восьми горизонталей.
О деревьях
Я помню, как один начинающий читал требования к программисту по ИИ для игр в разделе вакансий, где встретилось слово «деревья». Он произнес сакраментальную вещь: «А что там программировать деревья? Стоят, колышутся, или нужно запрограммировать движение каждого листика?». М-да. В советские времена под украинскими карикатурами писали просто: «Без слiв».
Итак, о том, что колышется. Точкой входа в дерево у нас будет установка первого ферзя. Второй ставится с учетом тех ограничений, которые задал последний, а именно исключил свою вертикаль, горизонталь и диагонали. Третий устанавливается с учетом ограничений двух предыдущих и так далее. Как мы построим поиск? Как многие помнят, в «Популярно об ИИ» мы обсуждали несколько вариантов алгоритмических структур поиска, основные из которых — в ширину и в глубину с помощью рекурсии. Мы будем делать смешанный метод, но при этом не использовать рекурсию. Наша задача — наиболее оптимально найти требуемый результат. И, например, нет необходимости в переборе всех возможных вариантов, достаточно получить одно правильное решение (их на самом деле достаточно много).
Обычный метод
Итак, нам понадобится таблица, которая будет подразумевать двумерный массив, имитирующий шахматную доску. За каждой клеткой мы закрепим только одно свойство и для простоты возьмем булевый тип. То есть, если клетка не находится под атакой, то она будет как true, если находится или на ней стоит ферзь — false.
В рамках приведенного впоследствии описания мы отобразим неоптимизированный код и избежим всяческих expression-oriented выражений. Для чего? Чтобы вы поняли саму суть написанного, а не разбирались с каждой закорючкой.
Предварительная подготовка
Таблица — гибкая структура. Но назначить ей функциональность двумерного массива одной строкой не получится. В принципе, таблицу лучше представлять как дерево. Потому как просто таблица — одномерный массив, но каждый ее элемент может включать в себя другую таблицу и так далее. Итак, запускаем SciTE, создаем новый файл, называем его, к примеру: 8Queens.lua.
В первых строках записываем:
a={}
k=1
for i=1,8,1 do
a[i]={}
end
Итак, мы объявили таблицу a. После этого запустили цикл, в рамках которого указали, что первые восемь элементов таблицы тоже являются таблицами. Другими словами, мы создали одномерный массив а, каждый из восьми элементов которого также является одномерным массивом. По существу, строкой a[i]={} мы открываем второе измерение. То есть после него можно без проблем писать a[1][2] и так далее, что нам и необходимо.
Многих приверженцев других языков испугает тот факт, что начали отсчет мы не с нуля. В этом мы сохраняем верность Lua, потому как таблицы в нем начинаются с первого элемента, а не нулевого, хотя это условно, можно начать и с -1000-го и любого другого.
Что такое k? Это будет нашим счетчиком количества установленных ферзей. Поскольку первый ход (установка первого ферзя) у нас будет
запрограммирован отдельно, то k=1, а счетчик включается потом. Почему отдельно?
Установка первого ферзя
Многие спросят, а где мы обозначили все поля как true? Делать это отдельно не с руки. Итак, устанавливаем первого ферзя, вернее, пишем функцию для реализации первого хода:
function first(b)
a[1][b]=false
print(1,b)
for i=1,8,1 do
for j=1,8,1 do
a[i][j]=true
a[1][j]=false
a[i][b]=false
if i+j==1+b then a[i][j]=false end
if i-j==1-b then a[i][j]=false end
end
end
end
Вспоминаем, что мы написали при постановке задачи: каждый ферзь будет находиться на одной из восьми вертикалей и на одной из восьми горизонталей. Ну что же, если под первым индексом мы будем воспринимать вертикаль, то понятно, что один из ферзей точно будет на ней. То есть в качестве аргумента в данную функцию мы будем засылать только данные горизонтали (от 1 до 8).
Установка первого ферзя ассоциируется с изначальными установками, а именно очисткой пространства (то есть указание всех полей в true), а потом указанием ограничений, накладываемых первым ходом (атакуемые диагонали, вертикаль и горизонталь — все эти клетки становятся false, клетка, где стоит первый ферзь — также false).
Все это вы можете наглядно увидеть в коде.
Калькуляция установки следующих ферзей
Итак, мы уже имеем совокупность полей, разграниченных на true и false. Новый ферзь может быть установлен только на клетку true, которая сразу же становится false, после чего производятся расчеты, подобные предыдущему пункту:
function fcalc(n,m)
if a[n][m]==true then
a[n][m]=false
print(n,m)
k=k+1
for i=1,8,1 do
for j=1,8,1 do
a[n][j]=false
a[i][m]=false
if i+j==n+m then a[i][j]=false end
if i-j==n-m then a[i][j]=false end
end
end
end
end
Здесь мы уже получаем некоторый вариант перебора, рассчитывающий ситуацию до конца.
И вот…
Пишем основную функцию:
function fmain(z)
for g=1,8,1 do
b[1]={1,g}
first(g)
for i=2,8,1 do
for j=1,8,1 do
fcalc(i,z)
fcalc(i,j)
end
end
if k==8 then
print("кол-во ферзей", k, " расстановка:", b[1][1], b[1][2], ".." , b[2][1], b[2][2], "..", b[3][1], b[3][2], "..", b[4][1], b[4][2], "..", b[5][1], b[5][2], "..", b[6][1], b[6][2], "..", b[7][1], b[7][2], "..", b[8][1], b[8][2])
end
k=1
end
end
for z=1,8,1 do
fmain(z)
end
Итак, здесь мы еще не оптимизировали вариант, то есть программу нужно прекратить как только появится первый ответ с k=8, мало того, в функции fcalc нужно поставить условие, что если k становится меньшим текущего значения i в цикле, то расчеты следует прекратить.
После идет дальнейшая оптимизация кода, что вы можете сделать самостоятельно, потому как здесь все уже понятно.
Без введенных ограничений программа выведет четыре найденных варианта.
кол-во ферзей 8 расстановка: 1 7 .. 2 2 .. 3 4 .. 4 1 .. 5 8 .. 6 5 .. 7 3 .. 8 6
кол-во ферзей 8 расстановка: 1 6 .. 2 4 .. 3 1 .. 4 5 .. 5 8 .. 6 2 .. 7 7 .. 8 3
кол-во ферзей 8 расстановка: 1 6 .. 2 1 .. 3 5 .. 4 2 .. 5 8 .. 6 3 .. 7 7 .. 8 4
кол-во ферзей 8 расстановка: 1 4 .. 2 8 .. 3 1 .. 4 3 .. 5 6 .. 6 2 .. 7 7 .. 8 5
В реальных условиях для оценки алгоритмов вам понадобится добавление счетчика проделываемых операций. Чуть менее эффективно использование строки: print(os.clock()), эта функция возвращает примерное количество времени в секундах, потраченное CPU на выполнение программы.
Порции и блоки
Теперь поговорим о некоторых ключевых понятиях. Порцией (chunks) в Lua называется любая последовательность Lua-операторов, и она воспринимается как единица исполнения Lua. Другими словами, исполняемая часть программы. Например, если из C/C++/C#/Java API будет вызываться написанная нами Lua-программа, то весь исполняемый код является порцией.
Порция может быть записана в файл или в строку в Lua-программе. Каждая порция воспринимается Lua как тело анонимной (неименованной) функции с произвольным набором параметров. Следовательно, порция может определять локальные переменные и возвращать значения.
В момент запуска порции на выполнение осуществляется компиляция ее в промежуточный байт-код (инструкции для виртуальной машины). Затем полученный код исполняется виртуальной машиной. Также порции могут быть компилированы в бинарный вид, при этом текстовые файлы с кодом и двоичные прекомпилированные части кода равноправны.
Блоки (block) также являются списками операторов и синтаксически они тождественно идентичны порциям. Но для того, чтобы понять разницу, можно указать и так, что блок может быть явно разграничен и включаться в рамки составного оператора: do block end. С помощью составных операторов можно ограничивать области видимости локальных переменных. В составные операторы могут быть добавлены директивы return или break для выхода из середины блока. Другими словами, блок может быть «телом» цикла, функции и так далее, либо просто ограничиваться do и end, и содержать внутри много кода с возможностью использования локальных переменных и директив return или break.
Знание этих фактов позволяет достаточно легко хотя бы на таком уровне управлять ресурсами, то есть те же локальные переменные будут иметь место только в рамках очерченных do и end.
Продолжение следует…
Кристофер christopher@tut.by
Задача с восемью ферзями имеет продолжение в реале. Например, в шахматах нужно определить, находится ли та или иная клетка под боем, в некоторых приложениях с иерархией элементы какого-либо одного типа нужно рассортировать так, чтобы не было явных пересечений и так далее.
Мы можем решить эту задачу несколькими способами, которые выражены, как это часто бывает, в обычном программировании и программировании с помощью рекурсивных функций (функций, которые вызывают сами себя). Последние часто недолюбливают программисты, потому как, во-первых, использование рекурсии требует специального понимания и навыков, а, во-вторых, рекурсия — это непосредственная работа со стеком, который может и переполниться. В некоторых языках на размер стека даже существуют ограничения. Хотя его переполнение часто бывает и при обычном программировании.
Впрочем, напомним основное правило, о котором мы уже писали: «Любая задача, которая решается с помощью рекурсии, может быть решена и без нее обычными методами». Но в ряде случаев рекурсия очень выгодна в силу минимизации кода, иначе он раздувается без всякой ощутимой пользы. То есть в некоторых случаях без рекурсии не обойтись.
Постановка задачи
Итак, шахматная доска имеет размеры 8х8, ферзь может атаковать по вертикали, горизонтали и диагоналям. За основу возьмем координатную систему, то есть X (от 1 до 8) — это горизонталь, Y (от 1 до 8) — вертикаль. Как быть с диагоналями? Достаточно просто. Если смотреть на восходящую (/), то можно отметить, что у нее будет неизменным значением являться разность X-Y, если на нисходящую (\), то будет постоянным значение суммы X+Y. Выводим базовые постулаты.
Ферзь оказывается под атакой другого, если:
. его координата Х соответствует X другого ферзя;
. его координата Y соответствует Y другого ферзя;
. сумма X+Y равна X+Y другого ферзя;
. разность X-Y равна X-Y другого ферзя.
При этом мы понимаем, что ферзи будут находиться каждый на одной из восьми вертикалей и на одной из восьми горизонталей.
О деревьях
Я помню, как один начинающий читал требования к программисту по ИИ для игр в разделе вакансий, где встретилось слово «деревья». Он произнес сакраментальную вещь: «А что там программировать деревья? Стоят, колышутся, или нужно запрограммировать движение каждого листика?». М-да. В советские времена под украинскими карикатурами писали просто: «Без слiв».
Итак, о том, что колышется. Точкой входа в дерево у нас будет установка первого ферзя. Второй ставится с учетом тех ограничений, которые задал последний, а именно исключил свою вертикаль, горизонталь и диагонали. Третий устанавливается с учетом ограничений двух предыдущих и так далее. Как мы построим поиск? Как многие помнят, в «Популярно об ИИ» мы обсуждали несколько вариантов алгоритмических структур поиска, основные из которых — в ширину и в глубину с помощью рекурсии. Мы будем делать смешанный метод, но при этом не использовать рекурсию. Наша задача — наиболее оптимально найти требуемый результат. И, например, нет необходимости в переборе всех возможных вариантов, достаточно получить одно правильное решение (их на самом деле достаточно много).
Обычный метод
Итак, нам понадобится таблица, которая будет подразумевать двумерный массив, имитирующий шахматную доску. За каждой клеткой мы закрепим только одно свойство и для простоты возьмем булевый тип. То есть, если клетка не находится под атакой, то она будет как true, если находится или на ней стоит ферзь — false.
В рамках приведенного впоследствии описания мы отобразим неоптимизированный код и избежим всяческих expression-oriented выражений. Для чего? Чтобы вы поняли саму суть написанного, а не разбирались с каждой закорючкой.
Предварительная подготовка
Таблица — гибкая структура. Но назначить ей функциональность двумерного массива одной строкой не получится. В принципе, таблицу лучше представлять как дерево. Потому как просто таблица — одномерный массив, но каждый ее элемент может включать в себя другую таблицу и так далее. Итак, запускаем SciTE, создаем новый файл, называем его, к примеру: 8Queens.lua.
В первых строках записываем:
a={}
k=1
for i=1,8,1 do
a[i]={}
end
Итак, мы объявили таблицу a. После этого запустили цикл, в рамках которого указали, что первые восемь элементов таблицы тоже являются таблицами. Другими словами, мы создали одномерный массив а, каждый из восьми элементов которого также является одномерным массивом. По существу, строкой a[i]={} мы открываем второе измерение. То есть после него можно без проблем писать a[1][2] и так далее, что нам и необходимо.
Многих приверженцев других языков испугает тот факт, что начали отсчет мы не с нуля. В этом мы сохраняем верность Lua, потому как таблицы в нем начинаются с первого элемента, а не нулевого, хотя это условно, можно начать и с -1000-го и любого другого.
Что такое k? Это будет нашим счетчиком количества установленных ферзей. Поскольку первый ход (установка первого ферзя) у нас будет
запрограммирован отдельно, то k=1, а счетчик включается потом. Почему отдельно?
Установка первого ферзя
Многие спросят, а где мы обозначили все поля как true? Делать это отдельно не с руки. Итак, устанавливаем первого ферзя, вернее, пишем функцию для реализации первого хода:
function first(b)
a[1][b]=false
print(1,b)
for i=1,8,1 do
for j=1,8,1 do
a[i][j]=true
a[1][j]=false
a[i][b]=false
if i+j==1+b then a[i][j]=false end
if i-j==1-b then a[i][j]=false end
end
end
end
Вспоминаем, что мы написали при постановке задачи: каждый ферзь будет находиться на одной из восьми вертикалей и на одной из восьми горизонталей. Ну что же, если под первым индексом мы будем воспринимать вертикаль, то понятно, что один из ферзей точно будет на ней. То есть в качестве аргумента в данную функцию мы будем засылать только данные горизонтали (от 1 до 8).
Установка первого ферзя ассоциируется с изначальными установками, а именно очисткой пространства (то есть указание всех полей в true), а потом указанием ограничений, накладываемых первым ходом (атакуемые диагонали, вертикаль и горизонталь — все эти клетки становятся false, клетка, где стоит первый ферзь — также false).
Все это вы можете наглядно увидеть в коде.
Калькуляция установки следующих ферзей
Итак, мы уже имеем совокупность полей, разграниченных на true и false. Новый ферзь может быть установлен только на клетку true, которая сразу же становится false, после чего производятся расчеты, подобные предыдущему пункту:
function fcalc(n,m)
if a[n][m]==true then
a[n][m]=false
print(n,m)
k=k+1
for i=1,8,1 do
for j=1,8,1 do
a[n][j]=false
a[i][m]=false
if i+j==n+m then a[i][j]=false end
if i-j==n-m then a[i][j]=false end
end
end
end
end
Здесь мы уже получаем некоторый вариант перебора, рассчитывающий ситуацию до конца.
И вот…
Пишем основную функцию:
function fmain(z)
for g=1,8,1 do
b[1]={1,g}
first(g)
for i=2,8,1 do
for j=1,8,1 do
fcalc(i,z)
fcalc(i,j)
end
end
if k==8 then
print("кол-во ферзей", k, " расстановка:", b[1][1], b[1][2], ".." , b[2][1], b[2][2], "..", b[3][1], b[3][2], "..", b[4][1], b[4][2], "..", b[5][1], b[5][2], "..", b[6][1], b[6][2], "..", b[7][1], b[7][2], "..", b[8][1], b[8][2])
end
k=1
end
end
for z=1,8,1 do
fmain(z)
end
Итак, здесь мы еще не оптимизировали вариант, то есть программу нужно прекратить как только появится первый ответ с k=8, мало того, в функции fcalc нужно поставить условие, что если k становится меньшим текущего значения i в цикле, то расчеты следует прекратить.
После идет дальнейшая оптимизация кода, что вы можете сделать самостоятельно, потому как здесь все уже понятно.
Без введенных ограничений программа выведет четыре найденных варианта.
кол-во ферзей 8 расстановка: 1 7 .. 2 2 .. 3 4 .. 4 1 .. 5 8 .. 6 5 .. 7 3 .. 8 6
кол-во ферзей 8 расстановка: 1 6 .. 2 4 .. 3 1 .. 4 5 .. 5 8 .. 6 2 .. 7 7 .. 8 3
кол-во ферзей 8 расстановка: 1 6 .. 2 1 .. 3 5 .. 4 2 .. 5 8 .. 6 3 .. 7 7 .. 8 4
кол-во ферзей 8 расстановка: 1 4 .. 2 8 .. 3 1 .. 4 3 .. 5 6 .. 6 2 .. 7 7 .. 8 5
В реальных условиях для оценки алгоритмов вам понадобится добавление счетчика проделываемых операций. Чуть менее эффективно использование строки: print(os.clock()), эта функция возвращает примерное количество времени в секундах, потраченное CPU на выполнение программы.
Порции и блоки
Теперь поговорим о некоторых ключевых понятиях. Порцией (chunks) в Lua называется любая последовательность Lua-операторов, и она воспринимается как единица исполнения Lua. Другими словами, исполняемая часть программы. Например, если из C/C++/C#/Java API будет вызываться написанная нами Lua-программа, то весь исполняемый код является порцией.
Порция может быть записана в файл или в строку в Lua-программе. Каждая порция воспринимается Lua как тело анонимной (неименованной) функции с произвольным набором параметров. Следовательно, порция может определять локальные переменные и возвращать значения.
В момент запуска порции на выполнение осуществляется компиляция ее в промежуточный байт-код (инструкции для виртуальной машины). Затем полученный код исполняется виртуальной машиной. Также порции могут быть компилированы в бинарный вид, при этом текстовые файлы с кодом и двоичные прекомпилированные части кода равноправны.
Блоки (block) также являются списками операторов и синтаксически они тождественно идентичны порциям. Но для того, чтобы понять разницу, можно указать и так, что блок может быть явно разграничен и включаться в рамки составного оператора: do block end. С помощью составных операторов можно ограничивать области видимости локальных переменных. В составные операторы могут быть добавлены директивы return или break для выхода из середины блока. Другими словами, блок может быть «телом» цикла, функции и так далее, либо просто ограничиваться do и end, и содержать внутри много кода с возможностью использования локальных переменных и директив return или break.
Знание этих фактов позволяет достаточно легко хотя бы на таком уровне управлять ресурсами, то есть те же локальные переменные будут иметь место только в рамках очерченных do и end.
Продолжение следует…
Кристофер christopher@tut.by
Компьютерная газета. Статья была опубликована в номере 21 за 2009 год в рубрике программирование
