I have difficulty thinking in 3D space¶

Our Jupyter Notebook Modeling Examples page contains an example called: Logic Programming - 3D Tic-Tac-Toe. This example comes from a well known textbook, Model Building in Mathematical Programming by H. Paul Williams.
The problem is to find an arrangement of X’s and O’s in a 3-dimensional tic-tac-toe grid such that the number of completed lines (of either X’s or O’s) is minimized. Even though the problem is quite easy for a human to understand, we found it difficult for our Custom GPT, despite the fact that its training data contains solutions to this exact model. We found the results to be inconsistent, sometimes yielding the correct answer, but more often, yielding a wrong answer.
Even when the model yielded the correct answer, we often found the generated model or its justification to be unsatifactory.
Given a 3-D tic-tac-toe board, where players take turns placing X's and O's, the game typically ends when one player completes a horizontal, vertical diagonal line; that is, when they manage to place their symbols in three cells that form a line or diagonal in the grid.
The twist that is tackled here is that the game continues until every cell contains a symbol, and the goal is to arrange the symbols to minimize the number of completed lines or diagonals.
Objective: Minimize the number of completed lines or diagonals
Constraints:
- The board must contain 14 X's and 13 O's (X goes first).
- A line is complete if there are 3 of the same character in a row in 3d space.
🔢 Problem Definition
Given a 3D tic-tac-toe board where players take turns placing X’s and O’s, the goal is to arrange the symbols to minimize the number of completed lines or diagonals.
Objective
Minimize the number of completed lines or diagonals.
Decision Variables
Let \(x_{ijk}\) be a binary variable where \(x_{ijk} = 1\) if an X is placed in the cell at position \((i, j, k)\) on the 3D tic-tac-toe board, and 0 otherwise.
Let \(o_{ijk}\) be a binary variable where \(o_{ijk} = 1\) if an O is placed in the cell at position \((i, j, k)\), and 0 otherwise.
Constraints
Symbol Placement Constraint: Each cell \((i, j, k)\) can contain either an X or an O, but not both:
\[x_{ijk} + o_{ijk} = 1 \quad \forall i, j, k\]Total X and O Constraints:
\[\sum_{i=1}^{3} \sum_{j=1}^{3} \sum_{k=1}^{3} x_{ijk} = 14\]\[\sum_{i=1}^{3} \sum_{j=1}^{3} \sum_{k=1}^{3} o_{ijk} = 13\]Line Completion Constraints: For each possible line (horizontal, vertical, and diagonal) in the 3D tic-tac-toe board, define a binary variable \(l\) to indicate whether a line is completed. A line is completed if all three cells in that line contain the same symbol. Thus:
\[l^X_h = 1 \text{ if a line } h \text{ is completed by X's, otherwise } l^X_h = 0\]\[l^O_h = 1 \text{ if a line } h \text{ is completed by O's, otherwise } l^O_h = 0\]Each line completion constraint would look like:
\[l^X_h \geq x_{i_1j_1k_1} + x_{i_2j_2k_2} + x_{i_3j_3k_3} - 2\]\[l^O_h \geq o_{i_1j_1k_1} + o_{i_2j_2k_2} + o_{i_3j_3k_3} - 2\]where \((i_1, j_1, k_1), (i_2, j_2, k_2), (i_3, j_3, k_3)\) are the indices of the cells forming line \(h\).
Objective Function
The objective is to minimize the total number of completed lines (either by X’s or O’s):
import gurobipy as gp
from gurobipy import GRB
# Create a model
model = gp.Model("3D_TicTacToe")
# Indices for the 3D board
n = 3
indices = [(i, j, k) for i in range(n) for j in range(n) for k in range(n)]
# Decision variables
x = model.addVars(indices, vtype=GRB.BINARY, name="X")
o = model.addVars(indices, vtype=GRB.BINARY, name="O")
# Constraints: Each cell can only contain either an X or an O
model.addConstrs((x[i, j, k] + o[i, j, k] == 1 for i, j, k in indices), "CellFill")
# Total number of X's and O's
model.addConstr(gp.quicksum(x[i, j, k] for i, j, k in indices) == 14, "TotalX")
model.addConstr(gp.quicksum(o[i, j, k] for i, j, k in indices) == 13, "TotalO")
# Possible lines on a 3D tic-tac-toe board
lines = []
# Horizontal and vertical lines
for i in range(n):
for j in range(n):
lines.append([(i, j, k) for k in range(n)]) # x-direction
lines.append([(i, k, j) for k in range(n)]) # y-direction
lines.append([(k, i, j) for k in range(n)]) # z-direction
# Diagonal lines within planes
for i in range(n):
lines.append([(i, k, k) for k in range(n)]) # Diagonal in yz-plane
lines.append([(i, k, n-1-k) for k in range(n)]) # Anti-diagonal in yz-plane
lines.append([(k, i, k) for k in range(n)]) # Diagonal in xz-plane
lines.append([(k, i, n-1-k) for k in range(n)]) # Anti-diagonal in xz-plane
lines.append([(k, k, i) for k in range(n)]) # Diagonal in xy-plane
lines.append([(k, n-1-k, i) for k in range(n)]) # Anti-diagonal in xy-plane
# Diagonal lines across the cube
lines.append([(k, k, k) for k in range(n)]) # Main diagonal
lines.append([(k, k, n-1-k) for k in range(n)]) # Other diagonal
lines.append([(k, n-1-k, k) for k in range(n)]) # Another diagonal
lines.append([(n-1-k, k, k) for k in range(n)]) # Yet another diagonal
# Line completion variables
l_x = model.addVars(len(lines), vtype=GRB.BINARY, name="L_X")
l_o = model.addVars(len(lines), vtype=GRB.BINARY, name="L_O")
# Line completion constraints
for h, line in enumerate(lines):
model.addConstr(l_x[h] >= gp.quicksum(x[i, j, k] for i, j, k in line) - 2, f"LineCompleteX_{h}")
model.addConstr(l_o[h] >= gp.quicksum(o[i, j, k] for i, j, k in line) - 2, f"LineCompleteO_{h}")
# Objective: Minimize the total number of completed lines
model.setObjective(gp.quicksum(l_x[h] + l_o[h] for h in range(len(lines))), GRB.MINIMIZE)
# Optimize the model
model.optimize()
# Retrieve the results
objective_value = model.ObjVal
x_solution = model.getAttr('x', x)
o_solution = model.getAttr('x', o)
completed_lines = sum(l_x[h].X + l_o[h].X for h in range(len(lines)))
x_positions = [(i, j, k) for i, j, k in indices if x_solution[i, j, k] > 0.5]
o_positions = [(i, j, k) for i, j, k in indices if o_solution[i, j, k] > 0.5]
In the above example results, both the Model formulation and Python code might initially look good, and the final answer produced by the generated code is correct. However, if we look at the Line Completion Constraints defined in the Generated Model formulation, the text says that the provided linear constraints will ensure that the line completion variables (\(l_h^X\) and \(l_h^O\)) will be equal to one if and only if their corresponding line of X’s or O’s is completed. However, the constraints provided only enforce that these variables must be one if the corresponding lines are completed but do not force them to zero if the lines are not completed. Since we are minimizing the number of completed lines, these constraints, together with the minimization objective, will lead to a correct model, as the objective forces as many of these variables to zero as possible.
This may seem like a nitpick; however, we found that if we asked our Custom GPT to instead maximize the number of completed lines, instead of minimizing them, it would sometimes build a model that allows all of the line completion variables to be set to 1, leading to a clearly wrong result.
We also found that, depending on the prompt we used, whether for minimization or maximization, the Custom GPT often miscalculated the number of lines to be considered in this hypothetical \(3\times 3\times 3\) tic-tac-toe board.