# minimax AI code stuck in a loop

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).

• 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. – realUser404 Feb 13 '17 at 14:30
• @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. – user39111 Feb 13 '17 at 14:40
• 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... – realUser404 Feb 13 '17 at 14:47
• @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). – user39111 Feb 13 '17 at 14:49

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...