0
\$\begingroup\$

Disclaimer: First time trying to implement a AI using minimax approach (its a turn-based game). There are not many good resources available online to learn AI (specifically minimax in C#) so I am pretty sure I messed up somewhere as I was rewriting a example I found online.

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

public class GameController : MonoBehaviour {

    public const int tilesX = 14;
    public const int tilesY = 9;
    public int[,] board;

    public GameObject redObject;
    public GameObject blueObject;

    public int currentPlayer = 1;

    //For AI
    public const int maxDepth = 7;
    public const int orangeWins = 1000000;
    public const int yellowWins = -orangeWins;
    public Board aiBoard;
    public int scoreOrig;



    // Use this for initialization
    void Start () {
        board = new int[tilesY, tilesX];
        aiBoard = new Board();              //AI
        scoreOrig = ScoreBoard(aiBoard); //AI

    }

    // Update is called once per frame
    void Update()
    {
        if (getWinner() != 0)
        {
            return;
            //Game Over
        }
        if (Input.GetButtonDown("Fire1"))
        {
            //Translate mousePosition from screenSize to actual gameViewUnits
            Ray ray = Camera.main.ScreenPointToRay(Input.mousePosition);
            //Run below function only if mouseClick's X/Y are within tileGrid
            mousePressed(ray);
        }
    }

    void mousePressed(Ray ray)
    {
        Vector2 mouseClickVector = new Vector2(ray.origin.x,ray.origin.y);
        int mouseClickX = (int) mouseClickVector.x;
        //Debug.Log(mouseClickX);
        int y = findNextSpace(mouseClickX);
        //Debug.Log("Y: "+y);
        if (y>=0)
        {
            board[y,mouseClickX] = currentPlayer;
            dropDisk(aiBoard, mouseClickX, Mycell.Orange);   //AI
            //Spawn and animate the circleObject
            spawnPlayerObject(mouseClickX, y);

            //End and change turn
            changeTurn();
        }

    }

    int findNextSpace(int x)
    {
        for(int y=0; y<= tilesY - 1; y++)
        {

            if(board[y,x]==0)
            {
                return y;
            }
        }
        return -1;
    }

    void spawnPlayerObject(int x, int y)
    {
        float posX = (float) x + 0.5f; //center in x tile
        float posY = (float)y + 0.5f; //center in y tile
        GameObject g;
        if(currentPlayer==1)
        {
            g = Instantiate(redObject, new Vector3(posX, posY, 0), Quaternion.identity);
        }
        else
        {
            g = Instantiate(blueObject, new Vector3(posX, posY, 0), Quaternion.identity);
        }
    }

    void changeTurn()
    {
        currentPlayer = currentPlayer == 1 ? 2 : 1;
        //check winner
        getWinner();

        int move, score;
        abMinimax(true, Mycell.Orange, maxDepth, aiBoard, out move, out score);
        Debug.Log("Move: "+move+" | Score: "+score);
        Debug.Log(aiBoard);
    }

    int getWinner()    //From rows,columns and diagnoals
    {
        ////////////
        //Columns///
        ///////////
        for(int y=0; y<tilesY; y++)
        {
            for (int x=0; x<tilesX; x++)
            {
                if (checkTile(y,x)!=0 && checkTile(y, x) ==checkTile(y, x+1) && checkTile(y, x) == checkTile(y, x+2) && checkTile(y, x) == checkTile(y, x+3))
                {
                    Debug.Log("Won Columns: "+ checkTile(y, x));
                    return checkTile(y, x);
                }
            }
        }
        ////////
        //Rows//
        ////////
        for (int y = 0; y < tilesY; y++)
        {
            for (int x = 0; x < tilesX; x++)
            {
                if (checkTile(y, x) != 0 && checkTile(y, x) == checkTile(y+1, x) && checkTile(y, x) == checkTile(y+2, x) && checkTile(y, x) == checkTile(y+3, x))
                {
                    Debug.Log("Won Rows: " + checkTile(y, x));
                    return checkTile(y, x);
                }
            }
        }
        /////////////
        //Diagnoals//
        /////////////
        for (int y = 0; y < tilesY; y++)
        {
            for (int x = 0; x < tilesX; x++)
            {
                for (int d = -1; d <= 1; d += 2)
                {
                    if (checkTile(y, x) != 0 && checkTile(y, x) == checkTile(y + 1 * d, x+1) && checkTile(y, x) == checkTile(y + 2 *d, x+2) && checkTile(y, x) == checkTile(y + 3 *d, x+3))
                    {
                        Debug.Log("Won Diagnoals: " + checkTile(y, x));
                        return checkTile(y, x);
                    }
                }
            }
        }
        ///////////////////////////
        //Still possible turns/////
        //////////////////////////
        for (int y = 0; y < tilesY; y++)
        {
            for (int x = 0; x < tilesX; x++)
            {
                if (checkTile(y, x) == 0)
                {
                    //Debug.Log("Still Possible turns left");
                    return 0;
                }
            }
        }

        //draw is default
        return -1;
    }

    int checkTile(int y, int x)
    {
        return (y < 0 || x < 0 || y >= tilesY || x >= tilesX) ? 0 : board[y, x];
    }






    ////////////////
    //////AI///////
    ///////////////

    public static bool g_debug = true;

    public enum Mycell
    {
        Orange = 1,
        Yellow = -1,
        Barren = 0
    };

    public class Board
    {
        // Initially, this was Mycell[,]
        // Unfortunately, C# 2D arrays are a lot slower
        // than simple arrays of arrays (Jagged arrays): Mycell[][]
        // BUT
        // using a 1D array is EVEN faster:
        //    _slots[width*Y + X]
        // is much faster than
        //    _slots[Y][X]
        //
        // (sigh) Oh well, C# is a VM-based language (specifically, .NET).
        // Running fast is not the primary concern in VMs...
        public Mycell[] _slots;
        public Board()
        {
            _slots = new Mycell[tilesY * tilesX];   //height * width
        }
    };

    public static int dropDisk(Board board, int column, Mycell color)
    {
        for (int y = tilesY - 1; y >= 0; y--)
            if (board._slots[tilesX * (y) + column] == Mycell.Barren)
            {
                board._slots[tilesX * (y) + column] = color;
                return y;
            }
        return -1;
    }

    public static int ScoreBoard(Board board)
    {
        int[] counters = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };

        // Horizontal spans
        for (int y = 0; y < tilesY; y++)
        {
            int score = (int)board._slots[tilesX * (y) + 0] + (int)board._slots[tilesX * (y) + 1] + (int)board._slots[tilesX * (y) + 2];
            for (int x = 3; x < tilesX; x++)
            {
                score += (int)board._slots[tilesX * (y) + x];
                counters[score + 4]++;
                score -= (int)board._slots[tilesX * (y) + x - 3];
            }
        }
        // Vertical spans
        for (int x = 0; x < tilesX; x++)
        {
            int score = (int)board._slots[tilesX * (0) + x] + (int)board._slots[tilesX * (1) + x] + (int)board._slots[tilesX * (2) + x];
            for (int y = 3; y < tilesY; y++)
            {
                score += (int)board._slots[tilesX * (y) + x];
                counters[score + 4]++;
                score -= (int)board._slots[tilesX * (y - 3) + x];
            }
        }
        // Down-right (and up-left) diagonals
        for (int y = 0; y < tilesY - 3; y++)
        {
            for (int x = 0; x < tilesX - 3; x++)
            {
                int score = 0;
                for (int ofs = 0; ofs < 4; ofs++)
                {
                    int yy = y + ofs;
                    int xx = x + ofs;
                    score += (int)board._slots[tilesX * (yy) + xx];
                }
                counters[score + 4]++;
            }
        }
        // up-right (and down-left) diagonals
        for (int y = 3; y < tilesY; y++)
        {
            for (int x = 0; x < tilesX - 3; x++)
            {
                int score = 0;
                for (int ofs = 0; ofs < 4; ofs++)
                {
                    int yy = y - ofs;
                    int xx = x + ofs;
                    score += (int)board._slots[tilesX * (yy) + xx];
                }
                counters[score + 4]++;
            }
        }

        if (counters[0] != 0)
            return yellowWins;
        else if (counters[8] != 0)
            return orangeWins;
        else
            return
                counters[5] + 2 * counters[6] + 5 * counters[7] -
                counters[3] - 2 * counters[2] - 5 * counters[1];
    }
    //End Scoreboard



    public static void abMinimax(bool maximizeOrMinimize, Mycell color, int depth, Board board, out int move, out int score)
    {
        if (0 == depth)
        {
            move = -1;
            score = ScoreBoard(board);
        }
        else
        {
            int bestScore = maximizeOrMinimize ? -10000000 : 10000000;
            int bestMove = -1;
            for (int column = 0; column < tilesX; column++)
            {
                if (board._slots[tilesX * (0) + column] != Mycell.Barren)
                    continue;
                int rowFilled = dropDisk(board, column, color);
                if (rowFilled == -1)
                    continue;
                int s = ScoreBoard(board);
                if (s == (maximizeOrMinimize ? orangeWins : yellowWins))
                {
                    bestMove = column;
                    bestScore = s;
                    board._slots[tilesX * (rowFilled) + column] = Mycell.Barren;
                    break;
                }
                int moveInner, scoreInner;
                if (depth > 1)
                    abMinimax(!maximizeOrMinimize, color == Mycell.Orange ? Mycell.Yellow : Mycell.Orange, depth - 1, board, out moveInner, out scoreInner);
                else
                {
                    moveInner = -1;
                    scoreInner = s;
                }
                board._slots[tilesX * (rowFilled) + column] = Mycell.Barren;
                /* when loss is certain, avoid forfeiting the match, by shifting scores by depth... */
                if (scoreInner == orangeWins || scoreInner == yellowWins)
                    scoreInner -= depth * (int)color;
                if (depth == maxDepth && g_debug)
                    Debug.Log("Depth: " + depth+", placing on: " + column+", score: " + scoreInner);
                if (maximizeOrMinimize)
                {
                    if (scoreInner >= bestScore)
                    {
                        bestScore = scoreInner;
                        bestMove = column;
                    }
                }
                else
                {
                    if (scoreInner <= bestScore)
                    {
                        bestScore = scoreInner;
                        bestMove = column;
                    }
                }
            }
            move = bestMove;
            score = bestScore;
        }
    }
    //End abMiniMax




}

Pretty sure its stuck in abMinimax function.
And yes, its a Connect 4 (Four in a Row).

\$\endgroup\$
  • \$\begingroup\$ Put a breakpoint in your loop and check what is happening. You will then be at least able to tell if it is really stuck where you think it is. \$\endgroup\$ – realUser404 Feb 13 '17 at 14:30
  • \$\begingroup\$ @realUser404 actually I found it being stuck in infinite loop and abMinimax function via breakpoints itself. if (depth > 1) is the one calling the function again and again but not decreasing depth anywhere neither is any of the conditions being matched. \$\endgroup\$ – user39111 Feb 13 '17 at 14:40
  • \$\begingroup\$ Are you sure you are in an infinite loop? in the if (depth > 1) condition, the abMinMax is called with depth - 1 in parameter so the depth is supposed to be decreasing... \$\endgroup\$ – realUser404 Feb 13 '17 at 14:47
  • \$\begingroup\$ @realUser404 okay actually you are right, I was going through a few more example codes/posts and found that the greater the depth the more time it takes and since the dept is set to 7, it was just taking too long to compute the move. I decreased the depth to just 4 and now its proceeding in 2-3 seconds. However, I don't think its working as intended (i.e. the moves suggested seems random). \$\endgroup\$ – user39111 Feb 13 '17 at 14:49
1
\$\begingroup\$

First of all I will try to mention some frequently found mistakes in your code, because they really disturb from reading:

  1. No abstractions at all. Try to use OOP and encapsulate some logic to other classes, because right now your GameController is just EverythingGuy (for example, you can split AI logic from whole game, then split game lifecycle (start, update ...) from turn-based logic).
  2. Code style: hardcode, no empty lines to show logic structure of code, not the best naming and so on. If you want to be good at it, try to read Steven Mcconnell "Code Complete" (the aesthetics part).

To the point: I've tried to compile this thing in my head, but it worked, so I've debugged the code and found that the problem is surely in abMinimax method. So...

In abMinimax you have a cycle with 13 iterations. And you also have a depth, which initial value equals to 7. So in pseudocode the complexity of method abMinimax looks like:

for every x from 0 to 12
    if ( depth > 1 )
        abMinimax( depth - 1 );

I can say, that you have kinda 4826809 (13 * 13 * 13 * 13 * 13 * 13) iterations in that cycle. Maybe this is too much. I can prove it by lowering the whole tileX value from 13 to 4 so the program will finish and there is no infinite cycle in it. For example, if we take 6 instead of 13 the program will execute in a few seconds. You can extrapolate and...

Hope this will help you!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for your reply. Yes I am aware of #1 but its more or less intentional here/right now as I was trying to prototype it fast and feel more comfortable at separating my code into classes at later stages. Its bad habbit but one I am more comfortable with. As for #2, I don't really get what you mean but will check out Code Complete, I do know that my code's are always not the prettiest to read. And yes, I was able to come to same conclusion but instead of reducing the tiles, it was the depth (7) taking so long to compute that it looked "stuck". Reduced depth to 4 and now its executing \$\endgroup\$ – user39111 Feb 14 '17 at 13:40
  • \$\begingroup\$ Cont.: However, it seems my minimax/evaluation code itself is not proper as the suggested moves are only in horizontal rows (not upper rows/columns). To fix this, I commented out the "continue" on line 343 which lets AI put coins in/above columns but still the AI feels weak and doesn't stop me from winning. Is it possible for you to suggest any improvements on AI part, specially a negamax approach ? \$\endgroup\$ – user39111 Feb 14 '17 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.