minimaxab

using System;
using System.Collections.Generic;
using UnityEngine;

public class AIAlphaBeta : AIPlayer
{
    //? WHITE = MIN PLAYER +inf
    //? BLACK = MAX PLAYER -inf

    GameManager gameManager;
    int maxDepth;
    int aiHeuristic;
    Builder AiBuilder;
    Square AiMove;
    Square AiBuild;
    bool playerSearching;

    //int iterations = 0;

    public AIAlphaBeta(GameManager gm, int aiDepth, int heuristicType) : base(gm, aiDepth, heuristicType)
    {
        gameManager = gm;
        maxDepth = aiDepth;
        aiHeuristic = heuristicType;
    }

    protected override (Builder, Square) GenerateMove()
    {
        //Generate move and build for AI
        (Builder, Square, Square) AiTurn = getAiMove(gameManager.Board, gameManager.playerTurn);
        //stores values to be used during correct stages of game
        AiBuilder = AiTurn.Item1;
        AiMove = AiTurn.Item2;
        AiBuild = AiTurn.Item3;

        //Return Move
        return (AiBuilder, AiMove);
    }

    protected override Square GenerateBuild()
    {
        //Return build generated previously
        return (AiBuild);
    }

    public (Builder, Square, Square) getAiMove(Board board, bool team)
    {
        //set best score to +/- inf depending on team
        int bestScore = team ? int.MinValue : int.MaxValue;
        playerSearching = team;

        //generate all possible moves for team from current position
        List<(Builder, Square)> moves = board.FindTeamMoves(team);
        //create best move and builds (start as null)
        (Builder, Square) bestMove = (null, null);
        Square bestBuild = null;

        //loop through every move generated, each returning a score, where the best score/move will be selected
        foreach ((Builder,Square) move in moves)
        {
            // create copy of board and builder, copy move on new board
            Board boardCopy = board.CopyBoard();
            Builder builderCopy = boardCopy.squares[(int)move.Item1.BuilderSquare.Pos.x, (int)move.Item1.BuilderSquare.Pos.y].OccupiedBuilder;
            Square moveCopy = boardCopy.squares[(int)move.Item2.Pos.x, (int)move.Item2.Pos.y];

            int score = 0;

            //make move on new board
            boardCopy.MakeMove(builderCopy, moveCopy);

            //find all possible builds from new position
            List<Square> builds = boardCopy.FindBuilds(builderCopy.BuilderSquare.Pos);

            //loop through all possible builds
            foreach (Square build in builds)
            {
                // create another copy of board to try every possible build
                Board boardCopyTwo = boardCopy.CopyBoard();
                Square buildCopy = boardCopyTwo.squares[(int)build.Pos.x, (int)build.Pos.y];

                //make build on new board
                boardCopyTwo.Build(buildCopy);

                //call minimaxAB to generate a score
                score = MinimaxAB(boardCopyTwo, maxDepth, !team, int.MinValue, int.MaxValue);

                //if minimax returns a score better than current, replace best score
                //black team is aiming for a score as high as possible while white team is aimijng for a score as low as possible
                if ((team && score > bestScore) || (!team && score < bestScore))
                {
                    //update score, move and build
                    bestScore = score;
                    bestMove = move;
                    bestBuild = board.squares[(int)build.Pos.x, (int)build.Pos.y];
                }
            }
        }
        //format move and build to be returned
        (Builder, Square, Square) AiTurn = (bestMove.Item1, bestMove.Item2, bestBuild);
        return AiTurn;
    }

    //Minimax algorithm with Alpha Beta Pruning enabled
    public int MinimaxAB(Board board, int depth, bool maximizingPlayer, int alpha, int beta)
    {
        //? WHITE = MIN PLAYER +inf
        //? BLACK = MAX PLAYER -inf

        bool checkWinVal = board.CheckWin(!maximizingPlayer);
        bool checkLossVal = board.CheckLoss(maximizingPlayer);

        if (checkWinVal || checkLossVal || depth == 0)
        {
            //generate score for given board position and return
            if (aiHeuristic == 0)
            {
                return board.BasicEvaluation(maximizingPlayer, checkLossVal, depth);
            }
            else if (aiHeuristic == 1)
            {
                return board.evaluateBoard(maximizingPlayer, checkLossVal);
            }
        }

        if (maximizingPlayer) //MAX PLAYER (BLACK) TURN
        {
            //set best move to negative inf
            int maxScore =  int.MinValue;
            //Generate every possible move for black team
            List<(Builder, Square)> moves = board.FindTeamMoves(true);

            // Check every possible move at this depth
            foreach ((Builder, Square) move in moves)
            {
                Board boardCopy = board.CopyBoard();
                Builder builderCopy = boardCopy.squares[(int)move.Item1.BuilderSquare.Pos.x, (int)move.Item1.BuilderSquare.Pos.y].OccupiedBuilder;
                Square moveCopy = boardCopy.squares[(int)move.Item2.Pos.x, (int)move.Item2.Pos.y];

                boardCopy.MakeMove(builderCopy, moveCopy);

                List<Square> builds = boardCopy.FindBuilds(builderCopy.BuilderSquare.Pos);

                foreach (Square build in builds)
                {
                    Board boardCopyTwo = boardCopy.CopyBoard();
                    Square buildCopy = boardCopyTwo.squares[(int)build.Pos.x, (int)build.Pos.y];

                    boardCopyTwo.Build(buildCopy);

                    //recursively call Minimax (flip flopping between players until max depth reached)
                    int score = MinimaxAB(boardCopyTwo, depth - 1, false, alpha, beta);

                    //get max score
                    maxScore = Math.Max(maxScore, score);

                    alpha = Math.Max(alpha, score);

                    if (beta <= alpha) break;
                }

                if (beta <= alpha) break;
            }
            return maxScore;
        }
        else //MIN PLAYER (WHITE) TURN
        {
            // set best move to pos inf
            int minScore =  int.MaxValue;
            //Generate every possible move for white team
            List<(Builder, Square)> moves = board.FindTeamMoves(false);

            // Check every possible move at this depth
            foreach ((Builder, Square) move in moves)
            {
                Board boardCopy = board.CopyBoard();
                Builder builderCopy = boardCopy.squares[(int)move.Item1.BuilderSquare.Pos.x, (int)move.Item1.BuilderSquare.Pos.y].OccupiedBuilder;
                Square moveCopy = boardCopy.squares[(int)move.Item2.Pos.x, (int)move.Item2.Pos.y];

                boardCopy.MakeMove(builderCopy, moveCopy);

                List<Square> builds = boardCopy.FindBuilds(builderCopy.BuilderSquare.Pos);

                foreach (Square build in builds)
                {
                    Board boardCopyTwo = boardCopy.CopyBoard();
                    Square buildCopy = boardCopyTwo.squares[(int)build.Pos.x, (int)build.Pos.y];

                    boardCopyTwo.Build(buildCopy);

                    int score = MinimaxAB(boardCopyTwo, depth - 1, true, alpha, beta);

                    minScore = Math.Min(minScore, score);

                    beta = Math.Min(beta, score);

                    if (beta <= alpha) break;
                }

                if (beta <= alpha) break;
            }
            return minScore;
        }
    }
}

/*
function alphabeta(node, depth, α, β, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            α := max(α, value)
            if value ≥ β then
                break (* β cutoff *)
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            β := min(β, value)
            if value ≤ α then
                break (* α cutoff *)
        return value
*/