I have been trying to write up a AI (minimax) for a checkers/connect4 type game by following some posts/examples I found online but its not working properly.
Right now, I think its countering my moves in horizontal row properly (very bottom row) but it has these 2 problems I have observed:
-
Its not taking into consideration/countering vertical rows i.e. if I put 3 red in last row, it do tries to counter me from doing so. But if I put 3 red in 1st column, it keeps suggesting moves in last/horizontal row only rather than trying to counter the vertical move.
-
When all the cells fill up in horizontal row (last), it should ideally use 2nd last row or whichever row has free space, but instead it suggests a value of -1 which is out of bounds from my board array
PS: Sorry for the messy code, I am used to writing single classes first and then divide up my code once it works. I know bad habit, but its something I am most comfortable with.
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 = 5;
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;
//For AI
if (currentPlayer == 2)
{
dropDisk(aiBoard, mouseClickX, Mycell.Yellow); //AI 2
} else
{
dropDisk(aiBoard, mouseClickX, Mycell.Orange); //AI 1
}
//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++) //bottom to top
{
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();
if (currentPlayer == 2)
{
int move, score;
abMinimax(true, Mycell.Orange, maxDepth, aiBoard, out move, out score);
Debug.Log("Move: " + move + " | Score: " + score);
Debug.Log(aiBoard._slots);
//Manually make CPU's turn
int y = findNextSpace(move);
board[y, move] = currentPlayer;
//For AI
if (currentPlayer == 2)
{
dropDisk(aiBoard, move, Mycell.Yellow); //AI 2
}
else
{
dropDisk(aiBoard, move, Mycell.Orange); //AI 1
}
//Spawn and animate the circleObject
spawnPlayerObject(move, y);
//End and change turn
currentPlayer = currentPlayer == 1 ? 2 : 1; //Not using function to avoid loop
}
}
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 = false;
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 = 0; y <= tilesY - 1; y++) //bottom to top
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
}