Цель этой статьи — пробудить интерес читателей к удивительному миру и показать различные способы решения таких же интересных головоломок, как «Пятнашки». Создайте свою базу данных с шаблонами и начните решать головоломки менее чем за 50 миллисекунд. Материалом делимся к старту курса по разработке на C#.
Искусственный интеллект связан с процессом разработки неживого рационального агента. Рациональный агент — это сущность, способная воспринимать окружение и, исходя из полученных представлений, действовать рационально. Под рациональностью здесь понимается принятие агентом оптимальных решений для достижения наилучшего ожидаемого результата.
Люди — лучший пример живых рациональных агентов, постоянно получающих информацию из своего окружения и реагирующих на неё принятием решений, которые обычно идут на пользу.
Человеческий интеллект остаётся самым способным, сложным, совершенным в известной нам части Вселенной. А если это так и в ближайшем будущем вряд ли что-либо сравнится с ним по мощи, которой он сегодня обладает, то зачем создавать ИИ?
В некоторых специфических условиях реакция на поступающую из окружения информацию у ИИ лучше, чем у людей. ИИ способен за короткое время вычислять миллионы инструкций и выдавать осуществимое, а иногда оптимальное решение очень сложных задач.
Поэтому, хотя у людей в плане мышления интеллект более развит, в вычислениях они компьютерам уступают и именно в вычислительной среде создают ИИ, способный ускорить процесс получения максимального результата. Люди не способны мгновенно и правильно выполнять сложные вычисления, а калькулятор облегчает им жизнь.
Можно привести другой пример ИИ с использованием рационального агента — программы на C# для решения головоломки «Пятнашки». Рациональность агента здесь обеспечивается алгоритмом поиска A*, который связан с эвристикой, направляющей поиск к максимальному результату.
Головоломка
Считается, что головоломку «Пятнашки» в 1870-х гг. создал шахматист и составитель шахматных задач Сэм Лойд (1841–1911). Она состоит из игрового поля размером N x M (рис. 1), в каждой клетке которого может быть всё что угодно: цифра, буква, изображение и т. д.:
Цель головоломки — переставить клетки из начального состояния так, чтобы все они в итоге располагались в соответствии с конфигурацией целевого (рис. 2).
Перемещение клеток из начального состояния в целевое
Целевое состояние достигается за несколько ходов. Каждый ход — это замена пустой клетки на соседнюю. Вот решение предыдущего примера:
Чтобы достичь цели необходима последовательность движений; один ход — это замена пустой плитки на другую плитку. Предыдущий пример решается, как показано на рисунке 3.
У читателя может возникнуть логичный вопрос: возможно ли вообще из начального состояния ниже достичь целевого? Сэм Лойд однажды пообещал $1000 любому, кто решит эту головоломку:
Кое-кто утверждал, что нашёл решение, но на самом деле решения нет. Как же узнать, есть ли решение у исходной конфигурации? Доказано, что конфигурация имеет решение при выполнении следующих условий:
Если ширина поля — нечётное число, для нахождения решения нужно сделать чётное число перестановок.
Если ширина поля — чётное число, для нахождения решения нужно сделать: а) чётное число перестановок, если пустая клетка находится на нечётной строке, считая снизу; б) нечётное число перестановок, если пустая клетка находится на чётной строке, считая снизу.
Перестановка происходит, когда за одной клеткой следует другая с меньшим значением. В целевом состоянии перестановок не будет. Например, в головоломке 4 х 4, где все числа идут по порядку, кроме числа 12 (оно в левом верхнем углу), будет 11 перестановок. В общем случае две клетки a и b меняются местами, если b идёт после a, но b меньше a.
Алгоритм A*
Агентом, который мы будем разрабатывать, выполняется поиск в пространстве состояний (пространстве всех возможных конфигураций игрового поля) с использованием информированного поиска A*. Поиск «информируется» при выборе следующего шага с учётом знаний предметной области, которые представлены значением функции, связанной с каждым состоянием задачи (рис. 5). Возможные состояния (вверх, вниз, влево и вправо) соответствуют направлениям перемещения пустой клетки:
Ключевой элемент A* находится в значении, которое присваивается каждому состоянию и даёт возможность резко сократить время на поиск целевого состояния из заданного начального состояния (рис. 6). Функция, которой выводится значение, привязанное к каждому состоянию s, раскладывается так:
f(s) = g(s) + h(s)где g — это стоимость достижения s из начального состояния (число ходов от начального состояния до s), h — рациональный компонент агента (эвристика), позволяющий определять стоимость всех возможных путей, начинающихся в s:
Эвристической функцией к агенту привязываются эмпирические правила. Поэтому, чем лучше добавляемые правила, тем скорее достигается целевое состояние. Функция MisplacedTiles(s), которой выводится число неправильно расположенных клеток для состояния s, может считаться потенциально эвристической: по ней всегда понятно, насколько далеко мы от целевого состояния. При создании или включении эвристики важна её допустимость, необходимая, чтобы гарантировать полноту и оптимальность алгоритма A*, то есть что алгоритм находит решение и это решение оптимальное.
Эвристика допустима, если минимальная стоимость достижения целевого состояния из узла s никогда не завышается: её значение не должно быть больше стоимости кратчайшего пути от s до целевого состояния. Эвристика неправильно расположенных клеток допустима, ведь каждая из них хотя бы раз должна быть перемещена, чтобы правильно расположить их.
Как показано на рисунке 6, набор состояний можно смоделировать в виде графа, где дочерние элементы узла состояния получаются перемещением пустой клетки во всех возможных направлениях. Чтобы определить целевое состояние, в такой графовой задаче логично использовать алгоритм поиска по графу.
Основа алгоритма A* — это поиск в ширину. При поиске в ширину значение всех узлов равно 1, поэтому не важно, какой узел расширять: в A* всегда расширяется узел, которым максимизируется нужный результат. В случае с головоломкой это узел с минимальной стоимостью, то есть кратчайшим путём до целевого состояния.
На рисунке 7 показано выполнение алгоритма A* (в качестве эвристической функции используются неправильно расположенные клетки):
Важно отметить, что при вычислении любой эвристики пустая клетка никогда не учитывается. Иначе реальная стоимость кратчайшего пути до целевого состояния может быть завышена, а эвристика станет недопустимой. Посмотрите, что бы произошло в предыдущем примере, если учесть пустую клетку:
В предыдущем узле мы всего в шаге от целевого состояния, но согласно эвристике до него остаётся не менее двух шагов (неправильно расположены 8-я и пустая клетка). Это явное завышение реальной стоимости, а потому недопустимо.
Приступим к анализу части кода и рассмотрим класс StateNode в первом листинге, который понадобится для представления состояний или конфигураций на игровом поле.
Листинг класса StateNode
class StateNode<T>: IComparable<StateNode<T>> where T: IComparable
{
public double Value { get; set; }
public T[,] State { get; private set; }
public int EmptyCol { get; private set; }
public int EmptyRow { get; private set; }
public int Depth { get; set; }
public string StrRepresentation { get; set; }
public StateNode() { }
public StateNode(T[,] state, int emptyRow, int emptyCol, int depth)
{
if(state.GetLength(0) != state.GetLength(1))
throw new Exception("Number of columns and rows must be the same");
State = state.Clone() as T[,];
EmptyRow = emptyRow;
EmptyCol = emptyCol;
Depth = depth;
for (var i = 0; i < State.GetLength(0); i++)
{
for (var j = 0; j < State.GetLength(1); j++)
StrRepresentation += State[i, j] + ",";
}
}
public int Size
{
get { return State.GetLength(0); }
}
public void Print()
{
for (var i = 0; i < State.GetLength(0); i++)
{
for (var j = 0; j < State.GetLength(1); j++)
Console.Write(State[i,j] + ",");
Console.WriteLine();
}
Console.WriteLine();
}
public int CompareTo(StateNode<T> other)
{
if (Value > other.Value)
return 1;
if (Value < other.Value)
return -1;
return 0;
}
}Первое, на что следует обратить внимание в классе StateNode, — это его дженерик-функция. Дженерик нужен, чтобы головоломка была с цифрами, буквами, изображениями и т. д., а универсальный тип T поддерживает любой из предыдущих типов. Нужно также, чтобы тип T был сравниваемым, это может оказаться полезным — даже необходимым — для проведения теста на решаемость.
Помните, что нужно будет рассчитать число перестановок, сравнивая элементы. Также обратите внимание на допущение, что ширина и высота игрового поля одинаковы (n = m), а пустая клетка равна 0.
Вот описание каждого поля и свойства:
Value — это значение f = g + h;
T[,] State — конфигурация или состояние, представленные данным узлом;
EmptyCol — номер столбца, в котором находится пустая клетка;
EmptyRow — номер строки, в которой находится пустая клетка;
Depth — глубина этого состояния от начального;
StrRepresentation — строковое представление конфигурации (то есть 1, 2, 3, 4, 5, 6, 7, 8, 0). Строится при создании объекта в конструкторе.
Метод Print() в формате CSV выводит значения клеток на игровом поле, а свойство Size возвращает его размер. Учитывая, что мы наследуем от IComparable<StateNode>, нужно реализовать метод CompareTo, его логика проста. Класс AStar представлен во втором листинге.
Листинг 2: класс AStar
class AStar<T> where T:IComparable
{
public int StatesVisited { get; set; }
public Dictionary<string, int> PatternDatabase { get; set; }
private readonly StateNode<T> _goal;
private T Empty { get; set; }
private readonly PriorityQueue<StateNode<T>> _queue;
private readonly HashSet<string> _hash;
public AStar(StateNode<T> initial, StateNode<T> goal, T empty)
{
_queue = new PriorityQueue<StateNode<T>>(new[] { initial });
_goal = goal;
Empty = empty;
_hash = new HashSet<string>();
}
public StateNode<T> Execute() ...
private void ExpandNodes(StateNode<T> node) ...
private double Heuristic(StateNode<T> node) ...
private int MisplacedTiles(StateNode<T> node) ...
private int ManhattanDistance(StateNode<T> node) ...
private int LinearConflicts(StateNode<T> node) ...
private int DatabasePattern(StateNode<T> node) ...
private int FindConflicts(T[,] state, int i, int dimension) ...
private int InConflict(int index, T a, T b, int indexA, int indexB, int dimension)...
}
}Снова описание каждого поля и свойства:
StatesVisited указывает число посещённых во время поиска состояний, равное числу удалённых из очереди узлов;
Словарь PatternDatabase используется в эвристике базы данных с шаблонами (подробнее о ней — позже), целью является цель StateNode;
Empty это пустая клетка;
queue — очередь с минимальным приоритетом, чтобы легко и эффективно получать из набора узлов узел состояния с минимальным значением f;
hashSet — хеш-множество для хранения строкового представления каждого найденного состояния.
Головоломка циклическая: начиная с исходного состояния, после ряда ходов мы можем оказаться в нём же. Чтобы избежать бесконечного цикла, каждое посещённое состояние сохраняем в хеше.
Теперь рассмотрим методы Execute() и Expand (узел StateNode) в листингах 3 и 4. Остальное относится к эвристике и понадобится в конце при запуске алгоритма и сравнениях.
Листинг 3: метод Execute
public StateNode<T> Execute()
{
_hash.Add(_queue.Min().StrRepresentation);
while(_queue.Count > 0)
{
var current = _queue.Pop();
StatesVisited++;
if (current.StrRepresentation.Equals(_goal.StrRepresentation))
return current;
ExpandNodes(current);
}
return null;
}Это очень простой метод, напоминает тело алгоритма поиска в ширину. Мы добавляем строковое представление начального состояния, а затем попадаем в цикл, который заканчивается, когда в _queue нет узлов. В текущей переменной всегда есть узел с минимальным значением, который и будет расширен. Расширение состоит из всевозможных перемещений от текущего состояния.
Листинг 4: метод ExpandNode
private void ExpandNodes(StateNode<T> node)
{
T temp;
T[,] newState;
var col = node.EmptyCol;
var row = node.EmptyRow;
StateNode<T> newNode;
// Up
if (row > 0)
{
newState = node.State.Clone() as T[,];
temp = newState[row - 1, col];
newState[row - 1, col] = Empty;
newState[row, col] = temp;
newNode = new StateNode<T>(newState, row - 1, col, node.Depth + 1);
if (!_hash.Contains(newNode.StrRepresentation))
{
newNode.Value = node.Depth + Heuristic(newNode);
_queue.Push(newNode);
_hash.Add(newNode.StrRepresentation);
}
}
// Down
if (row < node.Size - 1)
{
newState = node.State.Clone() as T[,];
temp = newState[row + 1, col];
newState[row + 1, col] = Empty;
newState[row, col] = temp;
newNode = new StateNode<T>(newState, row + 1, col, node.Depth + 1);
if (!_hash.Contains(newNode.StrRepresentation))
{
newNode.Value = node.Depth + Heuristic(newNode);
_queue.Push(newNode);
_hash.Add(newNode.StrRepresentation);
}
}
// Left
if (col > 0)
{
newState = node.State.Clone() as T[,];
temp = newState[row, col - 1];
newState[row, col - 1] = Empty;
newState[row, col] = temp;
newNode = new StateNode<T>(newState, row, col - 1, node.Depth + 1);
if (!_hash.Contains(newNode.StrRepresentation))
{
newNode.Value = node.Depth + Heuristic(newNode);
_queue.Push(newNode);
_hash.Add(newNode.StrRepresentation);
}
}
// Right
if (col < node.Size - 1)
{
newState = node.State.Clone() as T[,];
temp = newState[row, col + 1];
newState[row, col + 1] = Empty;
newState[row, col] = temp;
newNode = new StateNode<T>(newState, row, col + 1, node.Depth + 1);
if (!_hash.Contains(newNode.StrRepresentation))
{
newNode.Value = node.Depth + Heuristic(newNode);
_queue.Push(newNode);
_hash.Add(newNode.StrRepresentation);
}
}
}В каждом операторе if проверяется, возможно ли то или иное перемещение. Если да, клонируется текущее состояние (помните: массивы являются ссылочными типами), а затем пустая клетка меняется местами с клеткой, куда она перемещается. Помещаем строковое представление newNode в очередь и добавляем в хеш, если его там нет. Описав «скелет» алгоритма A*, переходим к главному компоненту поиска — эвристике.
Листинг 5: эвристический метод
private double Heuristic(StateNode<T> node)
{
return DatabasePattern(node);
}
private int MisplacedTiles(StateNode<T> node)
{
var result = 0;
for (var i = 0; i < node.State.GetLength(0); i++)
{
for (var j = 0; j < node.State.GetLength(1); j++)
if (!node.State[i, j].Equals(_goal.State[i, j]) && !node.State[i, j].Equals(Empty))
result++;
}
return result;
}Эвристика 1: неправильно расположенные клетки
Первую и, вероятно, самую простую эвристику для этой задачи (числа клеток, которые находятся не на своих местах) мы уже описали. В листинге 6 показана лаборатория для тестирования эвристики.
Листинг 6: лаборатория эвристики (неправильно расположенные клетки)
static void Main()
{
var initWorstConfig3x3 = new[,] { {8,6,7},
{2,5,4},
{3,0,1}
};
var initConfig4x4 = new[,] { {5,10,14,7},
{8,3,6,1},
{15,0,12,9},
{2,11,4,13}
};
var finalConfig3x3 = new[,] { {1,2,3},
{4,5,6},
{7,8,0}
};
var finalConfig4x4 = new[,] { {1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,0}
};
var initialState = new StateNode<int>(initWorstConfig3x3, 2, 1, 0);
var finalState = new StateNode<int>(finalConfig3x3, 2, 2, 0);
var watch = new Stopwatch();
var aStar = new AStar<int>(initialState, finalState, 0)
{
PatternDatabase = FillPatternDatabase()
};
watch.Start();
var node = aStar.Execute();
watch.Stop();
Console.WriteLine("Node at depth {0}", node.Depth);
Console.WriteLine("States visited {0}", aStar.StatesVisited);
Console.WriteLine("Elapsed {0} miliseconds", watch.ElapsedMilliseconds);
Console.Read();
}Для тестирования эвристики возьмём одну из худших конфигураций для игрового поля 3 x 3, показанную на рисунке 9. Для неё требуется 31 ход:
Вот полученные результаты:
В алгоритме A* с эвристикой неправильно расположенных клеток на поиск целевого состояния уходит ~2,5 с. Попробуем найти более умную эвристику с меньшим временем и числом посещённых узлов.
Эвристика 2: манхэттенское расстояние
Манхэттенское расстояние, или расстояние городских кварталов между точками A = (x1, y1) и B = (x2, y2), определяется как сумма абсолютной разности их соответствующих координат:
MD = |x1-x2| + |y1-y2|В листинге 7 манхэттенское расстояние допустимо как эвристика: по каждой клетке возвращается минимальное число шагов для перемещения в её целевое положение.
Листинг 7: эвристика 2 (манхэттенское расстояние)
private int ManhattanDistance(StateNode<T> node)
{
var result = 0;
for (var i = 0; i < node.State.GetLength(0); i++)
{
for (var j = 0; j < node.State.GetLength(1); j++)
{
var elem = node.State[i, j];
if (elem.Equals(Empty)) continue;
// Variable to break the outer loop and
// avoid unnecessary processing
var found = false;
// Loop to find element in goal state and MD
for (var h = 0; h < _goal.State.GetLength(0); h++)
{
for (var k = 0; k < _goal.State.GetLength(1); k++)
{
if (_goal.State[h, k].Equals(elem))
{
result += Math.Abs(h - i) + Math.Abs(j - k);
found = true;
break;
}
}
if (found) break;
}
}
}
return result;
}Вот результаты применения A* с манхэттенским расстоянием:
Сокращение времени и посещённых узлов значительное — информация для поиска лучше, поэтому цель находится гораздо быстрее.
Эвристика 3: линейный конфликт
В эвристике линейного конфликта даётся информация о необходимых ходах, которые не учитываются при расчёте манхэттенского расстояния. Клетки tj и tk находятся в линейном конфликте, если они и их целевые положения располагаются на одной линии, при этом tj — справа от tk, а целевое положение tj — слева от целевого положения tk.
На рисунке 12 клетки 3 и 1 хотя и в одной строке, но не на своих местах:
Чтобы привести их в целевые положения, нужно переместить одну из них вниз, а затем снова вверх (эти перемещения не учитываются в манхэттенском расстоянии). Клетка не может быть более чем в одном конфликте, ведь разрешение определённого конфликта может подразумевать разрешение других конфликтов в той же строке или столбце. Поэтому, если клетка 1 связана конфликтом с клеткой 3, она не может быть связана конфликтом с клеткой 2 — это может привести к завышению кратчайшего пути до целевого состояния и сделать эвристику недопустимой. Методы, реализующие эту эвристику, представлены в листинге 8.
Листинг 8: метод LinearConflict
private int LinearConflicts(StateNode<T> node)
{
var result = 0;
var state = node.State;
// Row Conflicts
for (var i = 0; i < state.GetLength(0); i++)
result += FindConflicts(state, i, 1);
// Column Conflicts
for (var i = 0; i < state.GetLength(1); i++)
result += FindConflicts(state, i, 0);
return result;
}
private int FindConflicts(T[,] state, int i, int dimension)
{
var result = 0;
var tilesRelated = new List<int>();
// Loop foreach pair of elements in the row/column
for (var h = 0; h < state.GetLength(dimension) - 1 && !tilesRelated.Contains(h); h++)
{
for (var k = h + 1; k < state.GetLength(dimension) && !tilesRelated.Contains(h); k++)
{
// Avoid the empty tile
if (dimension == 1 && state[i, h].Equals(Empty)) continue;
if (dimension == 0 && state[h, i].Equals(Empty)) continue;
if (dimension == 1 && state[i, k].Equals(Empty)) continue;
if (dimension == 0 && state[k, i].Equals(Empty)) continue;
var moves = dimension == 1
? InConflict(i, state[i, h], state[i, k], h, k, dimension)
: InConflict(i, state[h, i], state[k, i], h, k, dimension);
if (moves == 0) continue;
result += 2;
tilesRelated.AddRange(new List<int> { h, k });
break;
}
}
return result;
}
private int InConflict(int index, T a, T b, int indexA, int indexB, int dimension)
{
var indexGoalA = -1;
var indexGoalB = -1;
for (var c = 0; c < _goal.State.GetLength(dimension); c++)
{
if (dimension == 1 && _goal.State[index, c].Equals(a))
indexGoalA = c;
else if (dimension == 1 && _goal.State[index, c].Equals(b))
indexGoalB = c;
else if (dimension == 0 && _goal.State[c, index].Equals(a))
indexGoalA = c;
else if (dimension == 0 && _goal.State[c, index].Equals(b))
indexGoalB = c;
}
return (indexGoalA >= 0 && indexGoalB >= 0) && ((indexA < indexB && indexGoalA > indexGoalB) ||
(indexA > indexB && indexGoalA < indexGoalB))
? 2
: 0;
}Чтобы протестировать эвристику линейного конфликта, понадобится игровое поле 4 x 4 (рис. 13), где до целевого состояния нужно сделать 55 ходов. Значение узла s теперь будет определяться как f(s) = depth(s) + md(s) + lc(s). Объединим обе эвристики, ведь их ходы не пересекаются и завышения не будет:
Вот результаты:
Через пару минут алгоритм выдал результат. То же игровое поле протестировали с одним лишь манхэттенским расстоянием, и после 5-минутного ожидания результата получено не было.
Эвристика 4: база данных с шаблонами
Эвристика базы данных с шаблонами (рис. 15) определяется базой данных разных состояний игры. Каждое состояние связано с минимальным числом ходов, необходимым для приведения шаблона (подмножества клеток) в его целевое положение. Для этого случая мы создали небольшую базу данных с шаблонами, проведя поиск в ширину в обратном направлении — начиная с целевого состояния (3 x 3). Результаты сохранили в файле .txt всего с 60 000 записей. Для базы данных выбрали шаблон fringe с клетками из верхней строки и самого левого столбца:
Эвристическая функция базы данных с шаблонами в листинге 9 вычисляется с помощью функции табличного поиска. В данном случае это поиск по словарю с 60 000 сохранённых шаблонов. Он принципиально схож с техниками динамического программирования и подходом «разделяй и властвуй».
Листинг 9: эвристическая функция базы данных с шаблонами
private int DatabasePattern(StateNode<T> node)
{
var pattern = node.StrRepresentation
.Replace('5', '?')
.Replace('6', '?')
.Replace('7', '?')
.Replace('8', '?');
if (PatternDatabase.ContainsKey(pattern))
return PatternDatabase[pattern];
return ManhattanDistance(node);
}Вот результаты:
Чем больше записей в базе данных, тем меньше времени нужно на поиск целевого состояния. В нашем случае память и время сочетаются так, чтобы задействовать больший объём памяти для улучшения времени выполнения. Механизм работы здесь обычно такой: используется больше памяти, чтобы сократить время выполнения.
Эвристика базы данных с шаблонами — это определяющая альтернатива при решении головоломки с игровым полем не менее чем 4 x 4.
Об авторе
Арнальдо Перес Кастаньо — кубинский специалист компьютерных наук, автор серии книг по программированию (JavaScript Fácil, HTML, CSS Fácil и Python Fácil (Marcombo S.A.). Он имеет опыт работы с Visual Basic, C#, .NET Framework, ИИ и предлагает услуги фрилансера на nubelo.com. Его хобби — кино и музыка. Связаться с ним можно по адресу arnaldo.skywalker@gmail.com.
А мы поможем вам прокачать скиллы или освоить новую профессию, которая останется актуальной в любое время:
Выбрать другую востребованную профессию.
Краткий каталог курсов и профессий
Data Science и Machine Learning
Python, веб-разработка
Мобильная разработка
Java и C#
От основ — в глубину
А также
