# Minimax algorithm for Tic-Tac-Toe [3D variant]

### Godot Version

v3.5.3.stable.mono.official [6c814135b]

### Question

I’m working on an individual university project to create a 3D variation of Tic-Tac-Toe. The game is played on a 3-dimensional cube, and the first player to form a successful combination wins. Victory can be achieved on a single layer or across the entire cube.

I am attempting to develop an AI opponent for single-player gameplay. However, I encounter a recurring issue: the game crashes after the player moves, and I cannot determine the cause. Below is the code for my game logic:

Game.cs:

``````using Godot;
using System;
using System.Collections.Generic;

public class Game : Node
{
private int size;
private enum CellState { Empty, Cross, Circle }
private enum GameState { Playing, GameOver }

private CellState[,,] gameBoard;
private CellState currentPlayer;
private GameState currentGameState;

private int inARowToWin;
private List<Vector3> winningPositions = new List<Vector3>();

private const int WIN_SCORE = 1000;
private const int LOSE_SCORE = -1000;

{
size = Config.SIZE;
inARowToWin = size >= 5 ? 5 : 3;
gameBoard = new CellState[size, size, size];
currentPlayer = CellState.Cross;
currentGameState = GameState.Playing;

InitializeBoard();
}

private void InitializeBoard()
{
for (int z = 0; z < size; z++)
{
for (int y = 0; y < size; y++)
{
for (int x = 0; x < size; x++)
{
gameBoard[x, y, z] = CellState.Empty;
}
}
}
}

public void MakeMove(int x, int y, int z, Button button)
{
if (gameBoard[x, y, z] == CellState.Empty && currentGameState == GameState.Playing)
{
gameBoard[x, y, z] = currentPlayer;
button.Text = currentPlayer == CellState.Cross ? "X" : "O";

if (CheckForWinner(x, y, z))
{
currentGameState = GameState.GameOver;
DeclareWinner(currentPlayer);
}
else
{
SwitchPlayer();

if (Config.GAME_MODE == GameMode.PVE && currentPlayer == CellState.Circle && currentGameState == GameState.Playing)
{
PrintAIMove(); // Print the AI's move to the console
}
}
}
}

{
Label statusLabel = (Label)GetNode("UI/Status");
statusLabel.Text = currentPlayer == CellState.Cross ? "Tura: Krzyżyk" : "Tura: Kółko";
}

{
foreach (var child in GetTree().GetNodesInGroup("GameButtons"))
{
Button btn = child as Button;
if (btn != null)
{
btn.Modulate = new Color(0.8f, 0.8f, 0.8f, 0.5f);
}
}
}

private void SwitchPlayer()
{
currentPlayer = currentPlayer == CellState.Cross ? CellState.Circle : CellState.Cross;
}

private bool IsLineComplete(int x, int y, int z, (int dx, int dy, int dz) direction)
{
CellState first = gameBoard[x, y, z];
if (first == CellState.Empty) return false;

for (int i = 1; i < inARowToWin; i++)
{
int newX = x + i * direction.dx;
int newY = y + i * direction.dy;
int newZ = z + i * direction.dz;

if (newX < 0 || newX >= size || newY < 0 || newY >= size || newZ < 0 || newZ >= size)
return false;

if (gameBoard[newX, newY, newZ] != first)
return false;
}

return true;
}

private bool CheckForWinner(int x, int y, int z)
{
winningPositions.Clear();

var directions = new List<(int, int, int)>
{
// Straight lines
(1, 0, 0), (0, 1, 0), (0, 0, 1),
// Diagonals on XY plane
(1, 1, 0), (-1, 1, 0),
// Diagonals on XZ plane
(1, 0, 1), (-1, 0, 1),
// Diagonals on YZ plane
(0, 1, 1), (0, -1, 1),
// 3D Diagonals
(1, 1, 1), (-1, 1, 1), (1, -1, 1), (-1, -1, 1),
(1, 1, -1), (-1, 1, -1), (1, -1, -1), (-1, -1, -1)
};

foreach (var dir in directions)
{
for (int i = 0; i < size; i++)
{
if (IsLineComplete(i, y, z, dir)) return true;
if (IsLineComplete(x, i, z, dir)) return true;
if (IsLineComplete(x, y, i, dir)) return true;
}
}

return false;
}

private void DeclareWinner(CellState winner)
{
Label statusLabel = (Label)GetNode("UI/Status");
statusLabel.Text = winner == CellState.Cross ? "Wygrywa: Krzyżyk" : "Wygrał: Kółko";
statusLabel.Modulate = new Color(1, 0, 0);
GD.Print(winner.ToString() + " wins!");
}

private void _on_Exit_pressed()
{
GetTree().Quit();
}

private void PrintAIMove()
{
Vector3 bestMove = FindBestMove();
GD.Print(\$"AI wants to move to: ({bestMove.x}, {bestMove.y}, {bestMove.z})");
}

private Vector3 FindBestMove()
{
int bestVal = int.MinValue;
Vector3 bestMove = new Vector3(-1, -1, -1);

for (int z = 0; z < size; z++)
{
for (int y = 0; y < size; y++)
{
for (int x = 0; x < size; x++)
{
if (gameBoard[x, y, z] == CellState.Empty)
{
gameBoard[x, y, z] = CellState.Circle;
int moveVal = Minimax(gameBoard, 0, false);
gameBoard[x, y, z] = CellState.Empty;

if (moveVal > bestVal)
{
bestMove = new Vector3(x, y, z);
bestVal = moveVal;
}
}
}
}
}

return bestMove;
}

private int Minimax(CellState[,,] board, int depth, bool isMaximizing)
{
int score = EvaluateBoard(board);

if (Math.Abs(score) == WIN_SCORE || Math.Abs(score) == LOSE_SCORE || !IsMovesLeft(board))
{
return score;
}

if (isMaximizing)
{
int best = int.MinValue;
for (int z = 0; z < size; z++)
{
for (int y = 0; y < size; y++)
{
for (int x = 0; x < size; x++)
{
if (board[x, y, z] == CellState.Empty)
{
board[x, y, z] = CellState.Circle;
best = Math.Max(best, Minimax(board, depth + 1, !isMaximizing));
board[x, y, z] = CellState.Empty;
}
}
}
}
return best;
}
else
{
int best = int.MaxValue;
for (int z = 0; z < size; z++)
{
for (int y = 0; y < size; y++)
{
for (int x = 0; x < size; x++)
{
if (board[x, y, z] == CellState.Empty)
{
board[x, y, z] = CellState.Cross;
best = Math.Min(best, Minimax(board, depth + 1, !isMaximizing));
board[x, y, z] = CellState.Empty;
}
}
}
}
return best;
}
}

private bool IsMovesLeft(CellState[,,] board)
{
for (int z = 0; z < size; z++)
{
for (int y = 0; y < size; y++)
{
for (int x = 0; x < size; x++)
{
if (board[x, y, z] == CellState.Empty)
{
return true;
}
}
}
}
return false;
}

private int EvaluateBoard(CellState[,,] board)
{
for (int z = 0; z < size; z++)
{
for (int y = 0; y < size; y++)
{
for (int x = 0; x < size; x++)
{
if (board[x, y, z] == CellState.Circle && CheckForWinner(x, y, z))
{
return WIN_SCORE;
}
else if (board[x, y, z] == CellState.Cross && CheckForWinner(x, y, z))
{
return LOSE_SCORE;
}
}
}
}
return 0;
}

public void OnButtonPressed(Button button)
{
var indices = button.Name.Split('_');
int x = int.Parse(indices[1]);
int y = int.Parse(indices[2]);
int z = int.Parse(indices[3]);

MakeMove(x, y, z, button);
}
}

``````