Создание ИИ для игры с черепицей

Question

Im делает игру с таблицей «плиток», где цель состоит в том, чтобы сгруппировать их в блоки из 2 на 2 этого цвета с наличием 16 уникальных цветов. Я закончил эту часть игры и хотел бы перейти к созданию компонента ИИ, который дает предложение о минимальном количестве ходов, в которые вы можете закончить игру. Ive решила использовать массив 2d, чтобы он распознавал, где каждый цвет не влияет непосредственно на плату, и мне нужна помощь. как только я закончу массив, что он должен сделать, это узнать цвет первой плитки и посмотреть цвета этой плитки и поменять их окружающими блоками справа и снизу и направо. Может ли кто-нибудь помочь?

Answer 1

Это похоже на то, что вы хотите сделать, это решить более простую проблему, которая не требует AI, сама по себе. Лучше всего создать массив для каждого предпринятого решения - возможно, в самом двумерном массиве - и решить каждую головоломку несколько раз, отслеживая движения. Массив массивов будет действовать как список, чтобы убедиться, что вы получаете уникальные решения.

Возможно, вы захотите реализовать алгоритм рекурсивного решения для заполнения каждого массива, иметь верхний предел либо количеству попыток, либо времени для решения (или обоих), и предоставить решение с наименьшим числом поворотов в качестве подсказки ,

Возможно, вы не можете получить абсолютное минимальное количество поворотов, математически возможных, но это, по крайней мере, исходная точка (и с некоторыми дальнейшими исследованиями в математике и оптимизации алгоритмов вы можете натолкнуться на идеальное математическое решение). Это и игра, так что с удовольствием с ней ;-).

Answer 2

Не знаете, как работает игра. Я полагаю, что способ, которым он работает, - это менять цвета между соседними блоками до тех пор, пока не будет достигнуто условие завершения.

Если хотите вы хотите, чтобы найти лучшее решение, вы должны сделать что-то вроде этого:

FUNCTION SEARCH(StackOfMoves I,O) 
    FOR EACH position in chekcboard 
     FOR EACH direction in possibleMoves 
      makeMove(position , direction) 
      StackOfMoves->addMoveToStack(position, direction) 
      IF GameCompleted() 
       RETURN StackOfMoves 
      ELSE 
       SEARCH(StackOfMoves) 
      END IF 
     END FOR 
    END FOR 

    RETURN StackOfMoves 
END FUNCTION 

EDIT

Анализируются это тихо, и я думаю, что это wouldn't не работает должным образом, если вам установить предел итераций или условный выход, если он выбирает плохой ход, он может продолжать повторять за неудачными ходами снова и снова. Условие, чтобы убедиться, что текущее состояние уже обработано и возвращает false, если оно не может его исправить, но может быть лучшим решением. Я постараюсь дать лучший ответ позже.

Answer 3

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

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

Оценки для каждой позиции могут храниться в базе данных, так что, если одна и та же позиция может быть достигнута с различными последовательностями ходов, вам нужно только вычислить счет для этой позиции один раз. Затем, если вы снова попадете в ту же позицию в своем поиске, у вас уже есть оценка в базе данных. Обычно программы вычисляют хэш состояния платы для индексации позиций в таблице.

С глубиной во-первых, требуемый объем расчета зависит частично от глубины поиска. В ряде шахматных программ используется метод, называемый итеративным углублением, позволяющий быстро генерировать предположение, а затем генерировать лучшие ходы после большего времени поиска. Сначала вы выполняете поиск с глубиной в 1 шаг. Каждая из этих позиций хранится в базе данных, поэтому вам не нужно пересчитывать баллы. После того, как вы оцениваете все перемещения на глубину 1, вы начинаете сначала и оцениваете перемещение деревьев на глубину 2. Каждая итерация требует экспоненциально большего количества времени для вычисления, поэтому итеративное углубление позволяет вам генерировать лучшие движения, так как у вас больше времени на размышления.

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

Поиск по глубине - это всего лишь один алгоритм, который вы могли бы использовать. В зависимости от игры у вас могут быть лучшие результаты с другими видами алгоритмов. Например, вы можете использовать нейронную сеть, и это может заменить время поиска во время игры с временем тренировки до игры. Несмотря на это, вы можете потратить много времени на разработку ИИ, даже для простых игр.