2017-03-20 182 views
0

我目前正在为棋盘游戏Hex写一个AI。我想用蒙特卡洛树搜索来做到这一点,并且已经试图实现它。然而,人工智能做出了令人难以置信的愚蠢(随机)移动,我无法弄清楚为什么它不起作用。蒙特卡洛树搜索不工作

import java.util.ArrayList; 
import java.util.Random; 

/** 
* Created by Robin on 18.03.2017. 
*/ 
public class TreeNode { 


    private static final Random random = new Random(); 
    private static final double epsion=10e-5; 
    protected double nvisits; 
    protected double totValue; 
    protected int move=-1; 

    private HexBoard board; 
    protected ArrayList<TreeNode>children ; 



    public TreeNode(HexBoard board){ 
     this.board =board; 
    } 


    //Copy-Constructor 
    public TreeNode(TreeNode treeNode){ 
     this.nvisits=treeNode.nvisits; 
     this.totValue=treeNode.totValue; 
     this.move=treeNode.move; 
     this.board = new HexBoard(treeNode.board); 

    } 

    public void update(double value){ 
     totValue+=value*board.color; 
     nvisits++; 
    } 



    public void expand(){ 
     assert(children==null); 
     children = new ArrayList<>(121-board.moveCount); 
     for(int i=0;i<121;i++){ 
      if(board.board[i]!=HexBoard.EMPTY) 
       continue; 

       TreeNode newNode = new TreeNode(board); 
       newNode.move =i; 
       children.add(newNode); 

     } 
    } 

    public void calculateIteration(){ 
     ArrayList<TreeNode>visited = new ArrayList<>(); 
     TreeNode current =this; 
     visited.add(current); 

     while(!current.isLeafNode()){ 
      current =current.select(); 
      board.makeMove(current.move); 
      visited.add(current); 
     } 

     //Found a leaf node 
     double value; 
     if(current.board.getWinner()==0){ 
      current.expand(); 
      TreeNode newNode =current.select(); 
      value =playOut(newNode.board); 
     }else{ 
      value =current.board.getWinner(); 
     } 

     //update all the nodes 

     for(int i=1;i<visited.size();i++){ 
      visited.get(i).update(value); 
      board.undoMove(visited.get(i).move); 
     } 
     visited.get(0).update(value); 
    } 

    public static int playOut(HexBoard board){ 
     int winner=0; 

     if(board.moveCount==121) { 
      winner=board.getWinner(); 

      return winner; 
     } 

     //Checking-Movecount vs actual stones on the board 


     final double left =121-board.moveCount; 
     double probibility =1/left; 
     double summe =0; 
     double p =random.nextDouble(); 

     int randomMove =0; 
     for(int i=0;i<121;i++){ 
      if(board.board[i]!=HexBoard.EMPTY) 
       continue; 

      summe+=probibility; 

      if(p<=summe && probibility!=0) { 
       randomMove = i; 
       break; 
      } 
     } 

     board.makeMove(randomMove); 
     winner =playOut(board); 
     board.undoMove(randomMove); 

     return winner; 
    } 


    public TreeNode select(){ 

     TreeNode bestNode=null; 
     double bestValue =-10000000; 
     for(TreeNode node : children){ 

      double uctvalue =(node.nvisits==0)?100000:(node.totValue/(node.nvisits)+Math.sqrt((Math.log(this.nvisits))/(2*node.nvisits))); 
      uctvalue+=epsion*random.nextDouble(); 

      if(uctvalue>bestValue){ 
       bestValue=uctvalue; 
       bestNode =node; 
      } 
     } 

     return bestNode; 
     /// 
    } 

    public boolean isLeafNode(){ 
     return (children==null); 
    } 
} 

我在方法calcualteIteration()中的实现是否正确?

我知道这可能不是看一个非常有吸引力的问题,但我希望得到任何帮助

+0

这太宽泛了。请进行一些调试以缩小这个问题的范围,使其更简单一些,以及[最小测试用例](https://stackoverflow.com/help/mcve)。 –

+0

你真的在跟踪哪个球员做出哪些动作吗?你在迭代中轮流轮流吗?对我来说,看起来你只是让现在的玩家在你的模拟中填满整个棋盘,它假装没有对手。或者我错过了什么?此外,告诉我们您正在运行多少模拟以及如何最终决定在“真实”游戏中玩什么游戏会很有用 –

+0

对不起,我应该澄清这一点。 board.makemove()函数在两个玩家之间交替。我尝试了100-50000次模拟中的所有事情,结果几乎相同(坏随机动作)。根节点的“最佳”兄弟是具有最高uct值的兄弟,并且将由AI – CheckersGuy

回答

1

OP中添加了问题后评论额外信息。该额外信息的重要部分是实现了makeMove()方法来检查下一个播放器(确保更新板是正确的)。

鉴于这些信息,OP中select()的实现是不正确的,因为它没有考虑在计算UCT得分时哪个玩家要移动。 UCT得分包括一个“开发”部分(第一部分,计算所有先前模拟的平均得分)和一个“探索”部分(平方根下的部分,对于已经访问过的节点,相对于其父母来说很少)。当对手被允许下一步移动时,该等式的开发部分应该被否定。如果没有这样做,AI将基本上认为对手愿意积极帮助AI,而不是假设对手会为自己赢得胜利。

+1

谢谢。现在它运行得非常好只用5000次模拟测试,我无法获胜:P – CheckersGuy

+0

最好的价值是最高胜率,而不是uct值(用于指导树的进一步探索),特别是在引入随机组件。其他实施者在大约1000-1500个播出后已经实现了完美的播放。 –