Three Player Otrio will be Strongly Solved

Otrio is a 3D extension of classic Tic-Tac-Toe played with two to four players. Three-player Otrio has a big state space due to the additional dimension and players, and stands on the line between strongly and weakly solvable games. In this paper, we analyze the feasibility of strongly solving 3-player Otrio by giving a tighter upper bound and a fairly accurate approximation of the state-space complexity. We propose a new indexing scheme to subdivide the state space into slices that are manageable by a commodity computer, and then develop an algorithm to conduct a retrograde analysis of the game. We find that the state-space complexity of three player Otrio is in the order of 10
¹²
and that fully solving it would require approximately 248 days of CPU time per player cooperation configuration.