Sprague-Grundy values and complexity for LCTR
share
Given a Young diagram on n boxes as a non-increasing sequence of integers, we consider the impartial combinatorial game LCTR in which moves consist of removing either the left column or top row of boxes. We show that for both normal and misère play, the optimal strategy can consist mostly of mirroring the opponent's moves. This allows for computing the Sprague-Grundy value of the given game in O(log(n)) time units, where time unit allows for reading an integer, or performing a basic arithmetic operation. This improves on the previous bound of O(n) time units, due to by Ilić (2019), which can be obtained by an improvement of the Sprague-Grundy recursion.
READ FULL TEXT