モンテカルロツリー検索が機能しない

Question

現在、ボードゲームのAIを書いていますHex。私はMonte-Carlo-Tree-Searchを使ってそれを実装し、すでに実装しようとしています。しかし、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()メソッドを実装して、次にプレーするプレイヤーを確認することです（ボードの更新が正しいことを確認するため）。

UCTスコアを計算するときにどのプレイヤーを移動するのか考慮していないため、その情報が与えられた場合、select()のOPでの実装は正しくありません。 UCTスコアは、「搾取」部分（最初の部分、以前のすべてのシミュレーションよりも平均スコアを計算）、および「探索」部分（平方根の下の部分で、親に対してめったに訪問されなかったノード）。この方程式の搾取部分は、相手が次に動くことを許可されたときに否定されなければならない。これが行われない場合、AIは本質的に、対戦相手が自分自身で勝利しようとするのではなく、AIが積極的にAIを助けようとしていると仮定します。