Java迷宫解决和强化学习

Question

我正在写代码来自动模拟Theseus和Minoutaur的行为，如此逻辑游戏中所示; http://www.logicmazes.com/theseus.html

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

根据在过去几天内收到的建议，我调整了我的代码，将状态视为在给定时间既是thesesus也是minotaur的位置。当这些动作移动时，状态将被添加到“访问状态”列表中。通过将所建议的动作所产生的状态与访问状态列表进行比较，我能够确保这些动作不会导致以前的状态。

问题是我需要能够在某些情况下重新访问。例如使用迷宫3作为例子，牛头怪为每个移动移动2x。忒修斯移动4 - > 5，添加状态（t5，m1）。 mino移动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

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

对于您的“强化学习”方法，每当Theseus被抓到时您将完全重置迷宫，您需要更改该方法。我想你可以改变“从来没有拜访过以前你已经在状态”规则双管齐下的规则：这个迷宫的运行过程中

• 从未访问你已经在状态。 （这是为了防止无限循环。）
• disprefer访问您在忒修斯陷入迷宫运行期间一直呆在的状态。 （这是“学习”的一部分：如果选择以前很差制定出来的，应该不经常做。）

Answer 2

对于什么是值得，最简单的方法来解决这个问题优化是使用ALPHA-BETA，这是一个确定性双人游戏（如井字棋，跳棋，国际象棋）的搜索算法。这里有一个如何实现它为你的情况摘要：

1. 创建一个代表游戏，这 应包括的当前状态类：Thesesus的位置，Minoutaur的位置和 轮到谁是它 。说你调用这个类GameState

2. 创建一个启发式的函数，它的GameState作为paraemter一个实例，并返回一个两倍的AS计算公式如下：

   • 让申是Manhattan distance（平方数） Theseus是从出口。

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

   • 设T为1，如果是Theseus，则为1，如果是牛头怪，则设-1。

   • 如果DM不是零和DT不为零，则返回DM +（DT/2）* T

   • 如果DM是零，回到-Infinity * T

   • 如果dt为零，返回无限* T

上面的启发式函数返回值，维基百科是指作为对于给定的GameState“节点的启发式值”（正ode）在算法的伪代码中。

现在，您已经拥有了所有可用Java编写的元素。