Цель этой статьи — пробудить интерес читателей к удивительному миру и показать различные способы решения таких же интересных головоломок, как «Пятнашки». Создайте свою базу данных с шаблонами и начните решать головоломки менее чем за 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.

А мы поможем вам прокачать скиллы или освоить новую профессию, которая останется актуальной в любое время:

• Профессия C#-разработчик

• Профессия Data Scientist

Выбрать другую востребованную профессию.