講演情報
[2Yin-A-03]Endgame Databases for “Einstein Würfelt Nicht!”: Partition-Based Construction and Strategic Analysis
〇Ting-Shuo Hsu1, Tsan-Sheng Hsu2 (1. Univ. of Tokyo, 2. Academia Sinica, Taiwan)
キーワード：
autonomous agents、data engineering、knowledge base
“Einstein Würfelt Nicht!” (EWN) is a stochastic two-player game played on a 5 times 5 grid. Constructing endgame databases for EWN is computationally demanding due to the exponential explosion of the state space, which imposes prohibitive memory constraints on configurations with high piece counts.
In this paper, we introduce a novel database construction method that leverages the monotonic movement property of EWN pieces. By partitioning the board into irreversible regions, we establish a Directed Acyclic Graph (DAG) of dependencies between database subsets. This structural decomposition drastically reduces peak memory requirements during retrograde analysis. Surpassing the previous state-of-the-art limit of 7 pieces, we generated the first complete endgame databases for configurations of up to 9 pieces, totaling 105 TB of data.
These 9-piece databases reveal optimal strategies that were previously inaccessible. We conjecture that significant advanced play knowledge can be derived from these results; although EWN begins with 12 pieces, the piece count typically reduces rapidly, making our databases applicable to a vast majority of the game's decision space.
In this paper, we introduce a novel database construction method that leverages the monotonic movement property of EWN pieces. By partitioning the board into irreversible regions, we establish a Directed Acyclic Graph (DAG) of dependencies between database subsets. This structural decomposition drastically reduces peak memory requirements during retrograde analysis. Surpassing the previous state-of-the-art limit of 7 pieces, we generated the first complete endgame databases for configurations of up to 9 pieces, totaling 105 TB of data.
These 9-piece databases reveal optimal strategies that were previously inaccessible. We conjecture that significant advanced play knowledge can be derived from these results; although EWN begins with 12 pieces, the piece count typically reduces rapidly, making our databases applicable to a vast majority of the game's decision space.