Цель этой статьи — пробудить интерес читателей к удивительному миру и показать различные способы решения таких же интересных головоломок, как «Пятнашки». Создайте свою базу данных с шаблонами и начните решать головоломки менее чем за 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#
От основ — в глубину
А также
ссылка на оригинал статьи https://habr.com/ru/company/skillfactory/blog/655629/
Добавить комментарий