SHARE
TWEET

Untitled

a guest Sep 22nd, 2019 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. public class Player {
  4.     public final int PLAYER_A = 1;
  5.     public final int PLAYER_B = 2;
  6.     public final int MAXDEPTH = 2;
  7.     private static int[][] winningStates = getWinningStates();
  8.     private HashMap<Integer[], Integer> visitedStates = new HashMap<Integer[], Integer>();
  9.     private HashMap<GameState, Integer> state2val = new HashMap<GameState, Integer>();
  10.     /**
  11.      * Performs a move
  12.      *
  13.      * @param gameState
  14.      *            the current state of the board
  15.      * @param deadline
  16.      *            time before which we must have returned
  17.      * @return the next state the board is in after our move
  18.      */
  19.     public GameState play(final GameState gameState, final Deadline deadline) {
  20.         Vector<GameState> nextStates = new Vector<GameState>();
  21.         gameState.findPossibleMoves(nextStates);
  22.         long roundStartTime = Deadline.getCpuTime();
  23.         //System.err.println("TIME AT START: " + roundStartTime);
  24.         if (nextStates.size() == 0) {
  25.             // Must play "pass" move if there are no other moves possible.
  26.             return new GameState(gameState, new Move());
  27.         }
  28.  
  29.         /**
  30.          * Here you should write your algorithms to get the best next move, i.e.
  31.          * the best next state. This skeleton returns a random move instead.
  32.          */
  33.         GameState maxMove = new GameState();
  34.         int max = Integer.MIN_VALUE;
  35.         for (GameState child : nextStates) {
  36.             int value = miniMax(child, 0, Integer.MIN_VALUE, Integer.MAX_VALUE, PLAYER_B, deadline, deadline.timeUntil());
  37.             if (value > max) {
  38.                 max = value;
  39.                 maxMove = child;
  40.             }
  41.             long timePassed = Deadline.getCpuTime() - roundStartTime;
  42.             //if (timePassed >= 6000000) {System.err.println("\nBREAKING!!\n");break;}
  43.             //if (Deadline.getCpuTime() - roundStartTime >= 590000) break;
  44.         }
  45.         long timePassed = Deadline.getCpuTime() - roundStartTime;
  46.         //System.err.println("time passed: " + timePassed / 1000000);
  47.         //Random random = new Random();
  48.         //return nextStates.elementAt(random.nextInt(nextStates.size()));
  49.         //System.err.println("TIME AT END: " + Deadline.getCpuTime() + " time passed = " + (Deadline.getCpuTime() - roundStartTime));
  50.         return maxMove;
  51.     }
  52.  
  53.     int heuristic(GameState S, int player) {
  54.  
  55.         //We check the diagonal
  56.         if (S.isEOG()) {
  57.             if (S.isXWin()) return Integer.MAX_VALUE;
  58.             if (S.isOWin()) return Integer.MIN_VALUE;
  59.             return 0; // if tie
  60.         }
  61.  
  62.         int score = 0;
  63.         for (int i = 0; i < winningStates.length; i++) {
  64.             int countPlayerA = 0;
  65.             int countPlayerB = 0;
  66.             for (int j = 0; j < GameState.BOARD_SIZE; j++) {
  67.                 if (S.at(winningStates[i][j]) == Constants.CELL_X) countPlayerA++;
  68.                 if (S.at(winningStates[i][j]) == Constants.CELL_O) countPlayerB++;
  69.             }
  70.             if (countPlayerB == 0) {
  71.                 score += countPlayerA == 0 ? 0 : Math.pow(10, countPlayerA);
  72.             }
  73.             if (countPlayerA == 0) {
  74.                 score -= countPlayerB == 0 ? 0 : Math.pow(10, countPlayerB);
  75.             }
  76.         }
  77.         return score;
  78.     }
  79.    
  80.     int miniMax(GameState S, int depth, int alpha, int beta, int player, Deadline deadline, long timeLeft) {
  81.         // state: the current state we are analyzing
  82.         // alpha: the current best value achievable by A
  83.         // beta: the current best value achievable by B
  84.         // player: the current player
  85.         // returns the minimax value of the state
  86.         Vector<GameState> nextStates = new Vector<GameState>();
  87.         S.findPossibleMoves(nextStates);
  88.         //System.err.println("depth: " + depth + ", alpha = " + alpha + ", beta = " + beta + ", children: " + nextStates.size());
  89.         int value = 0;
  90.         long ttot = deadline.timeUntil();
  91.         double keepGoing = ttot - (ttot / (Math.pow(timeLeft, depth))); // this must be less than time left
  92.  
  93.         if (depth >= MAXDEPTH || nextStates.size() == 0 || keepGoing < deadline.timeUntil()) {
  94.             // terminal state
  95.             //System.err.println("reached terminal state with depth = " + depth + ", possible states: " + nextStates.size());
  96.             value = heuristic(S, player); // gamma
  97.             //return value;
  98.         } else if (player == PLAYER_A) {
  99.             value = Integer.MIN_VALUE;
  100.             for (GameState child : nextStates) {
  101.                 value = Math.max(value, miniMax(child, depth + 1, alpha, beta, PLAYER_B, deadline, deadline.timeUntil()));
  102.                 alpha = Math.max(alpha, value);
  103.                 if (beta <= alpha) break;
  104.             }
  105.            
  106.         } else if (player == PLAYER_B) {
  107.             value = Integer.MAX_VALUE;
  108.             for (GameState child : nextStates) {
  109.                 value = Math.min(value, miniMax(child, depth + 1, alpha, beta, PLAYER_A, deadline, deadline.timeUntil()));
  110.                 beta = Math.min(beta, value);
  111.                 if (beta <= alpha) break;
  112.             }
  113.         }
  114.  
  115.         return value;
  116.     }
  117.  
  118.     static int[][] getWinningStates() {
  119.        
  120.         ArrayList<int[]> arr = new ArrayList<int[]>();
  121.         int[][] winningStates = new int[76][GameState.BOARD_SIZE];
  122.         int index = 0;
  123.         for (int row = 0; row < GameState.BOARD_SIZE; row++) {
  124.             for (int col = 0; col < GameState.BOARD_SIZE; col++) {
  125.                 int[] winLayer = new int[GameState.BOARD_SIZE];
  126.                 for (int layer = 0; layer < GameState.BOARD_SIZE; layer++) {
  127.                     winLayer[layer] = GameState.rowColumnLayerToCell(row, col, layer);
  128.                 }
  129.                 winningStates[index++] = winLayer;
  130.                
  131.                 arr.add(winLayer);
  132.                
  133.             }
  134.         }
  135.  
  136.         for (int row = 0; row < GameState.BOARD_SIZE; row++) {
  137.             for (int layer = 0; layer < GameState.BOARD_SIZE; layer++) {
  138.                 int[] winCol = new int[GameState.BOARD_SIZE];
  139.                 for (int col = 0; col < GameState.BOARD_SIZE; col++) {
  140.                     winCol[col] = GameState.rowColumnLayerToCell(row, col, layer);
  141.                 }
  142.                 winningStates[index++] = winCol;
  143.                 arr.add(winCol);
  144.             }
  145.         }
  146.  
  147.         for (int layer = 0; layer < GameState.BOARD_SIZE; layer++) {
  148.             for (int col = 0; col < GameState.BOARD_SIZE; col++) {
  149.                 int[] winLayer = new int[GameState.BOARD_SIZE];
  150.                 for (int row = 0; row < GameState.BOARD_SIZE; row++) {
  151.                     winLayer[row] = GameState.rowColumnLayerToCell(row, col, layer);
  152.                 }
  153.                 winningStates[index++] = winLayer;
  154.                
  155.             }
  156.         }
  157.  
  158.         // Diagonals along the row-dimension
  159.  
  160.         for (int row = 0; row < GameState.BOARD_SIZE; row++) {
  161.             int[] rowDiag = new int[GameState.BOARD_SIZE];
  162.             //System.err.println("row diagonals: ");
  163.             for (int diag = 0; diag < GameState.BOARD_SIZE; diag++) {
  164.                 rowDiag[diag] = GameState.rowColumnLayerToCell(row, diag, diag);
  165.                 //System.err.print(rowDiag[diag] + " ");
  166.             }
  167.             //System.err.println();
  168.             winningStates[index++] = rowDiag;
  169.         }
  170.  
  171.         // Row diagonal opposite
  172.  
  173.         for (int row = 0; row < GameState.BOARD_SIZE; row++) {
  174.             //int colIdx = GameState.BOARD_SIZE - 1;
  175.             int colIdx = 0;
  176.             //System.err.println("opp row diagonals: ");
  177.             int[] rowDiag = new int[GameState.BOARD_SIZE];
  178.             int layerIdx = GameState.BOARD_SIZE - 1;
  179.             for (int i = 0; i < GameState.BOARD_SIZE; i++) {
  180.                 rowDiag[i] = GameState.rowColumnLayerToCell(row, colIdx++, layerIdx--);
  181.                 //System.err.print(rowDiag[i] + " ");
  182.             }
  183.             //System.err.println();
  184.             winningStates[index++] = rowDiag;
  185.         }
  186.  
  187.         // Col diagonal
  188.        
  189.         for (int col = 0; col < GameState.BOARD_SIZE; col++) {
  190.             int[] colDiag = new int[GameState.BOARD_SIZE];
  191.             //System.err.println("col diagonals: ");
  192.             int rowidx = 0;//GameState.BOARD_SIZE - 1;
  193.             int layeridx = 0;//GameState.BOARD_SIZE - 1;
  194.             for (int i = 0; i < GameState.BOARD_SIZE; i++) {
  195.                 colDiag[i] = GameState.rowColumnLayerToCell(rowidx++, col, layeridx++);
  196.                 //System.err.print(colDiag[i] + " ");
  197.             }
  198.             //System.err.println();
  199.             winningStates[index++] = colDiag;
  200.         }
  201.  
  202.         // Col diagonal opposite
  203.         for (int col = 0; col < GameState.BOARD_SIZE; col++) {
  204.             int[] colDiag = new int[GameState.BOARD_SIZE];
  205.             int rowidx = 0;//GameState.BOARD_SIZE - 1;
  206.             int layeridx = GameState.BOARD_SIZE - 1;
  207.             //System.err.println("opp col diagoals: ");
  208.             for (int i = 0; i < GameState.BOARD_SIZE; i++) {
  209.                 colDiag[i] = GameState.rowColumnLayerToCell(rowidx++, col, layeridx--);
  210.                 //System.err.print(colDiag[i] + " ");
  211.             }
  212.             winningStates[index++] = colDiag;
  213.             //System.err.println();
  214.         }
  215.  
  216.         // layer diagonal
  217.         for (int layer = 0; layer < GameState.BOARD_SIZE; layer++) {
  218.             int[] layerDiag = new int[GameState.BOARD_SIZE];
  219.             //System.err.println("Layer diagonals:");
  220.             for (int diag = 0; diag < GameState.BOARD_SIZE; diag++) {
  221.                 layerDiag[diag] = GameState.rowColumnLayerToCell(diag, diag, layer);
  222.                 //System.err.print(layerDiag[diag] + " ");
  223.             }
  224.             //System.err.println();
  225.             winningStates[index++] = layerDiag;
  226.         }
  227.  
  228.         // Layer diagonal opposite
  229.  
  230.         for (int layer = 0; layer < GameState.BOARD_SIZE; layer++) {
  231.             int[] layerDiag = new int[GameState.BOARD_SIZE];
  232.             //System.err.println("opp layer diags: ");
  233.             int rowidx = 0;
  234.             int colidx = GameState.BOARD_SIZE - 1;
  235.             for (int i = 0; i < GameState.BOARD_SIZE; i++) {
  236.                 layerDiag[i] = GameState.rowColumnLayerToCell(rowidx++, colidx--, layer);
  237.                 //System.err.print(layerDiag[i] + " ");
  238.             }
  239.             //System.err.println();
  240.             winningStates[index++] = layerDiag;
  241.         }
  242.  
  243.         //System.err.println("Before final 4: " + index);
  244.         // Finally the, 4 last solutions
  245.  
  246.         // Cross diagonal
  247.         int[] crossDiag0 = new int[GameState.BOARD_SIZE];
  248.         for (int diag = 0; diag < GameState.BOARD_SIZE; diag++) {
  249.             crossDiag0[diag] = GameState.rowColumnLayerToCell(diag, diag, diag);
  250.         }
  251.  
  252.         // cross diagonal opposite
  253.         int[] crossDiag1 = new int[GameState.BOARD_SIZE];
  254.         int idx = 0;
  255.         int col = GameState.BOARD_SIZE - 1;
  256.         int layer = 0;
  257.        
  258.         for (int row = 0; row < GameState.BOARD_SIZE; row++) {
  259.             crossDiag1[idx++] = GameState.rowColumnLayerToCell(row, col--, layer++);
  260.         }
  261.        
  262.        
  263.         col = 0;
  264.         int row = 0;
  265.         layer = GameState.BOARD_SIZE - 1;
  266.         int[] crossDiag2 = new int[GameState.BOARD_SIZE];
  267.  
  268.         for (int i = 0; i < GameState.BOARD_SIZE; i++) {
  269.             crossDiag2[i] = GameState.rowColumnLayerToCell(row++, col++, layer--);
  270.         }
  271.  
  272.  
  273.         col = 0;
  274.         row = GameState.BOARD_SIZE - 1;
  275.         layer = 0;
  276.         int[] crossDiag3 = new int[GameState.BOARD_SIZE];
  277.         for (int i = 0; i < GameState.BOARD_SIZE; i++) {
  278.             crossDiag3[i] = GameState.rowColumnLayerToCell(row--, col++, layer++);
  279.         }
  280.         winningStates[index++] = crossDiag0;
  281.         winningStates[index++] = crossDiag1;
  282.         winningStates[index++] = crossDiag2;
  283.         winningStates[index++] = crossDiag3;
  284.  
  285.         //for (int i = 0; i < 4; i++) {
  286.             //System.err.println("diag0 = " + crossDiag0[i] + ", diag1: " + crossDiag1[i] + ", diag2: " + crossDiag2[i] + ", diag4: " + crossDiag3[i]);
  287.         //}
  288.         /*
  289.         HashMap<int[], Integer> wins = new HashMap<int[], Integer>();
  290.         for (int i = 0; i < index; i++) {
  291.        
  292.             if (wins.containsKey(winningStates[i])) {
  293.                 System.err.print("double: idx = " + i);
  294.                 for (int x = 0; x < 4; x++) {
  295.                     System.err.print(winningStates[i][x] + " ");
  296.                 }
  297.                 System.err.println();
  298.             } else {
  299.                 wins.put(winningStates[i], 1);
  300.             }
  301.         }
  302.        
  303.         idx = 0;
  304.         System.err.println(" final index: " + index);
  305.         */
  306.         return winningStates;
  307.     }
  308. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top