Preface and Acknowledgements
This section introduces the Connect 4 AI project, its purpose, and acknowledges contributions from mentors and collaborators.
Connect 4 Overview
This section introduces the Connect 4 game, rules, and objectives, and explains the challenges in creating an AI opponent.
public int GetWinState()
{
int winState = Connect4Color.Empty;
for (int x = 0; x < 7; x++)
{
for (int y = 0; y < pieces.Length; y++)
{
if (GetCoordinateValue(x, y) == Connect4Color.Empty) { continue; }
if (y <= 2)
{
winState = Connect4(x, y, Connect4Direction.Up);
if (winState != Connect4Color.Empty) { return winState; }
}
if (x <= 3)
{
winState = Connect4(x, y, Connect4Direction.Right);
if (winState != Connect4Color.Empty) { return winState; }
}
if ((x <= 3) && (y <= 2))
{
winState = Connect4(x, y, Connect4Direction.UpRight);
if (winState != Connect4Color.Empty) { return winState; }
}
if ((x <= 3) && (y >= 3))
{
winState = Connect4(x, y, Connect4Direction.DownRight);
if (winState != Connect4Color.Empty) { return winState; }
}
}
}
if (GetValidMoves().Length == 0) { return Connect4Color.Draw; }
return Connect4Color.Empty;
}
Discs and Bits
This section details how the game board and discs are represented using bitwise operations for fast computation.
/*
Key:
x Values: |6 | |5 |4 | |3 |2 | |1 |0 |
0000 0000 0000 0000 00|00| |00|00| |00|00| |00|00|
Win Square Bits
0000 0000 000|0 0000 00|00 0000 0000 0000
Potential Win Square Bits
0000 |0000 000|0 0000 0000 0000 0000 0000
1111 1111 1101 1111 1111 1111 1111 1111
Red: 10
Yellow: 01
Empty: 00
0000 0000 0000 0000 0000 0000 0000 0000
*/
public int[] pieces;
public bool redToMove;
public int[] yellowWinCoords;
public int[] redWinCoords;
public Connect4Rack()
{
pieces = EmptyRack();
redToMove = false;
yellowWinCoords = new int[0];
redWinCoords = new int[0];
}
public int GetCoordinateValue(int x, int y)
{
int xValue = pieces[y] >> (x * 2);
return xValue & 3;
}
public void SetCoordinateValue(int x, int y, int value)
{
int xValue = value << (x * 2);
pieces[y] |= xValue;
}
Connect 4 Strategy
This section discusses basic connect 4 strategies and traps and how to represent them in code.
public int Connect4(int x, int y, int direction)
{
if (InvalidCoord(x, y)) { return Connect4Color.Empty; }
int baseValue = GetCoordinateValue(x, y);
if (baseValue == Connect4Color.Empty) { return baseValue; }
int x2 = x;
int y2 = y;
int xIterator = 0;
int yIterator = 0;
switch (direction)
{
case Connect4Direction.Up:
y2 = y + 3;
yIterator = -1;
break;
case Connect4Direction.Right:
x2 = x + 3;
xIterator = -1;
break;
case Connect4Direction.UpRight:
y2 = y + 3;
x2 = x + 3;
xIterator = -1;
yIterator = -1;
break;
case Connect4Direction.DownRight:
y2 = y - 3;
x2 = x + 3;
yIterator = 1;
xIterator = -1;
break;
default:
return 0;
}
if (InvalidCoord(x2, y2)) { return Connect4Color.Empty; }
for (int i = 0; i < 3; i++)
{
if (GetCoordinateValue(x2, y2) != baseValue) { return Connect4Color.Empty; }
x2 += xIterator;
y2 += yIterator;
}
x2 = x + (3 * -xIterator);
y2 = y + (3 * -yIterator);
for (int i = 0; i < 4; i++)
{
SetWinSquare(x2, y2);
x2 += xIterator;
y2 += yIterator;
}
return baseValue;
}
public int Connect4(int x, int y, int direction)
{
if (InvalidCoord(x, y)) { return Connect4Color.Empty; }
int baseValue = GetCoordinateValue(x, y);
if (baseValue == Connect4Color.Empty) { return baseValue; }
int x2 = x;
int y2 = y;
int xIterator = 0;
int yIterator = 0;
switch (direction)
{
case Connect4Direction.Up:
y2 = y + 3;
yIterator = -1;
break;
case Connect4Direction.Right:
x2 = x + 3;
xIterator = -1;
break;
case Connect4Direction.UpRight:
y2 = y + 3;
x2 = x + 3;
xIterator = -1;
yIterator = -1;
break;
case Connect4Direction.DownRight:
y2 = y - 3;
x2 = x + 3;
yIterator = 1;
xIterator = -1;
break;
default:
return 0;
}
if (InvalidCoord(x2, y2)) { return Connect4Color.Empty; }
for (int i = 0; i < 3; i++)
{
if (GetCoordinateValue(x2, y2) != baseValue) { return Connect4Color.Empty; }
x2 += xIterator;
y2 += yIterator;
}
x2 = x + (3 * -xIterator);
y2 = y + (3 * -yIterator);
for (int i = 0; i < 4; i++)
{
SetWinSquare(x2, y2);
x2 += xIterator;
y2 += yIterator;
}
return baseValue;
}
public bool XinWinCoords(int x, bool red)
{
if (red)
{
if (redWinCoords.Length > 0)
{
for (int i = 0; i < redWinCoords.Length; i++)
{
if (GetXFromCoord(redWinCoords[i]) == x) { return true; }
}
}
}
else
{
if (yellowWinCoords.Length > 0)
{
for (int i = 0; i < yellowWinCoords.Length; i++)
{
if (GetXFromCoord(yellowWinCoords[i]) == x) { return true; }
}
}
}
return false;
}
public int[] AddWinCoord(int[] winCoords, int newCoord)
{
bool add = true;
if (winCoords.Length > 0)
{
for (int i = 0; i < winCoords.Length; i++)
{
if (winCoords[i] == newCoord)
{
add = false;
break;
}
}
}
int newLength = 1;
if (winCoords.Length > 0) { newLength = winCoords.Length + 1; }
if (add)
{
int[] newCoords = new int[newLength];
for (int i = 0; i < newCoords.Length-1; i++)
{
newCoords[i] = winCoords[i];
}
newCoords[newCoords.Length - 1] = newCoord;
return newCoords;
}
return winCoords;
}
public int EvalWinCoords(int[] winCoords, int[] opposingWinCoords, bool redWinCoords, bool decidingPlayerIsRed)
{
int eval = 0;
int yDiff = -1;
int immediateWins = 0;
for (int i = 0; i < winCoords.Length; i++)
{
int x = GetXFromCoord(winCoords[i]);
int y = GetYFromCoord(winCoords[i]);
yDiff = DistanceFromEmptyY(x, y);
if ((yDiff < 0) || (yDiff > 6)) { continue; }
if (yDiff == 0) { immediateWins++; }
if (yDiff > 0)
{
if (InnefectiveWinCoord(x,y,yDiff,opposingWinCoords)) { continue; }
}
if (yDiff == 1)
{
if (StackedWinCoord(x, y, winCoords)) { immediateWins++; }
}
if (redWinCoords == decidingPlayerIsRed)
{
eval += (7 - yDiff) * (100*winCoords.Length);
}
else
{
eval += (7 - yDiff) * (150*winCoords.Length);
}
}
if (immediateWins > 1) { eval = 999999999; }
return eval;
}
public bool InnefectiveWinCoord(int x, int y, int yDiff, int[] opposingWinCoords)
{
for(int i = 1; i <= yDiff; i+=2)
{
if (CoordInWinCoords(opposingWinCoords, x, y - i)) { return true; }
}
return false;
}
public bool StackedWinCoord(int x, int y, int[] winCoords)
{
if (CoordInWinCoords(winCoords, x, y-1))
{
if (DistanceFromEmptyY(x, y - 1) == 0) { return true; }
}
return false;
}
Connect 4 Scoring System
This section explains how each board position is scored so that the AI can prune branches and decide on moves.
public int EvalDirection(int x, int y, int direction)
{
int eval = 0;
int xIterator = 0;
int yIterator = 0;
int lineLength;
switch (direction)
{
case Connect4Direction.Up:
yIterator = 1;
lineLength = 6;
break;
case Connect4Direction.Right:
xIterator = 1;
lineLength = 7;
break;
case Connect4Direction.UpRight:
xIterator = 1;
yIterator = 1;
lineLength = GetDiagonalLineLength(direction, x, y);
break;
case Connect4Direction.DownRight:
xIterator = 1;
yIterator = -1;
lineLength = GetDiagonalLineLength(direction, x, y);
break;
default:
return eval;
}
int yellow = 0;
int red = 0;
int empty = 0;
int indexOfLastEmpty = 0;
int checkX = x;
int checkY = y;
int checkValue = 0;
for (int i = 0; i < lineLength; i++)
{
if (i >= 4)
{
checkX = x + ((i - 4) * xIterator);
checkY = y + ((i - 4) * yIterator);
if (!InvalidCoord(checkX, checkY))
{
checkValue = GetCoordinateValue(checkX, checkY);
if (checkValue == Connect4Color.Yellow) { yellow--; }
if (checkValue == Connect4Color.Red) { red--; }
if (checkValue == Connect4Color.Empty){ empty--; }
}
}
checkX = x + (i * xIterator);
checkY = y + (i * yIterator);
if (!InvalidCoord(checkX, checkY))
{
checkValue = GetCoordinateValue(checkX, checkY);
if (checkValue == Connect4Color.Yellow) { yellow++; }
if (checkValue == Connect4Color.Red) { red++; }
if (checkValue == Connect4Color.Empty)
{
indexOfLastEmpty = i;
empty++;
}
}
if (i >= 3)
{
if ((yellow > 0) && (red <= 0))
{
if (yellow == 3)
{
int winCoordX = x + (indexOfLastEmpty * xIterator);
int winCoordY = y + (indexOfLastEmpty * yIterator);
yellowWinCoords = AddWinCoord(yellowWinCoords, MakeCoord(winCoordX, winCoordY));
}
if (yellow == 2)
{
if (redToMove) { eval += 10; }
else { eval += 30; }
}
if (yellow == 1)
{
eval += 1;
}
}
if ((red > 0) && (yellow <= 0))
{
if (red == 3)
{
int winCoordX = x + (indexOfLastEmpty * xIterator);
int winCoordY = y + (indexOfLastEmpty * yIterator);
redWinCoords = AddWinCoord(redWinCoords, MakeCoord(winCoordX, winCoordY));
}
if (red == 2)
{
if (!redToMove) { eval -= 10; }
else { eval -= 30; }
}
if (red == 1)
{
eval -= 1;
}
}
}
}
return eval;
}
Search Algorithms
This section explains the implementation of search algorithms like minimax and alpha-beta pruning for AI decision-making.
public void InitiateIterativeDeepening(int maxDepth, CancellationToken cancelToken, bool redIsDeciding)
{
Debug.Log("Initiating Iterative Deepening");
if (moveTree.currentNode == null) { Debug.Log("LOST CURRENT NODE!"); return; }
MoveTreeNode CurrentNode = moveTree.currentNode;
if ((CurrentNode.childNodes == null)||(CurrentNode.childNodes.Length <=0)){ /*Debug.Log("Attempting to populate child nodes...");*/ CurrentNode.PopulateChildNodes();}
if (CurrentNode.childNodes.Length <= 0) { /*Debug.Log("Current node has no valid children. Iterative Deepening Failed.");*/ return; }
CurrentNode.PrepBranchForDeeperSearch();
int alpha = int.MinValue;
int beta = int.MaxValue;
string debugString = "";
for(int i = 0; i < CurrentNode.childNodes.Length;i++)
{
if (cancelToken.IsCancellationRequested) { /*Debug.Log("Search cancelled before it could be completed!");*/ break; }
GrowNodesToDepth(CurrentNode.childNodes[i], 0, maxDepth, alpha, beta, redIsDeciding, cancelToken, debugString);
}
Debug.Log(CurrentNode.GetNodeEvalsString());
}
public int GrowNodesToDepth(MoveTreeNode Node, int currentDepth, int maxDepth, int alpha, int beta, bool redIsDeciding, CancellationToken cancelToken, string debugString)
{
currentDepth++;
int winState = Node.gameBoard.GetWinState();
if (winState != Connect4Color.Empty)
{
if (winState == Connect4Color.Yellow)
{
Node.DeclareYellowWin();
return Node.eval;
}
if (winState == Connect4Color.Red)
{
Node.DeclareRedWin();
return Node.eval;
}
}
if ((currentDepth >= maxDepth) || (!Node.PopulateChildNodes()))
{
Node.Evaluate(redIsDeciding);
return Node.eval;
}
for (int i = 0; i < Node.childNodes.Length; i++)
{
if (cancelToken.IsCancellationRequested) { break; }
int currentMoveValue = GrowNodesToDepth(Node.childNodes[i], currentDepth, maxDepth, alpha, beta, redIsDeciding, cancelToken, debugString);
if (Node.gameBoard.redToMove)
{
if (currentMoveValue < beta) { beta = currentMoveValue; }
}
else
{
if (currentMoveValue > alpha) { alpha = currentMoveValue; }
}
}
return Node.moveValues[Node.bestMoveIndex];
}
Multithreading and Asynchronous Code
This section covers how asynchronous programming and multithreading improve AI calculation speed and responsiveness.
private void CreateRedCalculationThread() { redAICalculatingThread = new Thread(() => RedAIIterativeDeepening(cancelRedThought.Token)); }
private void CreateYellowCalculationThread() { yellowAICalculatingThread = new Thread(() => YellowAIIterativeDeepening(cancelYellowThought.Token)); }
private void CreateRedDecisionThread() { redAIDecidingThread = new Thread(() => InitiateIterativeThinkingRedAI(cancelRedDecision.Token)); }
private void CreateYellowDecisionThread() { yellowAIDecidingThread = new Thread(() => InitiateIterativeThinkingYellowAI(cancelYellowDecision.Token)); }
public void InitiateRedAIThought() { InitiateAIThought(true); }
public void InitiateYellowAIThought() { InitiateAIThought(false); }
Potential Improvements
This section highlights possible future enhancements such as optimizing this monstrosity of a move tree implementation.
public class Connect4Tree
{
public Connect4TreeNode[] baseNodes;
public int maxNodes;
public Connect4TreeNode[][] nodesReadyToGrow;
public Connect4TreeNode[][] nodesPreparingForGrowth;
public Connect4Rack rootGameBoard;
public bool redTree;
public Connect4Tree()
{
baseNodes = null;
rootGameBoard = null;
nodesReadyToGrow = null;
redTree = false;
maxNodes = 99999;
}
public Connect4Tree(Connect4Rack gameBoard, bool RedTree, int MaximumNodeCount)
{
rootGameBoard = null;
baseNodes = null;
nodesReadyToGrow = GetBlankGrowingNodes();
nodesPreparingForGrowth = GetBlankGrowingNodes();
redTree = RedTree;
maxNodes = MaximumNodeCount;
InitiateRoot(gameBoard);
}
public Connect4TreeNode[][] GetBlankGrowingNodes()
{
Connect4TreeNode[][] blankGrowingNodes = new Connect4TreeNode[7][];
for(int i = 0; i < blankGrowingNodes.Length; i++)
{
blankGrowingNodes[i] = new Connect4TreeNode[0];
}
return blankGrowingNodes;
}
public bool InitiateRoot(Connect4Rack RootGameBoard)
{
rootGameBoard = RootGameBoard;
int[] potentialMoves = rootGameBoard.GetValidMoves();
rootGameBoard.PrioritizeMoves(potentialMoves,rootGameBoard);
baseNodes = new Connect4TreeNode[potentialMoves.Length];
if (potentialMoves.Length + GetTotalNodesInTree() > maxNodes)
{
Debug.Log("TREE TOO BIG!");
return false;
}
for (int i = 0; i < potentialMoves.Length; i++)
{
Connect4Rack duplicate = new Connect4Rack(rootGameBoard);
duplicate.TryMove(potentialMoves[i]);
baseNodes[i] = new Connect4TreeNode(this, duplicate, potentialMoves[i]);
//Debug.Log("New Root, new node");
AddAGrowingNode(baseNodes[i], baseNodes[i].branchingMove);
}
return true;
}
public int GetBestMove()
{
int currentBestNodeValue;
int bestMove = -1;
//Debug.Log("Choosing best node out of: ");
if (rootGameBoard.redToMove) { currentBestNodeValue = int.MaxValue; }
else { currentBestNodeValue = int.MinValue; }
for(int i = 0; i < baseNodes.Length; i++)
{
//Debug.Log("Node: " + baseNodes[i].branchingMove + "| Value: " + baseNodes[i].bestMoveValue);
if (rootGameBoard.redToMove)
{
if (baseNodes[i].bestMoveValue < currentBestNodeValue)
{
currentBestNodeValue = baseNodes[i].bestMoveValue;
bestMove = baseNodes[i].branchingMove;
}
}
else
{
if (baseNodes[i].bestMoveValue > currentBestNodeValue)
{
currentBestNodeValue = baseNodes[i].bestMoveValue;
bestMove = baseNodes[i].branchingMove;
}
}
if (baseNodes[i].bestMoveValue == currentBestNodeValue)
{
if (baseNodes[i].CoinFlip()) { bestMove = baseNodes[i].branchingMove; }
}
}
if ((baseNodes.Length > 0) && (bestMove <0))
{
bestMove = baseNodes[0].branchingMove;
}
return bestMove;
}
public bool InitiateRoot(Connect4TreeNode BaseNode)
{
if (BaseNode.childNodes == null)
{
return InitiateRoot(BaseNode.gameBoard);
}
else
{
baseNodes = BaseNode.childNodes;
for(int i = 0; i < baseNodes.Length; i++)
{
baseNodes[i].isBaseNode = true;
baseNodes[i].parentNode = null;
}
SetBaseNodesForGrowth();
return true;
}
}
public void SetBaseNodesForGrowth()
{
for(int i = 0; i < baseNodes.Length; i++)
{
if (baseNodes[i].childNodes == null)
{
//Debug.Log("Child nodes are null, adding growing node");
AddAGrowingNode(baseNodes[i], baseNodes[i].branchingMove);
continue;
}
if ((baseNodes[i].childNodes.Length == 0) &&
(baseNodes[i].gameBoard.GetValidMoves().Length > 0))
{
//Debug.Log("Child nodes need poppin', adding a growing node");
AddAGrowingNode(baseNodes[i], baseNodes[i].branchingMove);
continue;
}
}
}
}
On the Horizon
This section outlines long-term plans for the project, including potential expansions, UI upgrades, and AI learning enhancements.