问蒙特卡洛树搜索

EN

 // method to find  best turn
    Node findBest( )
    {
        Node startingPoint = new Node();
        startingPoint.CurrentField_Boxes = GameBoard.boxs;
        startingPoint.CurrentField_H = GameBoard.horizontal_line;
        startingPoint.CurrentField_V = GameBoard.vertical_line;

        Node rootNode = startingPoint;

       for( int i = 0; i < 2; i++)
        {
            //Selection
            Node promisingNode = selectPromisingNode(rootNode);
            Debug.Log("POST SELECTION CHECK VON X/Y " + promisingNode.x + "/" + promisingNode.y);

            //Expansion
            if (!checkField())
            {
                expandNode(promisingNode);
            }

            //Simulation
            Node nodeToExplore = promisingNode;
            Debug.Log("POST 2 SELECTION CHECK VON X/Y " + nodeToExplore.x + "/" + nodeToExplore.y);

            if (promisingNode.getChildren().Count > 0)
            {
                //get random child node
                nodeToExplore = promisingNode.getRandomChild();
                Debug.Log("POST 3 SELECTION CHECK VON X/Y " + nodeToExplore.x + "/" + nodeToExplore.y);
            }

            int playoutResult = simulation(nodeToExplore);
            Debug.Log("SIM RESULT :" + playoutResult);
            //backpropagation
            backPropogation(nodeToExplore);
        }

        Debug.Log("*********************************");
        Node  bestNode = new Node();
        Debug.Log("POST 4 SELECTION CHECK VON X/Y " + rootNode.getBestChild().x + "/" + rootNode.getBestChild().y);
        bestNode = rootNode.getBestChild();
        return bestNode;
    }

    private Node selectPromisingNode(Node rootNode)
    {
        Debug.Log("SELECTING");
        Node node = new Node();
        node = rootNode;

        while (node.getChildren().Count != 0) // checking if terminal
        {
            findBestNodeWithUCT(node);
        }

        return node;
    }

    Node findBestNodeWithUCT( Node root)
    {
        double j = 0;
        int bestIndex = 0; ;

        for (int i = 0; i < root.getChildren().Count; i++)
        {
            if (root.getChildren()[i].getVisitTimes() / root.getChildren()[i].getResult() > j)
            {
                j = root.getChildren()[i].getVisitTimes() / root.getChildren()[i].getResult();
                bestIndex = i;
                Debug.Log("BEST INDEX : " + bestIndex);
            }
        }

        Node bestOption = root.getChildren()[bestIndex];
        Debug.Log("BEST OPTION RETURN X/Y : " + bestOption.x + "/" + bestOption.y);

        return bestOption;
    }

    private void expandNode(Node node)
    {
        Debug.Log("Start EXPANSION");
        bool vert = false;
        bool hori = false;

    //Phase I : creating new Node
        //create a new node wit certain action A
        Node newNode = new Node();
        //init and setting parent 
        newNode.parent[0] = node;
        //init gamefield into node
        newNode.CurrentField_V = node.CurrentField_V;
        newNode.CurrentField_H = node.CurrentField_H;
        //init and setting child parent relationship
        newNode.visitTimes++;
        Debug.Log("ERSTELLE NEUEN KNOTEN");

     //Phase II : Validating Action
        //create a action a which leads to the expansion
        int x = UnityEngine.Random.Range(0,4);
        int y = UnityEngine.Random.Range(0, 4);
        //checking variables for valid coordinates
        Debug.Log("AKTION A IN EXPANSION :" + x + y);
        //Prechecking of generated coordinates to set corresponding obj
        if (y < 3)
        {
            vert = true;
        }
        if (x < 3 )
        {
            hori = true;
        }
        else if (x == 3 && y == 3)
        {
            Debug.Log(" OUT OF BOUNDS :NEW RANDOM");
            expandNode(node);

        }

     //Phase III : Doing Action
        if(vert && newNode.CurrentField_V[x, y].tag == "is play" && hori && newNode.CurrentField_H[x, y].tag != "is play")
        {
            expandNode(node);
        }
        //setting choice into sim gamefield with green color
        if (vert && newNode.CurrentField_V[x, y].tag != "is play")// && GameBoard.sim_vertical_line[x, y].tag != "is play")
        {
            Debug.Log("SETZEN DER VERTIKALEN AKTION IN KNOTENSTATE");
            GameBoard.sim_vertical_line[x, y].tag = "is play";
            GameBoard.sim_vertical_line[x, y].GetComponent<SpriteRenderer>().sprite = greenV;
          //  newNode.CurrentField_V[x, y].tag = "is play";
            newNode.x = x;
            newNode.y = y;
            node.nodeChildren.Add(newNode);

        }
        if (hori && newNode.CurrentField_H[x, y].tag != "is play" )//&& GameBoard.sim_horizontal_line[x, y].tag != "is play")
        {
            Debug.Log("SETZEN DER HORIZONTALEN AKTION IN KNOTENSTATE");
            GameBoard.sim_horizontal_line[x, y].tag = "is play";
            GameBoard.sim_horizontal_line[x, y].GetComponent<SpriteRenderer>().sprite = greenH;
          //  newNode.CurrentField_H[x, y].tag = "is play";
            newNode.x = x;
            newNode.y = y;
            node.nodeChildren.Add(newNode);

        }
        else { expandNode(node); }
    }

    private void backPropogation(Node nodeToExplore)
    {
        Node tempNode = nodeToExplore;
        Debug.Log("BACKPROPAGATION");
        while (tempNode != null)
        {
            int i = 0;

            if (i % 2 == 0)
            {
                tempNode.visitTimes++;
                int j = tempNode.result;
                tempNode.setResult(j);
                tempNode = tempNode.getParent();
            }
            else if (i % 2 != 0)
            {
                tempNode.visitTimes++;
                int j = tempNode.result;
                tempNode.setResult(j * -1);
                tempNode = tempNode.getParent();
            }
            i++;
        }
    }