Java迷宫解决和强化学习

Question

我正在编写代码来自动模拟 Theseus 和 Minoutaur 的 Action ，如这个逻辑游戏中所示； http://www.logicmazes.com/theseus.html

对于每个迷宫，我为它提供迷宫的位置，以及哪些位置可用，例如从位置 0 开始，下一个状态是 1,2 或保持在 0。我运行一个 QLearning 实例化，它计算了忒修斯到达逃离迷宫假设没有牛头怪。然后介绍了牛头怪。忒修斯向导出迈出第一步，不可避免地被捕获，导致最佳路径重新加权。在游戏中使用迷宫 3 作为测试，这种方法导致忒修斯不确定地在中间线上上下移动，因为这是唯一没有杀死它的 Action 。

根据最近几天在这里收到的建议，我调整了我的代码以将状态视为给定时间的 thesesus 和牛头怪的位置。当忒修斯移动时，状态将被添加到“访问状态”列表中。通过将建议移动产生的状态与访问状态列表进行比较，我能够确保忒修斯不会做出会导致以前的状态。

问题是在某些情况下我需要能够重新访问。例如，以迷宫 3 为例，每移动一次忒修斯，牛头怪移动 2 倍。忒修斯移动 4 -> 5，状态添加(t5，m1)。米诺移动 1->5。忒修斯被捕获，重置。 4-> 5 是一个糟糕的棋步，所以忒修斯走 4->3，轮到米诺 catch 了。现在(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

这里的问题是“永远不要访问你以前去过的状态”方法和你的“强化学习”方法之间的差异。当我推荐“永远不要访问你以前去过的状态”方法时，我假设你正在使用回溯:一旦忒修斯被捕获，你就会将堆栈展开到他做出非强制选择的最后一个地方，然后尝试不同的选项。 (也就是说，我假设您使用的是状态空间的简单深度优先搜索。)在这种方法中，没有任何理由去访问您之前访问过的状态。

对于您的“强化学习”方法，您需要在每次抓到 Theseus 时完全重置迷宫，您需要改变它。我想您可以将“永远不要访问您以前去过的州”规则更改为双管齐下的规则:

• 永远不要访问您在迷宫运行期间所处的状态。 (这是为了防止无限循环。)
• 不喜欢访问您在 Theseus 被捕获的迷宫中运行时所处的状态。 (这是“学习”部分:如果以前的选择效果不佳，则应减少选择次数。)