I have difficulty thinking in 3D space

Tic Tac Toe

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.

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.