2

我正在编写代码来自动模拟忒修斯和牛头怪的动作，如这个逻辑游戏所示；http://www.logicmazes.com/theseus.html

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

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

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

以上是忒修斯的移动方法；偶尔显示它暗示随机移动

4

2 回答 2

2

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

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

  • 永远不要访问您在迷宫中所处的状态。（这是为了防止无限循环。）
  • 不喜欢访问你在忒修斯被抓住的迷宫中所处的状态。（这是“学习”部分：如果一个选择以前效果不佳，那么应该减少它的频率。）
于 2012-03-25T17:22:11.060 回答
2

值得一提的是，以最佳方式解决此问题的最简单方法是使用ALPHA-BETA，这是一种用于确定性两人游戏（如井字游戏、跳棋、国际象棋）的搜索算法。以下是如何为您的案例实施它的摘要：

  1. 创建一个代表游戏当前状态的类，其中应包括：忒修斯的位置、Minoutaur 的位置以及 轮到谁了。假设你调用这个类GameState

  2. 创建一个启发式函数，该函数将 的实例GameState作为参数，并返回一个按如下方式计算的双精度数：

    • 令 Dt 为忒修斯与出口的曼哈顿距离（方格数）。

    • 令 Dm 为牛头怪与忒修斯的曼哈顿距离（平方数）。

    • 如果是忒修斯回合，则令 T 为 1，如果是牛头怪，则令 T 为 -1。

    • 如果 Dm 不为零且 Dt 不为零，则返回 Dm + (Dt/2) * T

    • 如果 Dm 为零，则返回 -Infinity * T

    • 如果 Dt 为零，则返回 Infinity * T

GameState上面的启发式函数返回 Wikipedia 引用的值，即算法伪代码中给定（节点）的“节点的启发式值” 。

您现在拥有了用 Java 编写代码的所有元素。

于 2012-03-25T17:27:37.910 回答