# Modeling Precomputation In Games Played Under Computational Constraints

arXiv: https://arxiv.org/abs/2105.09145 · HTML: https://mlsanity.com/paper/2105.09145/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 May 2021.

## Built on by (most cited first, 1 of 1)

- [Neural Interactive Proofs](https://mlsanity.com/paper/2412.08897/) (2024)

## Abstract (arXiv)

Understanding the properties of games played under computational constraints remains challenging. For example, how do we expect rational (but computationally bounded) players to play games with a prohibitively large number of states, such as chess? This paper presents a novel model for the precomputation (preparing moves in advance) aspect of computationally constrained games. A fundamental trade-off is shown between randomness of play, and susceptibility to precomputation, suggesting that randomization is necessary in games with computational constraints. We present efficient algorithms for computing how susceptible a strategy is to precomputation, and computing an ε-Nash equilibrium of our model. Numerical experiments measuring the trade-off between randomness and precomputation are provided for Stockfish (a well-known chess playing algorithm).