Монте-Карло-Три Поиск не работает

Question

В настоящее время я пишу AI для настольной игры Hex. Я хочу использовать Monte-Carlo-Tree-Search для этого и уже пытался реализовать это. Тем не менее, ИИ делает невероятные глупые (случайные) движения, и я не могу понять, почему он не работает.

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);
    }
}

Правильна ли моя реализация внутри метода calcualteItered ()?

Я знаю, что это не очень привлекательная проблема, но я был бы признателен за любую помощь

Answer 1

ОП добавил дополнительную информацию в комментариях после вопроса. Важной частью этой дополнительной информации является то, что makeMove() Реализован метод проверки игрока, который будет играть дальше (чтобы убедиться, что обновления на доске правильные).

Учитывая эту информацию, реализация select() в ОП неверен, потому что он не учитывает, какой игрок должен переместиться, вычисляя счет UCT. Оценка UCT состоит из части "эксплуатации" (первая фракция, вычисляемая средняя оценка по всем предыдущим симуляциям) и части "исследования" (часть под квадратным корнем, которая увеличивается для узлов, которые редко посещались по сравнению с их родителем). Эксплуатационная часть этого уравнения должна быть отменена, когда противнику разрешено сделать следующий шаг. Если этого не сделать, ИИ, по сути, будет предполагать, что противник готов активно помогать ИИ, вместо того, чтобы предполагать, что противник попытается выиграть для себя.