  The practical scalability of many optimization algorithms for large
extensive-form games is often limited by the games' huge payoff matrices. To
ameliorate the issue, Zhang and Sandholm (2020) recently proposed a
sparsification technique that factorizes the payoff matrix $\mathbf{A}$ into a
sparser object $\mathbf{A} = \hat{\mathbf{A}} + \mathbf{U}\mathbf{V}^\top$,
where the total combined number of nonzeros of $\hat{\mathbf{A}}$,
$\mathbf{U}$, and $\mathbf{V}$ is significantly smaller. Such a factorization
can be used in place of the original payoff matrix in many optimization
algorithm, such as interior-point and second-order methods, thus increasing the
size of games that can be handled. Their technique significantly sparsifies
poker (end)games, standard benchmarks used in computational game theory, AI,
and more broadly. We show that the existence of extremely sparse factorizations
in poker games can be tied to their particular \emph{Kronecker-product}
structure. We clarify how such structure arises and introduce the connection
between that structure and sparsification. By leveraging such structure, we
give two ways of computing strong sparsifications of poker games (as well as
any other game with a similar structure) that are i) orders of magnitude faster
to compute, ii) more numerically stable, and iii) produce a dramatically
smaller number of nonzeros than the prior technique. Our techniques enable --
for the first time -- effective computation of high-precision Nash equilibria
and strategies subject to constraints on the amount of allowed randomization.
Furthermore, they significantly speed up parallel first-order game-solving
algorithms; we show state-of-the-art speed on a GPU.
