Advertisement
Guest User

minimaxab

a guest
Apr 16th, 2023
29
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 8.43 KB | Source Code | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. using UnityEngine;
  4.  
  5. public class AIAlphaBeta : AIPlayer
  6. {
  7.     //? WHITE = MIN PLAYER +inf
  8.     //? BLACK = MAX PLAYER -inf
  9.    
  10.     GameManager gameManager;
  11.     int maxDepth;
  12.     int aiHeuristic;
  13.     Builder AiBuilder;
  14.     Square AiMove;
  15.     Square AiBuild;
  16.     bool playerSearching;
  17.  
  18.     //int iterations = 0;
  19.  
  20.     public AIAlphaBeta(GameManager gm, int aiDepth, int heuristicType) : base(gm, aiDepth, heuristicType)
  21.     {
  22.         gameManager = gm;
  23.         maxDepth = aiDepth;
  24.         aiHeuristic = heuristicType;
  25.     }
  26.  
  27.     protected override (Builder, Square) GenerateMove()
  28.     {
  29.         //Generate move and build for AI
  30.         (Builder, Square, Square) AiTurn = getAiMove(gameManager.Board, gameManager.playerTurn);
  31.         //stores values to be used during correct stages of game
  32.         AiBuilder = AiTurn.Item1;
  33.         AiMove = AiTurn.Item2;
  34.         AiBuild = AiTurn.Item3;
  35.  
  36.         //Return Move
  37.         return (AiBuilder, AiMove);
  38.     }
  39.  
  40.     protected override Square GenerateBuild()
  41.     {
  42.         //Return build generated previously
  43.         return (AiBuild);
  44.     }
  45.  
  46.     public (Builder, Square, Square) getAiMove(Board board, bool team)
  47.     {
  48.         //set best score to +/- inf depending on team
  49.         int bestScore = team ? int.MinValue : int.MaxValue;
  50.         playerSearching = team;
  51.  
  52.         //generate all possible moves for team from current position
  53.         List<(Builder, Square)> moves = board.FindTeamMoves(team);
  54.         //create best move and builds (start as null)
  55.         (Builder, Square) bestMove = (null, null);
  56.         Square bestBuild = null;
  57.  
  58.         //loop through every move generated, each returning a score, where the best score/move will be selected
  59.         foreach ((Builder,Square) move in moves)
  60.         {
  61.             // create copy of board and builder, copy move on new board
  62.             Board boardCopy = board.CopyBoard();
  63.             Builder builderCopy = boardCopy.squares[(int)move.Item1.BuilderSquare.Pos.x, (int)move.Item1.BuilderSquare.Pos.y].OccupiedBuilder;
  64.             Square moveCopy = boardCopy.squares[(int)move.Item2.Pos.x, (int)move.Item2.Pos.y];
  65.  
  66.             int score = 0;
  67.            
  68.             //make move on new board
  69.             boardCopy.MakeMove(builderCopy, moveCopy);
  70.  
  71.             //find all possible builds from new position
  72.             List<Square> builds = boardCopy.FindBuilds(builderCopy.BuilderSquare.Pos);
  73.  
  74.             //loop through all possible builds
  75.             foreach (Square build in builds)
  76.             {
  77.                 // create another copy of board to try every possible build
  78.                 Board boardCopyTwo = boardCopy.CopyBoard();
  79.                 Square buildCopy = boardCopyTwo.squares[(int)build.Pos.x, (int)build.Pos.y];
  80.  
  81.                 //make build on new board
  82.                 boardCopyTwo.Build(buildCopy);
  83.  
  84.                 //call minimaxAB to generate a score
  85.                 score = MinimaxAB(boardCopyTwo, maxDepth, !team, int.MinValue, int.MaxValue);
  86.  
  87.                 //if minimax returns a score better than current, replace best score
  88.                 //black team is aiming for a score as high as possible while white team is aimijng for a score as low as possible
  89.                 if ((team && score > bestScore) || (!team && score < bestScore))
  90.                 {
  91.                     //update score, move and build
  92.                     bestScore = score;
  93.                     bestMove = move;
  94.                     bestBuild = board.squares[(int)build.Pos.x, (int)build.Pos.y];
  95.                 }
  96.             }
  97.         }
  98.         //format move and build to be returned        
  99.         (Builder, Square, Square) AiTurn = (bestMove.Item1, bestMove.Item2, bestBuild);
  100.         return AiTurn;
  101.     }
  102.  
  103.     //Minimax algorithm with Alpha Beta Pruning enabled
  104.     public int MinimaxAB(Board board, int depth, bool maximizingPlayer, int alpha, int beta)
  105.     {
  106.         //? WHITE = MIN PLAYER +inf
  107.         //? BLACK = MAX PLAYER -inf
  108.  
  109.         bool checkWinVal = board.CheckWin(!maximizingPlayer);
  110.         bool checkLossVal = board.CheckLoss(maximizingPlayer);
  111.        
  112.         if (checkWinVal || checkLossVal || depth == 0)
  113.         {
  114.             //generate score for given board position and return
  115.             if (aiHeuristic == 0)
  116.             {
  117.                 return board.BasicEvaluation(maximizingPlayer, checkLossVal, depth);
  118.             }
  119.             else if (aiHeuristic == 1)
  120.             {
  121.                 return board.evaluateBoard(maximizingPlayer, checkLossVal);
  122.             }        
  123.         }
  124.  
  125.         if (maximizingPlayer) //MAX PLAYER (BLACK) TURN
  126.         {
  127.             //set best move to negative inf
  128.             int maxScore =  int.MinValue;
  129.             //Generate every possible move for black team
  130.             List<(Builder, Square)> moves = board.FindTeamMoves(true);
  131.  
  132.             // Check every possible move at this depth
  133.             foreach ((Builder, Square) move in moves)
  134.             {
  135.                 Board boardCopy = board.CopyBoard();
  136.                 Builder builderCopy = boardCopy.squares[(int)move.Item1.BuilderSquare.Pos.x, (int)move.Item1.BuilderSquare.Pos.y].OccupiedBuilder;
  137.                 Square moveCopy = boardCopy.squares[(int)move.Item2.Pos.x, (int)move.Item2.Pos.y];
  138.  
  139.                 boardCopy.MakeMove(builderCopy, moveCopy);
  140.  
  141.                 List<Square> builds = boardCopy.FindBuilds(builderCopy.BuilderSquare.Pos);
  142.  
  143.                 foreach (Square build in builds)
  144.                 {
  145.                     Board boardCopyTwo = boardCopy.CopyBoard();
  146.                     Square buildCopy = boardCopyTwo.squares[(int)build.Pos.x, (int)build.Pos.y];
  147.  
  148.                     boardCopyTwo.Build(buildCopy);
  149.  
  150.                     //recursively call Minimax (flip flopping between players until max depth reached)
  151.                     int score = MinimaxAB(boardCopyTwo, depth - 1, false, alpha, beta);
  152.  
  153.                     //get max score
  154.                     maxScore = Math.Max(maxScore, score);
  155.  
  156.                     alpha = Math.Max(alpha, score);
  157.  
  158.                     if (beta <= alpha) break;
  159.                 }
  160.  
  161.                 if (beta <= alpha) break;
  162.             }
  163.             return maxScore;
  164.         }
  165.         else //MIN PLAYER (WHITE) TURN
  166.         {
  167.             // set best move to pos inf
  168.             int minScore =  int.MaxValue;
  169.             //Generate every possible move for white team
  170.             List<(Builder, Square)> moves = board.FindTeamMoves(false);
  171.  
  172.             // Check every possible move at this depth
  173.             foreach ((Builder, Square) move in moves)
  174.             {
  175.                 Board boardCopy = board.CopyBoard();
  176.                 Builder builderCopy = boardCopy.squares[(int)move.Item1.BuilderSquare.Pos.x, (int)move.Item1.BuilderSquare.Pos.y].OccupiedBuilder;
  177.                 Square moveCopy = boardCopy.squares[(int)move.Item2.Pos.x, (int)move.Item2.Pos.y];
  178.  
  179.                 boardCopy.MakeMove(builderCopy, moveCopy);
  180.  
  181.                 List<Square> builds = boardCopy.FindBuilds(builderCopy.BuilderSquare.Pos);
  182.  
  183.                 foreach (Square build in builds)
  184.                 {
  185.                     Board boardCopyTwo = boardCopy.CopyBoard();
  186.                     Square buildCopy = boardCopyTwo.squares[(int)build.Pos.x, (int)build.Pos.y];
  187.  
  188.                     boardCopyTwo.Build(buildCopy);
  189.  
  190.                     int score = MinimaxAB(boardCopyTwo, depth - 1, true, alpha, beta);
  191.                    
  192.                     minScore = Math.Min(minScore, score);
  193.  
  194.                     beta = Math.Min(beta, score);
  195.  
  196.                     if (beta <= alpha) break;
  197.                 }
  198.  
  199.                 if (beta <= alpha) break;
  200.             }
  201.             return minScore;
  202.         }
  203.     }
  204. }
  205.  
  206. /*
  207. function alphabeta(node, depth, α, β, maximizingPlayer) is
  208.     if depth = 0 or node is a terminal node then
  209.         return the heuristic value of node
  210.     if maximizingPlayer then
  211.         value := −∞
  212.         for each child of node do
  213.             value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
  214.             α := max(α, value)
  215.             if value ≥ β then
  216.                 break (* β cutoff *)
  217.         return value
  218.     else
  219.         value := +∞
  220.         for each child of node do
  221.             value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
  222.             β := min(β, value)
  223.             if value ≤ α then
  224.                 break (* α cutoff *)
  225.         return value
  226. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement