MrSpaceCow

MCTS

Jul 17th, 2017
94
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System.Collections;
  2. using System.Collections.Generic;
  3. using UnityEngine;
  4. using System.Linq;
  5.  
  6. public class MCTS : MonoBehaviour {
  7.     private static System.Random rnd = new System.Random();
  8.     const float WIN_POINTS = 2.0f;
  9.     int t = 0;
  10.  
  11.     // Use this for initialization
  12.     void Start () {
  13.        
  14.     }
  15.    
  16.     // Update is called once per frame
  17.     void Update () {
  18.        
  19.     }
  20.  
  21.     Section[,] input(Section[,] original, Vector2[] move, Turn turn) {
  22.         Section[,] newBoard = new Section[3, 3];
  23.         for(int i = 0; i < 3; i++) {
  24.             for(int j = 0; j < 3; j++) {
  25.                 newBoard[i, j] = GameManager.cloneSection(original[i, j]);
  26.             }
  27.         }
  28.  
  29.         newBoard[0, 0].metaData.isBeingChallenged = false;
  30.         newBoard[0, 0].metaData.lastMove = move;
  31.  
  32.         switch(getSection(original, move).state) {
  33.             case States.Empty:
  34.                 getSection(newBoard, move).state = (turn == Turn.X) ? States.X : States.O;
  35.                 if(move.Length > 1) {
  36.                     t++;
  37.                     switch((int)analyzeState(getSection(newBoard, GameManager.dropASection(move)).sectionsInsideSection, turn)) {
  38.                         case 0:
  39.                             break;
  40.                         case (int)WIN_POINTS:
  41.                             Section sect = getSection(newBoard, GameManager.dropASection(move));
  42.                             sect.state = (turn == Turn.X) ? States.X : States.O;
  43.                             sect.sectionsInsideSection = null;
  44.                             break;
  45.                         case (int)-WIN_POINTS:
  46.                             sect = getSection(newBoard, GameManager.dropASection(move));
  47.                             sect.state = (turn == Turn.X) ? States.O : States.X;
  48.                             sect.sectionsInsideSection = null;
  49.                             break;
  50.                         case -1:
  51.                             sect = getSection(newBoard, GameManager.dropASection(move));
  52.                             sect.state = States.Empty;
  53.                             sect.sectionsInsideSection = null;
  54.                             break;
  55.                     }
  56.                 }
  57.                 break;
  58.             case States.X:
  59.                 Section section = getSection(newBoard, move);
  60.                 section.state = States.Board;
  61.                 section.sectionsInsideSection = new Section[3, 3];
  62.                 for(int i = 0; i < 3; i++) {
  63.                     for(int j = 0; j < 3; j++) {
  64.                         section.sectionsInsideSection[i, j] = new Section();
  65.                     }
  66.                 }
  67.                 newBoard[0, 0].metaData.isBeingChallenged = true;
  68.                 break;
  69.             case States.O:
  70.                 Section section2 = getSection(newBoard, move);
  71.                 section2.state = States.Board;
  72.                 section2.sectionsInsideSection = new Section[3, 3];
  73.                 for(int i = 0; i < 3; i++) {
  74.                     for(int j = 0; j < 3; j++) {
  75.                         section2.sectionsInsideSection[i, j] = new Section();
  76.                     }
  77.                 }
  78.                 newBoard[0, 0].metaData.isBeingChallenged = true;
  79.                 break;
  80.         }
  81.  
  82.         return newBoard;
  83.     }
  84.  
  85.     public List<Section[,]> generateMoves(Section[,] board, Vector2[] baseVector, Turn turn, bool recursive = false) {
  86.         if(board[0, 0].metaData == null)
  87.             board[0, 0].metaData = new MetaData();
  88.  
  89.         if(!board[0,0].metaData.isBeingChallenged || recursive) {
  90.             List<Section[,]> moves = new List<Section[,]>();
  91.             Section baseSection = getSection(board, baseVector);
  92.             for(int i = 0; i < 3; i++) {
  93.                 for(int j = 0; j < 3; j++) {
  94.                     States state = baseSection.sectionsInsideSection[i, j].state;
  95.                     if(state == States.Empty || ((state == States.O || state == States.X) && baseVector.Length + 1 < GameManager.MAXLAYER && board[0, 0].metaData.lastMove.SequenceEqual(GameManager.addASection(baseVector, new Vector2(i, j))))) {
  96.                         Section[,] move = input(board, GameManager.addASection(baseVector, new Vector2(i, j)), turn);
  97.                         //If there is a move that will win the player the game, only return that move
  98.                         if(analyzeState(move, turn) == WIN_POINTS) {
  99.                             moves.Clear();
  100.                             moves.Add(move);
  101.                             return moves;
  102.                         }
  103.                         moves.Add(move);
  104.                     } else if(state == States.Board) {
  105.                         moves.AddRange(generateMoves(board, GameManager.addASection(baseVector, new Vector2(i, j)), turn));
  106.                     }
  107.                 }
  108.             }
  109.             return moves;
  110.         }else {
  111.             return generateMoves(board, board[0, 0].metaData.lastMove, turn, true);
  112.         }
  113.     }
  114.  
  115.     public float analyzeState(Section[,] board, Turn perspective) {
  116.         //If is win State, return points based on perspective
  117.         for(int i = 0; i < 3; i++) {
  118.             if(GameManager.threequal(board[i, 0].state, board[i, 1].state, board[i, 2].state, States.X))
  119.                 return (perspective == Turn.X) ? WIN_POINTS : -WIN_POINTS;
  120.             if(GameManager.threequal(board[i, 0].state, board[i, 1].state, board[i, 2].state, States.O))
  121.                 return (perspective == Turn.O) ? WIN_POINTS : -WIN_POINTS;
  122.             if(GameManager.threequal(board[0, i].state, board[1, i].state, board[2, i].state, States.X))
  123.                 return (perspective == Turn.X) ? WIN_POINTS : -WIN_POINTS;
  124.             if(GameManager.threequal(board[0, i].state, board[1, i].state, board[2, i].state, States.O))
  125.                 return (perspective == Turn.O) ? WIN_POINTS : -WIN_POINTS;
  126.         }
  127.         if(GameManager.threequal(board[0, 0].state, board[1, 1].state, board[2, 2].state, States.X))
  128.             return (perspective == Turn.X) ? WIN_POINTS : -WIN_POINTS;
  129.         if(GameManager.threequal(board[0, 0].state, board[1, 1].state, board[2, 2].state, States.O))
  130.             return (perspective == Turn.O) ? WIN_POINTS : -WIN_POINTS;
  131.         if(GameManager.threequal(board[0, 2].state, board[1, 1].state, board[2, 0].state, States.X))
  132.             return (perspective == Turn.X) ? WIN_POINTS : -WIN_POINTS;
  133.         if(GameManager.threequal(board[0, 2].state, board[1, 1].state, board[2, 0].state, States.O))
  134.             return (perspective == Turn.O) ? WIN_POINTS : -WIN_POINTS;
  135.  
  136.         //If not tie, return 0 points
  137.         for(int i = 0; i < 3; i++)
  138.             for(int j = 0; j < 3; j++)
  139.                 if(board[i, j].state == States.Empty || board[i, j].state == States.Board)
  140.                     return 0;
  141.  
  142.         //If tie, return -1 points
  143.         return -1;
  144.     }
  145.  
  146.     public Section[,] mcts(State tree, int iterations) {
  147.         for(int i = 0; i < iterations; i++) {
  148.             //Selection
  149.             State selection = select(tree);
  150.  
  151.             //Expansion
  152.             State node = expand(selection);
  153.  
  154.             //Simulation
  155.             float value = simulate(node, tree.turn);
  156.  
  157.             //Back-propagation
  158.             backPropogate(node, value);
  159.         }
  160.  
  161.         //Find move with highest score
  162.         float best = float.MinValue;
  163.         Section[,] bestMove = null;
  164.  
  165.         for(int i = 0; i < tree.getChildren().Count; i++) {
  166.             if(tree.getChild(i).totalVal / tree.getChild(i).visits > best) {
  167.                 best = tree.getChild(i).totalVal / tree.getChild(i).visits;
  168.                 bestMove = tree.getChild(i).state;
  169.             }
  170.         }
  171.  
  172.         return bestMove;
  173.     }
  174.  
  175.     State select(State tree) {
  176.         int numOfChildren = tree.getChildren().Count;
  177.  
  178.         //If State is leaf node, select it
  179.         if(numOfChildren == 0)
  180.             return tree;
  181.  
  182.         //Otherwise find State with highest UCB1
  183.         float best = float.MinValue;
  184.         State selection = null;
  185.  
  186.         for(int i = 0; i < numOfChildren; i++) {
  187.             if(tree.getChild(i).getUCB1() > best) {
  188.                 best = tree.getChild(i).getUCB1();
  189.                 selection = tree.getChild(i);
  190.             }
  191.         }
  192.  
  193.         //and then select from that State's children
  194.         selection = select(selection);
  195.  
  196.         return selection;
  197.     }
  198.  
  199.     State expand(State node) {
  200.         //If is an end state just return it
  201.         if(analyzeState(node.state, node.turn) != 0)
  202.             return node;
  203.  
  204.         //Add every possible move as a child to the node
  205.         List<Section[,]> moves = generateMoves(node.state, new Vector2[0], node.turn);
  206.         for(int i = 0; i < moves.Count; i++) {
  207.             node.addChild(new State(moves[i], node, (node.turn == Turn.X) ? Turn.O : Turn.X));
  208.         }
  209.  
  210.         //Pick a random child and select it
  211.         return node.getChild((Mathf.FloorToInt((float)rnd.NextDouble() * node.getChildren().Count)));
  212.         //return node.getChild((Mathf.FloorToInt(Random.Range(0, node.getChildren().Count))));
  213.     }
  214.  
  215.     float simulate(State node, Turn turnMax) {
  216.         Section[,] currentState = new Section[3, 3];
  217.         for(int i = 0; i < 3; i++) {
  218.             for(int j = 0; j < 3; j++) {
  219.                 currentState[i, j] = GameManager.cloneSection(node.state[i, j]);
  220.             }
  221.         }
  222.         Turn currentTurn = node.turn;
  223.  
  224.         //While the simulation is not in an end state
  225.         while(analyzeState(currentState, turnMax) == 0) {
  226.             //Pick a random move from possible moves and go from there
  227.             List<Section[,]> moves = generateMoves(currentState, new Vector2[0], currentTurn);
  228.             currentState = moves[Mathf.FloorToInt((float)rnd.NextDouble() * moves.Count)];
  229.             //currentState = (Section[,])moves[Mathf.FloorToInt(Random.Range(0, moves.Count))];
  230.             currentTurn = (currentTurn == Turn.X) ? Turn.O : Turn.X;
  231.         }
  232.  
  233.         float value = analyzeState(currentState, turnMax);
  234.  
  235.         return value;
  236.     }
  237.  
  238.     void backPropogate(State node, float value) {
  239.         bool reachedRoot = false;
  240.  
  241.         //For ever node until the root add the value to the node and increment visits;
  242.         while(!reachedRoot) {
  243.             node.totalVal += value;
  244.             node.visits++;
  245.  
  246.             if(node.parent != null) {
  247.                 node = node.parent;
  248.             }else {
  249.                 reachedRoot = true;
  250.             }
  251.         }
  252.     }
  253.  
  254.     public Section getSection(Section[,] sections, Vector2[] sects) {
  255.         if(sects.Length == 0) {
  256.             Section section = new Section();
  257.             section.sectionsInsideSection = sections;
  258.             return section;
  259.         } else {
  260.             Section section = sections[(int)sects[0].x, (int)sects[0].y];
  261.             for(int i = 1; i < sects.Length; i++) {
  262.                 section = section.sectionsInsideSection[(int)sects[i].x, (int)sects[i].y];
  263.             }
  264.             return section;
  265.         }
  266.     }
  267. }
  268.  
  269. public class State {
  270.     public Section[,] state;
  271.     public float totalVal = 0;
  272.     public float visits = 0.0000001f;
  273.     public State parent;
  274.     List<State> children = new List<State>();
  275.     public Turn turn;
  276.  
  277.     public State(Section[,] state, State parent, Turn turn) {
  278.         this.state = state;
  279.         this.parent = parent;
  280.         this.turn = turn;
  281.     }
  282.  
  283.     public void addChild(State child) {
  284.         children.Add(child);
  285.     }
  286.  
  287.     public List<State> getChildren() {
  288.         return children;
  289.     }
  290.  
  291.     public State getChild(int index) {
  292.         return children[index];
  293.     }
  294.  
  295.     public float getUCB1() {
  296.         return totalVal / visits + Mathf.Sqrt((2 * Mathf.Log(parent.visits)) / visits);
  297.     }
  298. }
RAW Paste Data