Обучение лабиринту в Java

Question

Я пишу код для автоматизации симуляции действий Тесея и Минутавра, как показано в этой логической игре;http://www.logicmazes.com/theseus.html

Для каждого лабиринта я предоставляю ему позиции лабиринта, и какие позиции доступны, например, из позиции 0 следующие состояния равны 1,2 или остаются на 0. Я запускаю экземпляр QLearning, который вычисляетлучший путь для тезей, чтобы избежать лабиринта при условии отсутствия минотавра .затем вводится минотавр.Тесей делает свой первый шаг к выходу и неизбежно оказывается пойманным, что приводит к переоценке лучшего пути.используя лабиринт 3 в игре в качестве теста, этот подход привел к тому, что они перемещались вверх и вниз по средней линии неопределенно долго, поскольку это были единственные движения, которые не убили его.

В соответствии с предложением, полученным здесь в течение последних нескольких дней, я скорректировал свой код так, чтобы рассматривать состояние как положение тезиса и минотавра в данный момент времени.когда эти объекты будут перемещаться, состояние будет добавлено в список «посещенных состояний». Сравнивая состояние, полученное в результате предлагаемого перемещения, со списком посещенных состояний, я могу убедиться, что в этом случае не произойдет движение, которое приведет кпредыдущее состояние.

Проблема в том, что мне нужно иметь возможность вернуться в некоторых случаях.Например, используя лабиринт 3 в качестве примера, и минотавр двигается 2 раза за каждое движение Тесей.Тезей двигается 4 -> 5, состояние добавлено (t5, m1).Мино ход 1-> 5.Тесей поймал, сбросил.4-> 5 - плохой ход, поэтому эти ходы 4-> 3, Мино ловит на своем ходу.теперь и (t5, m1), и (t3 m1) находятся в списке посещений

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

public void move()
{
    int randomness =10;
    State tempState = new State();
    boolean rejectMove = true;
    int keepCurrent = currentPosition;
    int keepMinotaur = minotaurPosition;

    previousPosition = currentPosition;
    do
    {
        minotaurPosition = keepMinotaur;
        currentPosition = keepCurrent;
        rejectMove = false;

        if (states.size() > 10)
        {
            states.clear();
        }


        if(this.policy(currentPosition) == this.minotaurPosition )
        {
            randomness = 100;
        }

        if(Math.random()*100 <= randomness)
        {
            System.out.println("Random move");
            int[] actionsFromState = actions[currentPosition];
            int max = actionsFromState.length;
            Random r = new Random();
            int s =  r.nextInt(max);    

            previousPosition = currentPosition;
            currentPosition = actions[currentPosition][s];
        }
        else
        {
            previousPosition = currentPosition;
            currentPosition = policy(currentPosition);
        }

        tempState.setAttributes(minotaurPosition, currentPosition);
        randomness = 10;    

        for(int i=0; i<states.size(); i++)
        {
            if(states.get(i).getMinotaurPosition() == tempState.getMinotaurPosition()  &&  states.get(i).theseusPosition == tempState.getTheseusPosition())
            {

                rejectMove = true;

                changeReward(100);

            }
        }

    }
    while(rejectMove == true);

    states.add(tempState);
}       

выше - метод перемещения Тесея;иногда показывая случайный ход

Answer 1

Для чего стоит, самый простой способ решить эту проблему оптимально - это использовать ALPHA-BETA , который является алгоритмом поиска для детерминированных двух- Игровые игры (например, крестики-нолики, шашки, шахматы). Вот краткое изложение того, как реализовать это для вашего случая:

1. Создать класс, который представляет текущее состояние игры, которое должны включать в себя: положение тезиса, положение минутавра и чья очередь . Скажем, вы называете этот класс GameState

2. Создать эвристическую функцию, которая принимает экземпляр GameState в качестве параметра и возвращает значение типа double, которое рассчитывается следующим образом:

   • Пусть Dt будет Манхэттенским расстоянием (количество квадратов), что Тесей находится от выхода.

   • Пусть Dm - расстояние Манхэттена (количество квадратов), которое Минотавр находится от Тесея.

   • Пусть T будет 1, если он повернет Тесей, и -1, если это Минотавр.

   • Если Dm не равно нулю, а Dt не равно нулю, вернуть Dm + (Dt / 2) * T

   • Если Dm равно нулю, вернуть -Infinity * T

   • Если Dt равно нулю, вернуть бесконечность * T

Приведенная выше эвристическая функция возвращает значение, которое Википедия называет «эвристическим значением узла» для данного GameState (узла) в псевдокоде алгоритма.

Теперь у вас есть все элементы для его кодирования на Java.

Answer 2

Проблема здесь заключается в несоответствии между подходом «никогда не посещать государство, в котором вы ранее были» и вашим подходом «обучение с подкреплением». Когда я рекомендовал подход «никогда не посещать состояние, в котором вы были ранее», я исходил из предположения, что вы используете возвратный путь: как только Тесей будет пойман, вы развернете стек до последнего места, где он сделал вынужденный выбор, а затем попробуйте другой вариант. (То есть, я предположил, что вы использовали простой поиск в глубине пространства состояний.) При таком подходе никогда нет причин посещать ранее посещенное вами состояние.

Для вашего подхода «обучения подкреплению», когда вы полностью сбрасываете лабиринт каждый раз, когда Тесей попадает в ловушку, вам нужно это изменить. Я полагаю, что вы можете изменить правило "никогда не посещать государство, в котором вы были ранее" на правило с двумя аспектами:

• никогда Посетите штат, в котором вы были во время этого бега лабиринта. (Это предотвращает бесконечные циклы.)
• disprefer посещение штата, в котором вы были во время пробега по лабиринту, где Тесей был пойман. (Это «обучающая» часть: если выбор ранее удался, его следует делать реже.)