蒙特卡洛樹搜索不工作

Question

我目前正在爲棋盤遊戲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（）中的實現是否正確？

我知道這可能不是看一個非常有吸引力的問題，但我希望得到任何幫助

Answer 1

OP中添加了問題後評論額外信息。該額外信息的重要部分是實現了makeMove()方法來檢查下一個播放器（確保更新板是正確的）。

鑑於這些信息，OP中select()的實現是不正確的，因爲它沒有考慮在計算UCT得分時哪個玩家要移動。 UCT得分包括一個「開發」部分（第一部分，計算所有先前模擬的平均得分）和一個「探索」部分（平方根下的部分，對於已經訪問過的節點，相對於其父母來說很少）。當對手被允許下一步移動時，該等式的開發部分應該被否定。如果沒有這樣做，AI將基本上認爲對手願意積極幫助AI，而不是假設對手會爲自己贏得勝利。