Wild-Tic-Tac-Toe (W3T) is a combinatorial extension of the classic Tic-Tac-Toe game, distinguished by the rule that players may place either marks on each turn. This added flexibility introduces considerable strategic complexity and has hitherto left the game’s theoretical outcome unresolved. In this study, we rigorously address the solvability of W3T by constructing a complete representation of its state space and all legal move sequences using a specially designed directed acyclic graph structure termed the Atlas. The game’s finite and deterministic nature enables exhaustive traversal of all valid positions, culminating in a full labeling of states via retrograde analysis. We define and apply outcome labels—win, loss, or draw—propagated from terminal positions upward through the graph. Our implementation leverages a ternary encoding scheme to uniquely represent board states, with efficient memory access and state reuse facilitated by integer-indexed arrays. The results demonstrate that W3T is not only solvable in the classical sense of perfect-information zero-sum games but is also a forced win for the first player under optimal play. This work contributes a novel methodology for solving similar finite games and underscores the importance of structural optimization in state-space exploration. The proposed framework exemplifies a form of symbolic artificial intelligence applied to exhaustive state-space reasoning, offering a transparent alternative to statistical learning approaches commonly used in decision-making systems for the Internet of Everything.
Author Biographies
G.V. Poryev, National University of Water and Environmental Engineering, Rivne
Doctor of Technical Sciences, Associate Professor
Ya. Ya. Zubyk, National University of Water and Environmental Engineering, Rivne
